773_sliding_puzzle.py

# coding=utf-8
"""
https://leetcode.com/problems/sliding-puzzle/
Metaprogramming sub-millisecond solution beating 100% in performance.
"""
import itertools
from tqdm import tqdm
import pickle


def swap(src_perm, idx_from, idx_to):
    assert isinstance(src_perm, tuple)
    rv = list(src_perm)
    rv[idx_to], rv[idx_from] = rv[idx_from], rv[idx_to]
    return tuple(rv)


def build_perm_table():
    permtable = dict()  # {perm_hash: [perm_list, min_path_length]}
    revtable = dict()   # {perm_list: perm_hash}

    print('Generating permutation tables...')
    for h, p in tqdm(enumerate(itertools.permutations([1, 2, 3, 4, 5, 0]))):
        revtable[p] = h
        permtable[h] = [p, None]

    print('Building graph...')
    # Which elements a k'th element could swap with (2x3 board)
    tabswaps = {
        i: [
            j for j in range(6)
            if j != i and (abs(i % 3 - j % 3) + abs(i / 3 - j / 3) == 1)
        ] for i in range(6)
    }

    # Calculate least paths in graph from state i to state 0
    print('Calculating least paths...')

    def iterswaps(state):
        """
        Iterate over all states reachable from current state
        :param state: (int hash) current state
        :yield: (int hash) reachable state
        """
        # Find 0 (empty cell)
        perm_list = permtable[state][0]
        zidx = perm_list.index(0)

        for swap_tgt in tabswaps[zidx]:
            swapped = swap(perm_list, zidx, swap_tgt)

            # Return edge
            tgt_state = revtable[swapped]
            yield tgt_state

    def traverse(state, depth):
        # List of adjacent position we haven't visited yet
        adjacent = []

        # Calculate all viable swaps
        for tgt_state in iterswaps(state):
            # Mark length
            perm_target = permtable[tgt_state]
            if perm_target[1] is None:
                # No path here yet
                perm_target[1] = depth
                # Process adjacent positions
                adjacent.append(tgt_state)
            elif depth < perm_target[1]:
                print('Oops, found shorter path!')

        return adjacent

    # Fill graph with lengths breadth-first
    adj = [0]
    depth = 0
    permtable[0][1] = 0  # Reachable from itself in 0 moves
    while len(adj) > 0:
        newadj = []
        depth += 1
        for pos in adj:
            newadj += traverse(pos, depth)
        adj = newadj

    return permtable


if __name__ == '__main__':
    try:
        with open('permtable.pickle', 'rb') as fp:
            permtable = pickle.load(fp)
            print('Cached permutation table found and loaded')
    except IOError:
        permtable = build_perm_table()
        with open('permtable.pickle', 'wb') as fp:
            pickle.dump(permtable, fp)

    print('Partitioning decision tree...')
    dtree = dict()
    for _, (perm_list, min_path) in permtable.iteritems():
        curnode = dtree
        # If input data is always assumed valid, the last case is trivial!
        # Can optimize down to 4
        for pos in range(4):
            curnode = curnode.setdefault(perm_list[pos], dict())
        curnode[perm_list[4]] = min_path  # Leaf node

    print('Dumping C++ code...')
    with open('dectree.cpp', 'wt') as fp:
        # Header
        fp.write(
            'const int x[5] = {{{}}};\n\n'.format(
                ', '.join((
                    'board[{}][{}]'.format(i, j)
                    for i, j in itertools.product(range(2), range(3))
                ))
            )
        )

        def dumptree(treenode, depth):
            indent = depth

            def write(indent, line):
                fp.write('    ' * indent)
                fp.write(line)

            # Header
            write(indent, 'switch (x[{idx}]) {{\n'.format(idx=depth))
            indent += 1

            # Body
            for k, v in treenode.iteritems():
                write(indent, 'case {val}:\n'.format(val=k))
                if v is None:
                    write(indent + 1, 'return -1;\n')
                elif isinstance(v, int):
                    write(indent + 1, 'return {};\n'.format(v))
                else:
                    dumptree(v, depth + 1)

            # Footer
            indent -= 1
            write(indent, '}\n')

        # Tree
        dumptree(dtree, 0)

    print('Done!')