diff options
Diffstat (limited to '2024/aoc2024-d21_hardcoded.py')
| -rw-r--r-- | 2024/aoc2024-d21_hardcoded.py | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/2024/aoc2024-d21_hardcoded.py b/2024/aoc2024-d21_hardcoded.py new file mode 100644 index 0000000..1d360b2 --- /dev/null +++ b/2024/aoc2024-d21_hardcoded.py @@ -0,0 +1,237 @@ +#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); + |