diff options
| -rw-r--r-- | 2024/aoc2024-d17.py | 65 | ||||
| -rw-r--r-- | 2024/aoc2024-d18.py | 64 | ||||
| -rw-r--r-- | 2024/aoc2024-d19.py | 49 | ||||
| -rw-r--r-- | 2024/aoc2024-d20.py | 84 | ||||
| -rw-r--r-- | 2024/aoc2024-d21_hardcoded.py | 237 | ||||
| -rw-r--r-- | 2024/aoc2024-d22.py | 79 | ||||
| -rw-r--r-- | 2024/aoc2024-d23.py | 73 | ||||
| -rw-r--r-- | 2024/aoc2024-d24.py | 82 | ||||
| -rw-r--r-- | 2024/aoc2024-d25.py | 55 |
9 files changed, 788 insertions, 0 deletions
diff --git a/2024/aoc2024-d17.py b/2024/aoc2024-d17.py new file mode 100644 index 0000000..c5a41b1 --- /dev/null +++ b/2024/aoc2024-d17.py @@ -0,0 +1,65 @@ +#advent of code 2024 +#day 17 +#code needs input reading, hardcoded my input out of convenience +#the fucking commas where part of a solution lol, misread the problem there +#if I were to reverse the logic for 3rd argument in broot function +#it could work for longer inputs +import re +RegsRaw, ProgRaw = open("17.in","r").read().split("\n\n"); +#by Eric's request, the input is removed +MyCode = []; +MyA = ; + +Register = {}; +Register[0] = 0; #A +Register[1] = 0; #B +Register[2] = 0; #C + +def combo(op): + if op <= 3: return op; + elif op == 4: return Register[0]; + elif op == 5: return Register[1]; + elif op == 6: return Register[2]; + +def runprogram(code,A): + Results = []; + InstrPointer = 0; + Register[0] = A; #A + while InstrPointer < len(code): + operand = code[InstrPointer+1]; + Inst = code[InstrPointer]; + #print(InstrPointer, Inst , operand); + if Inst == 0: Register[0] = Register[0]>>combo(operand); + elif Inst == 1: Register[1] = Register[1]^operand; + elif Inst == 2: Register[1] = combo(operand)%8; + elif Inst == 3: + if Register[0] != 0: InstrPointer = operand -2; + elif Inst == 4: Register[1] = Register[1]^Register[2]; + elif Inst == 5: Results.append(combo(operand)%8); + elif Inst == 6: Register[1] = Register[0]>>combo(operand); + elif Inst == 7: Register[2] = Register[0]>>combo(operand); + InstrPointer += 2; + return Results; + +def broot(code,PotentialA,ind): + valid = []; + if ind == 0: + PotentialA = [0]; + for pa in PotentialA: + for option in range(8): + A_to_check = pow(8,(15-ind))*option + pa; + output = runprogram(code,A_to_check); + if output[-ind-1:] == code[-ind-1:]: valid.append(A_to_check); + if ind != 15: + valid = broot(code,valid.copy(),ind+1); + return valid; + +part1 = ",".join([str(n) for n in runprogram(MyCode,MyA)]); +print("part 1 =", part1); + +MinimalValues = broot(MyCode,[],0); +part2 = MinimalValues[0]; +for mv in MinimalValues: + if runprogram(MyCode,mv) == MyCode: part2 = min(part2,mv); + +print("part 2 =",part2); diff --git a/2024/aoc2024-d18.py b/2024/aoc2024-d18.py new file mode 100644 index 0000000..5f848fc --- /dev/null +++ b/2024/aoc2024-d18.py @@ -0,0 +1,64 @@ +#advent of code 2024 +#day 18 +#advent of gridbroot + +import heapq + +mygrid = {}; +FallingBytes = []; +lim = 70 + 1; +bytelim = 1024; +for p in [(X,Y) for Y in range(lim) for X in range(lim)]: mygrid[p] = "."; +#myfile = "18.ex"; +myfile = "18.in"; +if myfile != "18.in": #if example + lim = 7; + bytelim = 12; + +f = open(myfile,"r"); +for counter,l in enumerate(f): + bytex,bytey = [int(v) for v in l.strip().split(",")]; + FallingBytes.append((bytex,bytey)); + if counter < bytelim: mygrid[(bytex,bytey)] = "#"; +f.close(); + +start = (0,0); +end = (lim-1,lim-1); +dirs = [(1,0),(0,1),(-1,0),(0,-1)]; #east, south, west, north + +def getAdjacent(grid,coordinates): + adj = []; + xp, yp = coordinates; + for i,d in enumerate(dirs): + dx,dy = d; + if grid.get((xp+dx,yp+dy),"#") != "#": + adj.append((xp+dx,yp+dy)); + return adj; + +def shortestpath(grid,startpos): + score = 0; + visited = set(); + queue = [(0,startpos)]; + while queue: + dist, pos = heapq.heappop(queue); + if pos in visited: continue; + visited.add(pos); + if pos == end: + score = dist; + break; + NextPositions = getAdjacent(grid,pos); + for NP in NextPositions: + heapq.heappush(queue,(dist+1,NP)); + return score + +part1 = shortestpath(mygrid,start); +print("part 1 =",part1); +part2 = None; +for b_ind,b in enumerate(FallingBytes[bytelim:]): + mygrid[b] = "#"; + path = shortestpath(mygrid,start); + if path == 0: + part2 = f'{b[0]},{b[1]}'; + break; + +print("part 2 =",part2); diff --git a/2024/aoc2024-d19.py b/2024/aoc2024-d19.py new file mode 100644 index 0000000..eb3721a --- /dev/null +++ b/2024/aoc2024-d19.py @@ -0,0 +1,49 @@ +#advent of code 2024 +#day 19 +#unfortunately I didn't figure it out in time on my own +#I read some tips on the internet and returned to it on later date +#my attempt was kinda close but I didn't manage to correctly +#control the flow of the program which lead to duplicated paths +#I used the patterns dictionary to split the patterns based on their +#first letter so I don't need to check all patterns at the same time, +#only those potentially correct +#then, using CalcDesign function, we iterate over the whole string +#the dictionary PatternPaths stores the total amount of possible ways +#to reach a given substring of the function argument +#when we check each character c of the argument, we first look up +#how many paths there are to reach this substring (if it's the first +#letter then it is hardcoded as 1). Then we iterate over the list of +#patterns that begin with given character. +#if the substring plus pattern are the same as the substring of design +#then it is counted as possible path +#function returns a bool and an int: if there's at least one way to reach +#desired design (part 1), and amount of possible ways to reach it (part 2) + +def CalcDesign(design): + PatternPaths = {}; + for c_ind,c in enumerate(design): #character index, character + subpath = PatternPaths.get(design[:c_ind],0) + 1*(c_ind==0); + for pattern in patterns.get(c,[]): + subdesign = design[:c_ind] + pattern; + if subdesign == design[:c_ind + len(pattern)]: + if subdesign not in PatternPaths: + PatternPaths[subdesign] = 0; + PatternPaths[subdesign] += subpath + 0; + paths = PatternPaths.get(design,0); + return paths != 0, paths; + +part1 = 0; +part2 = 0; +patterns = {}; +data1, data2 = open("19.in","r").read().split("\n\n"); +for data in data1.strip().split(", "): + if data[0] not in patterns: patterns[data[0]] = []; + patterns[data[0]].append(data); + +for des in data2.strip().split("\n"): + ok,TotalPaths = CalcDesign(des); + part1 += ok*1; + part2 += TotalPaths; + +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d20.py b/2024/aoc2024-d20.py new file mode 100644 index 0000000..16ed3c4 --- /dev/null +++ b/2024/aoc2024-d20.py @@ -0,0 +1,84 @@ +#advent of code 2024 +#day 20 +#shamelessly copypasted previous pathfinding and input parsing +#except it needed much adjustments because it's not really pathfinding +#basically: calculate map of distances between each point with djikstra +#since the path never branches, you can use these distances +#instead of recalculating the path after each cheat +#cheat + +grid = {}; +xMin, yMin, xMax, yMax = 0,0,0,0; #could get rid of it but w/e +dirs = [(1,0),(0,1),(-1,0),(0,-1)]; #east, south, west, north + +f = open("20.in","r"); +for y,l in enumerate(f): + yMax = max(y,yMax); + for x,c in enumerate(l.strip()): + if c == "S": + start = (x,y); + c = "." + elif c == "E": + end = (x,y); + c = "." + grid[(x,y)]=c; + xMax = max(xMax,x); +f.close(); + +def getAdjacent(coordinates): + adj = []; + xp, yp = coordinates; + for d in dirs: + dx,dy = d; + if grid.get((xp+dx,yp+dy),"#") != "#": + adj.append((xp+dx,yp+dy)); + return adj; + +def djikstra(startpos,endpos): + queue = []; + DistanceMap = {}; + queue = [(startpos,0)]; + while queue: + coords,dist = queue.pop(); + if coords in DistanceMap: continue; + DistanceMap[coords] = min(DistanceMap.get(coords,float('inf')),dist); + for NextPos in getAdjacent(coords): + queue.append((NextPos,dist+1)); + return DistanceMap; + +def cheatAdjacent(coordinates,secs): + adj = set(); + px,py = coordinates; + for X in range(secs+1): + for Y in range(secs+1-X): + adj.add((px+X*1,py+Y*1)); + adj.add((px+X*(-1),py+Y*(-1))); + adj.add((px+X*(1),py+Y*(-1))); + adj.add((px+X*(-1),py+Y*(1))); + return adj; + +PathDistances = djikstra(start,end); +part1 = 0; +part2 = 0; +for position in PathDistances: + d1 = PathDistances.get(position,-1); #negative value if there's no match + CheatedSteps = cheatAdjacent(position,20); + for ch in CheatedSteps: + d2 = PathDistances.get(ch,-1); #negative value if there's no match + if d2 == -1: continue; #if the step isn't in the PathDistances, then it's not valid + manhattan = abs(ch[0]-position[0]) + abs(ch[1]-position[1]) + ScoreDifference = d2-d1 - manhattan + if ScoreDifference >= 100: #from description, doesn't work for example + part2 += 1; + part1 += 1*(manhattan <= 2); + +print("part 1 =", part1); +print("part 2 =", part2); +#grid print for reference/debugging +#for y in range(yMax+1): +# for x in range(xMax+1): +# c = grid[(x,y)]; +# if (x,y) == start: c = "S"; +# elif (x,y) == end: c = "E"; +# print(c, end=""); +# print(); 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); + diff --git a/2024/aoc2024-d22.py b/2024/aoc2024-d22.py new file mode 100644 index 0000000..5c4c809 --- /dev/null +++ b/2024/aoc2024-d22.py @@ -0,0 +1,79 @@ +#advent of code day 22 +#day 22 +#first puzzle I did after getting filtered by day 19 +#easy enough, just needed to calculate the prices per sequences +#before calculating the sums to speed things up +#for part 1 jsut calculate the new secret number after 2000 iterations +#for part 2: make 2 dictionaries with secret number indexes as keys +#each value in both dictionaries are lists +#1 dictionary is for how prices are changing, the other one is current prices +#make a set of all possible sequences from all secret keys based on price change dictionary +#make a 3rd dictionary which has secret number as key and another dictionary as value +#the nested dictionary contains prices based on a sequence +#after that just iterate over the set of possible sequences make a sum +#of the prices for that sequence, choose the highest +#one thing that lead to a wrong answer was that I was constantly updating +#the price in 3rd dictionary, but according to problem descriptions +#monkeys sell the first time the sequence occurs, which means I needed to +#only register the price once, then skip the sequence next time it occurs in +#given secret number + +SecretNumbers = [int(l) for l in open("22.in","r").read().strip().split("\n")]; + +def CalcSecret(previous_number): + next_number = (previous_number<<6)^previous_number; + next_number = next_number%16777216; + next_number = (next_number>>5)^next_number; + next_number = next_number%16777216; + next_number = (next_number<<11)^next_number; + next_number = next_number%16777216; + return next_number; + +print("please wait 1/3"); +part1 = 0; +step = 2000; +changes = {}; +prices = {}; +#calculate the 2000 iterations of each secret number +#sum up all values of 2000th iteration for part 1 +#store the prices of each number for each iteration +#store the change in price of each number for each iteration +for num_i,num in enumerate(SecretNumbers): + num_old = 0 + num; + changes[num_i] = []; + prices[num_i] = []; + prices[num_i].append(num%10); + for s in range(step): + num_new = CalcSecret(num_old); + changes[num_i].append(num_new%10-num_old%10); + prices[num_i].append(num_new%10); + num_old = 0 + num_new; + part1 += num_old; + +print("please wait 2/3"); +#create a set of all possible sequences +#store the price of a secret number when given sequence occurs +prices_per_seq = {}; +sequences = set(); +for num_i in changes: + prices_per_seq[num_i] = {}; + for j in range(3,len(changes[num_i])): + subseq = tuple(changes[num_i][j-3:j+1]); + sequences.add(subseq); + price_sub = prices[num_i][j+1]; + if subseq in prices_per_seq[num_i]: continue; + prices_per_seq[num_i][subseq] = price_sub + 0; + +print("please wait 3/3"); +#for each sequence calculate the sum of prices for each secret number +#when given sequence occurs. Store the highest sum for part 2 +part2 = 0; +for s_i,sequence in enumerate(sequences): + print(s_i+1,"/",len(sequences)); #to make sure the code still runs + score = 0; + for num_i in prices_per_seq: + score += prices_per_seq[num_i].get(sequence,0); + part2 = max(score,part2); + +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d23.py b/2024/aoc2024-d23.py new file mode 100644 index 0000000..ca87fb3 --- /dev/null +++ b/2024/aoc2024-d23.py @@ -0,0 +1,73 @@ +#advent of code 2024 +#day 23 +#this is rewritten to adapt for part 2. All possible sets of computers +#are searched for recursively (with FindNetwork function) +#and stored in subnetworks set. Then it iterates over all elements of +#subnetworks set. If the element has 3 computers, then it iterates over +#all computers in the set. If at least one computer starts with "t", +#it is counted towards part 1. We keep track of the longest set of +#computers and update part2 variable when it changes. +#The way FindNetwork works is that it takes a name of PC and a set of previously +#visited computers that are all iterconnected. Then the given PC is added +#to the set, the set is sorted (to avoid duplicates) and added to +#subnetworks set. It iterates over all computers connected to PC from argument +#according to Connections dictionary. If the computer is already in +#the cluster, it is skipped. Then, we nest another loop to check if the +#connections of the computer match the computers in the cluster. +#if not, it's skipped. if yes, it call the FindNetwork function again +#with the computer and updated cluster (NextCluster) as arguments. +#infinite loop is prevented while checking whether or not the computer +#is already in the cluster. Runtime is sped up due to discarding already +#visited clusters accoroding to subnetworks set. +#the password for part2 is just a string of computer names separated with commas +#similar to previous day +#I think the correct term is "ring" or "topology" but that's completely irrelevant +#for the puzzle + +Connections = {}; +f = open("23.in","r"); +for l in f: + PC1, PC2 = l.strip().split("-"); + if PC1 not in Connections: Connections[PC1] = set(); + if PC2 not in Connections: Connections[PC2] = set(); + Connections[PC1].add(PC2); + Connections[PC2].add(PC1); +f.close(); + +subnetworks = set(); + +def FindNetwork(PC,Cluster): + NextCluster = Cluster.copy(); + NextCluster.add(PC); + NextCluster = sorted(NextCluster); + if tuple(NextCluster) in subnetworks: return; + subnetworks.add(tuple(NextCluster)); + for NextPC in Connections[PC]: + ok = True; + if NextPC in Cluster: continue; + for OtherPCs in NextCluster: + if OtherPCs not in Connections[NextPC]: ok = False; + if not ok: continue; + FindNetwork(NextPC, set(NextCluster)); + + +for i,computer in enumerate(Connections): + print(i, "/", len(Connections)); + FindNetwork(computer,set()); + +part1 = 0; +part2 = None; +LargestNetworkSize = 0; +for subnet in subnetworks: + SubnetSize = len(subnet) + if SubnetSize == 3: + for computer in subnet: + if computer[0] == "t": + part1 += 1; + break; + LargestNetworkSize = max(LargestNetworkSize,SubnetSize); + if LargestNetworkSize == SubnetSize: part2 = subnet; + +part2 = ",".join(part2); +print("part 1 =",part1); +print("part 2 =",part2); diff --git a/2024/aoc2024-d24.py b/2024/aoc2024-d24.py new file mode 100644 index 0000000..49d2c6f --- /dev/null +++ b/2024/aoc2024-d24.py @@ -0,0 +1,82 @@ +#advent of code 2024 +#day 24 +#part 2 requires reading the input, then either solve by hand (like I did) +#or make some kind of detection of abnormailities (for example, +#z-wires should always by outputted by XOR gate, +#output of x XOR y should always go as input to another XOR connected to z-wire etc +#basically the whole program is just a lot of adder gates, +#adding all bits from x and y wires and outputting them into z-wires, +#mixed together with 8 errors. +#part 1 is kind of shitty so I won't bother explaining. +#I should probably implement some kind of verification of calculations +#that is: calculate the z in binary, calculate the x and y in binary +#and calculate the z as a sum of x and y + +import re +data_initial, data_gates = open("24.in","r").read().split("\n\n"); + +Wires = {}; +AllGates = {}; + +def calc(IN01,GATE,IN02,OUT): + CurrentValue = Wires.get(OUT,False); + if GATE == "AND": Wires[OUT] = Wires[IN01] & Wires[IN02]; + elif GATE == "OR": Wires[OUT] = Wires[IN01] | Wires[IN02]; + elif GATE == "XOR": Wires[OUT] = Wires[IN01] ^ Wires[IN02]; + +for line in data_gates.strip().split("\n"): + in1, gt, in2, out = re.findall(r'\w+',line.strip()); + AllGates[(in1, gt, in2, out)] = False; + +for line in data_initial.split("\n"): + wire, wireval = line.strip().split(": "); + Wires[wire] = bool(int(wireval)); + +go = True; #keep hgoing until all gates were used +while go: + go = False; + for Gate in AllGates: + if AllGates[Gate]: continue; #skip gates which already ran + go = True; + a1,a2,a3,a4 = Gate; + if Wires.get(a1,"notyet") != "notyet" and Wires.get(a3,"notyet") != "notyet": + calc(*Gate); + AllGates[Gate] = True; + +X_set = []; +Y_set = []; +Z_set = []; +for w in Wires: + if w[0] == "x": X_set.append((w,int(Wires[w]))); + if w[0] == "y": Y_set.append((w,int(Wires[w]))); + if w[0] == "z": Z_set.append((w,int(Wires[w]))); + +Xvals = reversed(sorted(X_set, key = lambda m: m[0])); +Yvals = reversed(sorted(Y_set, key = lambda m: m[0])); +Z_set = reversed(sorted(Z_set, key = lambda m: m[0])); +Xbinary, Ybinary, Zbinary = "","",""; +for zzz in Z_set: Zbinary += str(zzz[1]); +for yyy in Yvals: Ybinary += str(yyy[1]); +for xxx in Xvals: Xbinary += str(xxx[1]); +Zcorrect = int(Xbinary,2) + int(Ybinary,2); +Zcorrbin = str(bin(Zcorrect)); +print("diagnostics"); +print("binary X = ", Xbinary); +print("binary Y = ", Ybinary); +print(f'(addition) {"-"*len(Zcorrbin)}'); +print("binary Z =", Zcorrbin); +print(); +print("decimal X =", int(Xbinary,2)); +print("decimal Y =", int(Ybinary,2)); +print("decimal Z =", Zcorrect, "<- this should be the output for part 2"); +print("false Z =", Zbinary); + +part1 = int(Zbinary,2) +print(); +print("part 1 = ", part1); +#hardcoded for my input, I did it with pen and paper +FoundIncorrectWires = ["wbw","wgb","jct","z39","gwh","z09","rcb","z21"]; +FoundIncorrectWires = sorted(FoundIncorrectWires); +part2 = ",".join(FoundIncorrectWires); +print("part 2 = ", part2); + diff --git a/2024/aoc2024-d25.py b/2024/aoc2024-d25.py new file mode 100644 index 0000000..4f14ee6 --- /dev/null +++ b/2024/aoc2024-d25.py @@ -0,0 +1,55 @@ +#advent of code 2024 +#day 25 +#I'm not sure if my solution is general enough to work on modified inputs +#like bigboys but I guess it's good enough to work on original AOC one. +#parse schematics, decide if they are a key or a lock based on first row +#generate the heights of each pin +#compare each key with each lock column by column + +data = open("25.in","r").read().strip().split("\n\n"); + +def getDimensions(gridraw): + Category = None; + Schematics = {}; + xMax = 0; + yMax = 0; + for y, line in enumerate(gridraw.strip().split("\n")): + yMax = max(yMax,y); + if y == 0: + if line == "."*len(line): Category = "key"; + else: Category = "loc"; + for x, c in enumerate(line): + xMax = max(xMax,x); + Schematics[(y,x)] = c; + heights = []; + if Category == "key": + for x in range(xMax+1): + h = sum( Schematics[(y,x)]=="#" for y in range(1,yMax) ); + heights.append(h); + else: + for x in range(xMax+1): + h = sum( Schematics[(y,x)]=="#" for y in range(yMax-1,0,-1) ); + heights.append(h); + return Category, heights; + +Keyed = []; +Locked = []; +XMAX = 0; +YMAX = 0; +XMAX = len(data[0].split("\n")[0]) +YMAX = len(data[0].split("\n")) -2; +for d in data: + cat, dims = getDimensions(d); + if cat == "key": Keyed.append(dims); + if cat == "loc": Locked.append(dims); + +part1 = 0; +for Key in Keyed: + for Lock in Locked: + fit = True; + for col in range(XMAX): + if Key[col] + Lock[col] > YMAX: fit = False; + part1 += 1*fit; + +print("part 1 =", part1); + |