Cookie Notice

As far as I know, and as far as I remember, nothing in this page does anything with Cookies.

2015/10/11

Overkill II: The Quickening

Previously on /var/log/rant, I talked about using recursion to brute-force a middle-school math problem. Because I learned a little bit about using Xeon Phi co-processor (the part formerly called video cards), I thought I'd try C++. And found that, while the Perl version ran for about a minute and a half, the C++ version took about a second and a half.

I then tried a Python version, using the same workflow as with the C++. I backed off on the clever for the testing because I am not as sure about using multidimensional arrays in C++ and Python as I am in Perl. When you only code in a language about once every 15 years, you begin to forget the finer points.

Anyway. the code follows. I don't believe I'm doing a particularly stupid thing with my Perl here, but it's hard to ID particularly stupid things in languages sometimes. Here's the code, now with your USDA requirement of Node.js.

#include <stdio.h>
void recursive_magic_box ( int numbers[9] , int arrayc , int array[9] ) ;
int check_magic_box ( int arrayc , int array[9] ) ;
int contains_duplicates ( int arrayc , int array[9] ) ;
int main () {
int numbers[9] = {3,4,5,6,7,8,9,10,11} ;
int array[9] ;
recursive_magic_box( numbers , 0 , array ) ;
}
void recursive_magic_box ( int numbers[9] , int arrayc , int array[9] ) {
for ( int i = 0 ; i < 9 ; i++ ) {
int n = numbers[i] ;
int new_arrayc = arrayc + 1 ;
array[arrayc] = n ;
if ( check_magic_box( new_arrayc , array ) ){
recursive_magic_box( numbers , new_arrayc , array ) ;
}
}
}
int check_magic_box ( int arrayc , int array[9] ) {
if ( arrayc > 9 ) { return 0 ; }
if ( contains_duplicates( arrayc , array ) ) { return 0 ; }
if ( arrayc == 9 ) {
int sum = 21 ;
if ( sum != array[0] + array[1] + array[2] ) { return 0 ; }
if ( sum != array[3] + array[4] + array[5] ) { return 0 ; }
if ( sum != array[6] + array[7] + array[8] ) { return 0 ; }
if ( sum != array[0] + array[3] + array[6] ) { return 0 ; }
if ( sum != array[1] + array[4] + array[7] ) { return 0 ; }
if ( sum != array[2] + array[5] + array[8] ) { return 0 ; }
if ( sum != array[0] + array[4] + array[8] ) { return 0 ; }
if ( sum != array[6] + array[4] + array[2] ) { return 0 ; }
printf( "%4d%4d%4d\n" , array[0] , array[1] , array[2]) ;
printf( "%4d%4d%4d\n" , array[3] , array[4] , array[5]) ;
printf( "%4d%4d%4d\n" , array[6] , array[7] , array[8]) ;
printf ("\n");
}
return 1 ;
}
int contains_duplicates ( int arrayc , int array[9] ) {
int check[20] ;
for (int i=0;i<20;i++) {check[i]=0;}
for ( int i = 0 ; i < arrayc ; i++ ) {
int n = array[i] ;
if ( check[n] == 1 ) { return 1 ; }
check[n] = 1 ;
}
return 0 ;
}
view raw magicbox.cc hosted with ❤ by GitHub
package main
import "fmt"
// import "time"
func main() {
myarray := []int{}
numbers := []int{3,4,5,6,7,8,9,10,11}
recurse_magic_box( numbers , myarray )
}
func recurse_magic_box( numbers []int , myarray []int ) {
for i := 0 ; i < len(numbers);i++ {
// fmt.Println("----------------")
n := numbers[i]
// push
myarray = append( myarray , n )
// fmt.Println(myarray)
check := check_magic_box( myarray )
if check == 1 {
recurse_magic_box( numbers , myarray )
// fmt.Println(myarray)
}
// pop
x, newarray := myarray[len(myarray)-1], myarray[:len(myarray)-1]
myarray = newarray
x = x
}
}
func check_magic_box( myarray []int ) int {
if ( len(myarray) > 9 ) {
return 0
}
nodup := removeDuplicates( myarray )
if ( len(myarray) != len(nodup) ) {
return 0
}
if ( len(myarray) == 9 ) {
sum := 21
// rows
if ( sum != myarray[0] + myarray[1] + myarray[2] ) { return 0 }
if ( sum != myarray[3] + myarray[4] + myarray[5] ) { return 0 }
if ( sum != myarray[6] + myarray[7] + myarray[8] ) { return 0 }
// columns
if ( sum != myarray[0] + myarray[3] + myarray[6] ) { return 0 }
if ( sum != myarray[1] + myarray[4] + myarray[7] ) { return 0 }
if ( sum != myarray[2] + myarray[5] + myarray[8] ) { return 0 }
// diagonals
if ( sum != myarray[0] + myarray[4] + myarray[8] ) { return 0 }
if ( sum != myarray[6] + myarray[4] + myarray[2] ) { return 0 }
fmt.Println( myarray[0:3] )
fmt.Println( myarray[3:6] )
fmt.Println( myarray[6:9] )
fmt.Println( "" )
}
return 1
}
func removeDuplicates(elements []int) []int {
// Use map to record duplicates as we find them.
encountered := map[int]bool{}
result := []int{}
for v := range elements {
if encountered[elements[v]] == true {
// Do not add duplicate.
} else {
// Record this element as an encountered element.
encountered[elements[v]] = true
// Append to result slice.
result = append(result, elements[v])
}
}
// Return the new slice.
return result
}
// run
//
// real 1m41.756s
// user 1m5.212s
// sys 0m0.264s
// built
//
// real 1m44.859s
// user 1m4.772s
// sys 0m0.112s
view raw magicbox.go hosted with ❤ by GitHub
#!/usr/bin/env node
// real 0m24.494s
// user 0m22.725s
// sys 0m0.200s
function main () {
var numbers = range(3,11) ;
var array = [] ;
recurse_magic_box( numbers , array ) ;
}
function recurse_magic_box( numbers , array ) {
for (var n in numbers ) {
var num = numbers[n] ;
array.push(num);
if ( check_magic_box( array ) ) {
recurse_magic_box( numbers , array ) ;
}
array.pop() ;
}
}
function check_magic_box( array ){
if ( contains_duplicates( array ) ) { return 0 }
if ( array.length > 9 ) { return 0 }
if ( array.length == 9 ) {
var sum = 21 ;
if ( sum != array[0] + array[1] + array[2] ) { return 0 }
if ( sum != array[3] + array[4] + array[5] ) { return 0 }
if ( sum != array[6] + array[7] + array[8] ) { return 0 }
if ( sum != array[0] + array[3] + array[6] ) { return 0 }
if ( sum != array[1] + array[4] + array[7] ) { return 0 }
if ( sum != array[2] + array[5] + array[8] ) { return 0 }
if ( sum != array[0] + array[4] + array[8] ) { return 0 }
if ( sum != array[6] + array[4] + array[2] ) { return 0 }
console.log( [ '[' , array[0] , array[1] , array[2] , ']' ].join(" ") ) ;
console.log( [ '[' , array[3] , array[4] , array[5] , ']' ].join(" ") ) ;
console.log( [ '[' , array[6] , array[7] , array[8] , ']' ].join(" ") ) ;
console.log("");
}
return 1 ;
}
function contains_duplicates ( array ) {
var check = [] ;
for ( var i = 0 ; i < array.length ; i++ ) {
var n = array[i] ;
if ( check[n] == 1 ) { return 1 ; }
check[n] = 1 ;
}
return 0 ;
}
function range (start, end) {
return Array(++end-start).join(0).split(0).map(function(n, i) {
return i+start
});
}
main() ;
view raw magicbox.js hosted with ❤ by GitHub
#!/usr/bin/env perl6
my @numbers = 3 .. 11 ;
my @array ;
recurse_magic_box( @numbers, @array ) ;
sub recurse_magic_box ( @numbers , @array ) {
for @numbers -> $n {
@array.push($n) ;
if ( check_magic_box( @array ) ) {
recurse_magic_box( @numbers, @array ) ;
}
@array.pop ;
}
}
sub check_magic_box ( @array ) {
return 0 if @array.elems > 9 ;
my %done;
for @array -> $n {
return 0 if %done{$n}++ ;
}
if ( @array.elems == 9 ) {
# say @array ;
my $sum = 21 ;
return 0 if $sum != @array[0] + @array[1] + @array[2] ;
return 0 if $sum != @array[3] + @array[4] + @array[5] ;
return 0 if $sum != @array[6] + @array[7] + @array[8] ;
return 0 if $sum != @array[0] + @array[3] + @array[6] ;
return 0 if $sum != @array[1] + @array[4] + @array[7] ;
return 0 if $sum != @array[2] + @array[5] + @array[8] ;
return 0 if $sum != @array[0] + @array[4] + @array[8] ;
return 0 if $sum != @array[6] + @array[4] + @array[2] ;
say @array[ 0 .. 2 ] ;
say @array[ 3 .. 5 ] ;
say @array[ 6 .. 8 ] ;
say '' ;
}
return 1 ;
}
# real 104m3.203s
# user 93m25.498s
# sys 0m10.577s
# I think I'm doing something wrong, because this shouldn't take that long, but I don't know what.
view raw magicbox.p6 hosted with ❤ by GitHub
#!/usr/bin/env perl
use feature qw{ say signatures } ;
no warnings "experimental::signatures";
my $numbers = [ 3 .. 11 ] ;
my $array ;
recurse_magic_box( $numbers, $array ) ;
sub recurse_magic_box ( $numbers , $array ) {
# numbers is the list of allowable numbers
for my $n (@$numbers) {
push @$array, $n ;
if ( check_magic_box($array) ) {
recurse_magic_box( $numbers, $array ) ;
}
pop @$array ;
}
}
sub check_magic_box ( $array ) {
return 0 if scalar @$array > 9 ;
my %done ;
for my $n (@$array) {
return 0 if $done{$n}++ ;
}
do {
my $sum = 21 ;
return 0 if $sum != $array->[0] + $array->[1] + $array->[2] ;
return 0 if $sum != $array->[3] + $array->[4] + $array->[5] ;
return 0 if $sum != $array->[6] + $array->[7] + $array->[8] ;
return 0 if $sum != $array->[0] + $array->[3] + $array->[6] ;
return 0 if $sum != $array->[1] + $array->[4] + $array->[7] ;
return 0 if $sum != $array->[2] + $array->[5] + $array->[8] ;
return 0 if $sum != $array->[0] + $array->[4] + $array->[8] ;
return 0 if $sum != $array->[6] + $array->[4] + $array->[2] ;
say join "", map { sprintf '%4d', $_ } @$array[ 0 .. 2 ] ;
say join "", map { sprintf '%4d', $_ } @$array[ 3 .. 5 ] ;
say join "", map { sprintf '%4d', $_ } @$array[ 6 .. 8 ] ;
say '' ;
} if scalar @$array == 9 ;
return 1 ;
}
__DATA__
TIME:
magicbox
real 0m1.713s
user 0m1.520s
sys 0m0.008s
magicbox.py
real 0m45.771s
user 0m34.382s
sys 0m0.620s
magicbox.pl
real 1m39.328s
user 1m20.685s
sys 0m0.344s
view raw magicbox.pl hosted with ❤ by GitHub
#!/usr/bin/env python
def main ():
numbers = range(3,12)
array = []
recurse_magic_box( numbers , array )
def recurse_magic_box ( numbers , array ):
for i in numbers:
array.append(i)
if check_magic_box( array ):
recurse_magic_box( numbers , array )
array.pop()
def check_magic_box( array ):
if len(array) > 9:
return 0
for n in array:
if array.count(n) > 1 :
return 0
if len(array) == 9:
sum = 21
if sum != array[0] + array[1] + array[2]:
return 0
if sum != array[3] + array[4] + array[5]:
return 0
if sum != array[6] + array[7] + array[8]:
return 0
if sum != array[0] + array[3] + array[6]:
return 0
if sum != array[1] + array[4] + array[7]:
return 0
if sum != array[2] + array[5] + array[8]:
return 0
if sum != array[0] + array[4] + array[8]:
return 0
if sum != array[6] + array[4] + array[2]:
return 0
print( array[0:3] )
print( array[3:6] )
print( array[6:9] )
print( "" )
return 1
if __name__ == '__main__':
main()
view raw magicbox.py hosted with ❤ by GitHub
#!/usr/bin/env ruby
numbers=*(3..11)
array = Array.new
checks = 1
def recurse_magic_box( numbers, array )
for n in numbers
array.push(n)
if 1 == check_magic_box(array)
recurse_magic_box( numbers , array )
end
array.pop
end
end
def check_magic_box ( array )
if array.length > 9
return 0
end
if array.uniq.length != array.length
return 0
end
if 9 == array.length
sum = 21
# rows
if sum != array[0] + array[1] + array[2]
return 0
end
if sum != array[3] + array[4] + array[5]
return 0
end
if sum != array[6] + array[7] + array[8]
return 0
end
# columns
if sum != array[0] + array[3] + array[6]
return 0
end
if sum != array[1] + array[4] + array[7]
return 0
end
if sum != array[2] + array[5] + array[8]
return 0
end
# diagonal
if sum != array[0] + array[4] + array[8]
return 0
end
if sum != array[6] + array[4] + array[2]
return 0
end
puts array[0..2].join(' ')
puts array[3..5].join(' ')
puts array[6..8].join(' ')
puts ''
end
return 1
end
recurse_magic_box( numbers , array )
# real 1m2.287s
# user 0m59.544s
# sys 0m0.052s
view raw magicbox.rb hosted with ❤ by GitHub
Posted by Dave Jacob at 1:46:00 PM
Labels: , , , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)