Brute-force solution to up-it-up (game by CCL, IITGN)

up_it_up.py

import argparse
import sys
from collections import deque


BLOCK_TRN = {
    ('u', 'f'): 'f',
    ('u', 'b'): 'b',
    ('u', 'l'): 'l',
    ('u', 'r'): 'r',

    ('d', 'f'): 'b',
    ('d', 'b'): 'f',
    ('d', 'l'): 'r',
    ('d', 'r'): 'l',

    ('f', 'f'): 'd',
    ('f', 'b'): 'u',
    ('f', 'l'): 'f',
    ('f', 'r'): 'f',

    ('b', 'f'): 'u',
    ('b', 'b'): 'd',
    ('b', 'l'): 'b',
    ('b', 'r'): 'b',

    ('l', 'f'): 'l',
    ('l', 'b'): 'l',
    ('l', 'l'): 'd',
    ('l', 'r'): 'u',

    ('r', 'f'): 'r',
    ('r', 'b'): 'r',
    ('r', 'l'): 'u',
    ('r', 'r'): 'd',
}

MOVES = {
    0: {'l': 1, 'f': 3},
    1: {'r': 0, 'l': 2, 'f': 4},
    2: {'r': 1, 'f': 5},
    3: {'b': 0, 'l': 4, 'f': 6},
    4: {'b': 1, 'r': 3, 'l': 5, 'f': 7},
    5: {'b': 2, 'r': 4, 'f': 8},
    6: {'b': 3, 'l': 7},
    7: {'b': 4, 'r': 6, 'l': 8},
    8: {'b': 5, 'r': 7},
}


def change_config(config, dir):
    zpos = config.find('0')
    newpos = MOVES[zpos][dir]
    newor = BLOCK_TRN[(config[newpos], dir)]
    ors = list(config)
    ors[zpos], ors[newpos] = newor, '0'
    return ''.join(ors)


def get_nbrs(config):
    zpos = config.find('0')
    newconfigs = []
    for dir, newpos in MOVES[zpos].items():
        newor = BLOCK_TRN[(config[newpos], dir)]
        ors = list(config)
        ors[zpos], ors[newpos] = newor, '0'
        newconfigs.append((dir, ''.join(ors)))
    return newconfigs


def test_get_nbrs():
    config = input("Enter config: ")
    print(get_nbrs(config))


def find_path(s, t, maxiters=10**9, print_interval=None):
    dist = {s: 0}
    visited = set()
    parent = {}
    queue = deque()
    queue.append(s)
    found = False
    max_dist = 0

    i = 0
    while queue and not found:
        if i >= maxiters:
            break
        if print_interval is not None and (i + 1) % print_interval == 0:
            print('{}: max_dist: {}, visited: {}, queue: {}'.format(
                i, max_dist, len(visited), len(queue)))
        # print('visited:', visited, file=sys.stderr)
        # print('parent:', parent, file=sys.stderr)
        u = queue.popleft()
        if u not in visited:
            visited.add(u)
        for dir, v in get_nbrs(u):
            if v not in visited:
                parent[v] = (dir, u)
                dist[v] = dist[u] + 1
                max_dist = max(max_dist, dist[v])
                queue.append(v)
            if v == t:
                found = True
        i += 1

    if not found:
        print('not found', file=sys.stderr)
        return None

    path_verts = [t]
    dirs = []
    while path_verts[-1] in parent:
        dir, p = parent[path_verts[-1]]
        dirs.append(dir)
        path_verts.append(p)
    return (list(reversed(dirs)), list(reversed(path_verts)))


if __name__ == '__main__':
    parser = argparse.ArgumentParser()
    parser.add_argument('--max-iters', type=int, default=10**9)
    parser.add_argument('--print-interval', type=int)
    args = parser.parse_args()

    res = find_path('uuuu0uuuu', 'dddd0dddd', args.max_iters, args.print_interval)
    if res is not None:
        dirs, path_verts = res
        print(dirs)
        print(path_verts)

Moves: blfrrfllbrfrblflbrfrbblflbrflfrbrflb (b means rotate backwards, f is forward, l is left, r is right)
Intermediate configurations:
['uuuu0uuuu', 'u0uubuuuu', 'ul0ubuuuu', 'ulfub0uuu', 'ulfu0buuu', 'ulf0rbuuu', 'ulffrb0uu', 'ulffrbl0u', 'ulffrbll0', 'ulffr0lld', 'ulff0dlld', 'ulffldl0d', 'ulffld0ud', 'ulf0lduud', 'ulfd0duud', 'ulfdfdu0d', 'ulfdfdur0', 'ulfdf0urf', 'ulfd0furf', 'ulfdrfu0f', 'ulfdrf0rf', 'ulf0rffrf', '0lfbrffrf', 'd0fbrffrf', 'drfb0ffrf', 'drfbf0frf', 'dr0bfufrf', 'd0dbfufrf', 'dddb0ufrf', 'dddbl0frf', 'dddbldfr0', 'dddbldf0d', 'dddb0dfld', 'ddd0bdfld', 'ddddbd0ld', 'ddddbdd0d', 'dddd0dddd']
(u is upward-facing, d is downward-facing, f is forward-facing, ...)