Only Bayes Can Judge Me
- 33 Posts
- 1.24K Comments
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code 2024 - the home stretch - it's been an aMAZEing yearEnglish2·6 months agoI did part 2 manually! I will not bother writing a code solution unless I feel like it.
well well well
AoC, so you thought you could dredge up my trauma as an EE grad by making me debug a full-adder logic circuit? How dare you. You succeeded.
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code 2024 - the home stretch - it's been an aMAZEing yearEnglish3·6 months agothanks
I’ve probably learned that term at some point, so thanks for naming it. That made me realise my algorithm was too thicc and could just be greedy.
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code 2024 - the home stretch - it's been an aMAZEing yearEnglish2·6 months ago22
uh
pretty straightforward. At least it’s not a grid!
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code 2024 - the home stretch - it's been an aMAZEing yearEnglish2·6 months ago21!
Finally managed to beat this one into submission.
P1
I created this disgusting mess of a recursive search that happened to work. This problem was really hard to think about due to the levels of indirection. It was also hard because of a bug I introduced into my code that would have been easy to debug with more print statements, but hubris.
P2
Recursive solution from P1 was too slow, once I was at 7 robots it was taking minutes to run the code. It didn’t take long to realise that you don’t really care about where the robots other than the keypad robot and the one controlling the keypad robot are since the boundary of each state needs all the previous robots to be on the A button. So with memoisation, you can calculate all the shortest paths for a given robot to each of the directional inputs in constant time, so O(kn) all up where n is the number of robots (25) and k is the complexity of searching for a path over 5 or 11 nodes.
What helped was looking at the penultimate robot’s button choices when moving the keypad robot. After the first one or two levels, the transitions settle into the table in the appendix. I will not explain the code.
appendix
(P(0, 1), P(0, 1)): [], (P(0, 1), P(0, 2)): [btn.r], (P(0, 1), P(1, 0)): [btn.d, btn.l], (P(0, 1), P(1, 1)): [btn.d], (P(0, 1), P(1, 2)): [btn.d, btn.r], (P(0, 2), P(0, 1)): [btn.l], (P(0, 2), P(0, 2)): [], (P(0, 2), P(1, 0)): [btn.d, btn.l, btn.l], (P(0, 2), P(1, 1)): [btn.l, btn.d], (P(0, 2), P(1, 2)): [btn.d], (P(1, 0), P(0, 1)): [btn.r, btn.u], (P(1, 0), P(0, 2)): [btn.r, btn.r, btn.u], (P(1, 0), P(1, 0)): [], (P(1, 0), P(1, 1)): [btn.r], (P(1, 0), P(1, 2)): [btn.r, btn.r], (P(1, 1), P(0, 1)): [btn.u], (P(1, 1), P(0, 2)): [btn.u, btn.r], (P(1, 1), P(1, 0)): [btn.l], (P(1, 1), P(1, 1)): [], (P(1, 1), P(1, 2)): [btn.r], (P(1, 2), P(0, 1)): [btn.l, btn.u], (P(1, 2), P(0, 2)): [btn.u], (P(1, 2), P(1, 0)): [btn.l, btn.l], (P(1, 2), P(1, 1)): [btn.l], (P(1, 2), P(1, 2)): [],
swlabr@awful.systemsto Buttcoin@awful.systems•Man [Craig Wright] who claims he invented bitcoin faces prison after filing $1.1 trillion suitEnglish4·7 months ago1.1 trillion? Good luck, chuck.
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alikeEnglish3·7 months ago21 (wip)
2 meme 2 memeious
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alikeEnglish4·7 months agoUnderstandable, have a nice day
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alikeEnglish3·7 months agook disco
It took me too long to read the prompt and see that without the shortcuts, it’s a single path. I wasted too much time on search algorithms.
P1: Here’s what I did: Walk the path. Every time you hit a new grid, check if the two shortcuts you can take will save you 100 ps.
To calculate the shortcut saving:
If you index every grid position on the main path from 0, then it takes X ps to reach position X, The time it takes to travel from start to X, then a shortcut to Y, then from Y to the end, is X + 1 + (main path length - Y). The time saved is then just Y - X - 1, modulo maybe like 5 fence post errors.
P2. The prompt wasn’t really clear about whether or not cheating meant you can only travel through one set of walls before your cheat ends, or if it meant you could just move through walls for 20ps to wherever you could reach. Turns out, it’s the latter.
The above formula is then a special case of Y - X - manhattan distance(X, Y).
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alikeEnglish3·7 months ago20: currently a WIP but:
meme
Wait, so it’s all grids? 🧑🏿🚀🔫🧑🏿🚀
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alikeEnglish3·7 months agoDay 19! (the cuervo gold…)
disc and code
Ok so my path to this answer was circuitous and I now hate myself a little.
P1: Ok, a repeated dfs on suffixes. that shouldn’t be too hard. (it was not hard)
P2: Ok, a repeated dfs is a little too slow for me, I wonder how I can speed it up?
forgets about memoisation, a thing that you can do to speed this sort of thing up
I guess the problem is I’m doing an O(mn) match (where m is the number of towels, n is the max towel length) when I can do O(n). I’ll build a prefix tree!
one prefix tree later
Ok that still seems to be quite slow. What am I doing wrong?
remembers that memoisation exists
Oh I just need to memoise my dp from part 1. Oops.
Anyway posting the code because I shrunk it down to like two semicolons worth of lines.
(
List<String> input = getLines(); Set<String> ts = Set.from(input.first.split(', ')); Map<String, int> dp = {}; int dpm(String s) => dp.putIfAbsent( s, () => s.isNotEmpty ? ts .where((t) => t.matchAsPrefix(s) != null) .map((t) => dpm(s.substring(t.length))) .fold(0, (a, b) => a + b) : 1); void d19(bool sub) { print(input .skip(2) .map((s) => dpm(s)) .map((i) => sub ? i : i > 0 ? 1 : 0) .reduce((a, b) => a + b)); }
swlabr@awful.systemsto TechTakes@awful.systems•"Sam Altman is one of the dullest, most incurious and least creative people to walk this earth."English6·7 months agogilding the lily a bit but
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alikeEnglish2·7 months agoyes
What is this, day 16?
swlabr@awful.systemsto TechTakes@awful.systems•"Sam Altman is one of the dullest, most incurious and least creative people to walk this earth."English10·7 months agoDoes a sealion have bootlicker nature? Ugh.
swlabr@awful.systemsto TechTakes@awful.systems•"Sam Altman is one of the dullest, most incurious and least creative people to walk this earth."English14·7 months agoPlease, señor software engineer was my father. Call me Bob.
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alikeEnglish3·7 months ago17!
p1 discussion
Simultaneously very fun and also the fucking worst.
Fun: Ooooh, I get to simulate a computer, exciting!
Worst: Literally 8 edge cases where fucking up even just one can fuck up your hour.
p2 discussion
I did this by hand. sort of. I mean I didn’t code up something that found the answer.
Basically I looked at the program in the input and wrote it out, and realised that A was essentially a loop variable, where the number of iterations was the number of octal digits A would take to represent. The most significant octal digits (octits?) would determine the tail end of the output sequence, so to find the smallest A you can do a DFS starting from the MS octit. I did this by hand.
EDIT: code. Not gonna explain any of it.
class Comp { List<int> reg; List<int> prog; int ip = 0; List<int> output = []; late List<(int, bool) Function()> ops; int get combo => prog[ip + 1] < 4 ? prog[ip + 1] : reg[prog[ip + 1] - 4]; Comp(this.reg, this.prog) { ops = [ () => (reg[0] = (reg[0] >> combo), false), () => (reg[1] ^= prog[ip + 1], false), () => (reg[1] = combo % 8, false), () => (reg[0] != 0) ? (ip = prog[ip + 1], true) : (0, false), () => (reg[1] ^= reg[2], false), () { output.add(combo % 8); return (0, false); }, () => (reg[1] = (reg[0] >> combo), false), () => (reg[2] = (reg[0] >> combo), false) ]; } compute() { output.clear(); while (ip < prog.length) { if (!ops[prog[ip]]().$2) { ip += 2; } } } reset(int A) { ip = 0; reg[0] = A; reg[1] = 0; reg[2] = 0; } } void d17(bool sub) { List<String> input = getLines(); Comp c = Comp( input.take(3).map((s) => s.split(" ").last).map(int.parse).toList(), input.last.split(" ").last.split(",").map(int.parse).toList()) ..compute(); print("Part a: ${c.output.join(",")}"); if (!sub) return; List<int> sols = []; bool dfs(int cur) { bool found = false; sols.add(cur); int sol = sols.reduce((a, b) => 8 * a + b); c..reset(sol)..compute(); if (c.prog .whereIndexed((i, e) => i >= c.prog.length - c.output.length) .foldIndexed(true, (i, p, e) => p && c.output[i] == e)) { if (found = c.output.length == c.prog.length) { print("Part b: $sol"); } else { for (int i = 0; i < 8 && !(found = found || dfs(i)); i++) {} } } sols.removeLast(); return found; } for (int a = 0; a < 8 && !dfs(a); a++) {} }
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alikeEnglish4·7 months ago16!
p1
I used A*, though mathematically I would have been fine with Dijkstra’s. Also, here’s how I remember how to spell Dijkstra: ijk is in alphabetical order.
p2
If you’ve implemented path/back tracking on a search algo before, this wasn’t too bad, though instead of tracking best parent you need to track equivalently best parents. Woke AOC trying to normalise families with more than two parents, SMH
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code 2024 Week 2: this time it's all grids, all the timeEnglish2·7 months agoP2 complete
The issue with my code was that I didn’t make a push atomic, i.e. I would move boxes even if their ancestors couldn’t be pushed. Making a list of candidate boxes to push solved this.
Here’s the visualisation of the complete solution, though it doesn’t show the last 100 frames or so. Please forgive me
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code 2024 Week 2: this time it's all grids, all the timeEnglish2·7 months agoDay 15
p1
Pretty easy. Just check in the direction you want to push if you have space.
p2 DNF
Currently debugging with test cases from the subreddit. I’ve also created a shitty visualiser for it, stay tuned!
swlabr@awful.systemsto NotAwfulTech@awful.systems•Advent of Code 2024 Week 2: this time it's all grids, all the timeEnglish2·7 months agoHope this works!
vid for 14
25!
p1 tips
O(mn)/O(n2) is fast enough.
50 stars baby!
https://imgur.com/a/hwEVy9H