+/foobar

google programming puzzles

git clone https://git.julia.blue/+/foobar

Joseph RyanAdd benchmarks for level 5 and solve the encrpyted thingyaee14f5

master
9.3 KiB318 linesraw
1grid = []
2w, h = 0, 0
3
4
5def pprint(g):
6    print "\n".join("".join(map(str, row)) for row in g)
7    print
8
9
10def step(g, w, h):
11    result = [[0] * (w - 1) for i in range(h - 1)]
12    for y in range(h - 1):
13        for x in range(w - 1):
14            result[y][x] = int(g[y][x] + g[y + 1][x] + g[y][x + 1] + g[y + 1][x + 1] == 1)
15    return result
16
17
18def bruteforce_answer(g):
19    print "\n".join(map(str, g))
20    print
21    answers = 0
22    w = len(g[0]) + 1
23    h = len(g) + 1
24    for i in xrange(2 ** (w * h)):
25        temp = [[0] * w for n in range(h)]
26        for y in range(h):
27            for x in range(w):
28                temp[y][x] = int(i & 1 << (x + w * y) > 0)
29        if step(temp, w, h) == g:
30            answers += 1
31            print "\n".join(map(str, temp))
32            print
33    return answers
34
35
36def dfs_answer(g):
37    global grid, w, h
38    w = len(g[0])
39    h = len(g)
40    if w < h:
41        temp = [[0] * h for i in range(w)]
42        for x in range(w):
43            for y in range(h):
44                temp[x][y] = g[y][x]
45        w, h = h, w
46        g = temp
47    grid = g
48    temp = [[0] * (w + 1) for i in range(h + 1)]
49    firsthalf = [i[:] for i in temp]
50    temp[0][0] = 1
51    return solve(firsthalf, 1) + solve(temp, 1)
52
53
54def goup(g, x, y):
55    if y < 0:
56        return g
57    tot = g[y + 1][x - 1] + g[y][x - 1] + g[y + 1][x]
58    possible = ()
59    if grid[y][x - 1]:
60        if tot < 2:
61            possible = (1 - tot,)
62        else:
63            return []
64    else:
65        if tot < 2:
66            possible = (tot,)
67        else:
68            possible = (0, 1)
69    results = []
70    for p in possible:
71        temp = [i[:] for i in g]
72        temp[y][x] = p
73        temp = goup(temp, x, y - 1)
74        if temp:
75            if type(temp[0][0]) is not list:
76                temp = [temp]
77            results += temp
78    return results
79
80
81def goleft(g, x, y):
82    if x < 0:
83        return g[y]
84    tot = g[y][x + 1] + g[y - 1][x + 1] + g[y - 1][x]
85    possible = ()
86    if grid[y - 1][x]:
87        if tot < 2:
88            possible = (1 - tot,)
89        else:
90            return []
91    else:
92        if tot < 2:
93            possible = (tot,)
94        else:
95            possible = (0, 1)
96    results = []
97    for p in possible:
98        temp = [i[:] for i in g]
99        temp[y][x] = p
100        temp = goleft(temp, x - 1, y)
101        if temp:
102            if type(temp[0]) is not list:
103                temp = [temp]
104            results += temp
105    return results
106
107
108def solve(g, n):
109    if n > w:
110        return 1
111    x = n
112    y = min(n, h)
113    prev = g[y - 1][x - 1]
114    goal = grid[y - 1][x - 1]
115    possible = []
116    if goal and prev:
117        possible = [(0, 0, 0)]
118    elif goal:
119        possible = [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
120    elif prev:
121        possible = [(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (0, 1, 1), (1, 0, 1), (1, 1, 1)]
122    else:
123        possible = [(0, 0, 0), (1, 1, 0), (0, 1, 1), (1, 0, 1), (1, 1, 1)]
124
125    tot = 0
126    if n == 1:
127        for p in possible:
128            g[y][x] = p[0]
129            g[y - 1][x] = p[1]
130            g[y][x - 1] = p[2]
131            tot += solve(g, n + 1)
132    elif n != y:
133        for p in possible:
134            if g[y][x - 1] != p[2]:
135                continue
136            g[y][x] = p[0]
137            g[y - 1][x] = p[1]
138            g[y][x - 1] = p[2]
139            for i in goup(g, x, y - 2):
140                tot += solve(i, n + 1)
141    else:
142        for p in possible:
143            g[y][x] = p[0]
144            g[y - 1][x] = p[1]
145            g[y][x - 1] = p[2]
146            for i in goup(g, x, y - 2):
147                for left in goleft(g, x - 2, y):
148                    i[y] = left
149                    tot += solve(i, n + 1)
150    return 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):
173    for l in left:
174        for r in right:
175            if l[0][1] == r[0][0]:
176                l[1] += r[1]
177
178
179def old_vmerge(top, bottom):
180    newt = []
181    for t in top:
182        for b in bottom:
183            if t[0][-1] == b[0][0] and t[1][-1] == b[1][0]:
184                newt.append([i[:] for i in t])
185                newt[-1][0].append(b[0][1])
186                newt[-1][1].append(b[1][1])
187    return newt
188
189
190def old_answer(g):
191    w = len(g[0])
192    h = len(g)
193    possible = [[olds2g[g[y][x]][:] for y in range(h)] for x in range(w)]
194    for x in range(w):
195        for y in range(h):
196            if x and g[y][x - 1]:
197                del possible[x][y][8:]
198    for x in range(w - 1, -1, -1):
199        for y in range(1, h):
200            possible[x][y] = old_vmerge(possible[x][y - 1], possible[x][y])
201        possible[x] = map(lambda n: [n, x == w - 1], possible[x][-1])
202        if x < w - 1:
203            old_hmerge(possible[x], possible[x + 1])
204            possible[x] = filter(lambda x: x[1] > 0, possible[x])
205    return 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):
228    for l in left:
229        for r in right:
230            if l[0][1] == r[0][0]:
231                l[1] += r[1]
232
233
234def vmerge(top, bottom):
235    newt = []
236    for t in top:
237        for b in bottom:
238            if t[0] & 0x1 == (b[0] & 0x2) >> 1 and t[1] & 0x1 == (b[1] & 0x2) >> 1:
239                newt.append(t[:])
240                newt[-1][0] = (newt[-1][0] << 1) | b[0] & 0x1
241                newt[-1][1] = (newt[-1][1] << 1) | b[1] & 0x1
242    return newt
243
244
245def answer(g):
246    w = len(g[0])
247    h = len(g)
248    possible = [[s2g[g[y][x]][: 8 if x and g[y][x - 1] else None] for y in range(h)] for x in range(w)]
249    for x in range(w - 1):
250        for y in range(h):
251            if not g[y][x] and g[y][x + 1]:
252                del possible[x][y][5:8]
253    for x in range(w - 1, -1, -1):
254        for y in range(1, h):
255            possible[x][y] = vmerge(possible[x][y - 1], possible[x][y])
256        possible[x] = map(lambda n: [n, x == w - 1], possible[x][-1])
257        if x < w - 1:
258            hmerge(possible[x], possible[x + 1])
259            # print len(possible[x])
260            possible[x] = filter(lambda x: x[1] > 0, possible[x])
261            # print '\t', len(possible[x])
262    return 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        ],
290        6363446530708320359469050394834135793398,
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        ],
304        0,
305    ],
306]
307
308import time
309
310for case in enumerate(testcases):
311    start = time.time()
312    print "Case", case[0]
313    print
314    pprint(case[1][0])
315    print "  Expected:", case[1][1]
316    print "Calculated:", answer(case[1][0])
317    print "Time elapsed:", time.time() - start
318    print "=" * 80