Skip to content

Instantly share code, notes, and snippets.

@christianp
Created Dec 19, 2011
Embed
What would you like to do?
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)))
@christianp

This comment has been minimized.

Copy link
Owner Author

@christianp christianp commented Dec 19, 2011

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment