Friday, 2017-12-01

Advent of Code 2017

Project website: Advent of Code 2017.

Previous years: 2015, 2016.

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):

  • match or beat last year’s score of 49/50.
  • solve all problems within 24 hours of release
  • be among the first 750 on each day’s leaderboard

Day 1 — Inverse Captcha

Day 1 - complete solution

A nice little warmup problem. Eric pulls his usual trick of making you assume something in part 1 that you have to unassume in part 2.

Score: 2

Time: 47m

Leaderboard placement: 783 / 748

Day 2 — Corruption Checksum

Day 2 - complete solution

My suspicion that there’s going to be a lot of functional list-munging in this year’s edition is strengthening.

Score: 2

Time: 2h40m (it’s a Saturday, so I slept in!)

Leaderboard placement: 2,676 / 2,318

Day 3 — Spiral Memory

My solution for day 3: part 1, part 2

A nice headfake again. Of course you’re not going to brute-force the spiral, keeping track of the coordinates for each element, then taking the Manhattan distance of the element you want when you reach it!

Instead you use a solution from Project Euler to segment the search space and find the solution nice and quick.

Then you get to part 2 and discover you need to generate the spiral after all…

Score: 2

Time: 8h23m (first Advent Sunday, shopping for Christmas)

Leaderboard: 2,578 / 3,249

Day 4 — High-Entropy Passphrases

Day 4 - complete solution

A stark contrast to yesterday’s problem. Perl’s text processing features usually make parsing input a breeze but in this case it was almost too easy. I guess I have to be careful for what I wish for in the future.

Score: 2

Time: 37m

Leaderboard: 1,544 / 1,314

Day 5 — A Maze of Twisty Trampolines, All Alike

Day 5 - complete solution

Ah, the list of instructions! An AoC classic.

Wise to previous problems I decided to incorporate test input from the get-go, and to include a debug output. This was a nice addition for part 2, as I could just run the test input and instantly confirm my changes worked.

Runtime for part 2 is around 17.5s, which, as the answer is around 25M steps leads to a “MIPS” value of 1.4.

Score: 2

Time: 41m

Leaderboard: 1,865 / 1,712

Day 6 — Memory Reallocation

Day 6 - complete solution

I liked this puzzle, even if it was a bit on the easy side.

An interesting algorithm for detecting cycles was pointed out in the daily solutions thread: Floyd’s Tortoise and Hare. I don’t think it will give better performance for the limited data set of the puzzle, but part of the fun of AoC is learning new things.

TODO

If I get some time in the future I’d like to rework this problem using an iterator for generate the states and using the Floyd algorithm.

Score: 2

Time: 51m

Leaderboard: 1,553 / 1,433

Day 7 — Recursive Circus

Day 7 - complete solution

I was sure my lack of CS knowledge would bite me, but after 10 hours I’m not seeing any comments like “actually this is just algorithm X” on the subreddit daily thread. I guess most people solved this like I did.

A fun problem, all in all.

Score: 2

Time: 5h22m - solved part one before leaving for work, but part two was delayed by meetings and a reinstalled work computer.

Leaderboard: 1,518 / 2,406

Day 8 — I Heard You Like Registers

Day 8 - complete solution

As this is not my first register rodeo, I ran a quick check to make sure the input values were what I expected (comparison operators, whether a field was an integer or not). After that it was simply a matter of encoding the rules.

I could have used Perl’s eval to evaluate the expressions, but I’m not 100% comfortable with it so I just used a giant if/else statement instead.

I chose to write a specific function to read values from the register hash, which made inserting a statement to capture part 2 very simple.

TODO

Implement using dispatch table?

Score: 2

Time: 1h15m

Leaderboard: 1,667 / 1,639

Day 9 — Stream Processing

Day 9 - complete solution

This was a fun one!

After perusing other solutions for day 8 I decided to implement a dispatch table for handling the characters. I’m glad I did because it made adding further checks quite easy.

Part 2 threw me for a loop. I got the wrong answer for the number of garbage characters, and trying to find where my assumptions were wrong in the giant puzzle input felt impossible. However, there are a number of example inputs, and after running my code on them I found where I was mistaken…

Score: 2

Time: 5h35m (I’m not gonna get up at 6AM on a Saturday…)

Leaderboard: 2,604 / 2,850

Day 10 — Knot Hash

My solution for day 10: part 1, part 2

Difficulty is ramping up.

The biggest issue I had with this was the @#%&*! array manipulation in part 1.

Score: 2

Time: 5h09m

Leaderboard: 2,149 / 1,867

Day 11 — Hex Ed

Day 11 - complete solution

A fun problem. I didn’t know anything about hex grids but like everyone and their mom I googled and found this excellent site that explains them well.

Score: 2

Time: 1h02m

Leaderboard: 1,110 / 1,007

Day 12 — Digital Plumber

Day 12 - complete solution

