The occasional scrivener

Dec 2020 | Dec 2019 | Dec 2018 | Dec 2017 | Dec 2016 | Dec 2015 | Dec 2014 | Dec 2013 | Dec 2012 | Dec 2011 | Dec 2010

Some tips about participating in Advent of Code.

AoC is not a competition

If you were to go with online opinion, AoC is all about getting the solutions as fast as possible. This is actually not true, apart from the top 100 scorers every day[1]. Many people post their full solution online on the AoC subreddit as soon as the top 100 slots have been filled. So if you want to get 50 stars, you pick a popular language (like Python), hang out in the solutions megathread, and run the first posted solution on your input to get the correct results.

If your organization has a “competition” where the top scorers in their leaderboard get some reward, don’t participate. It’s too easy to suspect someone of “cheating” for it to be fun.

Instead, focusing on using the event to expand your skills.

You don’t need to finish each puzzle the day it is released, or within the 25 first days of December

The puzzles can be completed at any time and in any order.

Don’t let trivial mistakes trip you up

In almost every puzzle, your personalized input will be provided as a text file. Set up your environment to deal with this consistently.

For example, for every puzzle, I make a new subdirectory. The puzzle input goes into a file called input.txt. The example input goes into another file, test.txt. I then open a new file for my code, and enter a canned template that reads the content of a file into an array, one line per entry. It takes care of newlines and carriage returns (but preserves empty lines).

Then, when it comes to dealing with the input meaning, I can operate on an abstract array instead of a file.

In a similar manner I also set up some modules for dumping variables, running simple tests, etc.

You can see my (Perl) template here.

Use the examples

The puzzle text is clearly written, and any questions you might have regarding the rules of the puzzle are answered in the text or in the example. Once you get the example to run correctly, it’s generally just a question of changing the in-data to “live” to get your answer.

Generally. At higher levels there can be “twists” in how the real data is presented as compared to the examples. Also look out for edge cases. The example data might not include negative numbers, but the real input does. Have you taken that into account?

Puzzles start out easy but get harder

And weekends are generally tougher than weekdays.

Some problem classes tend to make an appearance every event

These include

• Conway’s Game of Life
• Register Rodeo - this is my term for a class of problem where you’re given a long list of statements, some of which are data and some of which are instructions, and you need to decode them
• pathfinding through a maze
• finding the lowest cost for some complicated series of actions (generalized Dijkstra’s)

Having a basic knowledge about these is beneficial, but not required.

Remember to have fun!

[1] if you want to try to crack the top 100, this guide is not for you.

First book in a new trilogy. MacLeod treads familiar ground for him - near future, socialist Europe vs. extrapolated USA “after the return of democracy”. I am looking forward to the rest of the books.

Not quite as much as last month but still keeping up a decent pace.

Link to portal.

Project website: Advent of Code 2021.

Previous years: 2015, 2016, 2017, 2018. 2019. 2020.

I use Perl for all the solutions.

Most assume the input data is in a file called input.txt in the same directory as the file.

Ratings

I’m giving each puzzle a subjective rating between 1 and 5. This is based on difficulty, “fiddliness” and how happy I am with my own solution.

A note on scoring

I score my problems to mark where I’ve finished a solution myself or given up and looked for hints. A score of 2 means I solved both the daily problems myself, a score of 1 means I looked up a hint for one of the problems, and a zero score means I didn’t solve any of the problems myself.

My goals for this year (in descending order of priority):

• get a total score of 40 or more (75%)
• solve all problems up until day 15 without any external input - not fulfilled
• solve all problems within 24 hours of release - not fulfilled

Link to Github repo.

Final status: score of 46/50.

Day 1 - Day 2 - Day 3 - Day 4 - Day 5 - Day 6 - Day 7 - Day 8 - Day 9 - Day 10 - Day 11 - Day 12 - Day 13 - Day 14 - Day 15 - Day 16 - Day 17 - Day 18 - Day 19 - Day 20 - Day 21 - Day 22 - Day 23 - Day 24 - Day 25 - Day 31

Day 1 - Sonar Sweep

Day 1 - complete solution

And we’re off!

