import sys, os, time,random

print ' *** *** *** *** *** *** *** *** *** *** *** *** '
print '                 Welcome to NIM                  '
print '      	    Writen by Alex Fry 2008             '
print '    Please visit www.AlexanderBastidasFry.com    '
print '    To learn the rules of NIM just Google it.    '
print '  In this version the last player to move wins   '

def input_taker(min,max,msg,error_msg1,error_msg2):
        while True:
                try:
                        value=max+666
                        while value<min or value>max:
                                value=int(raw_input(msg))
                                if value<min:
                                        print error_msg1
                                if value>max:
                                        print error_msg2
                        return value
                        #break
                except ValueError:
                        print "Not a valid input, must be an integer. Try again: "   

num_of_piles=input_taker(3,20,'Type in the number of piles: ','Please, at least 3 piles... ','Please, less than 20 piles...')

num_of_stones=input_taker(num_of_piles*3,99,'Type in the number of stones: ','Please, at least 3 stones per pile... ','Please, 99 stones or less...')

def binaryToDigital(binary):
	binarylist = list(binary)
	no = len(binarylist)
	no = no -1
	diginum = 0
	i = 0
        while no > -1:
        	if binarylist[no] == '1':
                	kj = 2**i
                        diginum = diginum + kj
                no = no -1
                i = i +1 
       	return diginum     

def digitalToBinary(number):
	#os.system('cls')
	number = int(number)
        aaa = str(number)
        i = 0
        numlist = []
        while number != 0:
        	numlist.append(number)
        	number = number/2 
        	i = i + 1
        binarynum = []
        i = i-1
        while i !=-1:
        	bd = str(numlist[i])
        	bdl = list(bd)
        	bdn = len(bdl)
        	bdn = bdn - 1
        	bx = bdl[bdn]
        	if bx == '0' or bx == '2' or bx == '4' or bx == '6' or bx == '8':
			binarynum.append(0)
		if bx == '1' or bx == '3' or bx == '5' or bx == '7' or bx == '9':
                	binarynum.append(1)
                i = i - 1
	return binarynum

#digital binary sum (dbs) is basically an addition in binary where no carries to the next place are preformed    
def dig_sum(aa,bb):
        if (aa==0 and bb==0 or aa==1  and bb==1):
                return 0
        else:
                return 1

#the piles start as numbers, but i want the data to be in a single list
def pile_maker(num):
	snum=str(num)
	qq=len(snum)
	i=0
	pl=[]
	while i<qq:
		pl.append(snum[i])
		i=i+1		
	return pl

#format and do dbs.  convert to binary and make leading zeros.  Then use the digital binary sum on both
def fmt(a,b):
	a=digitalToBinary(a)
	b=digitalToBinary(b)	

	al=len(a)
	bl=len(b)

#check lengths, add leading zeros
	while al!=bl:
		if al<bl :
			a.insert(0,0)
			al=al+1
		if bl<al :
			b.insert(0,0)
			bl=bl+1
	dbsum=[]
	alist=a
	blist=b
	i=0
	al=len(alist)
	while i<al:
		temp1=alist[i]
		temp2=blist[i]	
		dbsum.append(dig_sum(temp1,temp2))	
		i=i+1
	return dbsum
#how do i export alist and blist to outside this module?

#THE SECRET OF NIM:
#if you have a nonzero answer, you can always remove matches to get a zero result. If you get a zero answer, anything you do will leave a nonzero result. The winner, of course, leaves no matches at all, which is a zero result. So always play to leave a zero result for the operation.

piles=[]
stones=num_of_stones
temp=num_of_piles
while temp>0:
	piles.append(0)
	temp=temp-1

while stones>0:
	temp=random.randint(0,num_of_piles-1)
	piles[temp]=piles[temp]+1	
	stones=stones-1

lp=len(piles)
sum=piles[lp-1]
stones=num_of_stones

#this formats the sum quantity into a digital number
def sum_fmt(sum):
	sum=str(sum)
        sum=sum.replace(',','')
        sum=sum.replace('[','') 
        sum=sum.replace(']','')
        sum=sum.replace(' ','')
        sum=binaryToDigital(sum)
	return sum
	
while lp > 1:
	
	sum=fmt(sum,piles[lp-2])
	sum=sum_fmt(sum)
	lp=lp-1


#golden finds whether the given pile situation has a zero digital binary sum
def golden():
	lp=len(piles)	
	sum=piles[lp-1]
	while lp > 1:
#		returns DBS of sum and piles[x]
		sum=fmt(sum,piles[lp-2])
        	sum=sum_fmt(sum)	
		lp=lp-1
	
	try:
		#convert back to binary
		sum=fmt(sum,0)	
		#find the the index of the first occurance of a one	
		k=-666
		k=sum.index(1)
#it is possible the sum.index returns and exception of ValueError this means the dbs is zero
	except ValueError:
		return 0

	if k>=0:
		return 1				

def printer(x):
	print 'This pile has ',
	print x,
	print 'stones: ',	
	while x>0:
		print '0  ',
		x=x-1	
	print '\n',	

#def input_taker(min,max,msg,error_msg1,error_msg2):

def your_turn():
	valid=0
	while valid==0:
		ee=input_taker(1,len(piles),'Enter a pile to take from: ','Please, take from a real pile.  Try again... ','Please, take from a pile that exists.  Try again... ')
		if piles[ee-1]==0:
			print "You can't cheat by taking from an empty pile.  Choose a non empty pile. Try again... "
		if piles[ee-1]>0:
			valid=1
	pp=input_taker(1,piles[ee-1],'Enter the number of stones to take from pile: ','Please, take at least one stone.  Try again... ','Please, dont take more stones than exist in the pile.  Try again... ')
	piles[ee-1]=piles[ee-1]-pp
	return pp

#The heart of the program: loop which runs, asks the user for imput, executes the computer's moves, and ends when stones=0
#DIGITAL BINARY SUM
while stones > 0:
#display statuts with filter and printer	
	filter(printer,piles)

	pp=your_turn()
	stones=stones-pp
	print stones
	if stones==0:
		print 'you win!!!'
		break

	#filter(printer,piles)
	#if stones==1:
	#	print 'your going to lose!!!'
	print 'Now it is my turn... '	
	action=golden()
	if action==0:
		#computer cant always win
		#take random stones from random pile, in a valid manner (no zero taking)
		valid=0
		while valid==0:
        		temp=random.randint(0,num_of_piles-1)
			if piles[temp]!=0:
				temp2=random.randint(1,piles[temp])
				piles[temp]=piles[temp]-temp2
				stones=stones-temp2
        			valid=1
	if action==1:
		#print 'computer can always win and shuold always print this after seeing it once'
		npile=len(piles)-1
		list_end=len(piles)-1
		#temp_sz=piles[npile]
		mstone=1	
#this loop is entered if the DBS is not zero
#what we are looking for are the conditions that make it zero, when we find what n and m are that make it zero we are done
		while action==1:
			while npile>=0:
				#you were messing with stones in pile, put them back FIRST
				temp_sz=piles[npile]
				if action==0:
					break
				mstone=1
				s_in_pile=piles[npile]	
				while s_in_pile>0:
					piles[npile]=piles[npile]-1
					mstone=mstone+1		
					s_in_pile=s_in_pile-1	
					action=golden()
					if action==0:
						break
				piles[npile]=temp_sz
				npile=npile-1

		#npile and mstone are needed 
		mstone=mstone-1
		npile=npile+1
		piles[npile]=piles[npile]-mstone	
		stones=stones-mstone
		print "I will take ",
		print mstone,
		print "stones from pile ",
		print npile+1
	if stones==0:
		print "I win!!!"
#	if stones==1:
#		print "will lose..."
####