cozeのPython日記のPythonクイズを解いてみた。
所要時間は・・・３時間半くらい？腹が減った。
こんな事する間に、試験勉強しなきゃなぁ・・・
#Python2.6限定 from __future__ import ( with_statement, division, print_function, unicode_literals ) from itertools import * import turtle import psyco psyco.full() #============================================================================== def setup_gridpointtypes(): #周りに＊によって、その点から出て行く線分が決まるが、 #周りの＊の配置->線分の方向の集合 #の辞書を返す d = { ( 0, 0, 0, 0):[], ( 1, 0, 0, 0):[(0, -1), (-1, 0)], ( 1, 1, 0, 0):[(1, 0), (-1, 0)], ( 1, 0, 0, 1):[(-1, 0), (1, 0), (0, -1), (0, 1)], ( 1, 1, 0, 1):[(-1, 0), (0, 1)], ( 1, 1, 1, 1):[], } gridPointTypes = {} for blocks, roots in d.items(): blocks0 = [ ((-1, -1), blocks[0]), ((+1, -1), blocks[1]), ((-1, +1), blocks[2]), ((+1, +1), blocks[3]), ] roots0 = set(roots) gridPointTypes[tuple(sorted(blocks0))] = roots0 for i in xrange(4): #90度回転を登録 blocks1 = [((-y, x), b) for (x, y), b in blocks0] roots1 = set((-y, x) for x, y in roots0) gridPointTypes[tuple(sorted(blocks1))] = roots1 #さらに左右反転を登録 blocks2 = [((-x, y), b) for (x, y), b in blocks1] roots2 = set((-x, y) for x, y in roots1) gridPointTypes[tuple(sorted(blocks2))] = roots2 blocks0 = blocks1 roots0 = roots1 s1 = set() for b in product([0, 1], repeat=4): a = izip(product([-1, 1], repeat=2), b) a = tuple(sorted(a)) s1.add(a) s2 = set(gridPointTypes) assert s1 == s2 return gridPointTypes GridPointTypes = setup_gridpointtypes() def pprint_gridpointtypes(): for blocks, root in GridPointTypes.iteritems(): fmt = """\ {r0} {b0} {b1} {r3} {r1} {b3} {b2} {r2} """ blocks = dict(blocks) print(fmt.format( b0 = blocks[-1, -1], b1 = blocks[+1, -1], b2 = blocks[+1, +1], b3 = blocks[-1, +1], r0 = "a" if (0, -1) in root else " ", r1 = "a" if (+1, 0) in root else " ", r2 = "a" if (0, +1) in root else " ", r3 = "a" if (-1, 0) in root else " ", )) def is_connected(lines): #線分の集合から、単連結かどうか調べる if not lines: return True marked = set() all_nodes = set(n for line in lines for n in line) def rec_mark_node(n): if n in marked: return else: marked.add(n) nexts = [] for a in all_nodes: if frozenset((n, a)) in lines: rec_mark_node(a) start = list(all_nodes)[0] rec_mark_node(start) return marked == all_nodes def single_stroke_root(lines): #線分の集合から、一筆書きをするときに通る点のリストを返す all_nodes = [a for line in lines for a in line] odd_nodes = [n for n in all_nodes if len([line for line in lines if n in line]) % 2 == 1] assert len(odd_nodes) % 2 == 0 def single_stroke_root_rec(lines, start, level=0): root = [start] nexts = [] if not is_connected(lines): return None else: for line in lines: if start in line: next = list(line - set([start]))[0] lines1 = lines.difference([line]) r = single_stroke_root_rec(lines1, next, level + 1) if r is not None: root.extend(r) return root else: return root if 2 < len(odd_nodes): raise StandardError("一筆書き不可能") elif 2 == len(odd_nodes): start = odd_nodes[0] return single_stroke_root_rec(lines, start) else: start = all_nodes[0] return single_stroke_root_rec(lines, start) def main(): asterisks = set() txt = """\ **** ****** ******** ******** ******** ******** ****** **** """ for y, line in enumerate(txt.splitlines()): for x, c in enumerate(line): if not c.isspace(): asterisks.add((x, y)) W = max(x for x, y in asterisks) H = max(y for x, y in asterisks) pprint_gridpointtypes() gridPoints = {} #格子点-> 囲まれ具合 #の辞書を作成 for x, y in product(range(W + 2), range(H + 2)): t = [ ((-1, -1), (x-1, y-1) in asterisks), ((+1, -1), (x, y-1) in asterisks), ((-1, +1), (x-1, y) in asterisks), ((+1, +1), (x, y) in asterisks) ] gridPoints[x, y] = tuple(sorted(t)) lines = set() #線分の集合を得る for p, t in gridPoints.items(): for dp in GridPointTypes[t]: next = (p[0] + dp[0], p[1] + dp[1]) lines.add(frozenset((p, next))) if not is_connected(lines): print("単連結でない") exit(1) root = single_stroke_root(lines) scr = turtle.getscreen() scr.setworldcoordinates(-2, 2 + max(H, W), 2 + max(H, W), -2) turtle.tracer(0) #図形のアスタリスク(*)の代わりに円を描く。 for (x, y), t in gridPoints.iteritems(): for d, b in t: s = {(-1, -1):(-0.5, -0.75), (+1, -1):(0.5, -0.75), (-1, +1):(-0.5, 0.25), (+1, +1):(0.5, 0.25)} if b: turtle.penup() turtle.goto(x + s[d][0], y + s[d][1]) turtle.pendown() turtle.circle(0.25) #描く！ turtle.tracer(1) turtle.penup() for p in root: turtle.goto(*p) turtle.pendown() turtle.exitonclick() #============================================================================== if __name__ == "__main__": main()
