Haskell -> Python

[Simon Foster]

On 02/11/12 19:56, Dave Angel wrote:
> On 11/02/2012 03:19 PM, foster63 at gmail.com wrote:
>> 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.
>
>

Hi Dave,

Thanks for the comments.  Yes, I should have specified that the input is 
a list of ints giving the size of each heap, and the return value should 
be a list of all game positions reachable from the input position.

At the moment I'm not concentrating on any particular Nim flavour, just 
trying to enumerate all possible moves from a given position.

I know that there's an easier way to determine winning-losing positions, 
but my question was more about programming style than Nim strategy.

My code to calculate the "nim-value" looks like this:

def nim_val( heaps ):
     return functools.reduce( operator.xor, heaps, 0 )

Assuming that we're playing "non-misere" Nim then a zero nim-value is a 
lose for the player *about* to play.

Regards

Simon