bill lam wrote:
> mar, 15 Dec 2009, miridian skribis:
>> Maybe someone can suggest how to re-implement in J.
>
> What is your J solution?
Here the J code.
To have the "real" solution of the problem W must be 9.
I have check Python and J with
W = 2 answer = 153
W = 3 answer = 58234
W = 4 answer = 1895145
W = 5 answer = 198253934 (from here J is slow)
W = 6 answer = 27438555522 (here J is very slow)
W = 7 answer = 1949314526229 (from here only Python solutions)
W = 8 answer = 193553900967497
W = 9 answer = 20574308184277971 (This is the answer to euler
161; Python takes about 4.5 seconds)
---- J code ----
W =: 2 NB. 9
H =: 12
C =: 2 ^ 2 * W
Mem =: ( C, W , H ) $ _1x
Size =: 6 2 $ 3 1 1 3 2 2 2 2 2 1 2 2
Piece =: 6 2 $ (2^W), (2^( 2 * W )), (2^1), (2^2), (2^1), (2^W), (2^1),
(2^( W + 1 )), (2^W), (2^( W - 1 )), (2^W), (2^( W + 1 ))
PlacePiece =: monad define
'c w h i' =. y
if. ( h > H - ( < i, 0 ) { Size ) +. ( w > W - ( < i, 1 ) { Size ) do.
0, c, w, h return.
end.
if. ( i = 4 ) *. ( w = 0 ) do.
0, c, w, h return.
end.
f0 =. +./ *./ #: c, ( < i, 0 ) { Piece
f1 =. +./ *./ #: c, ( < i, 1 ) { Piece
if. ( f0 +. f1 ) do.
0, c, w, h return.
end.
c =. c + ( ( < i, 0 ) { Piece ) + ( ( < i, 1 ) { Piece )
c =. <. c % 2
w =. w + 1
while. 1 = 2 | c do.
c =. <. c % 2
w =. w + 1
end.
while. w >: W do.
w =. w - W
h =. h + 1
end.
1, c, w, h return.
)
p161 =: monad define
'c w h' =. y
if. ( w = 0 ) *. ( h = H ) *. ( c = 0 ) do.
1 return.
end.
if. _1x ~: ret =. ( < c, w, h ) { Mem do.
ret return.
end.
ret =. 0x
for_i. i. 6 do.
'f ct wt ht' =. PlacePiece c, w, h, i
if. f do.
ret =. ret + p161 ct, wt, ht
end.
end.
Mem =: ret ( < c, w, h ) } Mem
ret return.
)
NB. answer =: p161 0 0 0
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
