14
this post was submitted on 02 Dec 2024
14 points (100.0% liked)
NotAwfulTech
385 readers
5 users here now
a community for posting cool tech news you don’t want to sneer at
non-awfulness of tech is not required or else we wouldn’t have any posts
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
days 5 and 6.
5:
p1, p2:
Initially, I was thrown for a loop. It wasn't apparent to me what data structure to use or the problem's properties. My first (and correct) instinct was to interpret the data as a directed graph, but then what? Try to find some total ordering, if such a thing was possible?As it turns out, that instinct was also correct. By drawing the sample data (or counting or printing it out), I noticed that every page number had a defined relation with every other page number. This meant that a total ordering (rather than a lattice) existed, meaning it was possible to construct a comparison function.
So, the algorithm for part 1 was to check if a list was sorted, and part 2 was to sort the list. There's probably a 1-3 line solution for both parts a and b, but that's for Mr. The Reader.
6:
p1, p2
as discussed in a different part of the thread, I consider the input size for square inputs to be N, the "side length" of the square.Context: I participated (and completed!) in AoC last year and pragmatically wrote my code as a set of utility modules for solving these pathological problems. So, I had about 80% of the boilerplate for this problem written, waiting for me to read and relearn.
Anyway, the analysis: P1. was pretty straightforward. Just walk along the map, turn right if you hit an obstacle, and stop when you leave the map. I guessed that there may be a case where one needs to turn in place more than once to escape an obstacle, but I never checked if that was true. Either way, I got the answer out. This is a worst-case O(n^2^) solution, which was fast for n = 130.
P2. I chose to brute force this, and it was fine. I iterated through the grid, placing a wall if possible, and checked if this produced a loop using an explored set. This is worst case O(n^4^), which, for n=130, takes a few seconds to spit out the answer. It's parallelisable, though, so there's that. If a faster solution existed, I'd love to know.
day 6
part 2
I also brute-forced this. I figured there's a bit optimization to be done if you "draw a line" to the next obstacle instead of going step by step, and also maybe exclude some areas, but in the end I just set an exit value to break if the number of steps exceeded a certain value and say that was a loop. Took almost 20m but a star is a star.
update I only added obstructions in the original path, which cut the time down to 5 minutes or so.