+/foobar
google programming puzzles
git clone https://git.julia.blue/+/foobar
aee14f5
master
1grid = [] 2w ,h = 0 ,0 3 4 5def pprint (g ): 6"\n" .join ("" .join (map (str ,row ))for row in g ) 7def step (g ,w ,h ): 11result = [[0 ]* (w - 1 )for i in range (h - 1 )] 12for y in range (h - 1 ): 13for x in range (w - 1 ): 14result [y ][x ]= int (g [y ][x ]+ g [y + 1 ][x ]+ g [y ][x + 1 ]+ g [y + 1 ][x + 1 ]== 1 ) 15return result 16 17 18def bruteforce_answer (g ): 19"\n" .join (map (str ,g )) 20answers = 0 22w = len (g [0 ])+ 1 23h = len (g )+ 1 24for i in xrange (2 ** (w * h )): 25temp = [[0 ]* w for n in range (h )] 26for y in range (h ): 27for x in range (w ): 28temp [y ][x ]= int (i & 1 << (x + w * y )> 0 ) 29if step (temp ,w ,h )== g : 30answers += 1 31"\n" .join (map (str ,temp )) 32return answers 34 35 36def dfs_answer (g ): 37global grid ,w ,h 38w = len (g [0 ]) 39h = len (g ) 40if w < h : 41temp = [[0 ]* h for i in range (w )] 42for x in range (w ): 43for y in range (h ): 44temp [x ][y ]= g [y ][x ] 45w ,h = h ,w 46g = temp 47grid = g 48temp = [[0 ]* (w + 1 )for i in range (h + 1 )] 49firsthalf = [i [:]for i in temp ] 50temp [0 ][0 ]= 1 51return solve (firsthalf ,1 )+ solve (temp ,1 ) 52 53 54def goup (g ,x ,y ): 55if y < 0 : 56return g 57tot = g [y + 1 ][x - 1 ]+ g [y ][x - 1 ]+ g [y + 1 ][x ] 58possible = () 59if grid [y ][x - 1 ]: 60if tot < 2 : 61possible = (1 - tot ,) 62else : 63return [] 64else : 65if tot < 2 : 66possible = (tot ,) 67else : 68possible = (0 ,1 ) 69results = [] 70for p in possible : 71temp = [i [:]for i in g ] 72temp [y ][x ]= p 73temp = goup (temp ,x ,y - 1 ) 74if temp : 75if type (temp [0 ][0 ])is not list : 76temp = [temp ] 77results += temp 78return results 79 80 81def goleft (g ,x ,y ): 82if x < 0 : 83return g [y ] 84tot = g [y ][x + 1 ]+ g [y - 1 ][x + 1 ]+ g [y - 1 ][x ] 85possible = () 86if grid [y - 1 ][x ]: 87if tot < 2 : 88possible = (1 - tot ,) 89else : 90return [] 91else : 92if tot < 2 : 93possible = (tot ,) 94else : 95possible = (0 ,1 ) 96results = [] 97for p in possible : 98temp = [i [:]for i in g ] 99temp [y ][x ]= p 100temp = goleft (temp ,x - 1 ,y ) 101if temp : 102if type (temp [0 ])is not list : 103temp = [temp ] 104results += temp 105return results 106 107 108def solve (g ,n ): 109if n > w : 110return 1 111x = n 112y = min (n ,h ) 113prev = g [y - 1 ][x - 1 ] 114goal = grid [y - 1 ][x - 1 ] 115possible = [] 116if goal and prev : 117possible = [(0 ,0 ,0 )] 118elif goal : 119possible = [(1 ,0 ,0 ), (0 ,1 ,0 ), (0 ,0 ,1 )] 120elif prev : 121possible = [(1 ,0 ,0 ), (0 ,1 ,0 ), (0 ,0 ,1 ), (1 ,1 ,0 ), (0 ,1 ,1 ), (1 ,0 ,1 ), (1 ,1 ,1 )] 122else : 123possible = [(0 ,0 ,0 ), (1 ,1 ,0 ), (0 ,1 ,1 ), (1 ,0 ,1 ), (1 ,1 ,1 )] 124 125tot = 0 126if n == 1 : 127for p in possible : 128g [y ][x ]= p [0 ] 129g [y - 1 ][x ]= p [1 ] 130g [y ][x - 1 ]= p [2 ] 131tot += solve (g ,n + 1 ) 132elif n != y : 133for p in possible : 134if g [y ][x - 1 ]!= p [2 ]: 135continue 136g [y ][x ]= p [0 ] 137g [y - 1 ][x ]= p [1 ] 138g [y ][x - 1 ]= p [2 ] 139for i in goup (g ,x ,y - 2 ): 140tot += solve (i ,n + 1 ) 141else : 142for p in possible : 143g [y ][x ]= p [0 ] 144g [y - 1 ][x ]= p [1 ] 145g [y ][x - 1 ]= p [2 ] 146for i in goup (g ,x ,y - 2 ): 147for left in goleft (g ,x - 2 ,y ): 148i [y ]= left 149tot += solve (i ,n + 1 ) 150return tot 151 152 153olds2g = [ 154 [ 155 [[0 ,0 ], [0 ,0 ]], 156 [[0 ,0 ], [1 ,1 ]], 157 [[0 ,1 ], [0 ,1 ]], 158 [[0 ,1 ], [1 ,0 ]], 159 [[0 ,1 ], [1 ,1 ]], 160 [[1 ,0 ], [0 ,1 ]], 161 [[1 ,0 ], [1 ,0 ]], 162 [[1 ,0 ], [1 ,1 ]], 163 [[1 ,1 ], [0 ,0 ]], 164 [[1 ,1 ], [0 ,1 ]], 165 [[1 ,1 ], [1 ,0 ]], 166 [[1 ,1 ], [1 ,1 ]], 167 ], 168 [[[0 ,0 ], [0 ,1 ]], [[0 ,0 ], [1 ,0 ]], [[0 ,1 ], [0 ,0 ]], [[1 ,0 ], [0 ,0 ]]], 169] 170 171 172def old_hmerge (left ,right ): 173for l in left : 174for r in right : 175if l [0 ][1 ]== r [0 ][0 ]: 176l [1 ]+= r [1 ] 177 178 179def old_vmerge (top ,bottom ): 180newt = [] 181for t in top : 182for b in bottom : 183if t [0 ][- 1 ]== b [0 ][0 ]and t [1 ][- 1 ]== b [1 ][0 ]: 184newt .append ([i [:]for i in t ]) 185newt [- 1 ][0 ].append (b [0 ][1 ]) 186newt [- 1 ][1 ].append (b [1 ][1 ]) 187return newt 188 189 190def old_answer (g ): 191w = len (g [0 ]) 192h = len (g ) 193possible = [[olds2g [g [y ][x ]][:]for y in range (h )]for x in range (w )] 194for x in range (w ): 195for y in range (h ): 196if x and g [y ][x - 1 ]: 197del possible [x ][y ][8 :] 198for x in range (w - 1 ,- 1 ,- 1 ): 199for y in range (1 ,h ): 200possible [x ][y ]= old_vmerge (possible [x ][y - 1 ],possible [x ][y ]) 201possible [x ]= map (lambda n : [n ,x == w - 1 ],possible [x ][- 1 ]) 202if x < w - 1 : 203old_hmerge (possible [x ],possible [x + 1 ]) 204possible [x ]= filter (lambda x :x [1 ]> 0 ,possible [x ]) 205return sum (i [1 ]for i in possible [0 ]) 206 207 208s2g = [ 209 [ 210 [0b00 ,0b00 ], 211 [0b01 ,0b01 ], 212 [0b01 ,0b10 ], 213 [0b10 ,0b01 ], 214 [0b10 ,0b10 ], 215 [0b00 ,0b11 ], 216 [0b01 ,0b11 ], 217 [0b10 ,0b11 ], 218 [0b11 ,0b00 ], 219 [0b11 ,0b01 ], 220 [0b11 ,0b10 ], 221 [0b11 ,0b11 ], 222 ], 223 [[0b00 ,0b01 ], [0b00 ,0b10 ], [0b01 ,0b00 ], [0b10 ,0b00 ]], 224] 225 226 227def hmerge (left ,right ): 228for l in left : 229for r in right : 230if l [0 ][1 ]== r [0 ][0 ]: 231l [1 ]+= r [1 ] 232 233 234def vmerge (top ,bottom ): 235newt = [] 236for t in top : 237for b in bottom : 238if t [0 ]& 0x1 == (b [0 ]& 0x2 )>> 1 and t [1 ]& 0x1 == (b [1 ]& 0x2 )>> 1 : 239newt .append (t [:]) 240newt [- 1 ][0 ]= (newt [- 1 ][0 ]<< 1 )| b [0 ]& 0x1 241newt [- 1 ][1 ]= (newt [- 1 ][1 ]<< 1 )| b [1 ]& 0x1 242return newt 243 244 245def answer (g ): 246w = len (g [0 ]) 247h = len (g ) 248possible = [[s2g [g [y ][x ]][:8 if x and g [y ][x - 1 ]else None ]for y in range (h )]for x in range (w )] 249for x in range (w - 1 ): 250for y in range (h ): 251if not g [y ][x ]and g [y ][x + 1 ]: 252del possible [x ][y ][5 :8 ] 253for x in range (w - 1 ,- 1 ,- 1 ): 254for y in range (1 ,h ): 255possible [x ][y ]= vmerge (possible [x ][y - 1 ],possible [x ][y ]) 256possible [x ]= map (lambda n : [n ,x == w - 1 ],possible [x ][- 1 ]) 257if x < w - 1 : 258hmerge (possible [x ],possible [x + 1 ]) 259# print len(possible[x]) 260possible [x ]= filter (lambda x :x [1 ]> 0 ,possible [x ]) 261# print '\t', len(possible[x]) 262return sum (i [1 ]for i in possible [0 ]) 263 264 265# from random import randint 266# 267# for x in range(test5size[0]): 268# for y in range(test5size[1]): 269# test5[y][x] = randint(0,1) 270# # test5[y][x] = (y * x) % 2 271 272testcases = [ 273 [[[1 ,0 ], [0 ,1 ]],12 ], 274 [[[1 ,0 ,1 ], [0 ,1 ,0 ], [1 ,0 ,1 ]],4 ], 275 [[[1 ,0 ,1 ,0 ,0 ,1 ,1 ,1 ], [1 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ], [1 ,1 ,1 ,0 ,0 ,0 ,1 ,0 ], [1 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ], [1 ,0 ,1 ,0 ,0 ,1 ,1 ,1 ]],254 ], 276 [[[1 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,1 ,0 ], [1 ,1 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,0 ], [1 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ], [0 ,1 ,0 ,0 ,0 ,0 ,1 ,1 ,0 ,0 ]],11567 ], 277 [[[0 for n in range (3 )]for n in range (7 )],71482990 ], 278 [ 279 [ 280 [0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ], 281 [0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ], 282 [0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ], 283 [0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ], 284 [0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ], 285 [0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ], 286 [0 ,0 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ], 287 [0 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,0 ], 288 [1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,1 ], 289 ], 2906363446530708320359469050394834135793398 , 291 ], 292 [ 293 [ 294 [0 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,1 ,0 ], 295 [0 ,0 ,1 ,0 ,1 ,1 ,0 ,0 ,0 ,1 ,0 ,1 ,0 ], 296 [1 ,1 ,0 ,1 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,1 ,0 ], 297 [1 ,1 ,1 ,1 ,0 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,0 ], 298 [0 ,1 ,0 ,1 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ,1 ,1 ], 299 [1 ,1 ,0 ,0 ,1 ,1 ,1 ,1 ,1 ,0 ,1 ,1 ,0 ], 300 [1 ,0 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ], 301 [0 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,0 ,1 ], 302 [1 ,1 ,0 ,1 ,1 ,1 ,0 ,1 ,1 ,0 ,1 ,0 ,1 ], 303 ], 3040 , 305 ], 306] 307 308import time 309 310for case in enumerate (testcases ): 311start = time .time () 312"Case" ,case [0 ] 313pprint (case [1 ][0 ]) 315" Expected:" ,case [1 ][1 ] 316"Calculated:" ,answer (case [1 ][0 ]) 317"Time elapsed:" ,time .time ()- start 318"=" * 80