Haskell -> Python
Simon Foster
simon.foster at inbox.com
Fri Nov 2 21:09:29 CET 2012
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
More information about the Python-list
mailing list