edgematch

import string
import itertools
import time

orientations = "NESW"

def solve(gridsize, tiles, tileletters):
    solution = next(solutions(gridsize, tiles))
    print ' '.join([tileletters[tile] + orientation
                    for tile, orientation in solution])

def solutions(gridsize, tiles):
    return eval(compile_solutions(gridsize))(tiles)

def compile_solutions(gridsize):
    def compile_for(vars):
        return "for %s in candidates(tiles, [%s])" %\
            (vars[-1], ",".join(vars[:-1]))

    def compile_if(vars):
        pos = len(vars)-1
        if pos == 0:
            return ""
        elif pos < gridsize:
            return "if mleftof(%s,%s)" % (vars[pos-1], vars[pos])
        elif pos % gridsize == 0:
            return "if mabove(%s,%s)" % (vars[pos-gridsize], vars[pos])
        else:
            return "if mleftof(%s,%s) and mabove(%s,%s)" %\
                (vars[pos-1], vars[pos], vars[pos-gridsize], vars[pos])

    def compile_clause(vars):
        return " ".join([compile_for(vars), compile_if(vars)])

    vars = ["p" + str(pos) for pos in range(gridsize**2)]
    body = "(" + "(" + ",".join(vars) + ")\n" +\
           "\n".join([compile_clause(list(itertools.islice(vars, pos+1)))
                      for pos in range(len(vars))]) + ")"
    return "lambda tiles : %s" % body

def candidates(tiles, places):
    remaining = tiles.difference([tile for tile, _ in places])
    return itertools.product(remaining, orientations)

def match(edge1, edge2):
    return string.swapcase(edge1) == edge2

def mleftof(p1, p2):
    return match(rightedge(p1), leftedge(p2))

def mabove(p1, p2):
    return match(bottomedge(p1), topedge(p2))

def edge(n, place):
    (tile, orien) = place
    return tile[n-orientations.index(orien)]

def topedge(p): return edge(0, p)
def rightedge(p): return edge(1, p)
def bottomedge(p): return edge(2, p)
def leftedge(p): return edge(3, p)

def from_file(filename, sep='\n'):
    return file(filename).read().strip().split(sep)

def read_puzzle(filename):
    input = from_file(filename)
    gridsize = int(input[0])
    tiles = input[1:]
    tileletters = dict(zip(tiles, string.ascii_uppercase))
    return gridsize, set(tiles), tileletters

def timedcall(fn, *args):
    start = time.clock()
    result = fn(*args)
    t = time.clock()-start
    print '(%.2f seconds)\n' % t
    return (result, t)

def test():
    assert mleftof(("ycKC", "N"), ("mMyC", "N"))
    assert not mleftof(("ycKC", "N"), ("mMyC", "E"))

    assert mabove(("ycKC", "N"), ("kKcY", "N"))
    assert not mabove(("ycKC", "N"), ("kKcY", "E"))

    assert topedge(("kKcY", "N")) == "k"
    assert topedge(("kKcY", "E")) == "Y"
    assert topedge(("kKcY", "S")) == "c"
    assert topedge(("kKcY", "W")) == "K"

    assert match("A", "a")
    assert match("a", "A")
    assert not match("A", "A")
    assert not match("a", "a")

    print "All tests pass."

if __name__ == '__main__':
    test()
    timedcall(solve, *read_puzzle("input3.txt"))
    timedcall(solve, *read_puzzle("input4.txt"))
    timedcall(solve, *read_puzzle("input5.txt"))