thecakeisalime's recent activity
-
Comment on Day 12: Christmas Tree Farm in ~comp.advent_of_code
-
Comment on Day 11: Reactor in ~comp.advent_of_code
thecakeisalime Link ParentIt was intentional. If there were paths from `dac -> fft` and also paths from `fft -> dac` then that would create a loop, and thus infinite paths. So the "in any order" from the problem statement...It was intentional.
If there were paths from `dac -> fft` and also paths from `fft -> dac` then that would create a loop, and thus infinite paths. So the "in any order" from the problem statement was a little misleading (potentially on purpose). Since it's acycllic, I "cheated" a little and just ran the code a couple times to see which of the two paths existed. You're correct in noting that there are valid inputs that would not work with my code, but I didn't bother generalizing for all cases. To generalize, I'd just have to check both, and ignore the one that had 0 paths.There could potentially be other loops that don't go through both fft and dac, but since my code spit out an answer instead of hanging forever, I (now) know that there are no loops. I did consider loop detection, but did not end up implementing it.
-
Comment on Day 11: Reactor in ~comp.advent_of_code
thecakeisalime LinkMuch easier today. Of course, that didn't stop me from making the same mistakes as yesterday. Copied my BFS code (that was several orders of magnitude too inefficient for yesterday's problem) from...Much easier today. Of course, that didn't stop me from making the same mistakes as yesterday.
Copied my BFS code (that was several orders of magnitude too inefficient for yesterday's problem) from yesterday to solve part 1. Why didn't I reuse the DFS (that also was too inefficient for yesterday's problem)? Because the BFS code was prettier.
Get to Part 2 and realized I should have just started with DFS. Oh well. Easy enough to just rewrite a DFS. Luckily, DFS is actually the right tool for this job, and this worked as expected. My original plan was to use a "visited" check for visiting the fft and dac nodes, but that turned out to make caching much more complicated than I wanted.
Part 1&2 [Python]
def parse_input(lines: list[str]) -> dict[str, list[str]]: deviceIO = {} for line in lines: input, output = map(str.strip, line.split(':')) deviceIO[input] = output.split() return deviceIO def count_paths(deviceIO: dict[str, list[str]], node: str, end: str, memo: set[str]) -> int: if node in memo: return memo[node] paths = 0 for n in deviceIO[node]: if n == end: return 1 paths += count_paths(deviceIO, n, end, memo) memo[node] = paths return paths def part_one(deviceIO: dict[str, list[str]]) -> int: return count_paths(deviceIO, 'you', 'out', {}) def part_two(deviceIO: dict[str, list[str]]) -> int: deviceIO['out'] = [] return ( count_paths(deviceIO, 'svr', 'fft', {}) * count_paths(deviceIO, 'fft', 'dac', {}) * count_paths(deviceIO, 'dac', 'out', {}) ) def main() -> None: with open('11.in') as file: lines = [line.rstrip() for line in file] input = parse_input(lines) print('Part 1:', part_one(input)) print('Part 2:', part_two(input)) if __name__ == '__main__': main() -
Comment on Day 10: Factory in ~comp.advent_of_code
thecakeisalime Link ParentYes, that seems likely. A few days ago I crashed my computer by using too much memory in one of these puzzles, and this time it's been running for 2+ hours and my computer is still working, so I...Yes, that seems likely. A few days ago I crashed my computer by using too much memory in one of these puzzles, and this time it's been running for 2+ hours and my computer is still working, so I think I must have not done everything incorrectly, but this definitely feels more like "age of the universe" runtime and less "I can just let it run overnight".
It has been a very long time since I've worked with problems like this (does it show?). Seems like I need to study math and try again after work.
-
Comment on Day 10: Factory in ~comp.advent_of_code
thecakeisalime (edited )LinkAs I'm typing this, my code is still running. Probably not a great sign, but if it works it works! (It's yet to be seen if it works). Similar massive escalation in difficulty between Part 1 and...As I'm typing this, my code is still running. Probably not a great sign, but if it works it works! (It's yet to be seen if it works).
Similar massive escalation in difficulty between Part 1 and Part 2 today as to yesterday. Unlike yesterday, I did know how to solve Part 2, I just didn't know how to do it efficiently (and as we pass the 5 minute mark, it's clear that I never figured that out). I started with a basic recursive depth-first search, because I like to be extra inefficient and couldn't remember how to do a BFS off the top of my head. It "worked" for the sample data, but it was clear that it would probably take several days of processing to get the answer with the real data. Then I remembered that caching/memoization was a thing. That sped it up considerably, but also got the wrong answer sometimes, because DFS was the wrong tool for this.
So then I looked up how to implement a BFS, I cached results again, and now at the 10 minute mark, my code is still executing. At least the sample data processed quickly. With 177 independent inputs, I guess this is what parallelization is for.
I'm posting this at the 30 minute mark in case my computer crashes. I wish I'd added some logging statements so that I knew it was progressing. I'll update with the code if it turns out it actually worked.
EDIT: Killed the process after ~2.5 hours. Peeked at some AoC threads, and saw that this is something called Integer Linear Programming. I don't think I covered that in university, but if I did, I've forgotten all about it. But luckily, I can use google and found a tool called PuLP that I managed to figure out well enough to use. Not sure this really counts as "my" solution at this point, but it's at least a solution, and it runs in a couple seconds. Might actually be in milliseconds, but the console output is pretty slow.
Part 1 & 2 [Python]
import itertools import pulp BIG_NUMBER = 10000 def parse_input(lines: list[str]) -> tuple[list[str], list[list[list[int]]], list[list[int]]]: lights = [] buttons = [] joltages = [] for line in lines: light, *button, joltage = line.split() lights.append([c == '#' for c in light.strip('[]')]) buttons.append([list(map(int, b.strip('()').split(','))) for b in button]) joltages.append(list(map(int, joltage.strip('{}').split(',')))) return lights, buttons, joltages def toggle_lights(target: list[bool], button_combos: tuple[list[int]]): lights = [False]*len(target) for bc in button_combos: for b in bc: lights[b] ^= True if target == lights: return len(button_combos) return BIG_NUMBER def increase_joltage_ilp(target: list[int], button_list: list[list[int]]) -> int: matrix = [[0]*len(button_list) for _ in range(len(target))] for j, buttons in enumerate(button_list): for i in buttons: matrix[i][j] = 1 problem = pulp.LpProblem("Minimum Button Presses", pulp.LpMinimize) vars = [pulp.LpVariable(f'x_{i}', lowBound=0, cat='Integer') for i in range(len(button_list))] problem += pulp.lpSum(vars) for i in range(len(target)): problem += pulp.lpSum(matrix[i][j] * vars[j] for j in range(len(button_list))) == target[i] problem.solve() return int(sum(v.value() for v in vars)) def part_one(input: tuple[list[str], list[list[list[int]]], list[list[int]]]) -> int: target_lights, buttons, _ = input presses = 0 for target, button_list in zip(target_lights, buttons): button_combos = [] for r in range(0, len(button_list)): button_combos.extend(itertools.combinations(button_list, r+1)) presses += min(toggle_lights(target, bc) for bc in button_combos) return presses def part_two(input: tuple[list[str], list[list[list[int]]], list[list[int]]]) -> int: _, buttons, joltages = input presses = 0 for i, (button_list, target) in enumerate(zip(buttons, joltages)): print(i, target) #presses += increase_joltage_dfs(target, [0]*len(target), button_list, 0, {}) #presses += increase_joltage_bfs(target, button_list) presses += increase_joltage_ilp(target, button_list) return presses def main() -> None: with open('10.in') as file: lines = [line.rstrip() for line in file] input = parse_input(lines) print('Part 1:', part_one(input)) print('Part 2:', part_two(input)) if __name__ == '__main__': main() -
Comment on Day 9: Movie Theater in ~comp.advent_of_code
thecakeisalime Link ParentI've never done graphical stuff before, so this is pretty basic, but I've plotted the whole floor and all of the valid rectangles. It's pretty crowded, since there's so many rectangles, so you...I've never done graphical stuff before, so this is pretty basic, but I've plotted the whole floor and all of the valid rectangles. It's pretty crowded, since there's so many rectangles, so you can't tell which is the largest, but the shape of the floor is kinda spoilery information (if you've made it this far into the comments and are still trying to avoid spoilers).
-
Comment on Day 9: Movie Theater in ~comp.advent_of_code
thecakeisalime LinkPart 1: less than 5 minutes. Part 2: several hours of frustrating coding, just to finally import a library that does all the hard parts. I saw someone mention Shapely in a Reddit post, and figured...Part 1: less than 5 minutes. Part 2: several hours of frustrating coding, just to finally import a library that does all the hard parts. I saw someone mention Shapely in a Reddit post, and figured that I'd learn a lot more by playing around with a new library than just brute forcing a solution poorly.
Tomorrow's goal is to discover the best python library for the job without first reading AoC threads on Tildes or Reddit. If Part 2 was any indication, I think it's well past the point where I can solve the upcoming challenges with barebones Python.
Part 1 and 2 [Python]
from shapely.geometry import Polygon, box def parse_input(lines: list[str]) -> list[tuple[int,int]]: return [tuple(map(int, l.split(','))) for l in lines] def area(tile1: tuple[int, int], tile2: tuple[int, int]) -> int: x1,y1 = tile1 x2,y2 = tile2 return (abs(x1-x2)+1)*(abs(y1-y2)+1) def green_area(greenTiles, tile1: tuple[int, int], tile2: tuple[int, int]) -> int: x1,y1 = tile1 x2,y2 = tile2 if greenTiles.contains(box( min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2) )): return area(tile1, tile2) return 0 def part_one(tiles: list[tuple[int,int]]) -> int: return max(area(a, b) for i, a in enumerate(tiles) for b in tiles[i+1:]) def part_two(tiles: list[tuple[int,int]]) -> int: greenTiles = Polygon(tiles) return max(green_area(greenTiles, a, b) for i, a in enumerate(tiles) for b in tiles[i+1:]) def main() -> None: with open('09.in') as file: lines = [line.rstrip() for line in file] input = parse_input(lines) print('Part 1:', part_one(input)) print('Part 2:', part_two(input)) if __name__ == '__main__': main() -
Comment on Day 8: Playground in ~comp.advent_of_code
thecakeisalime LinkDefinitely more to think about today, and got to learn all about sets in python. I've also started hinting most of the types in function definitions because it feels like a good practice, and...Definitely more to think about today, and got to learn all about sets in python. I've also started
declaringhinting most of the types in function definitions because it feels like a good practice, and because I kept getting confused while implementing this. Looking at it now, almost everything is the same type, so it's pretty extraneous now, but it took a while for me to settle on (lists of) sets.Fun fact... Today I figured out that I've been globally scoping my file inputs and a handful of other variables this whole time. Mostly through luck it hasn't been an issue yet, but I'll try to not do that in the future. It could have easily been a disaster in today's puzzle.
Part 1 and 2 [Python]
import math def get_distance(x1:int, y1:int, z1:int, x2:int, y2:int, z2:int) -> int: return math.sqrt((x2-x1)**2 + (y2-y1)**2 + (z2-z1)**2) def get_ordered_connections(lines):# -> dict_keys: positions = [tuple(map(int, l.split(','))) for l in lines] distances = {} for i, p1 in enumerate(positions): for j, p2 in enumerate(positions[i+1:]): distances[(i,j+i+1)] = get_distance(*p1, *p2) return dict(sorted(distances.items(), key=lambda x: x[1])).keys() def find_circuits(circuits: list[set], connections:list[set]) -> list[set]: for conn in connections: add_connection(circuits, conn) while connections != circuits: return find_circuits([], circuits) return circuits def add_connection(circuits:list[set], connection:set) -> list[set]: set = next((c for c in circuits if not connection.isdisjoint(c)), None) if set: set.update(connection) else: circuits.append(connection) return circuits def part_one(connections) -> int: # 10 for test data, 1000 otherwise sets = [set(key) for key in list(connections)[:10]] circuits = find_circuits([], sets) circuits.sort(key=len, reverse=True) return math.prod([len(c) for c in circuits[:3]]) def part_two(connections, lines) -> int: sets = [set(key) for key in list(connections)] circuits = [] for s in sets: find_circuits(circuits, [s]) if len(circuits[0]) == len(lines): return int(lines[s.pop()].split(',')[0]) * int(lines[s.pop()].split(',')[0]) return 0 with open('08.in') as file: lines = [line.rstrip() for line in file] connections = get_ordered_connections(lines) print('Part 1:', part_one(connections)) print('Part 2:', part_two(connections, lines)) -
Comment on Day 6: Trash Compactor in ~comp.advent_of_code
thecakeisalime Link ParentThanks! In Part 1 I found that numpy.rot90() output a int32 numpy array, and I couldn't figure out how to set the dtype on it (still don't know how), so I didn't even think about that when working...Thanks! In Part 1 I found that
numpy.rot90()output a int32 numpy array, and I couldn't figure out how to set the dtype on it (still don't know how), so I didn't even think about that when working on Part 2. It looks like passing the proper dtype tonumpy.prod()makes it all work properly and I can get rid of a few casts.That rotation is pretty neat. I probably wouldn't have figured that out on my own, but I'm still trying to figure out all the tricks python (and some of its common libraries) have to offer. I see that someone else used
itertools.zip_longestwhich seems to do something similar, but doesn't truncate if the inputs are different lengths. -
Comment on Bagels and shrinkflation in ~food
thecakeisalime Link ParentFor more fun facts about bagels, there's a podcast that I listen to called Gastropod and they did an episode on the history of the bagel: https://gastropod.com/the-bagelization-of-america/For more fun facts about bagels, there's a podcast that I listen to called Gastropod and they did an episode on the history of the bagel: https://gastropod.com/the-bagelization-of-america/
-
Comment on Day 6: Trash Compactor in ~comp.advent_of_code
thecakeisalime LinkToday was a weird one. Numpy does not like how big these numbers get (leading to overflows), so there's a lot of ugly typecasting. If there's any numpy experts around here, I'd love to know how I...Today was a weird one. Numpy does not like how big these numbers get (leading to overflows), so there's a lot of ugly typecasting. If there's any numpy experts around here, I'd love to know how I could improve this (other than just writing the rotation function myself, which I considered but decided against).
Parts 1 and 2 (Python)
import numpy import math def operate(params, operation): match operation: case '*': # numpy.prod() overflows return math.prod(params) case '+': return sum(params) def part_one(lines): inputs = [[numpy.uint64(num) for num in l.split()] for l in lines[:-1]] operations = lines[-1].split() problems = numpy.rot90(inputs, k=3) return int(sum(operate(p, o) for p, o in zip(problems, operations))) def part_two(lines): inputs = [list(l) for l in lines[:-1]] grid = numpy.rot90(inputs, k=1) numbers = [''.join(num).strip() for num in grid] problem = [] problems = [] for n in numbers: if (n == ''): problems.append(problem) problem = [] else: problem.append(int(n)) problems.append(problem) operations = lines[-1].split()[::-1] return int(sum(operate(p, o) for p, o in zip(problems, operations))) with open('06.in') as file: lines = [line.rstrip('\n') for line in file] print('Part 1:', part_one(lines)) print('Part 2:', part_two(lines)) -
Comment on Day 5: Cafeteria in ~comp.advent_of_code
thecakeisalime (edited )LinkI foolishly didn't look at the input until I'd written a solution to Part 1, then when I saw how large the numbers were, I figured "eh, I'll run it and see what happens". Apparently, using up all...I foolishly didn't look at the input until I'd written a solution to Part 1, then when I saw how large the numbers were, I figured "eh, I'll run it and see what happens". Apparently, using up all my memory and crashing my computer is what happens.
And Part 2 had so many off-by-one errors. This is the first time I've had to submit an answer more than twice, and one of my submissions was only 16 away from the correct answer.
Part 1&2 - Python
def parse_input(lines): idx = lines.index('') fresh = lines[:idx] available = lines[idx+1:] return fresh, available def part_one(lines): fresh, available = parse_input(lines) count = 0 for a in available: n = int(a) for f in fresh: values = f.split('-') if int(values[0]) <= n <= int(values[1])+1: count += 1 break return count def part_two(lines): fresh = parse_input(lines)[0] pairs = [list(map(int, f.split('-'))) for f in fresh] pairs.sort() count = 0 for p1, p2 in zip(pairs[:-1], pairs[1:]): if p1[1] >= p2[1]: p2[0] = -1 p2[1] = p1[1] elif p1[1] >= p2[0]: p2[0] = p1[1]+1 if (p1[0] != -1): count += p1[1] - p1[0] + 1 if (-1 != pairs[-1][0] and pairs[-1][0] <= pairs[-1][1]): count += pairs[-1][1] - pairs[-1][0] + 1 return count with open('05.in') as file: lines = [line.rstrip() for line in file] print('Part 1:', part_one(lines)) print('Part 2:', part_two(lines)) -
Comment on Day 3: Lobby in ~comp.advent_of_code
thecakeisalime (edited )LinkNot too bad today. Happier with my solution than I have been for the previous days. I did have one weird thing that I couldn't make work, and maybe someone more familiar with Python can tell me if...Not too bad today. Happier with my solution than I have been for the previous days.
I did have one weird thing that I couldn't make work, and maybe someone more familiar with Python can tell me if it's possible. I'm moving a "pointer" demarking the end of a slice. I had originally tried iterating it from -11 through to 0, but a slice of a python
list[:-1]is very different thanlist[:0]. Is there a good way to do this? I ended up just iterating overlist[:len(list) - (11-n)], which works fine, but seems rather inelegant.Part 1 & 2 (Python)
def part_one(lines): total = 0 for line in lines: firstDigit = secondDigit = 0 digits = [int(num) for num in line] firstDigit = max(digits[:-1]) index = digits.index(firstDigit) secondDigit = max(digits[index+1:]) total += 10*firstDigit + secondDigit return total def part_two(lines): total = 0 for line in lines: digits = [int(num) for num in line] index = 0 for n in range(12): joltage = max(digits[index:len(digits)-(11-n)]) index += digits[index:].index(joltage) + 1 total += joltage * 10**(11-n) return total with open('20250103.in') as file: lines = [line.rstrip() for line in file] print("Part 1:", part_one(lines)) print("Part 2:", part_two(lines)) -
Comment on Day 2: Gift Shop in ~comp.advent_of_code
thecakeisalime Link ParentI had a very similar solution to you, also in python. Seems like the big difference is that you're iterating from smaller to larger chunk sizes, and I'm iterating from halving through to 1/n-ing....I had a very similar solution to you, also in python. Seems like the big difference is that you're iterating from smaller to larger chunk sizes, and I'm iterating from halving through to 1/n-ing. I think they're roughly equivalent in efficiency, but yours seems more intuitive. My only advantage is that it avoids the single digit issue you ran into.
I'm not super happy with this algorithm, but it seems like everyone has done pretty much the same thing, so at least I'm not alone.
Part 1
with open("20250102.in", "r") as file: ids = file.readline().split(',') total = 0 for id in ids: ranges = id.split('-') start = int(ranges[0]) end = int(ranges[1]) for i in range(start, end + 1): s = str(i) if len(s) % 2 != 0: continue firstHalf = s[:len(s)//2] secondHalf = s[len(s)//2:] if firstHalf == secondHalf: total += i print(total)Part 2
with open("20250102.in", "r") as file: ids = file.readline().split(',') total = 0 invalidIds = [] def hasPattern(s, chunkSize, numChunks): return s.count(s[:chunkSize]) == numChunks for id in ids: ranges = id.split('-') start = int(ranges[0]) end = int(ranges[1]) for i in range(start, end + 1): s = str(i) for n in range(2, len(s)+1): if len(s) % n == 0: if hasPattern(s, int(len(s)/n), n): total += i invalidIds.append(i) break print(total) #print(invalidIds) -
Comment on Day 1: Secret Entrance in ~comp.advent_of_code
thecakeisalime LinkI originally solved part 2 with brute force, because I kept getting hung up on corner cases. But I eventually figured it out. Looking at my solution, the cases aren't that bad overall, but it was...I originally solved part 2 with brute force, because I kept getting hung up on corner cases. But I eventually figured it out. Looking at my solution, the cases aren't that bad overall, but it was hard to make sure the cases were mutually exclusive. I was missing the second
elifcase for the longest time.Also, I'm new to python, so if there's anything I'm doing that looks weird or unnecessary or could be done better, please feel free to let me know.
Part 1
file = open("20250101.in", "r") dial = 50 count = 0 for line in file: if line[0] == 'L': dial -= int(line[1:]) else: dial += int(line[1:]) dial %= 100 if dial == 0: count += 1 file.close() print(count)Part 2
file = open("20250101.in", "r") dial = 50 count = 0 for line in file: rot = int(line[1:]) previousDial = dial if line[0] == 'L': dial -= rot else: dial += rot dial %= 100 count += rot // 100 if dial == 0 and previousDial == 0: count += 0 elif dial == 0: count += 1 elif previousDial == 0: count += 0 elif line[0] == 'L' and previousDial - (rot % 100) < 0: count += 1 elif line[0] == 'R' and previousDial + (rot % 100) > 100: count += 1 file.close() print(count) -
Comment on Advent of Code starts tomorrow/tonight! Are you participating? Do you have any specific plans for this year? in ~comp.advent_of_code
thecakeisalime LinkI did it in 2023 and it was fun, though it looks like I didn't finish it. 12 days should make it less of a commitment, though I suspect I didn't finish it because I couldn't solve a problem,...I did it in 2023 and it was fun, though it looks like I didn't finish it.
12 days should make it less of a commitment, though I suspect I didn't finish it because I couldn't solve a problem, rather than time.
Looking forward to trying to finish it this year. My goal is to finish all 12 problems, and do it in python, which seems to be a handy scripting language that I've never bothered to learn (though it doesn't seem too different from what I do already know).
This first problem is already giving me issues, so that's not a good start.
-
Comment on Is there a lookup tool for credit card leaks? in ~tech
thecakeisalime Link ParentI like the idea behind privacy.com, but unfortunately they don't support non-US customers. Seemingly, there are no banks in Canada that support temporary credit cards. I have multiple credit...I like the idea behind privacy.com, but unfortunately they don't support non-US customers. Seemingly, there are no banks in Canada that support temporary credit cards.
I have multiple credit cards, so losing one temporarily wasn't a big setback, I just want to be able to avoid this as much as possible in the future. Looks like Google Pay doesn't transmit card information to websites, so that might shield me somewhat.
-
Comment on Is there a lookup tool for credit card leaks? in ~tech
thecakeisalime Link ParentThanks, I should probably look more into the technicals of Google Pay. I used to use PayPal for this sort of thing online, but stopped using them after they made me jump through a lot of hoops for...Thanks, I should probably look more into the technicals of Google Pay. I used to use PayPal for this sort of thing online, but stopped using them after they made me jump through a lot of hoops for what should have been a very simple refund.
-
Comment on Is there a lookup tool for credit card leaks? in ~tech
thecakeisalime Link ParentYeah, there are a lot of good reasons to not have such a service, so I understand hibp's reluctance to do so, but I am surprised that no one less legitimate has been willing to provide this....Yeah, there are a lot of good reasons to not have such a service, so I understand hibp's reluctance to do so, but I am surprised that no one less legitimate has been willing to provide this.
Unfortunately, unlike passwords that can be different for each service to limit my exposure, I have to use the same credit card number everywhere, which means there's a non zero chance that whoever leaked my card number in the first place will get my new number and do it again.
-
Is there a lookup tool for credit card leaks?
A few months ago, my credit card number was used in a few unauthorized transactions. The charges were reversed, and I got a new card, so overall, no big deal. But I am curious as to how the thief...
A few months ago, my credit card number was used in a few unauthorized transactions. The charges were reversed, and I got a new card, so overall, no big deal. But I am curious as to how the thief actually got their hands on my information.
Are there any lookup tools for leaked credit cards, similar to Have I Been Pwned, that might tell me how my credit card number was exposed? Since my card has already been cancelled, I don't even mind typing the number into a somewhat sketchy site.
14 votes
"Solving" the knapsack packing problem was a huge escalation from previous days, even if today is the last day, and was dreading trying to implement that. So instead, I decided I'd start by calculating the upper and lower bounds of what the possible answers could be, since by now I've figured out that there's often a trick with the input that you can use to optimize these solutions. I was pleasantly surprised when I found they were equal. Of course, in what has become a daily occurrence for me, I still had the wrong answer; this time it was because I reversed the inequality signs. Once I fixed that though, I had the correct solution.
Solution [Python]