Insights from Advent Of Code (Week 1)

in elixir, ruby, perl

My first week solving advent of code has almost ended, which makes it a good time to reflect on the quizzes, my solutions and other solutions I found online.

tl;dr

Advent of Code is a series of coding quizzes delivered daily during December. Project website is: https://adventofcode.com

  1. AOC turned out to be a very nice way to learn a new programming language (I'm learning Elixir).

  2. Most puzzles are very easy, as seen in the leaderboard times.

  3. Practising a short coding quiz every day helped me learn a new language better than just reading about these concepts.

Day 1 - Inverse Captcha

I actually missed the first 2 days of the game and only remembered it was on in day 3. That wasn't too bad though, as they were really easy anyway.

I used regular expressions for both parts 1 and 2 and found it a nice reminder to how useful they always are.

Both parts in perl:

use v5.18;
use warnings;
use List::Util qw/sum0/;

while(<>) {
  chomp;
  my $len = length;
  my $step = ($len / 2) - 1;
  my $input1 = $_ . substr($_, 0, 1);
  my @digits1 = ($input1 =~ /([0-9])(?=\1)/g);
  say sum0(@digits1);

  my $input2 = $_ . substr($_, 0, $len / 2);
  my @digits2 = ($input2 =~ /(.)(?=.{$step}\1)/g);
  say sum0(@digits2);
}

Day 2: Corruption Checksum

Having split, max, min and sum0 in the language really simplifies the code. But it was still fun and would make a nice exercise in any programming course. Still perl of course. It'll take another day to switch.

use v5.18;
use warnings;
use List::Util qw/sum0 max min/;

my $sum1 = 0;
my $sum2 = 0;

while(<>) {
  chomp;
  my @row = split;
  $sum1 += max(@row) - min(@row);
  for (my $i=0; $i < @row; $i++) {
    for (my $j=0; $j < @row; $j++) {
      next if $i == $j;
      $sum2 += $row[$i] / $row[$j] if $row[$j] != 0 && $row[$i] % $row[$j] == 0;
    }
  }
}

say $sum1;
say $sum2;

Day 3: Spiral Memory

This is the first one I actually spent some time thinking about. I tried (and failed) to find the clever math solution. Only later after I looked at the solutions megathread I realized how close I was and what needed to be done.

In any case after failing to find the clever solution I went with a brute force ruby code. This was my longest (and ugliest) solution of the week:

require 'pp'

class Board
  attr_accessor :matrix

  def initialize
    @matrix = [{ x: 0, y: 0, val: 1 }]
  end

  def set(x, y)
    matrix.push(x: x, y: y, val: sum_neighbors(x, y))
  end

  def sum_neighbors(x, y)
    matrix
      .select { |item| (item[:x] - x).abs <= 1 && (item[:y] - y).abs <= 1 }
      .map { |item| item[:val] || 0 }
      .reduce(&:+)
  end
end

class Counter
  attr_accessor :sign, :group
  attr_accessor :counter
  attr_accessor :distance

  def initialize
    self.counter = 0
    self.group = 0
    self.sign = 1
    self.distance = { r: 0, u: 0 }
  end

  def step
    if counter.zero?
      self.group += 1
      self.counter = group * 2
      self.sign = -1 * sign
    end

    if counter <= group
      distance[:u] += sign
    else
      distance[:r] += sign
    end
    self.counter -= 1
  end
end

val1 = ARGV.shift.to_i - 1
val2 = ARGV.shift.to_i

# Part 1
c = Counter.new
val1.times do
  c.step
end
puts c.distance[:r].abs + c.distance[:u].abs

# Part 2
b = Board.new
c = Counter.new

loop do
  c.step
  b.set(c.distance[:r], c.distance[:u])
  break if b.matrix[-1][:val] > val2
end

puts b.matrix[-1][:val]

In part 1 I wrote a Counter class that calculates (x,y) coordinates for each step. Later in part 2 it was easy to add a Board class that remembers which squares were calculated and calculates the next by summing all the neighbors.

I later thought I could use that Board approach from the beginning to calculate the next square's coordinates. For example when moving right one could look "up" and continue moving right until you find a free square above. I never did that refactoring though because new days brought new quizzes.

Day 4 - High-Entropy Passphrases

Day 4 is when I realized if I want to learn something from this game I better pick a new language. Level was back to fizz-buzz style games so it shouldn't be too hard. I picked Elixir and from here all my solutions are written in it (hope I'll be able to continue this till the end of the month).

