Devon McCormick wrote:
> There is frequently performance degradation on a straight port of an
> algorithm from a compiled language to J. However, two advantages that J
> brings are 1) a different outlook on the problem, sometimes allowng a new
> and different algorithm, and 2) a quick way to try different methods and
> algorithms.
True.
I like J very much.
:-)
In this case the performance degradation on a straight port was
much much bigger than I expected.
:-(
> You say your solution took 4.5 seconds in Python. How many times did you
> run this program and how long did it take you to get working code?
In my case it was just a translation from C++ to Python.
That is I already had a solution and just re-implemented it in Python
and then in J.
I just tried to implement a given solution and not to be creative and
invent a new one.
:-/
The J solution is correct (as far as I know) and work for smaller size
of the board.
By the way, here the Python code as a reference.
(in Python a dictionary is used instead of an array for memoizing)
Maybe someone can suggest how to re-implement in J.
(if possible without using a totally new algorithm)
#!/usr/bin/env python
W = 9
H = 12
Piece = ( ( 1 << W, 1 << ( 2 * W ) ),
( 1 << 1, 1 << 2 ),
( 1 << 1, 1 << W ),
( 1 << 1, 1 << ( W + 1 ) ),
( 1 << W, 1 << ( W - 1 ) ),
( 1 << W, 1 << ( W + 1 ) ) )
Size = ( ( 3, 1 ),
( 1, 3 ),
( 2, 2 ),
( 2, 2 ),
( 2, 1 ),
( 2, 2 ) )
def place_piece( c, w, h, i ) :
global H, W, Piece, Size
if h > H - Size[i][0] or w > W - Size[i][1] :
return ( False, c, w, h )
if i == 4 and w == 0 :
return ( False, c, w, h )
if c & Piece[i][0] or c & Piece[i][1] :
return ( False, c, w, h )
c += Piece[i][0] + Piece[i][1]
c /= 2
w += 1
while c % 2 == 1 :
c /= 2
w += 1
while w >= W :
w -= W
h += 1
return ( True, c, w, h )
Mem = {}
def p161( c, w, h ) :
global Mem
if w == 0 and h == H and c == 0 :
return 1
if Mem.has_key( ( c, w, h ) ) :
return Mem[ ( c, w, h ) ]; # return memoized
ret = 0
for i in range( 6 ) :
flag, ct, wt, ht = place_piece( c, w, h, i )
if flag :
ret += p161( ct, wt, ht )
Mem[ ( c, w, h ) ] = ret; # memoize..
return ret; # ..and return
if __name__ == '__main__' :
print "The solution is %d" % p161( 0, 0, 0)
MfG
Luca.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
