Haskell -> Python

[foster63]

Hi All,

As part of a Nim solver I'm playing around with I'm trying to code this Haskell snippet:

options [x] = zero : [ [y] | y <- [1..x - 1] ]
options (x:xs) = map (++ xs) (options [x]) ++ map (x (options xs)

in Python. So far I have this, which works OK, but somehow doesn't feel right:

def options( heaps ):

if heaps == []: return []

head, tail = heaps[:1], heaps[1:]

# Calculate all possible moves which is the sum of
# prepending all possible head "moves" to the tail
# and appending all possible tail "moves" to the head

return [ [h] + tail for h in range( head[0] ) ] \
+ [ head + t for t in options( tail ) ]

Is there anything anyone could recommend to make it more "Pythonic" or more functional. It looks clumsy next to the Haskell.

Regards

etc.

 

[Dave Angel]

Hi All,

As part of a Nim solver I'm playing around with I'm trying to code this Haskell snippet:

options [x] = zero : [ [y] | y <- [1..x - 1] ]
options (x:xs) = map (++ xs) (options [x]) ++ map (x (options xs)

in Python. So far I have this, which works OK, but somehow doesn't feel right:

def options( heaps ):

if heaps == []: return []

head, tail = heaps[:1], heaps[1:]

# Calculate all possible moves which is the sum of
# prepending all possible head "moves" to the tail
# and appending all possible tail "moves" to the head

return [ [h] + tail for h in range( head[0] ) ] \
+ [ head + t for t in options( tail ) ]

Is there anything anyone could recommend to make it more "Pythonic" or more functional. It looks clumsy next to the Haskell.

Regards

etc.

You'd save people a lot of time if you'd specify that the parameter
heaps is a list of ints, perhaps initially [1,3,5,7] or [3, 4, 5]
depending on which variation of Nim you're trying to. There are many.
One variant is that some versions of Nim say the winner is the player
who does NOT take the last piece. I'll assume that the goal is to end
up with [0,0,0,0]

My main problem with studying your code is that brute force is totally
unnecessary; there's a fairly simple strategy for winning at Nim.
Certainly it's simple enough to have perfect strategy without any computer.

A "good" move is any one where the xor of all the items in the list ends
up as zero. There is always at least one move for an "ungood" position
that results in a "good" one. Thus the strategy is to go from good to
good, with the opponent always stuck on an ungood one.

 

[Ian Kelly]

Is there anything anyone could recommend to make it more "Pythonic" or more functional. It looks clumsy next to the Haskell.

def options(heaps):
for i, heap in enumerate(heaps):
head = heaps[:i]
tail = heaps[i+1:]
yield from (head + [x] + tail for x in range(heap))

"yield from" is Python 3.3 syntax. If you're not using Python 3.3,
then that line could be replaced by:

for x in range(heap):
yield head + [x] + tail

Cheers,
Ian

 

[Ian Kelly]

Is there anything anyone could recommend to make it more "Pythonic" or more functional. It looks clumsy next to the Haskell.

def options(heaps):
for i, heap in enumerate(heaps):
head = heaps[:i]
tail = heaps[i+1:]
yield from (head + [x] + tail for x in range(heap))

"yield from" is Python 3.3 syntax. If you're not using Python 3.3,
then that line could be replaced by:

for x in range(heap):
yield head + [x] + tail

In fact, the more that I look at it, the more that I think the latter
might be preferable in any case.

 

[Dave Angel]

Is there anything anyone could recommend to make it more "Pythonic" or more functional. It looks clumsy next to the Haskell.

def options(heaps):
for i, heap in enumerate(heaps):
head = heaps[:i]
tail = heaps[i+1:]
yield from (head + [x] + tail for x in range(heap))

"yield from" is Python 3.3 syntax. If you're not using Python 3.3,
then that line could be replaced by:

for x in range(heap):
yield head + [x] + tail

Cheers,
Ian

Perhaps range(heap) should be replaced by range(len(heap))

 

[Ian Kelly]

Perhaps range(heap) should be replaced by range(len(heap))

"heaps" is a list of ints per the OP, so "heap" is an int.

 

[Dave Angel]

"heaps" is a list of ints per the OP, so "heap" is an int.

You're right of course <blush>. I was distracted by the fact that a
heap is normally a collection of thing, and didn't notice that here it
is a count of those things.

 

[Aahz]

def options( heaps ):

if heaps == []: return []

head, tail = heaps[:1], heaps[1:]

# Calculate all possible moves which is the sum of
# prepending all possible head "moves" to the tail
# and appending all possible tail "moves" to the head

return [ [h] + tail for h in range( head[0] ) ] \
+ [ head + t for t in options( tail ) ]

Is there anything anyone could recommend to make it more "Pythonic" or
more functional. It looks clumsy next to the Haskell.

If you want more Pythonic, follow PEP8 in your formatting. ;-)