I could probably have solved this in a more Perlish way but here I at least understand what’s going on.

Score: 2

Time: 2h47m

Leaderboard: 2,108 / 2,038

Day 13 — Packet Scanners

My solution for day 13: part 1, part 2

This was the first problem that has a significant runtime (without optimization). Even after some work I have a ~10m runtime for part 2.

TODO

Optimize for faster runtime.

Score: 2

Time: 13h23m

Leaderboard: 2,462 / 4,224

Day 14 — Disk Defragmentation

Day 14 - complete solution

A nice mix of difficulty and entertainment. Unreasonably proud of independently finding the four-way flood fill algorithm.

Score: 2

Time: 4h51m

Leaderboard: 1,096 / 1,636

Day 15 — Dueling Generators

Day 15 - complete solution

Brute force, baby!

I used an iterator for part 2, then wrangled both solutions into one using that technique.

The generators are well known.

Score: 2

Time: 3h06m

Leaderboard: 1,130 / 1,929

Day 16 — Permutation Promenade

Day 16 - complete solution

After the usual struggles with Perl’s lists I got this working.

I decided to go with a dispatch table from the start, which made part 2 easier to implement.

Score: 2

Time: 4h34m

Leaderboard: 1,682 / 1,370

Thursday, 2017-11-30

November

Gamla stan

Nov 2016 | Nov 2015 | Nov 2014 | Nov 2013 | Nov 2012 | Nov 2011

Tuesday, 2017-11-07

New host

For a number of years my friend Thomas has graciously hosted this blog, a shell account, and a number of other things that are essential to the modern person (IMHO). However external circumstances will deprive me of this service, for which I am sorry, for Thomas has been the best sysadmin, and it’s been free!

I’ve shelled out a couple FIAT dollars a month for a “droplet” at Digital Ocean, and worked to transfer stuff from the old server to the new. These are some notes in case I have to do it again.

I chose Ubuntu as a distro because I like the Debian-based packaging.

Web hosting and Perl CGI

I installed Nginx because I’ve vaguely heard it’s “better”. Getting it to deal with CGI scripts in Perl was a bit fiddly but it worked out OK.

You need the fcgiwrap and spawn-fcgi packages.

The following addition was made to the server section of Nginx config for my site.

# we have separate htdocs and cgi-bin dirs under the gerikson.com dir
# this location is to make sure we can have a specific section for cgi-bin
location /cgi-bin/ {
    root /home/www/gerikson.com/;
    try_files $uri =404;
    gzip off;
    fastcgi_pass unix:/var/run/fcgiwrap.socket;
    fastcgi_index index.pl;
    fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name;
    include fastcgi_params;
}

Added packages

These are needed for some stuff I host

libcgi-pm-perl
libconfig-simple-perl
libdate-calc-perl
libdatetime-perl
libdbd-sqlite3-perl
libdbi-perl
libjson-perl
libnumber-format-perl
libstatistics-linefit-perl
libtext-csv-perl
libwww-perl
lynx
mutt
sqlite3
zip
perltidy
tree
cpanminus
perl-doc

These are needed for coding contests

libmath-bigint-gmp-perl
libmath-prime-util-gmp-perl

Python 3 stuff

python3
python-pip
virtualenv

Tuesday, 2017-10-31

Tuesday, 2017-10-24

Fotografiska, October 2017

Höstsalongen

The traditional fall salon. My friend Ylva had an exhibit with pictures from Yakutsk. Other than that there wasn’t that much that stood out, apart maybe some tiny, almost contact-print sized photos from a horse race in Ireland taken with a panoramic camera.

Last Night in Sweden

A photographic counterpoint to El Trumpo’s blathering about imagined happenings in Sweden during last year’s presidential campaign.

Viviane Sassen — UMBRA

Arty stuff, but some decent bits among the dross.

Saturday, 2017-09-30

Tuesday, 2017-09-26

Dissing Disqus

I’ve removed the Disqus integration as I almost never get any comments anyway. If you have a comment, ping me on Twitter.

Thursday, 2017-08-31

August

Hammarby kaj

Aug 2016 | Aug 2015 | Aug 2014 | Aug 2013 | Aug 2012 | Aug 2011 | Aug 2010 | Aug 2009

Saturday, 2017-08-26

The Politics of Bitcoin: Software as Right-Wing Extremism by David Golumbia

A good overview of some of the weirder ideological views behind Bitcoin, and internet libertarianism in general.

While I’m sure there’s a lot of background to get if you follow the sources, the book itself makes a lot of assumptions about the reader’s own political stances, which are assumed to be more or less the same as the author’s.

Friday, 2017-08-25

Two books on the Korean War

This Kind of War by T.R. Fehrenbach

The Coldest Winter: America and the Korean War by David Halberstam

These books are good read together. Fehrenbach’s, written in the 1960s, is better at describing the actual course of the war , while Halberstam excels in the top-level politicking between Truman and MacArthur.