{{ message }}

Instantly share code, notes, and snippets.

# christianp/flip.py

Created Dec 19, 2011
Flipping squares puzzle
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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)))

### christianp commented Dec 19, 2011

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