#advent of code 2024
#day 21 
#finally fucking worked
#I had a good idea for part1 to not generate all steps but only count
#the number of steps since the strings for part 2 would eat up all the RAM
#however I got hit by another problem which I didn't forsee,
#that is permutations. Basically, for part 2, you need to take into account
#that maybe going in different order is going to yield better results
#I hardcoded the possible steps instead of DFSing them like a normal
#human being and doubled down on it later. When I'll have more time and will to
#improve the code, I'll include the part where I generate the movements
#solution for part 1 was developed on my own, but for part 2 I needed
#external help (at least I understand what's going on in here so it's not
#that I copy-pasted someone else's code).
from functools import cache
import itertools
#use this for later
'''
keyboard_num = {};
keyboard_num["7"] = (0,0);
keyboard_num["8"] = (1,0);
keyboard_num["9"] = (2,0);
keyboard_num["4"] = (1,0);
keyboard_num["5"] = (1,1);
keyboard_num["6"] = (1,2);
keyboard_num["3"] = (2,0);
keyboard_num["2"] = (2,1);
keyboard_num["1"] = (2,2);
keyboard_num["0"] = (3,1);
keyboard_num["A"] = (3,2);
keyboard_dir = {};
keyboard_dir"^"] = (1,0);
keyboard_dir"A"] = (2,0);
keyboard_dir"<"] = (0,1);
keyboard_dir"v"] = (1,1);
keyboard_dir">"] = (2,1); #'''

dn = {};
dn["^"] = {};
dn["A"] = {};
dn["<"] = {};
dn["v"] = {};
dn[">"] = {};
dn["^"]["^"] =["A"];
dn["^"]["A"] =[">A"];
dn["^"]["<"] =["v<A"];
dn["^"]["v"] =["vA"];
dn["^"][">"] =["v>A",">vA"];
dn["A"]["^"] =["<A"];
dn["A"]["A"] =["A"];
dn["A"]["<"] =["v<<A","<v<A"];
dn["A"]["v"] =["v<A","<vA"];
dn["A"][">"] =["vA"];
dn["<"]["^"] =[">^A"];
dn["<"]["A"] =[">^>A",">>^A"];
dn["<"]["<"] =["A"];
dn["<"]["v"] =[">A"];
dn["<"][">"] =[">>A"];
dn["v"]["^"] =["^A"];
dn["v"]["A"] =["^>A",">^A"];
dn["v"]["<"] =["<A"];
dn["v"]["v"] =["A"];
dn["v"][">"] =[">A"];
dn[">"]["^"] =["^<A","<^A"];
dn[">"]["A"] =["^A"];
dn[">"]["<"] =["<<A"];
dn[">"]["v"] =["<A"];
dn[">"][">"] =["A"];