I wonder if I got a bit too clever by half in this solution, as I’ve been looking over older solutions and can’t even remember solving them. But that’s how it goes I guess.

Puzzle rating: 3/5

Score: 2

Day 2 - Dive!

Day 2 - complete solution

A “standard” Perlish solution (well, my kind of Perl, anyway): a dispatch table for the else/if “switch” construct, and a compact hash containing the state of the two solutions.

Puzzle rating: 3/5

Score: 2

Day 3 - Binary Diagnostic

Day 3 - complete solution

I was honestly surprised that the canonical solution to this wasn’t some esoteric bit-twiddling trick that reduces it to a one-liner.

In part 2, the naive solution is to loop through each “column” to determine which values to count so as to determine whether they are most frequent or not. I used an index for each “set” to keep track of the values already assigned to that set.

Puzzle rating: 3/5

Score: 2

Day 4 - Giant Squid

Day 4 - complete solution

Fairly straight-forward, although part 2 threw me for a loop. I didn’t find a good way to determine the exit condition.

Puzzle rating: 4/5

Score: 2

Day 5 - Hydrothermal Venture

Day 5 - complete solution

Finally ok with my solution.

The first attempt got the job done, but was super-scruffy. I realized after I’d finished that I could treat the direction as unit vectors and work from there, so I re-wrote my solution, but only in as so far as to use the direction as a “selector” to chose which subroutine to call to “paint” the map.

After adding that to the repo, I finally remembered what I’d decided before the rewrite - to use the value of the vector in the paint routine itself.

Note that just using atan2 blindly to determine the direction will point the Y axis incorrectly. It’s probably only an issue if you’re printing the results, but I found that very helpful in debugging.

If anything good can be said about this method is that I eliminated a lot of weirdness along the way. It wasn’t all wasted effort.

Puzzle rating: 3/5

Score: 2

Day 6 - Lanternfish

Day 6 - complete solution

I got off on a bad start with this puzzle, because it worked perfectly for the test input but failed for my puzzle input. I whinged about it on IRC, mentioning I had a very old fish (41 days!). Turns out that was a mispaste and fixing that gave me the correct solution.

I got the answer to the second part 40 seconds later.

Puzzle rating: 4/5, just because my solution was so smooooth

Score: 2

Day 7 - The Treachery of Whales

Day 7 - complete solution

A quite fun one, and the first this year I managed to solve within 1hr of release. This might be TMI but I usually perform my morning ablutions and brew a pot of coffee before starting on a puzzle.

Thinking about this led me to try the average (mean) of the values as the natural solution, but that gave incorrect values. So I just checked the fuel consumption for each and every possible end point, selecting the minimum value. This went plenty fast, as did part 2 once I didn’t actually step through each distance calculating fuel as I went (hint: google “Gauss sum 100”).

When I had both solutions, I checked the various IRC chats and subreddits and discovered a raging debate on whether taking the median for part 1 and the average for part 2 always gave the correct result for every input. For me they did, so I just restricted by search space to the span of these values, plus a few extra integers for safety. This shaved a couple more milliseconds off the run time.

Puzzle rating: 4/5, I like grade school math

Score: 2

Day 8 - Seven Segment Search

Day 8 - complete solution

Today was a tough one - not the problem, per se, but commitments that made it hard to me to get to a solution that I was happy with.

In the end I just went for brute-forcing every possible permutation, which is 7! or 5,040. The solution takes around 2s to run on my VPS.

Puzzle rating: 3/5, bit fiddly

Score: 2

Day 9 - Smoke Basin

Day 9 - complete solution

This was a straight-forward problem.

I’m a bit surprised my BFS solution worked first time.

Puzzle rating: 3/5

Score: 2

Day 10 - Syntax Scoring

Day 10 - complete solution

Not the most elegant solution but it gets the job done.

Puzzle rating: 3/5

Score: 2

Day 11 - Dumbo Octopus

Day 11 - complete solution

Nice and easy, got 2 stars within one hour of downloading the input.

I don’t think my handling of some flags ($has_changed, $has_synced) is the most elegant. I’m pretty sure I’m doing an extra scan of the entire map every step to ensure everything has settled down. But I get a result within 1s (just) so let’s do some weekend chores instead.

I suspect tomorrow will be… more challenging.

Puzzle rating: 3/5

Score: 2

Day 12 - Passage Pathing

Day 12 - complete solution

I had to look up a solution for this, which was kind of embarrasing for such an early problem.

Full credit in source.

Puzzle rating: 3/5

Score: 0

Day 13 - Transparent Origami

Day 13 - complete solution

As usual, a breather after the weekend.

I was tearing my hair out, running spot checks on my code, before I realized I had coded my output incorrectly.

The rest of my issues was making it read the right way up…

“Best” result so far, around rank 6,500 for part 1…

Puzzle rating: 3/5

Score: 2

Day 14 - Extended Polymerization

Day 14 - complete solution Day 14 - part 1

A tough but fun problem.

Part 1 only for now.

Update 2021-12-15: finished both parts.

Puzzle rating: 4/5

Score: 2

Day 15 - Chiton

Day 15 - part 2

I think I finally figured out A*Dijkstra’s. With the help of a lot of cribbing from previous solutions (like 2018 day 22).

I’ve only included part 2 because I can’t be bothered bounding the box for part 1 so it doesn’t choose a cheaper solution outside those limits.

Puzzle rating: 4/5

Score: 2

Day 16 - Packet Decoder

Day 16 - complete solution Day 16 - part 1

Many people went “BERR” when they saw this: Binary Encoded Register Rodeo!

I had a lot of problems with this, mostly because I managed to get the correct solution for part one a bit by accident, which didn’t help solving part 2.

After a day of tearing my hair trying to pass data between recursion levels I managed to solve it.

Puzzle rating: 4/5 - tough, but fair

Score: 2

Day 17 - Trick Shot

Day 17 - complete solution

Suspiciously easy.

This year’s last weekend is coming up.

Brace yourselves.

Puzzle rating: 3/5

Score: 2

Day 18 - Snailfish

Day 18 - complete solution Day 18 - testing

Completed 2021-12-31

Actually less complicated then at first glance. The main issue was figuring out how to implement the rules where “explode” had higher precedence than “split”, but I managed that with a stack.

Puzzle rating: 4/5

Score: 2

Day 19 - Beacon Scanner

Day 19 - complete solution

Completed 2021-12-28

A fun problem. I found a list of all possible rotation transforms and used them to generate the set of rotations to try, then just compared each and every one to find offsets. Runtime is around 15s.

Puzzle rating: 4/5

Score: 2

Day 20 - Trench Map

Day 20 - complete solution

Back on track after a tough weekend - which I had to skip due to travel.

This was a fun problem once you figured out the trick.

Puzzle rating: 4/5

Score: 2

Day 21 - Dirac Dice

Day 21 - complete solution

A fun problem, but part 2 was too tough for me. I copped out and took a “free” star. Full credit in source!

Puzzle rating: 4/5

Score: 1

Day 22 - Reactor Reboot

Day 22 - part 1 Day 22 - part 2

Cubes - IN SPACE!!

I only had time for part 1 on release day.

Part 2 completed on 2021-01-04.

Puzzle rating: 4/5

Score: 2

Day 23 - Amphipod

Day 23 - complete solution

Completed 2021-12-26

A fun problem but one I had to skip on release day due to preparations for Christmas.

We’ve seen this sort of thing before, I solved it using Dijkstra’s.

In general, we have a start state and an end state, and we can generate new states based on the given rules. These intermediate states can be seen as nodes in a graph we’re constructing on the fly. Applying the movement costs for each amphipod gives the total cost for moving form start to end, and Dijkstra’s algorithm gives the lowest cost.

Puzzle rating: 4/5

Score: 2

Day 24 - Arithmetic Logic Unit

Day 24 - complete solution

I had to crib a solution (credit in source, of course) but I gave myself a point because it was Christmas Eve and that’s when we get presents here, damnit.

Puzzle rating: 4/5

Score: 1

Day 25 - Sea Cucumber

Day 25 - complete solution

And… it’s a wrap.

Not the most elegant solution but it’s a star. I’ll take it.

Puzzle rating: 3/5

Score: 2 (assuming I fix the missing stars!)

Day 31 - Template

Day 31 - commented template

Related to this entry.