bitwise not - not what I expected

[Elaine Jackson]

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.python-list 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 bit-manipulation 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=(magicDigit-targetDigit)
| >             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.
|
|