Advent of Gleam

Advent of Code solutions in Gleam.

Why

• Gleam is fun
• I ran out of Gleam exercises on Exercism

Running locally

1. Install Gleam
2. Run all tests:

   gleam test

   Or start watch mode (possible thanks to Glacier):

   gleam test -- --glacier

   Or run a single day's tests (this too is possible thanks to Glacier):

   gleam test -- test/year_2023/day_01_test.gleam

About puzzle inputs and tests

The tests use the example inputs from adventofcode.com.

To also use your own puzzle inputs, create e.g. test/year_2023/day_01_input.txt (ignored by Git). Though note that the test assertions use my personal results (your results will be different with your own puzzle inputs).

Solutions

• year_2023/day_01.gleam × adventofcode.com/2023/day/1

• year_2023/day_02.gleam × adventofcode.com/2023/day/2

• year_2023/day_03.gleam × adventofcode.com/2023/day/3

• year_2023/day_04.gleam × adventofcode.com/2023/day/4

  Part 2 was silly (i.e. fun), and I like how simple my number_list_to_numbers function turned out.

• year_2023/day_05.gleam × adventofcode.com/2023/day/5

  Part 2 was tough.

  With my puzzle input, there are 1,638,141,121 seed numbers.

  Iterating over the seed numbers one by one would take an eternity.

  I tried to parallelize the iterations with OTP Tasks, but that still took too long – about 3 minutes on my machine.

  Eventually I realized to iterate over number ranges instead of single numbers. Now Part 2 runs in less than 0.02 seconds (on my machine).

  But I'm glad I tried the parallelization route, as it made me start learning that OTP stuff (using Benjamin Peinhardt's Learn OTP w/ Gleam repo).

• year_2023/day_06.gleam × adventofcode.com/2023/day/6

• year_2023/day_07.gleam × adventofcode.com/2023/day/7

  I'm quite pleased with the approach I came up with: calculating the rank of a hand type by counting the number of different cards, and calculating the rank of cards by handling the cards as (hexadecimal) numbers.

• year_2023/day_08.gleam × adventofcode.com/2023/day/8

• year_2023/day_09.gleam × adventofcode.com/2023/day/9

• year_2023/day_10.gleam × adventofcode.com/2023/day/10

  Ahh, I love how eleganto my solution is.

  Part 2 is impossible (fight me) without specific math knowledge – which I didn't have, so I had to do some digging.

  At first I tried to loop over all points not on the path and check if each point is inside or outside the path. Based on Point in polygon on Wikipedia, I tried a ray casting algorithm.

  Well, it didn't work, so I went to /r/adventofcode to look for spoilers. I found two curious terms:

  • Shoelace formula on Wikipedia
  • Pick's theorem on Wikipedia

  A-ha, so instead of looping over all non-path points, I need to treat the path as a polygon, and then calculate the polygon's area, and then subtract the amount of boundary (non-interior) points from the area... who would have thought!

• year_2023/day_11.gleam × adventofcode.com/2023/day/11

• year_2023/day_12.gleam × adventofcode.com/2023/day/12

  I managed to get Part 1 (with example input + full input) and Part 2 (with only example input) to run in about 0.07s (on my machine).

  Then I struggled in Part 2 with full input.

  TL;DR: The secret ingredient I was missing is memoization.

  It was not a new concept to me, but implementing memoization in a functional language with immutable data structures felt like a mystery.

  And it still feels like it, but luckily I found rememo which implements memoization with "Erlang Term Storage" (whatever that is) and is a breeze to use.

  After adding memoization with rememo, the run time for Part 2 with full input dropped from eternity to about 0.43s.

  Parallelizing the work with OTP Tasks dropped the run time further to about 0.15s.

  Running both parts, with example input + full input, takes about 0.18s on my machine. Not bad!

  When looking for help, I liked David Brownman's step-by-step explanation for 2023/12. Reading that page helped me simplify my code a bit.

  Three interesting alternative approaches that I found via the 2023/12 megathread on /r/adventofcode:

  • Dynamic programming approach in Rust
  • "Using DFA (Deterministic Finite Automata) to turn an exponential problem to a linear one"
  • Another DFA solution/explanation

  I don't understand any of those ("dynamic programming"? "DFA"?), but I'm putting these links here for future reference.

• year_2023/day_13.gleam × adventofcode.com/2023/day/13

  This felt very easy after day 12. :P

  Runs in 0.022s on my machine, so I won't bother optimizing this further.

• year_2023/day_14.gleam × adventofcode.com/2023/day/14

  1. Rotate the platform 90 degrees to the left.
  2. North is on the left, south is on the right.
  3. ???
  4. Profit!!

  I.e. by rotating the platform back and forth, the rocks need to be rolled only horizontally, which is much easier than rolling them vertically.

  The constant rotations take their toll though; the tests run in about 295ms on my machine. (Actually I don't know if the rotations are the bottleneck.)

  On the other hand, I was stuck at about 470ms for many hours (!), so in the end I'm quite pleased in my sub-300ms result.

  Two things helped me break the 300ms barrier:

  • Mapping the string values (#, O and .) to a custom type (Boulder, Rock and Space) lowered the run time from 470ms to 370ms. This surprised me – maybe custom types are cheaper to compare etc. than strings. But 100ms seems still very much.
  • Optimizing the rolling algorithm lowered the run time from 370ms to 295ms. I'm quite proud of this new rolling algorithm which uses queues. This could come in handy in the future if other days' puzzles require similar "sorting" of a few kinds of items.

  With strings (instead of the custom type) and the new rolling algorithm, the run time difference is 40ms (i.e. 295ms vs 335ms). Less than 100ms, but the difference is still surprisingly large.

  So today's lesson: mapping strings to custom types can give a surprising speed boost.

  I tried another approach as well: turning the platform into a map (Dict(Coord, Item)) and iterating over each row and column one-by-one. So no platform rotations, but a test run still took over 700ms (IIRC) – a poor result, which I attribute to Gleam's immutable data structures. (Mutating lists/arrays could maybe be significantly faster.)

• year_2023/day_15.gleam × adventofcode.com/2023/day/15

• year_2023/day_16.gleam × adventofcode.com/2023/day/16

  Like day 10 – walking on a map – but now with multiple, overlapping, potentially looping paths.

  I dislike that running the tests takes about 380 ms (that's slow).

  But I like that I came up with the deferred "trick" to keep the walk function tail-recursive.