# Author: Manfred Scheucher # Date : Jun 03 2015 from sys import argv def neighbors((a,b)): yield (a-2,b) yield (a-1,b-1) yield (a+1,b-1) yield (a+2,b) yield (a+1,b+1) yield (a-1,b+1) def new_ring(grid,prev_ring): na = set(neighbors(prev_ring[0])) nb = set(neighbors(prev_ring[-1])) todo = set() for y in prev_ring: for z in neighbors(y): if z not in grid: todo.add(z) x = (na&nb&todo).pop() todo.remove(x) new_ring = [x] while x: nx = neighbors(x) x = None for y in nx: if y in todo: x = y todo.remove(x) new_ring.append(x) break return new_ring def print_grid(numbered_grid): X = [x for (x,y) in numbered_grid] Y = [y for (x,y) in numbered_grid] d = len(str(max(numbered_grid.values()))) for y in [min(Y)..max(Y)]: for x in [min(X)..max(X)]: p = (x,y) i = str(numbered_grid[p] if p in numbered_grid else "").rjust(d,'.') print i, print def gen_grid(rings): grid = ring0 = [(0,0),(2,0),(1,1)] while rings > 0: rings -= 1 ring1 = new_ring(grid,ring0) grid += ring1 ring0 = ring1 return grid def gen_fib_grid(grid): numbered_grid = { grid[0]: 1, grid[1]: 1 } for k in range(2,len(grid)): prev = grid[k-1] curr = grid[k] nprev = [] for n in neighbors(prev): if n in grid and grid.index(n) < k-1: nprev.append(n) numbered_grid[curr] = numbered_grid[prev]+sum(numbered_grid[n] for n in nprev) return numbered_grid n = int(argv[1]) grid = gen_grid(n) numbered_grid = { grid[i]: i for i in range(len(grid)) } fib_grid = gen_fib_grid(grid) if n <= 3: print_grid(numbered_grid) print print_grid(fib_grid) print for i in range(len(grid)): print i+1,fib_grid[grid[i]]