Skip to content

Instantly share code, notes, and snippets.

@ogurets
Last active January 23, 2019 03:22
Show Gist options
  • Save ogurets/a66d914781c6e82ecf87bed453a28f9f to your computer and use it in GitHub Desktop.
Save ogurets/a66d914781c6e82ecf87bed453a28f9f to your computer and use it in GitHub Desktop.
# 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