The rest of the code:
cacheson
- 0 Posts
- 28 Comments
Joined 1 year ago
Cake day: June 13th, 2023
You are not logged in. If you use a Fediverse account that is able to follow users, you can follow this user.
Nim
Another tough one. Judging by the relative lack of comments here, I wasn’t the only one that had trouble. For me this one was less frustrating and more interesting than day 12, though.
I solved part 1 by doing a recursive depth-first search, biasing towards a zigzag path directly to the goal in order to establish a baseline path cost. Path branches that got more expensive than the current best path terminated early. I also stored direction, speed, and heat loss data for each tile entered. Any path branch that entered a tile in the same direction and at the same (or greater) speed as a previous path was terminated, unless it had a lower temperature loss.
This ran pretty slowly, taking around an hour to finish. I took a break and just let it run. Once it completed, it had gotten pretty late, so I did a quick naive modification for part 2 to account for the new movement restrictions, and let that run overnight. The next day it was still running, so I spent some time trying to think of a way to speed it up. Didn’t really get anywhere on my own, so I started reading up on A* to refresh my memory on how it worked.
The solution that I arrived at for the rewrite was to use Dijkstra’s algorithm to pre-compute a map of what the minimum possible costs would be from each tile to the goal, if adjacent tiles could be moved to without restriction. I then used that as the heuristic for A*. While I was writing this, the original part 2 program did finish and gave the correct answer. Since I was already this far in though, I figured I’d finish the rewrite anyway.
The new program got the wrong answer, but did so very quickly. It turned out that I had a bug in my Dijkstra map. I was sorting the node queue by the currently computed cost to move from that node to the goal, when it instead should have been sorted by that plus the cost to enter that node from a neighbor. Since the node at the head of the queue is removed and marked as finalized on each iteration, some nodes were being finalized before their actual minimum costs were found.
When using the A* algorithm, you usually want your heuristic cost estimate to underestimate the actual cost to reach the goal from a given node. If it overestimates instead, the algorithm will overlook routes that are potentially more optimal than the computed route. This can be useful if you want to find a “good enough” route quickly, but in this case we need the actual best path.
Nim
I’m caught up!
This one was pretty straighforward. Iterate through the beam path, recursively creating new beams when you hit splitters. The only gotcha is that you need a way to detect infinite loops that can be created by splitters. I opted to record energized non-special tiles as
-or|, depending on which way the beam was traveling, and then abort any path that retreads those tiles in the same way. I meant to also use+for where the beams cross, but I forgot and it turned out not to be necessary.Part 2 was pretty trivial once the code for part 1 was written.
Nim
Almost caught up. Not much to say about this one. Part 1 was a freebie. Part 2 had a convoluted description, but was still pretty easy.
Nim
Getting caught up slowly after spending way too long on day 12. I’ll be busy this weekend though, so I’ll probably fall further behind.
Part 2 looked daunting at first, as I knew brute-forcing 1 billion iterations wouldn’t be practical. I did some premature optimization anyway, pre-calculating north/south and east/west runs in which the round rocks would be able to travel.
At first I figured maybe the rocks would eventually reach a stable configuration, so I added a check to detect if the current iteration matches the previous one. It never triggered, so I dumped some of the grid states and it became obvious that there was a cycle occurring. I probably should have guessed this in advance. The spin cycle is effectively a pseudorandom number generator, and all PRNGs eventually cycle. Good PRNGs have a very long cycle length, but this one isn’t very good.
I added a hash table, mapping the state of each iteration to the next one. Once a value is added that already exists in the table as a key, there’s a complete cycle. At that point it’s just a matter of walking the cycle to determine it’s length, and calculating from there.
Nim
This one was a nice change of pace after the disaster of day 12. For part 1 I kept a list of valid column indexes, and checked those columns in each row for reflections, eliminating columns from the list as I went. To find vertical reflections, I just transposed the grid first.
Part 2 looked daunting at first, but I just needed to add a
smudgescounter to each column candidate, eliminating them when their counter reaches 2. For scoring, just count the 1-smudge columns.
And finally:
Nim
I don’t want to talk about it. -_-
Nim
Approached part 1 in the expected way, by expanding the grid. For part 2, I left the grid alone and just adjusted the galaxy location vectors based on how many empty rows and columns there were above and to the left of them. I divided my final totals by 2 instead of bothering with any fancy combinatoric iterators.
Unfortunately then it’ll be broken for kbin users. I can do it anyway though if the bot is too annoying, just lmk.
Nim
I got a late start on part 1, and then had to sleep on part 2. Just finished everything up with a little time to spare before day 11.
Part 2 probably would have been easier if I knew more about image processing, but I managed:
- Made a copy of the grid and filled it with
.tiles - Copied all of the path tiles that I had calculated in part 1
- Flood-filled all the
.tiles that are connected to the outside edges of the grid withOtiles - Walked along the path, looking for an adjacent
Otile at each step. Stopped when one was found, and recorded whether it was to the left or right of the path. - Walked the path again, flood-filling any adjacent inside
.tiles withI, and counted them
Code:
- Made a copy of the grid and filled it with
Nim
Pretty easy one today. Made a
Pyramidtype to hold the values and their layers of diffs, and anextendfunction to predict the next value. For part 2 I just had to make anextendLeftversion of it that inserts and subtracts instead of appending and adding.
Nim
I like how if you have an error in your calculations, you end up wandering the haunted desert for eternity. Very flavorful.
My solution for part 2 is pretty much the same as for part 1, just modified to work on a sequence of nodes instead of a single node. However, it doesn’t find an answer in the time that I was willing to wait for it. I thought about trying to optimize it to run faster, but figured that if it was taking this long on Nim, then interpreted languages would have no chance, so that couldn’t be the right approach.
I suspected that maybe the ghosts arrived at the Z locations at predictable intervals. I added some code to output the step count each time each ghost reached a Z (see commented code), and my suspicion was correct. Just needed to calculate the least common multiple of the 6 cycle lengths.
Nim
I wrote some nice code for sorting poker hands, just defining the
<and==operations for myCardSetandHandtypes, and letting the standard library’s sort function handle the rest.It was quite frustrating to be told that my answer was wrong, though. I dumped the full sorted hand list and checked it manually to make sure everything was working properly, and it was. Wasted a few hours trying to figure out what was wrong. Ended up grabbing someone else’s code and running it in order to compare the resulting hand list. Theirs was clearly ordered wrong, but somehow ended up with the correct answer?
Turns out that Camel Cards isn’t Poker. -_-
Rather than rewrite my code entirely, I settled on some slightly ugly hacks to make it work for Camel Cards, and to handle the wildcards in part 2.
Nim
Hey, waitaminute, this isn’t a programming puzzle. This is algebra homework!
Part 2 only required a trivial change to the parsing, the rest of the code still worked. I kept the data as singleton arrays to keep it compatible.
Yeah, roughly the same idea. I guess I could have just used HSlice for my range type, I thought maybe there was some special magic to it.
It looks like your if-else ladder misses a corner case, where one range only intersects with the first or last element of the other. Switching to
<=and=for those should take care of it though.
Treated each range as an object, and used set operations on them
That’s smart. Honestly, I don’t understand how it works. 😅
“Set operations” should probably be in quotes. I just mean that I implemented the
*(intersection) and-(difference) operators for my ValueRange type. The intersection operator works like it does for sets, just returning the overlap. The difference operator has to work a little differently, because ranges have to be contiguous, whereas sets don’t, so it returns a sequence of ValueRange objects.My ValueMapping type uses a ValueRange for it’s source, so applying it to a range just involves using the intersection operator to determine what part of the range needs to move, and the difference operator to determine which parts are left.
Thank you, I’ll keep those in mind. Functional programming seems interesting to me, but I don’t have any practical experience with it. At some point I want to learn one of the languages that are dedicated to it. Nim does have some features for enabling a functional style, but the overall flexibility of the language probably makes it harder to learn said style.
Ended up solving it by working backwards by trying different location values and seeing if that can become a valid seed.
Huh, that’s clever.
This would have been really useful to know about. I’ve committed to a certain level of wheel-reinvention for this event unless I get really stuck, but I’m sure it’ll come up again in the future.