Solve the first part of the GCHQ Christmas puzzle using a concise, easy-to-understand Python program.
The puzzle is a 25x25 nonogram. I decided to write a program that uses the same method that I would use if solving the puzzle by hand:
from itertools import combinations_with_replacement
SHOW_TESTS = True
Put all the clues into a list of lists:
ROW_CLUES = [
[7, 3, 1, 1, 7,],
[1, 1, 2, 2, 1, 1,],
[1, 3, 1, 3, 1, 1, 3, 1,],
[1, 3, 1, 1, 6, 1, 3, 1,],
[1, 3, 1, 5, 2, 1, 3, 1,],
[1, 1, 2, 1, 1,],
[7, 1, 1, 1, 1, 1, 7,],
[3, 3,],
[1, 2, 3, 1, 1, 3, 1, 1, 2,],
[1, 1, 3, 2, 1, 1,],
[4, 1, 4, 2, 1, 2,],
[1, 1, 1, 1, 1, 4, 1, 3,],
[2, 1, 1, 1, 2, 5,],
[3, 2, 2, 6, 3, 1,],
[1, 9, 1, 1, 2, 1,],
[2, 1, 2, 2, 3, 1,],
[3, 1, 1, 1, 1, 5, 1,],
[1, 2, 2, 5,],
[7, 1, 2, 1, 1, 1, 3,],
[1, 1, 2, 1, 2, 2, 1,],
[1, 3, 1, 4, 5, 1,],
[1, 3, 1, 3, 10, 2,],
[1, 3, 1, 1, 6, 6,],
[1, 1, 2, 1, 1, 2,],
[7, 2, 1, 2, 5,],
]
COL_CLUES = [
[7, 2, 1, 1, 7,],
[1, 1, 2, 2, 1, 1,],
[1, 3, 1, 3, 1, 3, 1, 3, 1,],
[1, 3, 1, 1, 5, 1, 3, 1,],
[1, 3, 1, 1, 4, 1, 3, 1,],
[1, 1, 1, 2, 1, 1,],
[7, 1, 1, 1, 1, 1, 7,],
[1, 1, 3,],
[2, 1, 2, 1, 8, 2, 1,],
[2, 2, 1, 2, 1, 1, 1, 2,],
[1, 7, 3, 2, 1,],
[1, 2, 3, 1, 1, 1, 1, 1,],
[4, 1, 1, 2, 6,],
[3, 3, 1, 1, 1, 3, 1,],
[1, 2, 5, 2, 2,],
[2, 2, 1, 1, 1, 1, 1, 2, 1,],
[1, 3, 3, 2, 1, 8, 1,],
[6, 2, 1,],
[7, 1, 4, 1, 1, 3,],
[1, 1, 1, 1, 4,],
[1, 3, 1, 3, 7, 1,],
[1, 3, 1, 1, 1, 2, 1, 1, 4,],
[1, 3, 1, 4, 3, 3,],
[1, 1, 2, 2, 2, 6, 1,],
[7, 1, 3, 2, 1, 1,],
]
ROW_LEN = len(COL_CLUES)
COL_LEN = len(ROW_CLUES)
Set up a grid to contain the result, and fill in the cells we already know.
Notes:
# Create blank results grid
result = [[None] * ROW_LEN for c in range(COL_LEN)]
# Fill in the cells we already know
known_coords = {3: (3, 4, 12, 13, 21),
8: (6, 7, 10, 14, 15, 18),
16: (6, 11, 16, 20),
21: (3, 4, 9, 10, 15, 20, 21)
}
for row, cols in known_coords.items():
for col in cols:
result[row][col] = 1
Define some functions to display the results:
SYMBOLS = {None: '?', 1:'#', 0:'.'}
def print_row(row, i=0):
print '%s [%s]' % (str(i).rjust(2), ' '.join(SYMBOLS[cell] for cell in row))
def print_grid(rows):
col_labels = [str(i).rjust(2) for i in range (len(rows[0]))]
print ' ', ' '.join(cl[0] for cl in col_labels)
print ' ', ' '.join(cl[1] for cl in col_labels)
for i, row in enumerate(rows):
print_row(row, i)
# Test
if SHOW_TESTS:
print_grid(result)
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 0 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 1 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 2 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 3 [? ? ? # # ? ? ? ? ? ? ? # # ? ? ? ? ? ? ? # ? ? ?] 4 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 5 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 6 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 7 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 8 [? ? ? ? ? ? # # ? ? # ? ? ? # # ? ? # ? ? ? ? ? ?] 9 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 10 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 11 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 12 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 13 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 14 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 15 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 16 [? ? ? ? ? ? # ? ? ? ? # ? ? ? ? # ? ? ? # ? ? ? ?] 17 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 18 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 19 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 20 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 21 [? ? ? # # ? ? ? ? # # ? ? ? ? # ? ? ? ? # # ? ? ?] 22 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 23 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?] 24 [? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?]
And a function to count the number of unknown cells in the results. We'll use this to check if we've solved the puzzle, or if we're not making progress.
def count_unknowns(rows):
return sum(row.count(None) for row in rows)
# Test
if SHOW_TESTS:
print 'Unknowns = %s' % count_unknowns(result)
Unknowns = 603
Terminology:
The generate_patterns function does step 1 of the general approach: give it the clue and the pattern length, and it generates all the possible patterns.
For the clue [7, 3, 1, 1, 7] and length = 25:
position | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | |
---|---|---|---|---|---|---|---|---|---|---|---|
blocks and fixed spaces | 1111111 | 0 | 111 | 0 | 1 | 0 | 1 | 0 | 1111111 | ||
movable spaces (any 2 of 6 positions) | ? | ? | ? | ? | ? | ? |
def generate_patterns(clue, length):
blocks = [0] + clue
fixed_spaces = [0] + [1] * (len(clue) - 1) + [0]
positions = range(len(blocks))
n_movable_spaces = length - sum(clue) - len(clue) + 1
for space_positions in combinations_with_replacement(positions, n_movable_spaces):
movable_spaces = [space_positions.count(p) for p in positions]
yield sum(([1] * b + [0] * (fs + ms) for b, fs, ms in zip(blocks, fixed_spaces, movable_spaces)), [])
# Test
if SHOW_TESTS:
test_pats = list(generate_patterns([7, 3, 1, 1, 7], 25))
print_grid(test_pats)
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 0 [. . # # # # # # # . # # # . # . # . # # # # # # #] 1 [. # # # # # # # . . # # # . # . # . # # # # # # #] 2 [. # # # # # # # . # # # . . # . # . # # # # # # #] 3 [. # # # # # # # . # # # . # . . # . # # # # # # #] 4 [. # # # # # # # . # # # . # . # . . # # # # # # #] 5 [. # # # # # # # . # # # . # . # . # # # # # # # .] 6 [# # # # # # # . . . # # # . # . # . # # # # # # #] 7 [# # # # # # # . . # # # . . # . # . # # # # # # #] 8 [# # # # # # # . . # # # . # . . # . # # # # # # #] 9 [# # # # # # # . . # # # . # . # . . # # # # # # #] 10 [# # # # # # # . . # # # . # . # . # # # # # # # .] 11 [# # # # # # # . # # # . . . # . # . # # # # # # #] 12 [# # # # # # # . # # # . . # . . # . # # # # # # #] 13 [# # # # # # # . # # # . . # . # . . # # # # # # #] 14 [# # # # # # # . # # # . . # . # . # # # # # # # .] 15 [# # # # # # # . # # # . # . . . # . # # # # # # #] 16 [# # # # # # # . # # # . # . . # . . # # # # # # #] 17 [# # # # # # # . # # # . # . . # . # # # # # # # .] 18 [# # # # # # # . # # # . # . # . . . # # # # # # #] 19 [# # # # # # # . # # # . # . # . . # # # # # # # .] 20 [# # # # # # # . # # # . # . # . # # # # # # # . .]
The eliminate_patterns function does steps 2 and 4 of the general approach: give it a list of patterns, and it will eliminate the patterns that don't match the already-known cells.
Notes:
def eliminate_patterns(patterns, knowns):
for i in reversed(range(len(patterns))):
if any(k not in (p, None) for p, k in zip(patterns[i], knowns)):
del patterns[i]
# Test
if SHOW_TESTS:
print 'Before:'
print_grid(test_pats)
print
print 'Apply Knowns:'
test_knowns = [1] + [None]*23 + [1]
print_row(test_knowns)
print
print 'After:'
eliminate_patterns(test_pats, test_knowns)
print_grid(test_pats)
Before: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 0 [. . # # # # # # # . # # # . # . # . # # # # # # #] 1 [. # # # # # # # . . # # # . # . # . # # # # # # #] 2 [. # # # # # # # . # # # . . # . # . # # # # # # #] 3 [. # # # # # # # . # # # . # . . # . # # # # # # #] 4 [. # # # # # # # . # # # . # . # . . # # # # # # #] 5 [. # # # # # # # . # # # . # . # . # # # # # # # .] 6 [# # # # # # # . . . # # # . # . # . # # # # # # #] 7 [# # # # # # # . . # # # . . # . # . # # # # # # #] 8 [# # # # # # # . . # # # . # . . # . # # # # # # #] 9 [# # # # # # # . . # # # . # . # . . # # # # # # #] 10 [# # # # # # # . . # # # . # . # . # # # # # # # .] 11 [# # # # # # # . # # # . . . # . # . # # # # # # #] 12 [# # # # # # # . # # # . . # . . # . # # # # # # #] 13 [# # # # # # # . # # # . . # . # . . # # # # # # #] 14 [# # # # # # # . # # # . . # . # . # # # # # # # .] 15 [# # # # # # # . # # # . # . . . # . # # # # # # #] 16 [# # # # # # # . # # # . # . . # . . # # # # # # #] 17 [# # # # # # # . # # # . # . . # . # # # # # # # .] 18 [# # # # # # # . # # # . # . # . . . # # # # # # #] 19 [# # # # # # # . # # # . # . # . . # # # # # # # .] 20 [# # # # # # # . # # # . # . # . # # # # # # # . .] Apply Knowns: 0 [# ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #] After: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 0 [# # # # # # # . . . # # # . # . # . # # # # # # #] 1 [# # # # # # # . . # # # . . # . # . # # # # # # #] 2 [# # # # # # # . . # # # . # . . # . # # # # # # #] 3 [# # # # # # # . . # # # . # . # . . # # # # # # #] 4 [# # # # # # # . # # # . . . # . # . # # # # # # #] 5 [# # # # # # # . # # # . . # . . # . # # # # # # #] 6 [# # # # # # # . # # # . . # . # . . # # # # # # #] 7 [# # # # # # # . # # # . # . . . # . # # # # # # #] 8 [# # # # # # # . # # # . # . . # . . # # # # # # #] 9 [# # # # # # # . # # # . # . # . . . # # # # # # #]
The generate_knowns function does steps 3 and 5 of the general approach: give it a set of patterns, and it will deduce which cells are now known.
For each cell, if all the patterns have the same value for each cell, then that is the only possible value for that cell.
Notes:
def generate_knowns(patterns):
for col in zip(*patterns):
yield col[0] if all(c == col[0] for c in col) else None
# Test
if SHOW_TESTS:
print 'Patterns:'
print_grid(test_pats)
print
print 'Knowns:'
test_knowns = list(generate_knowns(test_pats))
print_row(test_knowns)
Patterns: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 0 [# # # # # # # . . . # # # . # . # . # # # # # # #] 1 [# # # # # # # . . # # # . . # . # . # # # # # # #] 2 [# # # # # # # . . # # # . # . . # . # # # # # # #] 3 [# # # # # # # . . # # # . # . # . . # # # # # # #] 4 [# # # # # # # . # # # . . . # . # . # # # # # # #] 5 [# # # # # # # . # # # . . # . . # . # # # # # # #] 6 [# # # # # # # . # # # . . # . # . . # # # # # # #] 7 [# # # # # # # . # # # . # . . . # . # # # # # # #] 8 [# # # # # # # . # # # . # . . # . . # # # # # # #] 9 [# # # # # # # . # # # . # . # . . . # # # # # # #] Knowns: 0 [# # # # # # # . ? ? # ? ? ? ? ? ? . # # # # # # #]
Do step 1: generate sets of patterns that match the clues given for each row and column.
rows_valid_patterns = [list(generate_patterns(c, ROW_LEN)) for c in ROW_CLUES]
cols_valid_patterns = [list(generate_patterns(c, COL_LEN)) for c in COL_CLUES]
Calculate how many unknowns there are before we start trying to solve:
unknowns = [count_unknowns(result)]
Repeat through steps 2-5 until either:
Notes:
while len(unknowns) < 2 or unknowns[-1] not in (0, unknowns[-2]):
map(eliminate_patterns, rows_valid_patterns, result)
result = map(generate_knowns, rows_valid_patterns)
map(eliminate_patterns, cols_valid_patterns, zip(*result))
result = zip(*map(generate_knowns, cols_valid_patterns))
unknowns.append(count_unknowns(result))
Display the results:
for i, u in enumerate(unknowns):
print 'pass %s: %s unknowns' % (i, u)
print_grid(result)
pass 0: 603 unknowns pass 1: 317 unknowns pass 2: 58 unknowns pass 3: 10 unknowns pass 4: 0 unknowns 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 0 [# # # # # # # . # # # . . . # . # . # # # # # # #] 1 [# . . . . . # . # # . # # . . . . . # . . . . . #] 2 [# . # # # . # . . . . . # # # . # . # . # # # . #] 3 [# . # # # . # . # . . # # # # # # . # . # # # . #] 4 [# . # # # . # . . # # # # # . # # . # . # # # . #] 5 [# . . . . . # . . # # . . . . . . . # . . . . . #] 6 [# # # # # # # . # . # . # . # . # . # # # # # # #] 7 [. . . . . . . . # # # . . . # # # . . . . . . . .] 8 [# . # # . # # # . . # . # . # # # . # . . # . # #] 9 [# . # . . . . . . # # # . # # . . . . # . . . # .] 10 [. # # # # . # . # # # # . # # . # . . . . # # . .] 11 [. # . # . . . # . . . # . # . # # # # . # . # # #] 12 [. . # # . . # . # . # . . . . . . # # . # # # # #] 13 [. . . # # # . # # . # # . # # # # # # . # # # . #] 14 [# . # # # # # # # # # . # . # . . # # . . . . # .] 15 [. # # . # . . # # . . . # # . # # # . . . . . # .] 16 [# # # . # . # . # . . # . . . . # # # # # . # . .] 17 [. . . . . . . . # . . . # # . # # . . . # # # # #] 18 [# # # # # # # . # . . # # . . . # . # . # . # # #] 19 [# . . . . . # . # # . . # . . # # . . . # # . # .] 20 [# . # # # . # . . . # # # # . . # # # # # . . # .] 21 [# . # # # . # . # # # . # # # # # # # # # # . # #] 22 [# . # # # . # . # . . # # # # # # . # # # # # # .] 23 [# . . . . . # . . # # . . . . . . # . # . # # . .] 24 [# # # # # # # . # # . . . # . # # . . . # # # # #]