Instantly share code, notes, and snippets.

# christianp/flip.py Created Dec 19, 2011

Flipping squares puzzle
 from itertools import product from operator import mul from functools import reduce from math import log #represent the state of the board with a binary string of 9 digits #the states form a group under XOR on each cell - #when combining states S1 and S2, a cell is lit up iff it is lit up in S1 XOR it is lit up in S2 #states commute: S1.S2 = S2.S1, because XOR commutes #additionally, note that for every state S, S.S = 0. #this class represents a state of the board (element of the group) class State: def __init__(self,state): self.state = state #This function combines two states and returns the resulting state def __mul__(s1,s2): # what this is doing is taking s1_ij XOR s2_ij for each cell (i,j) return State(''.join([str(int(x)^int(y)) for x,y in zip(s1.state,s2.state)])) # ^ ^ # x XOR y pairs (s1_ij, s2_ij) #test if two states are equal def __eq__(s1,s2): return s1.state==s2.state #hash a state - used by the Set data type. We just need to return an integer unique to this state def __hash__(self): m=0 for x in self.state: m=m*2+int(x) return m #helper function to display a state as a 3x3 grid. def __repr__(self): return '\n'.join([self.state[x:x+3] for x in range(0,9,3)]) def makegens(n): gens=[] d1,d2='','' for i in range(0,n): gens.append(('0'*i+'1'+'0'*(n-i-1))*n) #flip column i gens.append(('0'*n)*i+('1'*n)+('0'*n)*(n-i-1)) #flip row i d1+='0'*i+'1'+'0'*(n-i-1) #first diagonal: flip cell i in row i d2+='0'*(n-i-1)+'1'+'0'*i #second diagonal: flip cell n-i in row i gens+=[d1,d2] return [State(x) for x in gens] grid_size=int(input('Size of grid: ')) gens=makegens(grid_size) #The question is: do they form a basis set for all possible states? #Straightforward answer is no: there are 2^9 possible states, and we're only given eight generators, so they can produce at most 2^8 states (since states commute and have order 2) #So we'll test that, but we'll also ask: is this an independent set of generators? Can any of these states be obtained by a combination of the others? #work out the set of all possible states binstrings = product([True,False],repeat=len(gens)) #get all the binary strings with as many digits as we have generators words = [[x for x,y in zip(gens,b) if y] for b in binstrings] #get the words corresponding to those binary strings - use a generator if the relevant binary digit is True states = [reduce(mul,word,State('0'*grid_size*grid_size)) for word in words] #for each word, multiply all its letters together to get the equivalent state. (State('0'*9) is the initial state, with all cells set to 0) states=set(states) #chuck out duplicates print('%s states generated by the given moves' % len(states)) #report how many states we can make with the given generators! print('So %s independent moves' % int(log(len(states),2)))
Owner Author

### christianp commented Dec 19, 2011

 In answer to this problem: http://i.imgur.com/mLHGc.jpg