Skip to content

Instantly share code, notes, and snippets.

@sharmaeklavya2

sharmaeklavya2/up_it_up.py

Created February 20, 2020 12:40
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sharmaeklavya2/c0eb4e7f148db9e922292868ae4f4ecb to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sharmaeklavya2/c0eb4e7f148db9e922292868ae4f4ecb to your computer and use it in GitHub Desktop.
Download ZIP
Brute-force solution to up-it-up (game by CCL, IITGN)
Raw
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)
@sharmaeklavya2
Copy link
Author

sharmaeklavya2 commented Feb 20, 2020

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, ...)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment