Відео

Stuck on that task in 2021. Did several other attempts in next years, last time was yesterday/today, already after I've finished AoC 2024, and still nothing. It might be that I got stuck with the idea of doing bfs over all positions/scores, or perhaps that's just a skill issue :) Anyway, finally I surrendered and watched this video. Really elegant solution, definitely I need to practice with dynamic programming problems. Thanks, Jonathan!

bro do something about that cough, you have been coughing since day 16 or so... anyway great video as always

Thanks for all the interesting videos. Congrats on making the top 100!

The problem was disappointingly easy - pairwise zip all items and check for presence of (#,#), that is it. No need to preclasify things into locks / keys.

Thanks for the videos and happy holidays!

congrats, and big thanks for all your videos! see you next year ;-) having precomputed set of pin coordinates for multiple reuse and let intersection (&) do the heavy lifting ;-) def solve1(text): blocks = text.split(" ") block_rows = blocks[0].splitlines() R = len(block_rows) C = len(block_rows[0]) locks = [] keys = [] for block in blocks: block_lines = block.splitlines() pins = set((r, c) for r in range(R) for c in range(C) if block_lines[r][c] == "#") if all(x == "#" for x in block_lines[0]): locks.append(pins) elif all(x == "#" for x in block_lines[-1]): keys.append(pins) else: assert False return len([1 for lock in locks for key in keys if len(lock & key) == 0])

It's a Ripple Carry Adder. That's the official term.

gotta just love the manually scanning the tree for things that don't look right, after over an hour trying to figure it out. Hardest part 2 so far. I did part one, and upon reading part 2, not a chance

Anyone can share the flag ?

what is the flag in advent of cyber 2024 day 24

Hi, Can you make a video on how to set up vim like in your computer in windows?

I've been trying to do this in base 10, turns out it takes a while I guess it all the extra iterations it ends up going through. Thanks for this JP I'm an old hand developer but new to puzzles and I'm pretty sure I'd never of got this one.

With networkx the two parts in total were 6 lines

def solve1(text): E = defaultdict(set) for line in text.splitlines(): a, b = line.strip().split("-") E[a].add(b) E[b].add(a) res = 0 for a in E.keys(): for b in E[a]: for c in E[b]: if a < b < c and c in E[a] and any([x.startswith("t") for x in [a,b,c]]): res += 1 return res

not sure if the best, but I have something like this: def solve2(text): E = defaultdict(set) P = [] for line in text.splitlines(): a, b = line.strip().split("-") E[a].add(b) E[b].add(a) P.append({a, b}) groups = P seen = set() while True: new_groups = [] for set_members in groups: possible_candidates = set.intersection(*(E[x] for x in set_members)) for candidate in possible_candidates: new_grp = set_members | {candidate} key = tuple(sorted(new_grp)) if key not in seen: seen.add(key) new_groups.append(new_grp) if not new_groups: break groups = new_groups assert len(groups) == 1 res = ",".join(sorted(groups[0])) return res

For part 2, I used a floodfill, where I checked if the new vertex is connected to every other vertex in the current component. I am not sure I fully understand why your approach works as well as it does

For part 2, I did a recursive search with parameters `curr_node` and `visited` set. Iterate over all adjacent vertices `next_node` such that `next_node > curr_node` and `visited.issubset(adj[next_node])`. This prunes it well enough to run fast, but I'm sure there are inputs where it doesn't.

I just created a "dict" for sequences and their score per "linenumber". In Go. map[Sequence]map[int]int. Where sequence is just last 4 diffs and add it to map if only there is no present record for the "linenumber" aka first occurance of sequence for initial number. Then just iterate all sequences to find the maximum one for all the line numbers. ~2s in Go

can you please explain what DP is doing here a bit more? I see it's essential to the speed but I'm not 100% on what is it doing

This problem took me over a day, and you know its a doozy if even Jon took almost three hours to do it.

I was 100% sure today that part 2 will be about ridiculously huge binary numbers, since all the calculations are bitwise operations. Especially after I made some mistakes in my first implementation of calculcations, and saw some really big numbers. So I spent about an hour and a half implementing my own bit number operations class and had a lot of fun, and it did work! But of course that was really slow, so for part 2 I had to fallback to regular bitwise operations after that anyway :)

Well im 5 days behind, was just checking your times, and seeing 3h scares me a lot

I think I'm doing AoC wrong (first year I'm doing it), because I got a ranking PB solving part 1 by hand today. Definitely not the way, but still "fun". Thanks for sharing how it's meant to be done (at least part1!)

I'm thrilled to see my solution and yours are pretty identical...except you implemented it about 10x faster!

Okay, I am fucking scared after seeing the length of the video.

