# Input: three-digit numbers followed by "A"
# Output: using 26 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_up_down = ""
      keys_left_right = ""
      for r in range(abs(cr - gr)):
        if cr > gr:
          keys_up_down += "^"
        if cr < gr:
          keys_up_down += "v"
      for c in range(abs(cc - gc)):
        if cc > gc:
          keys_left_right += "<"
        if cc < gc:
          keys_left_right += ">"
      key_lists = []
      key_lists.append(keys_up_down + keys_left_right)
      key_lists.append(keys_left_right + keys_up_down)
      options = []
      for key_list in list(set(key_lists)):
        # if it crosses a gap, then omit it
        r, c = cr, cc
        key_list_valid = True
        for key in key_list:
          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
        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)

d2d_tiered = {}
number_tiers = 25

def get_tier_key(pair, tier):
  return pair + "," + str(tier)

for tier in range(number_tiers, 0, -1):
  for pair in d2d:
    s_list = get_all_sub_sequences(pair, False)
    shortest_cost = -1
    for s in s_list:
      cost = 0
      if tier == number_tiers:
        cost = len(s)
      else:
        s2 = "A" + s
        for i in range(len(s2) - 1):
          cost += d2d_tiered[get_tier_key(s2[i:i+2], tier + 1)]
      if shortest_cost == -1 or shortest_cost > cost:
        shortest_cost = cost
    d2d_tiered[get_tier_key(pair, tier)] = shortest_cost

total = 0
for line in lines:
  code = int(line.replace("A", ""))
  options = get_all_sequences(line, True)
  shortest_cost = -1
  for option in options:
    cost = 0
    option2 = "A" + option
    for i in range(len(option2) - 1):
      cost += d2d_tiered[get_tier_key(option2[i:i+2], 1)]
    if shortest_cost == -1 or shortest_cost > cost:
      shortest_cost = cost
  total += code * shortest_cost
print (total)