kn={};
kn["7"] = {};
kn["8"] = {};
kn["9"] = {};
kn["4"] = {};
kn["5"] = {};
kn["6"] = {};
kn["1"] = {};
kn["2"] = {};
kn["3"] = {};
kn["0"] = {};
kn["A"] = {};
kn["7"]["7"] =["A"];
kn["7"]["8"] =[">A"];
kn["7"]["9"] =[">>A"];
kn["7"]["4"] =["vA"];
kn["7"]["5"] =["v>A",">vA"];
kn["7"]["6"] =["v>>A",">v>A",">>vA"];
kn["7"]["1"] =["vvA"];
kn["7"]["2"] =["vv>A","v>vA",">vvA"];
kn["7"]["3"] =["vv>>A","v>v>A","v>>vA",">vv>A",">v>vA",">>vvA"];
kn["7"]["0"] =["vv>vA","v>vvA",">vvvA"];
kn["7"]["A"] =["vv>v>A","vv>>vA","v>vv>A","v>v>vA","v>>vvA",">vvv>A",">vv>vA",">v>vvA",">>vvvA"];
kn["8"]["7"] =["<A"];
kn["8"]["8"] =["A"];
kn["8"]["9"] =[">A"];
kn["8"]["4"] =["v<A","<vA"];
kn["8"]["5"] =["vA"];
kn["8"]["6"] =["v>A",">vA"];
kn["8"]["1"] =["vv<A","v<vA","<vvA"];
kn["8"]["2"] =["vvA"];
kn["8"]["3"] =["vv>A","v>vA",">vvA"];
kn["8"]["0"] =["vvvA"];
kn["8"]["A"] =["vvv>A","vv>vA","v>vvA",">vvvA"];
kn["9"]["7"] =["<<A"];
kn["9"]["8"] =["<A"];
kn["9"]["9"] =["A"];
kn["9"]["4"] =["v<<A","<v<A","<<vA"];
kn["9"]["5"] =["v<A","<vA"];
kn["9"]["6"] =["vA"];
kn["9"]["1"] =["vv<<A","v<v<A","v<<vA","<vv<A","<v<vA","<<vvA"];
kn["9"]["2"] =["vv<A","v<vA","<vvA"];
kn["9"]["3"] =["vvA"];
kn["9"]["0"] =["vvv<A","vv<vA","v<vvA","<vvvA"];
kn["9"]["A"] =["vvvA"];
kn["4"]["7"] =["^A"];
kn["4"]["8"] =["^>A",">^A"];
kn["4"]["9"] =["^>>A",">^>A",">>^A"];
kn["4"]["4"] =["A"];
kn["4"]["5"] =[">A"];
kn["4"]["6"] =[">>A"];
kn["4"]["1"] =["vA"];
kn["4"]["2"] =["v>A",">vA"];
kn["4"]["3"] =["v>>A",">v>A",">>vA"];
kn["4"]["0"] =["v>vA",">vvA"];
kn["4"]["A"] =["v>v>A","v>>vA",">vv>A",">v>vA",">>vvA"];
kn["5"]["7"] =["^<A","<^A"];
kn["5"]["8"] =["^A"];
kn["5"]["9"] =["^>A",">^A"];
kn["5"]["4"] =["<A"];
kn["5"]["5"] =["A"];
kn["5"]["6"] =[">A"];
kn["5"]["1"] =["v<A","<vA"];
kn["5"]["2"] =["vA"];
kn["5"]["3"] =["v>A",">vA"];
kn["5"]["0"] =["vvA"];
kn["5"]["A"] =["vv>A","v>vA",">vvA"];
kn["6"]["7"] =["^<<A","<^<A","<<^A"];
kn["6"]["8"] =["^<A","<^A"];
kn["6"]["9"] =["^A"];
kn["6"]["4"] =["<<A"];
kn["6"]["5"] =["<A"];
kn["6"]["6"] =["A"];
kn["6"]["1"] =["v<<A","<v<A","<<vA"];
kn["6"]["2"] =["v<A","<vA"];
kn["6"]["3"] =["vA"];
kn["6"]["0"] =["vv<A","v<vA","<vvA"];
kn["6"]["A"] =["vvA"];
kn["1"]["7"] =["^^A"];
kn["1"]["8"] =["^^>A","^>^A",">^^A"];
kn["1"]["9"] =["^^>>A","^>^>A","^>>^A",">^^>A",">^>^A",">>^^A"];
kn["1"]["4"] =["^A"];
kn["1"]["5"] =["^>A",">^A"];
kn["1"]["6"] =["^>>A",">^>A",">>^A"];
kn["1"]["1"] =["A"];
kn["1"]["2"] =[">A"];
kn["1"]["3"] =[">>A"];
kn["1"]["0"] =[">vA"];
kn["1"]["A"] =[">v>A",">>vA"];
kn["2"]["7"] =["^^<A","^<^A","<^^A"];
kn["2"]["8"] =["^^A"];
kn["2"]["9"] =["^^>A","^>^A",">^^A"];
kn["2"]["4"] =["^<A","<^A"];
kn["2"]["5"] =["^A"];
kn["2"]["6"] =["^>A",">^A"];
kn["2"]["1"] =["<A"];
kn["2"]["2"] =["A"];
kn["2"]["3"] =[">A"];
kn["2"]["0"] =["vA"];
kn["2"]["A"] =["v>A",">vA"];
kn["3"]["7"] =["^^<<A","^<^<A","^<<^A","<^^<A","<^<^A","<<^^A"];
kn["3"]["8"] =["^^<A","^<^A","<^^A"];
kn["3"]["9"] =["^^A"];
kn["3"]["4"] =["^<<A","<^<A","<<^A"];
kn["3"]["5"] =["^<A","<^A"];
kn["3"]["6"] =["^A"];
kn["3"]["1"] =["<<A"];
kn["3"]["2"] =["<A"];
kn["3"]["3"] =["A"];
kn["3"]["0"] =["v<A","<vA"];
kn["3"]["A"] =["vA"];
kn["0"]["7"] =["^^^<A","^^<^A","^<^^A"];
kn["0"]["8"] =["^^^A"];
kn["0"]["9"] =["^^^>A","^^>^A","^>^^A",">^^^A"];
kn["0"]["4"] =["^^<A","^<^A"];
kn["0"]["5"] =["^^A"];
kn["0"]["6"] =["^^>A","^>^A",">^^A"];
kn["0"]["1"] =["^<A"];
kn["0"]["2"] =["^A"];
kn["0"]["3"] =["^>A",">^A"];
kn["0"]["0"] =["A"];
kn["0"]["A"] =[">A"];
kn["A"]["7"] =["^^^<<A","^^<^<A","^^<<^A","^<^^<A","^<^<^A","^<<^^A","<^^^<A","<^^<^A","<^<^^A"];
kn["A"]["8"] =["^^^<A","^^<^A","^<^^A","<^^^A"];
kn["A"]["9"] =["^^^A"];
kn["A"]["4"] =["^^<<A","^<^<A","^<<^A","<^^<A","<^<^A"];
kn["A"]["5"] =["^^<A","^<^A","<^^A"];
kn["A"]["6"] =["^^A"];
kn["A"]["1"] =["^<<A","<^<A"];
kn["A"]["2"] =["^<A","<^A"];
kn["A"]["3"] =["^A"];
kn["A"]["0"] =["<A"];
kn["A"]["A"] =["A"];


codes = [l for l in open("21.in","r").read().strip().split("\n")];

def GenDirMoves(mystring, seqs):
    options = [seqs[x][y] for x, y in zip("A" + mystring, mystring)]
    return ["".join(x) for x in itertools.product(*options)]

@cache
def CalcSteps(DirMoves,PrevPos,depth):
	if depth == 1:
		return sum(len(dn[pos1][pos2][0]) for pos1,pos2 in zip("A"+DirMoves,DirMoves));
	score = 0;
	for pos1, pos2 in zip("A"+DirMoves,DirMoves): 
		score += min(CalcSteps(substring,"A",depth-1) for substring in dn[pos1][pos2])
	return score;

def get_score(inputs,NumberOfRobots):
	total = 0;
	for data in inputs: 
		options = GenDirMoves(data,kn);
		LengthOfShortestSequence = float('inf');
		for op in options:
			LengthOfShortestSequence = min(LengthOfShortestSequence,CalcSteps(op,"A",NumberOfRobots))
		NumericPartOfCode = int(data[:-1]);
		Complexity = NumericPartOfCode*LengthOfShortestSequence;
		total += Complexity;
	return total;

part1 = get_score(codes,2);
part2 = get_score(codes,25);

print("part 1 =", part1);
print("part 1 =", part2);