i have 4x multiplier of Jonathan, so for me it should be 12h? :D not watched, just commenting...

13 minutes for p1. 2.5 hours for P2. wow

No need for dijkstra, it's far easier to do a DFS (bcs of constant need to press A you can segment out each button1 -> button2 sequence on each depth), and cache all of the results

This guy had his best part 1 performance and the worst part 2 performance on the same day. Anyways, congrats for the 2nd place, i myself got 50s for part 2 too !

Agreed, I think the explanation of a "cheat" could've been better

For part 2, I looped through each position in the path once. At each point, loop through every other point on the path (all cheats must end on the path). If the Manhattan distance is <= 20 for that point and dist_along_path(p2) - dist_along_path(p1) - manhat_dist <= 100, the point is valid. Python3 on my machine takes ~8s, don't know if there's a way to get around needing the second loop to lower the time complexity

almost 3 hours omg ,, congrats for the 2 place

after long long painful solving, trying more approaches, then refactored leveraging statement that there is just 1 "linear" path through, no standard BFS nor DP is needed ;-) and runs ~0.5 sec path is enough and search space is path position combinations - point vs further points within cheat manhatthan dist def solve(text, threshold, cheat_len): G = [[x for x in line.strip()] for line in text.split(" ")] R = len(G) C = len(G[0]) sr, sc = None, None er, ec = None, None for r in range(R): for c in range(C): if G[r][c] == "S": sr, sc = r, c G[r][c] = "." elif G[r][c] == "E": er, ec = r, c G[r][c] = "." seen = set() path = [] r, c, d = sr, sc, 0 while (r, c) != (er, ec): path.append((r, c)) seen.add((r, c)) d += 1 for rr, cc in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]: if 0 <= rr < R and 0 <= cc < C and G[rr][cc] == "." and (rr, cc) not in seen: r, c = rr, cc path.append((er, ec)) res = 0 for i in range(0, len(path) - 1): for j in range(i + 1, len(path)): r1, c1 = path[i] r2, c2 = path[j] cheat_diff = abs(r1 - r2) + abs(c1 - c2) if cheat_diff <= cheat_len: norm_diff = j - i if norm_diff - cheat_diff >= threshold: res += 1 return res

12:52 I felt that

bruteforcing p1 with astar and go, finished in dozen seconds, gave up for part 2 :D and bruteforcing cheats

I also found the instructions rather confusing and unclear and have seen other people get confused as well. When reading the problem very carefully, I think everything is explained but it's very light on the details and there are a fair few rather ambiguous statements with no examples that clear them up.

there's only 1 route from S to E, so I dijkstra for a cost map first, and for every next point(deterministic) since and including S, - find cheat points [p1, p2, ...] and steps to these points: exactly 2 steps away for p1, 1-20 steps for p2 - for every point p, (S, p) is a new unique pair, pairs are only valid cheat when it's closer to current point than the normal route, that is: (saving = cost-p - cust-r - step) > 0 - insert this pair into global map of {saved-steps: pairs} it's still slow but not that slow.. implementation is somehow tedius

suppose you have calculated dp[i][j] where it's a min distance from S to (i, j) then if we cheat form (i,j) to (ni, nj), we can simply recalculate it with formula dist = cost - dp[ni][nj)] + dp[i][j] + abs(i - ni) + abs(j - NJ) where cost = d[End_i][End_j] Hence only one bfs is needed

Perfect

Thank you for all your effort.

DP is just magic

❤

After day 11, this day was also memoization. Instead of manually having the ""DP" set, you can just put an @cache decorator before the function (from functools).

I solved part 1 with a depth-first-search. But handling the different combinations for part2 is kind of hard this way. Do you think it would be possible (in a reasonable amount of time) with a depth-first-search?

My solution to part 1 was to remove any words that were themselves composite words which sped things up enough to run an exhaustive search which would break after finding a solution, but it was still slow (around 13s) but that also meant part 2 wasn't possible, so I had to do something else and came up with basically the same solution as you.

Re memoization being that fast even for an answer in the hundreds of trillions - my cache info had 23390 hits and a final size of 12634. The number of combinations of letters here just isn't that large, I think edit: ah, you go over this at the end

Nice solution! Get well soon Jonathan. I really enjoy watching your AoC Videos after solving myself to see how dumb my solutions are. :D Keep up the good work!

Thank you for the videos and commentary. I watched them all last year and was looking forward to them again this year. Even though I've switched to C++, seeing your Python solutions is still fun.

also hit the 70+1 error...

I did astar. For p2 I reversed it (started with all corrupt bytes in) and went until it did find a path, but idk if that was maybe only good for my data (my answer was on line 3000 out of 3400 something)