While tackling the Day 1 challenge from this year's Advent of Code in Elixir, I was reminded of some of the many ways that Elixir let's us write concise, efficient, and eloquent code. In this post, I break down my solution and dive into how you can use recursion, pattern matching and custom guard clauses to implement even complex logic and control flow in an easy-to-reason about way that also avoids common time complexity pitfalls.
Advent of Code Challenge
Advent of Code is...
...an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.
You can complete Advent of Code challenges in any language and submit your answers to "win" stars :star: :star: :star:
It's a fun way to play around with a new language that you're just starting to learn or to refine your skills in a language that you're already familiar with.
After being pestered kindly reminded about it by someone who is definitely not annoying, I decided to try out the Day 1 puzzle in Elixir.
I had a lot of fun putting my solution together and, unsurprisingly, I found that Elixir's features allowed me to implement even complex logic and control flow in a way that was remarkably concise, as well as efficient with regards to time complexity. Keep reading to see how to leverage pattern matching, recursion and custom guard clauses to write some super clean and extremely elegant Elixir code. :soap: :star: :soap:
The Prompt
The Day 1 Advent of Code prompt can be simply stated as:
Find the two elements in a given list that sum to 2020 and return the product of those two numbers.
For example, of the following list:
[979, 1721, 366, 299, 675, 1456]
,
1721 + 299 == 2020
, and1721 * 299 = 514579
.
So, your code should return
514579
Attempt 1: Lots of Iterating
Before writing any code, I attempted to conceptualize my approach. The first conceptualization that jumped out at me was heavily reliant on iteration and went something like this:
- Iterate over the list
- For each element in the list, iterate over the remaining elements in the list
- For each pair of elements, add them up. If the sum equals 2020, stop.
- If the sum does not equal 2020, keep going
So, taking the example of our list from above, it would look something like this:
- Does 979 + 1721 = 2020? Nope!
- Does 979 + 366 = 2020? Nope!
- Does 979 + 299 = 2020? Nope!
- Does 979 + 675 = 2020? Nope!
- Does 979 + 1456 = 2020? Nope!
Okay, move on to the second element in the list...
- Does 1721 + 366 = 2020? Nope!
- ...
This approach uses nested iteration and is not very efficient. For each item in the list you have to iterate over the remainder of the list and execute the check to see if the two numbers sum to 2020
. In other words, the outer loop executes N times, once for each element in the list. And every time the outer loop executes, the inner loop executes M times, where M is however many steps it must complete to check the current outer loop element against the remaining list elements. As a result, the "check to see if the two numbers sum to 2020
" statement executes a total of N * M times.
So, the number of operations your code has to do will grow exponentially for each element added to the list. This represents a high degree of time complexity. Thanks to Elixir, we can do better.
We'll use recursion and pattern matching to avoid the need to perform ๐ธ ๐ธ ๐ธ expensive nested iterations ๐ธ ๐ธ ๐ธ. Keep reading to find out how!
Attempt 2: Pattern Matching and Recursion
Once I recognized the time complexity of the "lots of iterating" approach, I knew I needed to cut down on iterations. Luckily, Elixir provides us a way to pull elements from a list without iterating over that list--pattern matching. In the next section, we'll use pattern matching and recursion to peel off list elements and perform out "sum to 2020
" check on them.
Efficient Code with Pattern Matching
First, let's walk through how Elixir's pattern matching can be applied to list elements such that we can perform our "check if sum is 2020
" statement against all of the list elements, without iterating. This will give us the ability to solve our Advent of Code problem with code that is not overly time-complex.
Pattern Matching List Elements: The Concept
In order to illustrate how we can use pattern matching in this way, let's focus on the goal of checking to see if the first element in our list, plus any other element in the list, equals 2020
.
With Elixir's pattern matching, we can separate out list elements into a "head", i.e. the first element, and a "tail", i.e. everything after the first element.
Something like this:
iex> [head | tail] = [1, 2, 3]
iex> head
1
iex> tail
[2, 3]
Using this approach, we can match a variable to the first list element, the second list element, and then everything else like this:
iex> list = [979, 1721, 366, 299, 675, 1456]
[979, 1721, 366, 299, 675, 1456]
iex> [first | [second | rest] = tail] = list
[979, 1721, 366, 299, 675, 1456]
iex> first
979
iex> second
1721
iex> rest
[366, 299, 675, 1456]
iex> tail
[1721, 366, 299, 675, 1456]
In this way, we can establish a variable, first
, set equal to the first list element, and another variable, second
, bound to the value of the second list element.
Then, we can check if the sum of these two numbers equals 2020
. If so, great! We're done.
If not, we can construct a new list using the same first element, and the list remainder stored in rest
, cutting out the second element entirely.
Like this:
iex> new_list = [first | rest]
[979, 366, 299, 675, 1456]
Now, we can repeat the step above to see if the first element in the list plus the new second element in the list equals 2020
:
iex> [first | [second | rest]] = new_list
[979, 366, 299, 675, 1456]
iex> first
979
iex> second
366
From here, we repeat the process. Does first + second == 2020
? If so, great! We're done. If not...construct a new list using the same first element, and the list remainder stored in rest
.
Eventually, if the first element cannot be added to any other list element to get the sum of 2020
, then we end up with a list that contains only one element. We'll have cut out all the other elements until only the first element remains.
What do we want to do then? We want to revisit the initial starting list and pick up with the second element there. The tail of the original list will be a list that starts with the original list's second element.
In other words, if our original list read [979, 1721, 366, 299, 675, 1456]
, and we didn't find any other number added to 979
to equal 2020
, then the tail of that list should read:
[1721, 366, 299, 675, 1456]
We already matched a variable, tail
to the original list's tail above, like this:
iex> list = [979, 1721, 366, 299, 675, 1456]
[979, 1721, 366, 299, 675, 1456]
iex> tail
[1721, 366, 299, 675, 1456]
So, using the list stored in the tail
variable, we can simply repeat the process described above.
Now that we have a basic understanding of what we need to do, let's write some code.
Pattern Matching List Elements: The Code
We'll define a module Accountant
, that implements one public function, product_of_equals_twenty_twenty
. This function will take in a list and return the product of the two numbers in the list that sum to 2020
. The public interface of our module will work like this:
Let's begin implementing it now.
The function head will use pattern matching to pull out the tail of the list and save it for later in a variable, tail
. Then it will pass the list to a helper function that is responsible for stepping through the process we described above. Let's revisit that process now by taking a closer look at get_two/1
.
Pattern Matching Function Heads
We'll implement a few versions of the get_two/1
function that use pattern matching in the function head to determine how to behave. We'll also see recursion make a guest appearance. Let's take a look!
Let's examine each of the versions of this function. Some of this code should look familiar from our discussion of pattern matching list elements above. One function version pattern matches the first and second elements of the list and uses a guard clause to check if they sum to 2020
. More on guard clauses in a bit.
If the first and second list element do sum to 2020
, then the function body will execute and return the product of the two numbers.
If the first and second list element do not sum to 2020
, i.e. if our guard clause does not evaluate to true
, then we hit the next version of the function implementation:
Here, we build a new list constructed from the first list element and the remainder of that list, minus the second element. That new list is given as an argument to a recursive call to get_two/1
. This will continue until we either hit the guard clause and return the product of the two elements. Or, until we have removed every element after the first one, resulting in a list with a length of 1
. In that case, we will return nil
:
So, we have a function that, when invoked with a given list, will call itself recursively until it finds two elements that sum to 2020
--in which case it returns their product--or until there is only one list element left--in which case it returns nil
.
By calling get_two/1
with the list [979, 1721, 366, 299, 675, 1456]
, we will have successfully checked to see if 979
plus any other number in the list equals 2020
.
This brings us back to the public function, product_of_equals_twenty_twenty/1
. If this first invocation of get_two/1
returns something that is not nil
, then we're done! We found the product of the two numbers that sum to 2020
. Let's implement some logic to that effect now:
If the first get_two/1
invocation does not return a number and does return nil
, we need to start the whole process again, this time with the tail end of our original list.
This will restart the process, this time with a list that reads: [1721, 366, 299, 675, 1456]
. Once again, our code will try to sum each number with the first list element, this time 1721
. If it returns some product, then we're done! If not, we'll keep invoking product_of_equals_twenty_twenty/1
with the next list tail, and the next, until we find what we're looking for.
To wrap up this code, we'll add a function head for product_of_equals_twenty_twenty/1
that can handle being invoked with an empty list--that is what will happen if our list does not contain any two numbers that equal 2020
and we continue to invoke product_of_equals_twenty_twenty/1
until we have a tail that is empty.
Putting It All Together
Putting all together, our code reads:
Our code works, and it's highly efficient. We're never iterating over the list, never mind iterating over it in a nested fashion. Instead, we are recursively pulling the first and second elements off of a list, and shrinking the list each step of the way.
This looks pretty clean, but I think we can do even better. Anytime I see an if
condition in Elixir, I wonder if I can replace it with recursion and pattern matching. Elixir allows us to combine recursion and pattern matching into an elegant solution for control flow. Could we implement product_of_equals_twenty_twenty/1
such that it can handle the case of a "found product"? Let's give it a shot!
Clean Control Flow with Pattern Matching and Recursion
We'll take a similar approach here to the one we used with our get_two/1
implementation. A set of function heads will use pattern matching to determine how to behave. One such function will leverage recursion to continue code flow, while other function heads will determine when the code will stop executing and return. In this way, Elixir pairs recursion and pattern matching to implement control flow--without if
conditions or while
loops.
Let's take a look.
We've changed the arity of product_of_equals_twenty_twenty
to take in two arguments. The second argument will be the product of the two numbers that sum to 2020
, and it will default to nil
.
So, when our function is invoked with a list,
The product
argument evaluates to nil
, and we find ourselves in this version of our function:
Here, we kick off the process by recursively invoking product_of_equals_twenty_twenty/2
with the tail of the original list and the result of calling get_two/1
with the original list.
If get_two/1
returns a product that is not nil
, then we'll find ourselves in this other version of the product_of_equals_twenty_twenty/1
function:
In which case, we break out of our recursive function calls, stop code execution, and return the product.
Let's step through this code in detail.
- The user calls
Accountant.product_of_equals_twenty_twenty([979, 1721, 366, 299, 675, 1456])
At this point, we hit this function,
where list
evaluates to [979, 1721, 366, 299, 675, 1456]
, tail
is set to [1721, 366, 299, 675, 1456]
and product
is nil
.
get_two/1
is called with thelist
- Since
979
is not one of the numbers that sums to2020
, this call returnsnil
. - So, we call
product_of_equals_twenty_twenty/2
withtail
andnil
- This brings us back to this same function body:
This time around, list
is equal to [1721, 366, 299, 675, 1456]
, tail
is [366, 299, 675, 1456]
and product
is still nil
get_two/1
is called with thelist
- Since
1721
plus299
does equal2020
, this will return the result of1721 * 299
, which is514_579
- So, we call
product_of_equals_twenty_twenty/2
willtail
and514_579
. - This brings us to this other function body:
So, we stop recursing, code execution is done, and the product is returned.
Phew! Seems like a fair amount of complexity, but when we put it altogether, we see some very clean and concise code.
In just about a dozen lines of code, we've implemented an efficient, iteration-free solution--all thanks to the beauty of Elixir's pattern matching. By pattern matching list elements, we were able to avoid expensive iterations. By using pattern matching in function heads, along with recursion, we were able to implement control flow that didn't rely on if
conditions or while
loops.
Before we go, we'll do just a bit more refactoring for readability with the help of custom guard clauses.
Refactoring with Custom Guard Clauses
Guard clauses allows us to apply more complex checks to pattern matching function heads. We're using a number of guard clauses throughout our code, for example:
Here, we've implemented a version of the get_two/1
function that will execute if the length of the provided list
argument is equal to 1
.
Guard clauses give us even more fine-grained control over which code to execute under which conditions. This is yet another way that we can handle complex control flow without verbose and hard-to-reason-about if
and nested if
conditions.
Only a certain set of expressions are allowed for usage in guard clauses, see docs here. But, we can define custom guard clauses to wrap up more complex guard logic. The guard clause we wrote to check if two numbers sum to 2020
is a great candidate for a custom guard clause. By wrapping up that logic in a custom guard clause, we can name the concept to make it easier to read and reason about.
To define a custom guard clause, we'll use the defguard
macro:
Now, we can use our guard clause like this:
Custom guard clauses give us the ability to implement even complex control flow with pattern matching function heads, while keeping our code readable.
Putting it all together:
Elixir Encourages Efficient and Eloquent Code
By using Elixir's pattern matching against our list of numbers, we were able to write efficient code that avoided the time complexity of expensive nested iterations.
By using that same pattern matching feature, paired with guard clauses and recursion, we were able to implement control flow in a way that is ๐งผ clean ๐งผ and ๐ฃ eloquent ๐ฃ. The code speaks for itself by being readable and easy to reason about. No messy, nested if
conditions to deal with.
This Advent of Code challenge really shows off some of Elixir's simplest, but most powerful features.