quiz を解いてみた - None is None is None

所要時間は・・・３時間半くらい？腹が減った。
こんな事する間に、試験勉強しなきゃなぁ・・・
#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()