Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Wall Keeper by Sim0000
from collections import deque
pat = [ 0x1880000,0x1c40000,0x0e20000,0x0710000,0x0308000,
0x10c4000,0x08e2000,0x0471000,0x0238800,0x0118400,
0x0086200,0x0047100,0x0023880,0x0011c40,0x0008c20,
0x0004310,0x0002388,0x00011c4,0x00008e2,0x0000461,
0x0000218,0x000011c,0x000008e,0x0000047,0x0000023]
def wall_keeper(wall):
ban = sum(1 << (25 - i) for i in wall) # convert to bit pattern
q = deque([(ban, ())]) # initial state
# BFS
while q:
ban, log = q.popleft()
if log and ban >= 1 << (30 - log[-1]): continue # speed up (1)
if ban == 0: return list(log) # goal?
s = log[-1] if log else 0 # speed up (2)
for n in range(s, 25):
p = pat[n]
q.append((ban ^ p, log + (n + 1,))) # speed up (3)
raise Exception('not found')
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
from itertools import chain
def checker(solution, on_panels):
answer = solution(on_panels)
wk_p = list((0, 1)[n in on_panels] for n in range(1, 26))
p = list(wk_p[n: n+5] for n in range(0, 25, 5))
for a in answer:
r, c = (a-1) // 5, (a-1) % 5
p[r][c] = 1 - p[r][c]
if r+1 < 5:
p[r+1][c] = 1 - p[r+1][c]
if r-1 > -1:
p[r-1][c] = 1 - p[r-1][c]
if c+1 < len(p[0]):
p[r][c+1] = 1 - p[r][c+1]
if c-1 > -1:
p[r][c-1] = 1 - p[r][c-1]
return sum(chain(*p)) == 0
assert checker(wall_keeper, [5, 7, 13, 14, 18]), 'basic'
assert checker(wall_keeper, list(range(1, 26))), 'all_lights'
March 15, 2017
Comments: