Advent of Code 2022 — Day 1 (Elixir)

I’m a massive fan of the Elixir programming language. I like its terse, easily-comprehended prose and elegant concurrency model.

So I decided to solve all of the Advent of Code problems with it.

Photo by FLY:D on Unsplash

Table of Contents | Advent of Code Day 2

Let’s start with Day 1.

Day 1 introduces us to the theme of Advent of Code. I’ve never participated before this year, so it was new to me. Perhaps it’s not to you, but I’ll spend a bit of time talking about it anyways.

The event’s setting and theme revolve around Santa and his elves, and we are solving problems that his elves need help in solving. This year, they are trekking through a jungle to find their favorite fruit in the only grove in which it grows. Not sure where they were able to find this jungle so close to the North Pole and Santa’s Workshop, so I imagine Santa is hiding some teleportation tech from us.

Anyways. You can find our Day 1 problem here: https://adventofcode.com/2022/day/1

Our first day on this trek through the jungle has our little elven friends counting the calories stored in each of their meals. Each elf has multiple meals consisting of things elves eat. I won’t hazard a guess at what they’re eating besides “various meals, snacks, rations, etc,” which is also where Advent of Code’s description of their diet trails off.

Our elves have compiled each of their calorie lists into a single input file. Your elves will have different meals from my elves, and we may even have a different number of elves, so you will not be able to collaborate with any other Advent of Code participants. Again, I am new to this annual event, so I’m glad that cheating is a consideration.

This list they’ve created looks something like this:

1000
2000
3000

4000

5000
6000

7000
8000
9000

10000

Of note, the sample input and your problem’s input will contain \n line endings. If you save this text/file to a Windows machine, there’s a chance that your IDE will automatically format the line endings to \r\n. We’ll need to account for this in our solution.

Per line, we are given one meal’s calories. Empty lines tell us that the current elf’s meals are all listed and a new elf is starting to list theirs.

The first elf has meals of 1000, 2000, and 3000 calories. This elf’s calorie total is 6000.

The second elf carries only 4000 calories. Tough break, friend. I don’t know how anyone can survive a trek through a jungle with only one meal.

The third elf carries meals of 5000 and 6000, totaling 11000 calories.

And so on.

Since it’s our first day, we need to create a new Elixir project with its compiler mix. Let’s break out the terminal first:

mix new advent_of_code

Elixir is a compiled language. Its compiler looks in the my_new_project/lib/ directory for source code to compile. Creating a new project with mix new will create this directory for us.

I’m going to open my new folder advent_of_code with VSCode, my preferred code editor. Now, we can attack our problem in a subdirectory of lib/ just for Day 1, lib/day01/. I am going to download my input from the website and save it as the file lib/day01/input.txt.

Let’s start attacking the problem in lib/day01/day1.ex. Our first function will read our input file and separate the text input into a list of lists:

defmodule AdventOfCode.Day1 do
  def chunk_input do
    (__DIR__ <> "/input.txt")
    |> File.read!()
    |> String.split(~r/(\r?\n){2}/)
    |> Enum.map(&String.split(&1, ~r/(\r?\n)/, trim: true))
  end
end

Let’s talk about it.

String concatenation in Elixir uses the <> operator. We concatenate the current directory of the file and our input file’s path relative to that directory to form the file path lib/day01/input.txt. Then we pipe our file path to File.read!(). This is the same as calling File.read!(__DIR__ <> "/input.txt").

In fact, none of these pipes are necessary for our code to work properly. But they are necessary if you want readers to read your code like a book. Pipes allow us to write code where each line is read left-to-right, wrapping to the next line if there is text there.

Let’s compare the same in JavaScript’s right-to-left (you can also consider this inner-to-outer) style of reading:

def chunk_input do
  Enum.map(
    String.split(
      File.read!(__DIR__ <> "/input.txt"),
      ~r/(\r?\n){2}/
    ),
    &String.split(&1, ~r/(\r?\n)/, trim: true)
  )
end

The second version has us mentally re-reading the commas and parentheses. Enum.map() is not our first function call — it is our last. Likewise, File.read!() is our first function, but it is the 3rd function call in this block of code. While this code is perfectly readable for a subset of programmers and does the exact thing as the piped example, I will prefer to use pipes whenever possible. They’re simply better.

Now that my rant on pipes is done, let’s talk about what our chunking does:

After we read our file, we split with a match to the regular expression (\r\n?){2}. The regex exactly matches the following line breaks: \r\n\r\n and \n\n. This will appropriately handle our empty lines separating each elf’s input for Mac or Windows. And because our operating systems do not like mixing line breaks, we will not have to worry about matching \n\r\n or \r\n\n.

This separates our text input into a string list:

["1000\n2000\n3000", "4000", "5000\n6000", "7000\n8000\n9000", "10000\n"]

Our last item “10000” shouldn’t have a line break, but it does. This is because your problem input will contain a trailing newline that is blank. This will not match the (\r?\n){2} regular expression as there’s only one newline. So we use the handy trim keyword to remove that trailing newline in our pipe to Enum.map(&String.split(&1, ~r/(\r?\n)/, trim: true)).

Again, we split on the regular expression (\r?\n) to extract just the numbers:

[
  ["1000", "2000", "3000"],
  ["4000"],
  ["5000", "6000"],
  ["7000", "8000", "9000"],
  ["10000"]
]

Hello gorgeous list of lists! As our last step for our first problem of day one, we need to sum each of these lists and find the largest calorie total. Let’s start by creating our solution pipeline:

def solution1 do
  [count | []] =
    chunk_input()
    |> count_calories()
    |> get_from_top(1)
  count
end

And let’s go ahead and define our counting algorithm:

def count_calories(elf_calories, elf_sums \\ [])
def count_calories([], elf_sums), do: elf_sums

def count_calories([elf | elf_calories], elf_sums) do
    elf_sum =
      elf
      |> Stream.map(&String.to_integer/1)
      |> Enum.sum()

    count_calories(elf_calories, [elf_sum | elf_sums])
  end

Let’s talk about it.

Elixir allows “destructuring” of a list or an object much like ES6 JavaScript, except it’s actually more powerful. This is called pattern matching.

Let’s look at regular variable assignment using the = operator.

foo = "bar"

Not much explanation needed — it assigns a value on the right to the variable on the left, right?

Well, not exactly. You see, this is actually a pattern match too, not a variable assignment. The pattern foo is not defined, so our compiler allows any value to be bound to the pattern. This pattern is analogous to a JavaScript assignment without destructuring, but we’ll get into some destructuring examples in due time.

When foo is defined, the = operator’s behavior is a bit more explicit:

foo = "bar"
"baz" = foo
# ** (MatchError) no match of right hand side value: "bar"

Okay, well this isn’t super helpful. Why doesn’t it say SyntaxError: cannot assign to literal like Python when you try these same statements?

Because “baz” is a pattern, not a literal. We can pattern match any 2 patterns together, like so:

foo = "bar"
"bar" = foo
# prints "bar"

Let’s talk about pattern matching a list next, since our solution relies on them to function properly. List can be pattern matched by fixed length or by variable length:

[a, b, c] = [1, 2, 3]
# a = 1, b = 2, c = 3
[head | tail] = [1, 2, 3]
# head = 1
# tail = [2, 3]

Pattern matching a fixed length list looks very similar to ES6 JavaScript’s array destructuring. This fixed length pattern matching will fail if we do not exactly match the length of the list we’re given, which you know is not a great way to keep code from rotting if you’ve used lists in other languages before. They’re designed for variable lengths, and if a list is assigned a fixed length, it should be a tuple , not a list. Except for you, JavaScript, since you don’t even have tuples.

[a, b, c] = [1, 2, 3, 4]
# ** (MatchError) no match of right hand side value: [1, 2, 3, 4]

What do we do to match a list of variable length?

We use [head | tail] pattern matching. Head and tail will sound familiar if you’ve used singly linked lists in other languages. Lists in Elixir are designed to preserve memory as much as possible, as all data is immutable. This allows you to iteratively build a list through enumeration or recursion:

mylist = []
mylist = [3 | mylist]
mylist = [2 | mylist]
mylist = [1 | mylist]

Our tail, i.e. the rest of our list apart from the first element, will be [] for our first insertion into the list. That makes sense — there’s nothing else in the list except the first element, so the “rest” or tail would be an empty array.

Our tail the second time is the list [3] . The array [3] is already in memory, and it’s not going away until our garbage collector handles it. So let’s reuse it by saying our new array is a single element and the rest of the list is already defined in memory: [2 | mylist] (or [2 | [3]] ).

Hopefully, you’re beginning to see the power of Elixir lists. You can think of our Elixir singly linked lists as last-in-first-out (LIFO) queues. Concatenating 3 then 2 then 1 creates the list [1, 2, 3] (or [1 | [2 | [3 | []]]] ).