defmodule Day4 do
  def count1(line) do
    words = String.split(line)
    MapSet.size(MapSet.new(words)) == length(words)
  end

  def count2(line) do
    words = String.split(line)
            |> Enum.map(fn(word) ->
              String.split(word, "", trim: true)
              |> Enum.sort
              |> Enum.join("")
            end)
    MapSet.size(MapSet.new(words)) == length(words)
  end
end

IO.stream(:stdio, :line)
|> Enum.map(&Day4.count2/1)
|> Enum.filter(fn(x) -> !!x end)
|> Enum.count
|> IO.puts

I used a MapSet to find duplicates and checked each line's unique word count to see if it's a valid passphrase. I learned to use String.split with trim to remove blanks. I also learned elixir's way to read from stdin.

Day 5: A Maze of Twisty Trampolines

In day 5 I learned about elixir's strange performance issue: Being an immutable language means it has no efficient way to mutate a vector.

Following some advice in elixir subreddit I eventually learned to use a hash map with increasing numbers as keys (and values are the things in the "vector") to emulate a vector. This has allowed running part 2 in 12 seconds (instead of 40 using tuples).

In this quiz I also started to use Stream.unfold to create custom streams. This turned out to be a good patterns because it allows one to decouple the quiz logic from the actual question.

defmodule Day5 do
  def list_to_indexed_map(list) do
    list
    |> enum.with_index(0)
    |> enum.map(fn({k,v}) -> {v,k} end)
    |> map.new
  end

  def next({ arr, ip }) do
    try do
      jump = Map.fetch!(arr, ip)
      diff = if jump >= 3, do: -1, else: 1
      {
        arr,
        {
          Map.replace(arr, ip, jump + diff),
          ip + jump,
        }
      }
    rescue
      KeyError -> nil
    end
  end

  def parse(line) do
    Stream.unfold({ line, 0 }, &Day5.next/1)
  end
end

IO.stream(:stdio, :line)
|> Stream.map(&String.trim/1)
|> Stream.map(&String.to_integer/1)
|> Enum.to_list
|> Day5.list_to_indexed_map
|> Day5.parse
|> Enum.count
|> IO.inspect

Day 6: Memory Reallocation

Sticking with Elixir this one uses a lot of the same concepts as day 5: Indexed maps as vectors; streams to represent game logic.

Decoupling the streams made it easy to calculate the loop length in part 2.

defmodule Day6 do
  def next_index(map, index) do
    rem(index+1, map_size(map))
  end

  def redistribute(map, _, 0) do
    map
  end

  def redistribute(map, index, count) do
    redistribute(
      Map.update!(map, index, fn(x) -> x + 1 end),
      next_index(map, index),
      count - 1
    )
  end

  def list_to_indexed_map(list) do
    list
    |> Enum.with_index(0)
    |> Enum.map(fn({k,v}) -> {v,k} end)
    |> Map.new
  end

  def next(acc) do
    { index, val } = Enum.max_by(acc, fn({_, v}) -> v end)    
    el = redistribute(
        Map.replace(acc, index, 0),
        next_index(acc, index),
        val)
    { el, el }
  end

  def run_till_dup(stream) do
    Stream.transform(stream, MapSet.new, fn(el, acc) ->
      if MapSet.member?(acc, el) do
        { :halt, acc }
      else
        { [el], MapSet.put(acc, el) }
      end
    end)
  end
end

banks = IO.stream(:stdio, :line)
        |> Enum.at(0)
        |> String.split
        |> Enum.map(&String.trim/1)
        |> Enum.map(&String.to_integer/1)
        |> Day6.list_to_indexed_map

s1 = Stream.unfold(banks, &Day6.next/1)

count = s1
        |> Day6.run_till_dup
        |> Enum.count

count = count + 1

loop_start = s1
             |> Day6.run_till_dup
             |> Enum.at(-1)

loop_count = Stream.unfold(loop_start, &Day6.next/1)
             |> Day6.run_till_dup
             |> Enum.count

IO.puts(count)
IO.puts(loop_count)

Note the second part (the "main" of the program). Having the game logic implemented as streams makes it trivial to run the streams until we reach a certain point, and then continue from that same point to count something else. The second loop takes as its starting condition the last element from the first loop.

All in all it was a fun week. I learned a lot about Elixir. I plan to continue with Elixir hoping to gain a better understanding of the language.

Comments