The official awful.systems Advent of Code 2023 thread
The official awful.systems Advent of Code 2023 thread
Rules: no spoilers.
The other rules are made up as we go along.
Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.
You're viewing a single thread.
Starting a new comment thread for my solutions to 10-19. Double digits, baby! Code here: https://github.com/Fluxward/aoc2023/
a,b
a: Just copied what I did for 10 b. and applied it to work here. Had to fiddle with it to make it work, but it worked. I implemented a line-crossing counting algorithm. If you slice up the area into rows, you can tell if you are inside the area if you cross an odd number of lines that vertically cross that row.
b. Pretty much just changed the input parsing and ran the same algorithm. Thought that it might be too slow, but I put in some stopwatch ticks and found out that it should take about 5 minutes to run my a) algorithm to get the answer.
The actual time elapsed was 5m50s.
I miiiiight try make a faster version but my head is too fucked up to care right now, hence me letting the slow algorithm run.
Update on 18.
It's not cheating if it's something you learned and forgot from a university course
So, I have made my code a million times faster. My original algorithm counted every square of area individually, plus a bunch of other inefficient things.
My new algorithm now uses some swanky computational geometry to calculate the enclosed area. It took a bit of scribbling on a paper pad to get this right. Some notes:
- If you naively use the coordinates you land on as the points of a polygon and then calculate the area of that polygon, you will slightly underestimate the enclosed area.
- The error comes from the contribution of the area of the perimeter. Drawing out the sample case and observing how it contributes, it basically contributes 1/2 m^3 for every straight portion of the perimeter, and 1/4 or 3/4 for a corner, depending on if that corner is a right or left turn. It should instead contribute 1 for each perimeter tile, so you need to calculate this difference.
- You can use the cross product to determine if a set of 3 points forms a straight line, a left turn, or a right turn.
So, here's what I did. I looked at some old lecture notes I had on programming competition computation geometry implementation details. I copied and pasted some code that implemented a counter-clockwise check and one that calculated the area of a simple polygon. That's pretty much all I needed.
Now my code runs in a few milliseconds.
There is almost definitely a more elegant way to do what I did for this iteration but I'm happy to leave that to someone else to figure out (or copy paste from reddit or something).
18
The beauty is you don't need to keep track of the corners at all: ultimately the area contributed by the perimeter is ( 1/2 * perimeter ) + 1. The short justification is that is if was just ( 1/2 * perimeter ), for every inside corners you overcount by 1/4 and for every outside corner you undercount. And there is exactly 4 more outside corners that inside ones, always. You can justify that by having an arrow follow the eddges, utlmately the arrow must make 1 full turn, each outside corner adds 1/4 turn. each inside corner removes 1/4 turn.
I knew there was a better way! Thanks!
perhaps
A more elegant proof might show that starting with a rectangle, you have 4 corners contributing 1/4. You can push out parts of the edges of the rectangle to generate more corners, but they will always be in pairs of opposite types.
a,b, not much to say
The hardest part has finding the right dart ascii library to use (by default dart treats everything as UTF-16, which is horrible for this sort of thing) and the right data structure (linked hash map, which is a map that remembers insertion order.)
spoiler
"you have linked hash maps? LUXURY!"
In my code I had to resort to this sorting
for my $lens ( sort { $Boxes->[$idx]{$a}{pos} <=> $Boxes->[$idx]{$b}{pos} } keys %{ $Boxes->[$idx] } )Perl at its best!
I am so mad that I don’t know Perl, honestly.
It's a nice language! And I believe it's what AoC is made in. Certainly a lot of stuff seems tailor-made for the language.
- After this problem, I will create a new reply in the OP if it is not there already, and will discuss under that thread.
a,b
So, like many other problems from this year, this is one of those direct solution problems where there isn't much of a neat trick to getting the answer. You just have to implement the algorithm they specify and hope you can do it correctly.
a) I used a regex to do some parsing because I haven't looked at dart regex much and wanted to dip my toes a little.
I considered doing this "properly" with OO classes and subclasses for the different rules. I felt that it would be too difficult and just wrote something janky instead. In hindsight, this was probably the wrong choice, especially since grappling with all the nullable types I had in my single rule class became a little too complex for my melting brain (it is HOT in Australia right now; also my conjunctivae are infected from my sinus infection. So my current IQ is like down 40 IQ points from its normal value of probably -12)
b) There may have been a trick here to simplify the programming (not the processing). Again, I felt that directly implementing the specified algorithm was the only real way forward. In brief:
- Start with an "open" set containing a part with 4 ranges from [1, 4001) and an "accepted" set that is empty.
- Start at the workflow "in"
- For each rule in the current workflow:
- If the rule accepts part of the ranges in the open set, remember those ranges in a closed set and remove them from the open set.
- Remove anything the rule rejects from the open set.
- If the rule redirects to a different workflow W, split off the applicable ranges and recurse at 3 with the current workflow as W.
- Keep in the open set anything the rule doesn't consider.
Because this is AOC, I assumed that the input would be nice and wouldn't have anything problematic like overlapping ranges, and I was right. I had a very stupid off by one error that took me a while to find as well.
The code I have up as of this comment is pretty long and boring, I might try clean it up later.
update: have cleaned up the code.
Replying in OP: Yeah, Lemmy punishes old threads/posts a bit too much for my taste ^^.
Good note for next year!
11
a,b
a: So, I've been in the habit of skipping the flavour text and glossing over the prompt. This time, it hurt me badly.
I read the problem as follows: for N galaxies, find N/2 pairings such that the sum of distances is minimal.
At this point, I was like, wow, the difficulty has ramped up. A DP? That will probably run out of memory with most approaches, requiring a BitSet. I dove in, eager to implement a janky data structure to solve this humdinger.
I wrote the whole damn thing. The bitset, the DP, everything. I ran the code, and WOAH, that number was much smaller than the sample answer. I reread the prompt and realised I had it all wrong.
It wasn't all for naught, though. A lot of the convenience stuff I'd written was fine. Also, I implemented a sparse parser, which helped for b.
b: I was hoping they were asking for what I had accidentally implemented for a. My hopes were squandered.
Anyway, this was pretty trivial with a sparse representation of the galaxies.
Love ur premature optimization
Watch me as I solve P=NP and then find out I was only supposed to solve fizzbuzz
- I have contracted some kind of sinus infection, so rn I have a -20 IQ debuff.
a,b
part a: nothing to say here.
part b: Before diving into the discussion, I timed how long 1000 cycles takes to compute, and apparently, it would take 1643175 seconds or just over 19 days to compute 1 billion cycles naively. How fun!
So, how do you cut down that number? First, that number includes a sparse map representation, so you can tick that box off.
Second is intuiting that the result of performing a cycle is cyclical after a certain point. You can confirm this after you've debugged whatever implementation you have for performing cycles- run it a few times on the sample input and you'll find that the result has a cycle length of 7 after the second interaction.
Once you've got that figured out, it's a matter of implementing some kind of cycle detection and modular arithmetic to get the right answer without having to run 1000000000 cycles. For the record, mine took about 400 cycles to find the loop.
a,b
I took a very similar approach to parts a and b, with the difference that i was too lazy to do titling in each direction, and wanted to abuse regex so Instead i always titled up and rotated, which given my method of tilting up and rotating had some satisfying cancelling of transpose operations: https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/14-b.jq
# Relevant portion # oneCycle expects an array, of array of chars (3x3 eg: [[".","#","."],[".",".","."],["O",".","#"]]) def oneCycle: # Tilt UP = T . MAP(scan) . T # Rotate = T . MAP(reverse) # Titl UP . Rotate = T . MAP(scan) . Map(reverse) | T . T = Identity def tilt_up_rotate: transpose # Gets subgroups # Within each group, # starring with "#" # In order 1 "#", x "O", y "." | map( ("#" + add) | [ scan("#[^#]*") | ["#", scan("O"), scan("\\.")] ] | add[1:]) | map(reverse) ; # Tilt North, West, South, East tilt_up_rotate | tilt_up_rotate | tilt_up_rotate | tilt_up_rotate ;JQ does allow some nice sortcuts sometimes, again
transposeis nice to have.neat!
I need like 25 more IQ points before I think of using a transpose in any context
12
a,b
Finally! a Dee Pee!!!
This problem was mainly testing:
- Are you a bad enough dude to formulate this DP correctly?
- Are you a bad enough dude to choose a good DP state storage schema?
- Is your computer a bad enough dude to store all the DP states if you choose a bad storage schema?
...which is true of all DP problems, honestly. So given you know and understand how to approach DP problems, this would be more an engineering issue than anything.
16
So, as I've been doing the AoC things, I've been creating small libraries of convenience functions to reuse, hopefully. This time, I reused some things I wrote for problem 10, which was vindicating.
a. was a fun coding exercise. Not much more to say.
b. I lucked out by making a recursive traversal function for a), which let me specify the entry and direction of where my traversal would start. Besides that, similar to a., this was a fun coding exercise. I was surprised that my code (which just ran the function from a) on every edge tile) It only took 2s to run; I thought I might need to memoize some of the results.
16 a,b
Neat!
In my case it was a lot more of headbanging, the traverse function i wrote for part a was way to slow, since JQ isn't happy with loop-heavy assignments (if not buried within C-implemented builtins). Part a completed in ~2seconds, which was never going to do (in hindsight it would have taken me less time to simply let it run slowly), I had to optimize it so that the beams don't step one square at a time, but shoot straight to any obstacle.
It took me waaaay too long to troubleshoot it into something that actually worked. I'm sure there's a compact implementation out there, but my part b ended up looking very meaty (and still took ~30s to run): https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/16-b.jq
That’s such a different programming paradigm than I’m used to!
a,b
a. while you can brute force this one in time, one simple trick to make it faster is to treat the symbols as bits and interpret the grid as numbers. It then becomes a matter of locating the reflection point.
b. It's not much of a difference to solve b. The trick here is that if you did the bit stuff I suggested above, you'd quickly realise that a smudge interpreted as a binary number is a power of two. Finding a smudge is equivalent to if the bitwise XOR of two numbers is a power of 2, which can be done with some bitwise magic.
17, We’re in the back third now, folks!
a, b
A and B were roughly the same difficulty.
So in my first year in university, in my intro DSA class, we learned A*. Have I learned any other ways to search since? Not really. So I used A* here.
It took way longer than it should have to solve, which I blame on my ongoing illness. The main sticking point was that I implemented a class to represent the search state, and since I was going to use it as a key to a map, I implemented a hashcode for it. The rest of the A* code freely flowed from my brain (really the wikipedia pseudocode).
Cue like 40 mins plus of wondering how the test input was searching over millions of states, wondering if I’d fucked up the A* implementation, wondering if the problem was too big for A*, and wondering if it was finally time to take a days break from all the aoc nonsense.
Anyway at some point I realised I forgot to implement the corresponding equals method to my hashcode. Once I had that my code ran in seconds and everything was fine. This sickness is the worst!!!
10!
a, b
a was relatively straightforward - again, an implementation test.
b was interesting- luckily, I remembered how to test if a point lives inside a curve. The line-crossing count algorithm was a little tricky to write from scratch, but I finally got there. Also, I screwed up for like an hour when I didn't realise you were supposed to count junk pipes as part of the territory. Code wise it got messy, and I've thrown something up on my github, but might try clean it up a little later.
Update: I've cleaned up my code and made it "dartier" i.e. I use more neat dart syntactic sugar at the cost of readability.