So how do we pattern match it? Let’s demonstrate using our count_calories function clauses:

def count_calories(elf_calories, elf_sums \\ [])
def count_calories([], elf_sums), do: elf_sums

def count_calories([elf | elf_calories], elf_sums) do

Recognize the [head | tail] syntax?

Q: Are the arguments of a function variables or patterns?
A: They’re patterns!

So you can pass in literals like [] , and only the function branch count_calories([], elf_sums) will respond. This is awesome for base cases like when a list has no more items. Let’s explain our count_calories() with this information in hand.

def count_calories(elf_calories, elf_sums \\ []) is our function header. In C/C++, a function header is a stub that describes how many parameters a function has, what type those parameters are, and what type the function returns. In Elixir it’s much the same. This function that lacks the do keyword will never be called. It simply describes the function, and most of the time they aren’t needed. In select cases mix will warn you to add a function header, which is why it’s included here.

def count_calories([], elf_sums), do: elf_sums is our base case. When there are no more items in the list and the function is passed the empty list, return our elf_sums aggregator. This would be analogous to defining the function like so in JavaScript:

function count_calories(elf_list, elf_sums) {
  if (Array.isArray(elf_list) && elf_list.length === 0) {
    return elf_sums;
  }
  // and then the rest of the algorithm is after the base case check
}

Except we simply define how a function respond to our input. No if statements necessary!

Lastly, we have the actual recursive algorithm function branch:

def count_calories([elf | elf_calories], elf_sums) do
  elf_sum =
    elf
    |> Stream.map(&String.to_integer/1)
    |> Enum.sum()

  count_calories(elf_calories, [elf_sum | elf_sums])
end

We start by pattern matching our list. We bind the current list we’re working on to the elf variable and the rest of our list of lists to elf_calories. This acts as a JavaScript .pop(). Remember that elf_calories is not already defined, so any value can be bound to it so long as the entire pattern matches.
This branch will capture the cases where we have 2 or more items in the list: [[“1000”, “2000”, “3000”] | [[“4000”] | [[“5000”, “6000”] | rest]]]
As well as having exactly one elf still in the list: ["10000" | []]

The rest of the algorithm is straightforward recursion. We push our elf_sum to the elf_sums list, then we recurse until all elves in the elf_list have been processed.

Lastly, let’s talk about get_from_top(). This function takes an unsorted list of elf calorie totals and an integer parameter n to take from the highest once the list is sorted:

def get_from_top(elf_sums, n \\ 1) do
  elf_sums
  |> Enum.sort(&(&2 < &1))
  |> Enum.take(n)
end

As our last step in Problem 1 of Day 1, we sort our list in descending order with the function capture &(&2 < &1) (this is effectively saying fn num1, num2 -> num2 < num1 end but without allocating memory for a useless function wrapper), then we take n highest total calorie counts from the sorted list.

Let’s go back to our solution1() function. Enum.take() returns a list, so we pattern match to get only the single highest number:

def solution1 do
    [count | []] =
      chunk_input()
      |> count_calories()
      |> get_from_top(1)

    count
  end

This concludes our code for Problem 1. Let’s compile our code:

iex -S mix

This starts an interactive REPL session with our application code compiled and ready for us to start using. Executing the following Elixir statement gives us our solution to Day 1, Problem 1:

AdventOfCode.Day1.solution1
# 24000

Problem 2 requires minor changes to the solution in solution1 because we’ve designed our code to be enumerable. It will be solved much quicker.

Let’s get to work on Problem 2:

def solution2 do
  chunk_input()
  |> count_calories()
  |> get_from_top(3)
  |> Enum.sum()
end

Because we’ve crafted our code using recursion and enumeration, we can simply get the top 3 calorie counts instead of the top 1, and then sum the returned list.

Recompile the code and execute in the Elixir REPL session:

AdventOfCode.Day1.solution2
# 45000

Source code for this article can be found at https://github.com/benjamindburke/advent-of-code-2022/blob/main/lib/day01/day1.ex.

This is Day 1 of my series on Advent of Code 2022. You can find the Table of Contents here: https://talesoffullstack.medium.com/advent-of-code-2022-dcac87b26b35
For more entries of Advent of Code and other topics, please follow me on Medium at https://talesoffullstack.medium.com/

Your support helps me decide whether this content is helpful and informative, and your feedback also helps me create better, more in-depth articles. If you liked this article, please consider leaving a clap or a comment!