You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
119 lines
2.9 KiB
119 lines
2.9 KiB
#!/usr/bin/env python3
|
|
|
|
import sys, math
|
|
from itertools import product
|
|
|
|
DIR = {
|
|
('A', '>'): ['vA'],
|
|
('A', '^'): ['<A'],
|
|
('A', 'v'): ['v<A', '<vA'],
|
|
('A', '<'): ['v<<A'],
|
|
('A', 'A'): ['A'],
|
|
('^', '^'): ['A'],
|
|
('<', '<'): ['A'],
|
|
('v', 'v'): ['A'],
|
|
('>', '>'): ['A'],
|
|
('^', 'A'): ['>A'],
|
|
('^', '>'): ['v>A', '>vA'],
|
|
('^', 'v'): ['vA'],
|
|
('^', '<'): ['v<A'],
|
|
('<', 'A'): ['>>^A'],
|
|
('<', '^'): ['>^A'],
|
|
('<', 'v'): ['>A'],
|
|
('<', '>'): ['>>A'],
|
|
('v', 'A'): ['>^A', '^>A'],
|
|
('v', '^'): ['^A'],
|
|
('v', '<'): ['<A'],
|
|
('v', '>'): ['>A'],
|
|
('>', 'A'): ['^A'],
|
|
('>', '<'): ['<<A'],
|
|
('>', '^'): ['<^A', '^<A'],
|
|
('>', 'v'): ['<A'],
|
|
}
|
|
|
|
NUM = {
|
|
'A': (0,2),
|
|
'0': (0,1),
|
|
'1': (1,0),
|
|
'2': (1,1),
|
|
'3': (1,2),
|
|
'4': (2,0),
|
|
'5': (2,1),
|
|
'6': (2,2),
|
|
'7': (3,0),
|
|
'8': (3,1),
|
|
'9': (3,2),
|
|
}
|
|
|
|
|
|
def memo(f):
|
|
memo = {}
|
|
|
|
def f2(x,y):
|
|
if (tuple(x),y) not in memo: memo[(tuple(x),y)] = f(x,y)
|
|
return memo[(tuple(x),y)]
|
|
return f2
|
|
|
|
|
|
def options(start, end, pad):
|
|
s, e = pad[start], pad[end]
|
|
d = {'^': (1,0), 'v': (-1,0), '>': (0,1), '<': (0,-1)}
|
|
dy = e[0]-s[0]
|
|
dx = e[1]-s[1]
|
|
opt = ['^'] * dy + ['v'] * -dy + ['<'] * -dx + ['>'] * dx
|
|
for o in [tuple(opt), tuple(reversed(opt))]:
|
|
s, e = pad[start], pad[end]
|
|
gap = False
|
|
for step in list(o):
|
|
s = s[0] + d[step][0], s[1] + d[step][1]
|
|
if s == (0,0): gap = True
|
|
if not gap: yield ''.join(o+('A',))
|
|
|
|
|
|
def numeric(code):
|
|
strings = ['']
|
|
prev = 'A'
|
|
for key in list(code):
|
|
strings = [s1+s2 for (s1,s2) in product(strings,[opt for opt in options(prev, key, NUM)])]
|
|
prev = key
|
|
return strings
|
|
|
|
# reddit solution... (prevKey is 'A' the first time)
|
|
def buildSeq(keys, index, prevKey, currPath, result):
|
|
if index == len(keys):
|
|
result.append(currPath)
|
|
return
|
|
for path in DIR[(prevKey,keys[index])]:
|
|
buildSeq(keys, index+1, keys[index], currPath + path, result)
|
|
|
|
|
|
@memo
|
|
def shortestSeq(keys, depth):
|
|
if depth == 0: return len(keys)
|
|
total = 0
|
|
subKeys = keys.split('A')
|
|
for subKey in subKeys[:-1]:
|
|
seqs = []
|
|
buildSeq(subKey+'A', 0, 'A', '', seqs)
|
|
minimum = min([shortestSeq(seq, depth-1) for seq in seqs])
|
|
total += minimum
|
|
return total
|
|
|
|
|
|
if __name__ == '__main__':
|
|
codes = [line.strip('\n') for line in open(sys.argv[1])]
|
|
res1, res2 = 0, 0
|
|
for code in codes:
|
|
dirs = set(numeric(code))
|
|
l1, l2 = math.inf, math.inf
|
|
for d in dirs: l1 = min(shortestSeq(d,2), l1)
|
|
res1 += l1 * int(code[:-1])
|
|
for d in dirs: l2 = min(shortestSeq(d,25), l2)
|
|
res2 += l2 * int(code[:-1])
|
|
|
|
# challenge 1
|
|
print(f"challenge 1:\n{res1}\n")
|
|
|
|
# challenge 2
|
|
print(f"challenge 2:\n{res2}")
|
|
|
|
|