Thursday, 2016-12-01

Advent of Code 2016

Project website: Advent of Code 2016.

My solutions for AoC 2015.

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. Some require extra modules from CPAN.

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.

The times are hours and minutes from the time of the puzzle release (00:00 EST) until I posted an announcement on Twitter.

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

  • solve all problems myself (higher cumulative score than last year’s 43/50).
  • solve all problems within 24 hours of release
  • be among the first 1,000 on each day’s leaderboard

Final score

  • Problems solved by myself: 49 / 50 — a big improvement over last year’s 43/50.
  • 3 parts not solved within 24 hours. Shortest time for both parts: 40 minutes. Average time: 5h07m.
  • Average finishing place for each day: 677.8 for part 1, 747.6 for part 2.

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 1 — No Time for a Taxicab

My solution for day 1: part 1, part 2.

I managed to get the correct solution in part 1 despite not taking absolute values in consideration, fixed in code.

Part 2 was frustrating as I didn’t have time to re-think the problem, instead I kludged something on top of part 1.

Score: 2, 9h50m.

Day 2 — Bathroom Security

My solution for day 2: part 1, part 2.

Actually reading the Wikipedia article linked from day 1 helped me with part 2.

Alternate part 2, inspired by this solution.

Score: 2, 4h21m.

Day 3 — Squares With Three Sides

My solution for day 3: part 1, part 2.

The hardest part of this problem was cleaning up the input…

Score: 2, 3h59m.

Day 4 — Security Through Obscurity

My solution for day 4: part 1, part 2.

A fun problem!

Score: 2, 3h38m.

Day 5 — How About a Nice Game of Chess?

My solution for day 5: part 1, part 2.

I already had the required modules installed since 2015 day 4 and initially thought this was going to be straight repeat. While part 1 was indeed simple enough, part 2 threw me for a little loop due to the requirements to keep track of previous entries.

Score: 2, 2h32m.

Day 6 — Signals and Noise

My solution for day 6. Alternative with more map.

Decided to try to solve this over breakfast.

Score: 2, 0h40m.

This was the last of the warmup problems. Things will get tougher from now on.

Day 7 — Internet Protocol Version 7

My solution for day 7: part 1, part 2.

Not very proud of part 2, but at least I know what it does. Using regexps would be the obvious choice but I frankly lack the regex-fu to handle it.

Update: some quick googling revealed the existence of lookahead to deal with overlapping matches, so I whipped together an alternative part 2. This runs appreciably faster (although still within a second).

Just made the first 1,000 submitters for part 2.

Score: 2, 4h36m.

Day 8 — Two-Factor Authentication

My solution for day 8, both parts.

Really didn’t want to do this, it reeked of fiddly bit-flipping, but after thinking a bit the solution presented itself.

Again just squeeked in under the 1,000 first submitters for both parts.

Score: 2, 4h27m.

Day 9 — Explosives in Cyberspace

My solution for day 9: part 1, part 2.

I’m debating whether to award myself 2 points for this, as I had to look for hints for part 2.

The issue was that I was running a recursive solution, but instead of simply counting the characters of a single part and then multiplying by the number of repetitions, I actually created a new array that was the part repeated repetitions times! This led to horrendous execution times.

Score: 2, 5h11m.

Day 10 — Balance Bots

My solution for day 10, both parts.

I usually don’t forget to sort numerically but I did this time, which led to a wild goose chase trying to find out why real input differed from test.

Family commitments prevented a faster time but I still submitted in the first thousand.

Score: 2, 8h15m

Day 11 — Radioisotope Thermoelectric Generators

Finally a solution after almost 6 days.

Not fantastically proud of this, kept plugging away at some solutions even if I’d have had better luck taking a step back and reconsidering. But I solved it myself!

The most problems I had was with the shuffling stuff to and from floors. The last piece fell into place when I realized I had to keep track of the elevator too when considering already visited states.

Solves part 2 in around 11m, which is just barely acceptable.

Score: 2.

Day 12 — Leonardo’s Monorail

Day 12 - complete solution

Score: 2, 5h05m.

Day 13 — A Maze of Twisty Little Cubicles

My solution for day 13: part 1, part 2.

I’ve been thinking a lot about day 11, so the breadth-first search concept came in handy.

Score: 2, 4h39m.

Day 14 — One-Time Pad

My solution for day 14.

This was both tough and kind of boring.

Key insight was this throwaway comment by /u/askalski. Each candidate index is stored in a hash keyed on the duplicate character, and any hit of quintuples is checked

A lot of subtle off-by-one errors made this quite frustrating.

Performance is respectable, especially part 2. Example input:

$ time perl ./
real    0m0.601s

$ time perl ./ 2
real    0m41.553s

Update 16 Dec 2016 alternative version with cleaner code.

Score: 2, 12h18m.

Day 15 — Timing is Everything

My solution for day 15.

Fast and simple brute-force solved this one.

Score: 2, 1h06m.

Day 16 — Dragon Checksum

My solution for day 16.

The nice and tidy recursive solution I coded for part one takes 1m34s to complete part two, but this is not a very interesting problem so I will just leave it at that.

Score: 2, 3h22m (this is day off for me).

Day 17 — Two Steps Forward

My solution for day 17.

Straight-forward application of techniques known so far. Key to part 2 is to realize BFS returns all solutions, not just the shortest.

Score: 2, submitted after 8h57m on a Saturday.

Day 18 — Like a Rogue

My solution for day 18: complete.

Quick and dirty fourth Advent Sunday breakfast solution. Part 2 runs in 2m30s using the same code as part 1, just many more rows. Brute force baby.

I might try to improve part 2 later.

Edit: here’s a a second attempt. Credit.

Part 2 runtime is 33s for this version.

Score: 2, 3h25m.

Day 19 — An Elephant Named Joseph

My solution for day 19 part 1: part 1.

Part 2 defeated me, this is part 2 with copied code, credit in source.

Update: this alternative is way more Perlish, credit in source!

This is the first problem I actually bailed on, which is a step up from last year. I liked it in a way that you simply couldn’t just run part 2 as a straight continuation of part 1, but had to rethink your strategy, but this problem was too boring for me to bother doing that.

Score: 1, 5h49m.

Day 20 — Firewall Rules

Day 20 - complete solution

Straightforward. Runtime 0.11s.

Score: 2, 4h18m.

Day 21 — Scrambled Letters and Hash

My solution for day 21: part 1, part 2.

A boring and fiddly part 1 led to a straight-forward brute-force solution for part 2. That part finishes in 40s on my machine.

At least I finally got to learn how splice works…

TODO: implement dispatch table?

Score: 2, 5h19m

Day 22 — Grid Computing

My solution for day 22: part 1, part 2.

For part 2, I took a chance that there was nothing hindering moving the empty slot in straight lines apart from the “walls”. A simple count of the needed steps gave the solution.

Score: 2, 4h22m.

Day 23 — Safe Cracking

Complete solution.

Entirely unoptimized, runtime for part 2 is 101 minutes!

I was sidetracked by the fact that my first attempt at part 1 gave the correct solution, but failed for part 2.

TODO: better performance?

Score: 2.

Day 24 — Air Duct Spelunking

Complete solution

I used BFS to compute the distances between all points, then used the technique from AoC 2015 day 9 to generate all possible permutations and print them out.

Part 2 runs in less than 2 seconds.

Score: 2, 8h52m on Christmas eve!

Day 25 — Clock Signal

Complete solution

All done! Quick and dirty solution using brute force with crappy pattern detection.

Score: 2, 4h24m.