# Input: three-digit numbers followed by "A"
# Output: using three tiers of directional keypads
#            ^A
#           <v>
#         (A = push button), get a numeric keypad
#           789
#           456
#           123
#            0A
#         to type each line (while never pointing to a gap)
#         find sum of (shortest sequence * three-digit number)

import itertools

from functools import cache

lines = []

file = open("21_input.txt", "r")
for line in file:
  line = line.replace("\n", "")
  lines.append(line)

dk_keys = {} # key = character, value = [row, column]
dk_keys[" "] = [0, 0]
dk_keys["^"] = [0, 1]
dk_keys["A"] = [0, 2]
dk_keys["<"] = [1, 0]
dk_keys["v"] = [1, 1]
dk_keys[">"] = [1, 2]

nk_keys = {}
nk_keys["7"] = [0, 0]
nk_keys["8"] = [0, 1]
nk_keys["9"] = [0, 2]
nk_keys["4"] = [1, 0]
nk_keys["5"] = [1, 1]
nk_keys["6"] = [1, 2]
nk_keys["1"] = [2, 0]
nk_keys["2"] = [2, 1]
nk_keys["3"] = [2, 2]
nk_keys[" "] = [3, 0]
nk_keys["0"] = [3, 1]
nk_keys["A"] = [3, 2]

# assumption: longer sequence of presses never has lower cost

def get_sequences(dict):
  derived_dict = {}
  for current in dict:
    if current == " ":
      continue
    for goal in dict:
      if goal == " ":
        continue
      cr, cc = dict[current][0], dict[current][1]
      gr, gc = dict[goal][0], dict[goal][1]
      keys_to_press = []
      for r in range(abs(cr - gr)):
        if cr > gr:
          keys_to_press.append("^")
        if cr < gr:
          keys_to_press.append("v")
      for c in range(abs(cc - gc)):
        if cc > gc:
          keys_to_press.append("<")
        if cc < gc:
          keys_to_press.append(">")
      options = []
      for key_permutation in list(itertools.permutations(keys_to_press)):
        # if it crosses a gap, then omit it
        r, c = cr, cc
        key_list_valid = True
        key_list = ""
        for key in key_permutation:
          if key == "^":
            r -= 1
          if key == "v":
            r += 1
          if key == "<":
            c -= 1
          if key == ">":
            c += 1
          if r == dict[" "][0] and c == dict[" "][1]:
            key_list_valid = False
            break
          key_list += key
        if key_list_valid:
          options.append(key_list)
      derived_dict[current + goal] = options
  return derived_dict

d2d = get_sequences(dk_keys)
n2d = get_sequences(nk_keys)

@cache
def get_all_sub_sequences(str, use_n2d):
  dict = d2d
  if use_n2d:
    dict = n2d
  if len(str) == 1:
    return [""]
  options = []
  for next_step in dict[str[:2]]:
    for rest_of_steps in get_all_sub_sequences(str[1:], use_n2d):
      options.append(next_step + "A" + rest_of_steps)
  return list(set(options))

@cache
def get_all_sequences(str, use_n2d):
  return get_all_sub_sequences("A" + str, use_n2d)

total = 0
for line in lines:
  code = int(line.replace("A", ""))
  options = get_all_sequences(line, True)
  shortest_option = -1
  for option in options:
    for option2 in get_all_sequences(option, False):
      for option3 in get_all_sequences(option2, False):
        if shortest_option == -1 or shortest_option > len(option3):
          shortest_option = len(option3)
  total += code * shortest_option
print (total)