{{ message }}

Instantly share code, notes, and snippets.

# borispf/1rclassic.py Secret

Last active Jan 28, 2018
Riddler 2018 01 29
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import matplotlib.pyplot as plt # numbering in neighbours.png NEIGHBOURS = [ [1, 4, 5], # 0 [0, 2, 8], [1, 3, 9, 11], [2, 13], [0, 5], [0, 4, 6, 7, 8], # 5 [5, 7], [5, 6, 8], [1, 5, 7, 9], [2, 8, 10], [9, 11], # 10 [2, 10, 12], [11, 13], [3, 12], ] def check_neighbours(): for u, ns in enumerate(NEIGHBOURS): for v in ns: assert u in NEIGHBOURS[v], f'{u} - {v}' check_neighbours() NUM_COLS = 3 COL = [0, -1, -1, -1, 1, 2, -1, -1, -1, -1, -1, -1, -1, -1] SIZES = [12, 6, 12, 24, 12, 12, 6, 3, 21, 6, 12, 6, 9, 3] COL_SIZES = [SIZES, SIZES, SIZES, 0] TOTAL_SIZE = sum(SIZES) TARGET_SIZE = TOTAL_SIZE // NUM_COLS def solve(k): out = [] place_col(k, COL, COL_SIZES, 0, out) return out def place_col(k, cs, ss, i, out): # 0, 4, 5 are fixed W.L.O.G. if i in [0, 4, 5]: place_col(k, cs, ss, i + 1, out) return if i == len(NEIGHBOURS): out.append(cs.copy()) return for c in range(k): cs[i] = c ss[c] += SIZES[i] if check_sizes(k, ss) and check_neighbours(cs, i): place_col(k, cs, ss, i + 1, out) cs[i] = -1 ss[c] -= SIZES[i] def check_sizes(k, ss): for s in ss: if s > TOTAL_SIZE // k: return False return True def check_neighbours(cs, u): for v in NEIGHBOURS[u]: if cs[u] == cs[v]: return False return True COORDS = [ {'x': [0, 4, 6], 'y': [12, 8, 12]}, # 0 {'x': [4, 6, 6], 'y': [8, 6, 12]}, {'x': [6, 8, 9, 6], 'y': [6, 4, 6, 12]}, {'x': [6, 9, 12, 12], 'y': [12, 6, 8, 12]}, {'x': [0, 2, 0], 'y': [0, 10, 12]}, {'x': [0, 4, 2], 'y': [0, 8, 10]}, # 5 {'x': [0, 3, 2], 'y': [0, 0, 4]}, {'x': [2, 3, 3], 'y': [4, 0, 6]}, {'x': [3, 6, 6, 4, 3], 'y': [0, 0, 6, 8, 6]}, {'x': [6, 8, 6], 'y': [0, 4, 6]}, {'x': [6, 12, 8], 'y': [0, 0, 4]}, # 10 {'x': [8, 12, 9], 'y': [4, 0, 6]}, {'x': [9, 12, 12], 'y': [6, 0, 6]}, {'x': [9, 12, 12], 'y': [6, 6, 8]}, ] for k in [3, 4]: sols = solve(k) print(f'Num Sols for k={k}: {len(sols)}') for i, sol in enumerate(sols): plt.figure() for color, shape in zip(sol, COORDS): plt.fill(shape['x'], shape['y'], color=f'C{color}') plt.savefig(f'k{k}-{i}.png')
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters            