bitwise not  not what I expected
Elaine Jackson
elainejackson7355 at home.com
Mon Aug 18 18:50:10 CEST 2003
Cool. Thanks a bunch. I find the documentation about 'enumerate' a little
sketchy, but it seems like, as a first approximation, I can think of
enumerate(piles) as the list of all pairs [ i, piles[i] ] with 0 <= i <
len(piles). Is that right?
"Tim Peters" <tim.one at comcast.net> wrote in message
news:mailman.1061169151.30094.pythonlist at python.org...
 [Elaine Jackson]
 > In case any fellow newbies have been following this thread, here is
 > the finished Nim script. It doesn't use bitmanipulation as much as I
 > thought it would. (Still, I got the basics straight. Thanks again to
 > everyone who helped out!) For a readable account of the optimal
 > strategy for Nim, see Hardy & Wright's "Introduction to the Theory of
 > Numbers". Peace.
 >
 > ## NIM
 > from random import random
 > piles=[0,0,0]
 >
 > ...
 >
 > def yourMove():
 > magicNum=piles[0]^piles[1]^piles[2]
 > if magicNum==0:
 > i=indexOfMax()
 > piles[i]=piles[i]1
 > else:
 > magicIndex=leftmostBitIndex(magicNum)
 > targetIndex=(1)
 > for i in range(3):
 > if (piles[i]>>magicIndex)%2==1:
 > targetNum=piles[i]
 > targetIndex=i
 > break
 > replacement=0
 > for i in range(magicIndex):
 > magicDigit=(magicNum>>i)%2
 > targetDigit=(piles[targetIndex]>>i)%2
 > if magicDigit==1:
 > replacementDigit=(magicDigittargetDigit)
 > else:
 > replacementDigit=targetDigit
 > replacement=replacement+replacementDigit*pow(2,i)
 > newNum=targetNum(targetNum%pow(2,magicIndex+1))+replacement
 > piles[targetIndex]=newNum
 > print piles

 OK, what you're trying to do is force the xor of the pile counts to 0.
 There may be more than one way to do that. For example, if piles is

 [2, 6, 7]

 you can force a win by doing any of these:

 remove 1 from the 2 pile, leaving [1, 6, 7]
 remove 1 from the 6 pile, leaving [2, 5, 7]
 remove 3 from the 7 pile, leaving [2, 6, 4]

 because 1^6^7 == 2^5^7 == 2^6^4 == 0. Now the educational <wink> thing is
 that it's possible to find all these solutions easily *without* picking
 apart any bits:

 def myMove(piles):
 all = 0
 for count in piles:
 all ^= count
 for i, count in enumerate(piles): # enumerate() new in 2.3
 all_without_count = all ^ count
 if all_without_count < count:
 print "leave %d in pile #%d" % (all_without_count, i)

 For example,

 >>> myMove([2, 6, 7])
 leave 1 in pile #0
 leave 5 in pile #1
 leave 4 in pile #2
 >>>

 Note that the function works for any number of piles, and doesn't care how
 big each pile may be; for example,

 >>> myMove([2**50, 3**67, 5**12, 76**30])
 leave 92709463147897838211662074651978 in pile #3
 >>> 2**50 ^ 3**67 ^ 5**12 ^ 92709463147897838211662074651978
 0L
 >>>

 I think you'll enjoy figuring out why that function works; proving that it
 finds all solutions is a bit delicate, but not truly hard.


More information about the Pythonlist
mailing list