Last active
January 23, 2019 03:22
-
-
Save ogurets/a66d914781c6e82ecf87bed453a28f9f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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!') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment