Advent of Code 2022 – Every Puzzle Solved in Erlang
- Erlang Solutions Team
- 1st Dec 2022
- 93 min of reading time
Contents
Day 1
Christmas is getting closer and with that, the annual Advent of Code begins. For those who do not know, Advent of Code is a fun and inclusive event which provides a new programming puzzle every day. The fun is that these puzzles can be solved in any programming language and are accessible for varying levels of coding experience and skills. The real test is in your problem-solving. This year, we’ll be solving each of the problems in Erlang and publishing the results. We hope you enjoy it – if you’ve come up with a different solution and want to discuss it with us, we encourage you to comment on Twitter.
The code will be added to the repo here: https://github.com/aleklisi/AdventOfCode2022 as I manage to solve each next puzzle.
Day 1
Full problem description: https://adventofcode.com/2022/day/1
The example input file:
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Day 1- Puzzle 1
We are given a file with a list of values for calories in snacks carried by elves. The Elves take turns writing down the number of Calories contained in the various snacks that they’ve brought with them, one item per line. Each Elf separates its own inventory from the previous Elf’s inventory (if any) by a blank line. So the first task is to read and parse the data and decide how to represent it.
I decided to represent the input as a list of two-element tuples, where each tuple stores the elf’s number and a list of snacks. Here is an example data representation for the example file:
[
{1,[1000,2000,3000]},
{2,[4000]},
{3,[5000,6000]},
{4,[7000,8000,9000]},
{5,[10000]}
]
Now we just need to define a max function, which compares elements based on the sum of elements in a list of the calories in the snacks. I assumed that the list of elves is not empty, so I start with its first element as the current max and then started comparisons with other elves. Every time I find an elf with a bigger calorie sum I replace my current elf with the new one so that I will end up with the elf with the highest calorie total. Once the elf with the most calories is found, we can return the sum of calories.
See the code: https://github.com/aleklisi/AdventOfCode2022/blob/main/day1_puzzle1/src/day1_puzzle1.erl#L48-L56 .
Day 1- Puzzle 2
The only difference in puzzle 2 compared to puzzle 1 is that now we need to find 3 elves with the most calories total instead of just 1 elf and sum their calories altogether.
We can heavily rely on solutions from puzzle 1.
To find the top 3 elves I will just:
- Find the elf with the highest calories and save this elf as the first one.
- Remove the first elf from the list of elves.
- Find the next top elf with the highest calories from the list of elves (without the first elf) and save this elf as the second one.
- Remove the second elf from the list of elves.
- Find the next top elf with the highest calories from the list of elves (without the first and second elf) and save this elf as the third one.
- Return the sum of calories of the first, second and third elf.
Voila!
Day 2
Day 2 of Advent of Code sees us helping the Elves to score a game of Rock, Paper, Scissors. The Elves have provided us with a strategy guide and it’s our job to help them score their game.
Day 2- Puzzle 1
To complete the task we need to calculate the results of the above games. Since the games are unrelated (the result of previous games does not impact the next games, the best way to approach the problem is to start by implementing a single game’s score count function and then map a list of games with this function, to get the scores for each of the games. To get the final score (which is a sum of the games’ scores) we then sum all of the elements of the list.
The data structure I decided to use to represent a single game is a two element tuple, where the first element is the opponent’s move and the second element is my move.
The list of games is parsed into something like this:
[{rock, rock},
{scissors, rock},
{scissors, rock},
{scissors, rock},
{paper, paper},
…
]
Looking back (after solving the problem) I could have used maps with a structure like the one below:
#{my_move = > rock, opponent_move => paper}
It might have helped me debug and avoid errors, which I did when first approaching the problem. That error was to confuse my move with my opponent’s move. In other words, I decoded A, B and C to be my moves and X, Y, and Z to be my opponent’s moves. It is an obvious mistake when you spot it, but easy oversight when reading the puzzle’s description fast. I obviously had to read the description carefully 2 more times to spot my mistake, so as we say in Polish: “the cunning one loses twice”.
Both parsing and solving today’s puzzle heavily rely on pattern matching, so let’s see that in action.
Firstly, let’s take a look at how the data is decoded using pattern matching:
% "The first column is what your opponent is going to play:
% A for Rock,
% B for Paper,
% C for Scissors.
translate_opponent_move("A") -> rock;
translate_opponent_move("B") -> paper;
translate_opponent_move("C") -> scissors.
% The second column, you reason, must be what you should play in response:
% X for Rock,
% Y for Paper,
% Z for Scissors.
translate_my_move("X") -> rock;
translate_my_move("Y") -> paper;
translate_my_move("Z") -> scissors.
A smart observer might notice that I could have used a single function to handle that translation, but I find dividing the decoding into two separate functions much more readable.
Now let’s take a look at how scoring can be conveniently calculated:
count_games_score({OpponentMove, MyMove}) ->
count_shape_score(MyMove) + count_result_score(OpponentMove, MyMove).
% The score for a single round is the score for the shape you selected (
% 1 for Rock,
% 2 for Paper,
% 3 for Scissors
count_shape_score(rock) -> 1;
count_shape_score(paper) -> 2;
count_shape_score(scissors) -> 3.
% ) plus the score for the outcome of the round (
% 0 if you lost,
% 3 if the round was a draw,
% 6 if you won
% ).
count_result_score(rock, scissors) -> 0;
count_result_score(paper, rock) -> 0;
count_result_score(scissors, paper) -> 0;
count_result_score(OpponentMove, MyMove) when MyMove == OpponentMove -> 3;
count_result_score(scissors, rock) -> 6;
count_result_score(rock, paper) -> 6;
count_result_score(paper, scissors) -> 6.
Again a keen observer might notice that it could be done in a single function, but I think most people will agree that translating the specifications one-to-one is way more convenient and much easier to understand and possibly debug if the need arises.
The solution can be found here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day2_puzzle1
Day 2- Puzzle 2
Puzzle two introduces a plot twist. It turns out that the second part of the input for each of the games is not what we are supposed to play, but the expected game result. We need to figure out what to play, based on what our opponent’s move is and the expected result. Notice that the game score count does not change, so if we determine what we have played based on the new understanding of input and provide parsing output to follow the same rules as we did in today’s puzzle 1 when doing the parsing, the rest of the code should work correctly without any change.
Let’s now see how to achieve that in practice.
In the `read_and_parse_data/1` function I modified the anonymous function inside a map function to translate the predicted result into my move:
fun(RawGame) ->
[OpponentMoveRaw, GameResultRaw] = string:split(RawGame, " "),
OpponentMove = translate_opponent_move(OpponentMoveRaw),
GameResult = translate_result(GameResultRaw),
MyMove = find_my_move(OpponentMove, GameResult),
{OpponentMove, MyMove}
endAnd this is the implementation of the translating functions:
% "The first column is what your opponent is going to play:
% A for Rock,
% B for Paper,
% C for Scissors.
translate_opponent_move("A") -> rock;
translate_opponent_move("B") -> paper;
translate_opponent_move("C") -> scissors.
% The second column says how the round needs to end:
% X means you need to lose,
% Y means you need to end the round in a draw,
% Z means you need to win.
translate_result("X") -> lose;
translate_result("Y") -> draw;
translate_result("Z") -> win.
find_my_move(OpponentMove, draw) -> OpponentMove;
find_my_move(rock, lose) -> scissors;
find_my_move(paper, lose) -> rock;
find_my_move(scissors, lose) -> paper;
find_my_move(rock, win) -> paper;
find_my_move(paper, win) -> scissors;
find_my_move(scissors, win) -> rock.
Again they heavily rely on pattern matching.
The solution can be found here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day2_puzzle2
Conclusions after completing day 2
Firstly, ALWAYS carefully read the requirements, and do not skip any part, because you find it “obvious”.
Secondly, pattern matching is a great tool to have, it allows us to easily implement readable code.
And last but not least, if you struggle or get stuck with something, it helps to add readable printing/logging to your code. When my implementation of `find_my_move/2` function (when solving puzzle 2) did not work. I added the following printing debug to the parsing data function:
…
MyMove = find_my_move(OpponentMove, GameResult),
io:format("OpponentMoveRaw: ~p\t", [OpponentMoveRaw]),
io:format("OpponentMove: ~p\t", [OpponentMove]),
io:format("GameResultRaw: ~p\t", [GameResultRaw]),
io:format("MyMove: ~p\t", [MyMove]),
io:format("GameResult: ~p\t", [GameResult]),
io:format("Result Score: ~p\n", [count_games_score({OpponentMove, MyMove})]),
{OpponentMove, MyMove}
…
Which for the test file:
A X
A Y
A Z
B X
B Y
B Z
C X
C Y
C Z
Results with the following output:
OpponentMoveRaw: "A" OpponentMove: rock GameResultRaw: "X" MyMove: scissors GameResult: lose Result Score: 3
OpponentMoveRaw: "A" OpponentMove: rock GameResultRaw: "Y" MyMove: rock GameResult: draw Result Score: 4
OpponentMoveRaw: "A" OpponentMove: rock GameResultRaw: "Z" MyMove: paper GameResult: win Result Score: 8
OpponentMoveRaw: "B" OpponentMove: paper GameResultRaw: "X" MyMove: rock GameResult: lose Result Score: 1
OpponentMoveRaw: "B" OpponentMove: paper GameResultRaw: "Y" MyMove: paper GameResult: draw Result Score: 5
OpponentMoveRaw: "B" OpponentMove: paper GameResultRaw: "Z" MyMove: scissors GameResult: win Result Score: 9
OpponentMoveRaw: "C" OpponentMove: scissors GameResultRaw: "X" MyMove: paper GameResult: lose Result Score: 2
OpponentMoveRaw: "C" OpponentMove: scissors GameResultRaw: "Y" MyMove: scissors GameResult: draw Result Score: 6
OpponentMoveRaw: "C" OpponentMove: scissors GameResultRaw: "Z" MyMove: rock GameResult: win Result Score: 7
Which I found extremely helpful when finding the mistake. It turned out that instead of:
% …
find_my_move(rock, lose) -> scissors;
find_my_move(paper, lose) -> rock;
find_my_move(scissors, lose) -> paper;
% …
I had:
% …
find_my_move(rock, lose) -> paper;
find_my_move(paper, lose) -> rock;
find_my_move(scissors, lose) -> paper;
% …
In the event that I was unable to locate my mistake, I would recommend implementing unit tests, hoping not to duplicate the mistake there.
That’s it for day 2. Come back on Monday for the solutions to the weekend’s puzzles as well as Monday’s solution.
Day 3
In today’s puzzles we are tasked with finding intersections of sets. I know that for 99% of my audience sets intersection is an obvious term, but for the 1% that do not know the intersection of sets is a fancy name for a collection of common elements of those sets.
An important note is that this definition works not only for two sets but for any number of sets.
In the diagram above, the intersection for the Sets’ is marked in green.
Day 3- Puzzle 1
In this puzzle, we need to divide each input line in half and then find the intersection (a single element) of the first and second half of each line. This can be done very simply using functions from Erlang’s sets (https://www.erlang.org/doc/man/sets.html) module:
Once we have the found intersections, we need to map them to priorities. This is one of the rare moments when using a dollar sign followed by character syntax makes the code much more readable. The one thing that we need to remember is that a letter is stored as a number, it’s ASCII code. So $a is stored internally in Erlang as number 97 etc. Having those 2 facts established we can implement mapping items (chars) to priorities:
For letters other than a, z, A and Z the code is not as obvious, but fortunately, we are provided with a description that can be translated directly into unit tests:
% Lowercase item types a through z have priorities 1 through 26.
% Uppercase item types A through Z have priorities 27 through 52.
priority_conversions_are_correct_for_edge_cases_test() ->
?assertEqual(1, item_to_priority($a)),
?assertEqual(26, item_to_priority($z)),
?assertEqual(27, item_to_priority($A)),
?assertEqual(52, item_to_priority($Z)).
% the priority of the item type that appears in both compartments of each rucksack is
% 16 (p),
% 38 (L),
% 42 (P),
% 22 (v),
% 20 (t),
% 19 (s)
priority_conversions_are_correct_test() ->
?assertEqual(16, item_to_priority($p)),
?assertEqual(38, item_to_priority($L)),
?assertEqual(42, item_to_priority($P)),
?assertEqual(22, item_to_priority($v)),
?assertEqual(20, item_to_priority($t)),
?assertEqual(19, item_to_priority($s)).To run the tests execute: `rebar3 eunit` which should result in a message like this one:
$ rebar3 eunit
===> Verifying dependencies...
===> Analyzing applications...
===> Compiling day3_puzzle2
===> Performing EUnit tests...
..
Finished in 0.077 seconds
2 tests, 0 failuresHaving the item-to-priority conversion implemented and tested is enough to get the intersections for the first and second compartments of each rucksack, map intersections to priorities and then sum priorities.
Full code available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day3_puzzle1
Day 3 – Puzzle 2
Today’s second puzzle seems to actually be simpler than the first one. The task requires us to divide the input into groups of 3 lines (Elves group), where each line represents the Elf’s rucksack content. This can be achieved by a custom recursive function:
The next step is to find the intersection of those 3 collections (which is the Elve’s group badge, a single character) and reuse the item for the priority conversion function from puzzle 1. This will reveal the priorities of the badges. Last but not least, just sum up the priorities to get the answer.
Full code available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day3_puzzle2
Day 4
Today’s puzzles are about cleaning up the camp. From a mathematical/algorithmic perspective, it is all about numerical ranges (discrete intervals, aka with integers only) and finding common elements between them.
For the input, we are given a list of paired ranges.
Day 4- Puzzle 1
The first task is to find how many assignment pairs in one range, fully contains the other. This is a simple enough task. After parsing the data we just need to apply a filter with a custom predicate of one range containing the other.
Take a second to notice that the first range contains the second one when both of the following conditions are met:
- the smallest number in the second range is bigger or equal to the smallest number in the first range
- the biggest number in the second range is smaller or equal to the biggest number in the first range
Also spot that the second range might be the one containing the first one, so we have to reverse the condition (that is the part after `orelse`).
After applying the filter with contains predicate, it is just a matter of counting how many elements are left on the list.
Complete code available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day4_puzzle1
Day 4 – Puzzle 2
The second puzzle today differs from the first one only in the nature of the predicate, because the second task is to find pairs which have any common part (overlap).
The only change that needs to be made is the predicate, this time instead of `contains/1` I defined a new predicate `overlap/1`. Notice that there can be a few approaches to this problem:
- Two ranges overlap when one end of one of the ranges is in the other range or one range contains the other.
- The size of the intersection of the two sets of integers that those ranges contain is bigger than zero (0), in other words, the two rangers overlap if they have at least 1 common element.
Let’s see how to implement those two approaches.
Firstly, the conditions of one range containing one of the ends of the other range. Notice that instead of checking if the `contains/` predicate we could alternatively reverse the roles and check if any of the ends of the first range is in the second range.
The second approach is leveraging the erlang sets module:
Playing around with multiple implementations and checking if they all work correctly I added some unit tests at the end of the module. If you want to play around with the conditions change the code and run `rebar3 eunit`.
If you are wondering how the test cases were constructed to cover all cases (I hope I did not miss anyone). I fixed one range (5 to 7) and placed the other range in different configurations, starting from both ends of the second range being smaller and ending on both ends of the second range being bigger (the only 2 cases when the two ranges do not overlap). This is how the code doing that looks:
do_overlap_sections_test() ->
Cases = [
{{2, 5},{5, 7}},
{{2, 6},{5, 7}},
{{2, 7},{5, 7}},
{{2, 8},{5, 7}},
{{2, 9},{5, 7}},
{{4, 9},{5, 7}},
{{5, 9},{5, 7}},
{{6, 9},{5, 7}},
{{7, 9},{5, 7}},
{{2, 7},{3, 5}},
{{3, 5},{2, 7}}
],
[?assertEqual(true, overlap(#{
first_section => #{from => FromF, to => ToF},
second_section => #{from => FromS, to => ToS}}))
||{{FromF, ToF}, {FromS, ToS}} <- Cases].
do_not_overlap_sections_test() ->
Cases = [
{{2, 4},{5, 7}},
{{8, 9},{5, 7}}
],
[?assertEqual(false, overlap(#{
first_section => #{from => FromF, to => ToF},
second_section => #{from => FromS, to => ToS}}))
||{{FromF, ToF}, {FromS, ToS}} <- Cases].
When there are many cases to be considered I think that the saying “a picture is worth a thousand words” applies. So I’ve provided the image above.
Complete code available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day4_puzzle2
Day 5
Today’s puzzle is about implementing an interpreter for manipulating crates between stacks. The most difficult part of today’s puzzle turned out to be parsing and loading initial stacks into a reasonable data structure.
Here is an example input file:
First, I divided the input into initial stacks of cranes and a list of commands. Since parsing the list of commands is pretty straightforward and can be done in many ways I will skip describing how to parse commands. If you are interested in looking more into how I did that, take a look at the code here.
To parse initial stacks, I read the rows, divided them into crates and if there is an empty space (for lower crates stack), replace it with an atom `empty`. Now the partially parsed crates look like this:
Next for a list of parsed rows, I picked the heads of those lists to a separate list (my first stack) and then reapplied the same function recursively for the tails of those rows (to deliver the following stacks).
Let’s see a simplified version of getting a single stack:
There were a few minor operations to be made to finally get the following data structure to represent my stacks:
This creates a map where the key is the stack’s number, and the value is a list of crates from the top crate at the beginning of a list to the bottom, the last element at this list.
Day 5 – Puzzle 1
After creating the initial stacks of crates and a list of commands parsed, we can execute the operations. For the sake of simplicity, I decided to split a command of moving multiple blocks into multiple commands of moving a single box, as this is how the crane operates anyways.
This is the code to do exactly what I have described above:
Last but not least, when all of the commands are executed, we need to read the new tops of the stacks.
This is done by changing the map of stacks back into a list of tuples with stack numbers as the first element and stack as the second one. Then, a relatively rarely used function `lists:keysort/1` comes in handy, as we need to sort those tuples by stack number.
After sorting it remains to get only the top element for each stack.
Complete code available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day5_puzzle1
Day 5 – Puzzle 2
The only modification for this puzzle is how we move the crates. Previously they were moved one by one, now all of the crates are moved at once. So, the only change that needs to be made to the code is how the command is executed. Now, I split the stack into parts using `lists:split/2` function, instead of just getting the top one element from the source stack, like it was done in today’s puzzle 1. Pay attention to the fact that now we need to concatenate a list of moving elements, instead of adding the moving elements as a single head of the destination stack like it was done in the previous puzzle.
The complete code for this is available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day5_puzzle2
As always if you want to discuss, or compare your solutions with us you are welcome to do so on Twitter.
Day 6
Today, both puzzles are about finding the first subsequence of N (4 in the first puzzle and 14 in the second puzzle) characters that are all different in a given input sequence.
Unfortunately using mapping does not work, because we need to process more than one element at a time. Folding does not work either (obviously I bet someone can make it work, but it is way too complicated to be interested in doing) as it always needs to process the whole list. But we want to be able to stop processing as soon as we find the expected subsequence.
Day 6- Puzzle 1
For the first puzzle today, we need to find where in the given sequence of characters ends the first subsequence of 4 unique (all are different) characters. To find the first such sequence, I recursively check if the current 4 characters are all different. If they are then I return the result position, otherwise I remove the first character from the analysed sequence, increment the position counter by one and run the search again and so on until eventually the searched section is found.
find_start_of_packet_marker(Subroutine) ->
find_start_of_packet_marker(4, Subroutine).
find_start_of_packet_marker(MarkerPos, [_ | Rest] = Subroutine) ->
case first_4_chars_are_all_different(Subroutine) of
true -> MarkerPos;
false -> find_start_of_packet_marker(MarkerPos + 1, Rest)
end.
In the snippet above, a very powerful concept of using recursion with an accumulator is shown. The idea of recursion with an accumulator is basically to add another parameter to the recursive function and to store partial results in this parameter. To see the difference, let’s take a look at 2 approaches to implementing finding the Nth element of the Fibonacci sequence. Firstly the classical implementation:
fib(0) -> 1;
fib(1) -> 1;
fib(N) -> fib(N - 1) + fib(N - 2).
And let’s compare it to the one using an accumulator:
fib_with_acc(0) -> 1;
fib_with_acc(N) ->
fib_with_acc(N, {1, 1}).
fib_with_acc(0, {Prev, _Curr}) -> Prev;
fib_with_acc(N, {Prev, Curr}) -> fib_with_acc(N - 1, {Curr, Prev + Curr}).I cannot disagree that at first glance the implementation with an accumulator is more complex, but much faster code. Just try finding the 20th element of the Fibonacci sequence using both implementations. And they give the same results (at least for the first few elements of the sequence) which I checked using this assertion:
fib_implementations_are_equivalents_test() ->
[ ?assert(fib(N) == fib_with_acc(N)) || N <- lists:seq(0, 6) ].
Complete code available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day6_puzzle1
Day 6-Puzzle 2
The second puzzle only differs in the length of the subsequence where all elements must be different. In the first puzzle, I defined checking if all four elements are different “by hand”:
first_4_chars_are_all_different([A, B, C, D | _]) ->
A /= B andalso A /= C andalso A /= D
andalso B /= C andalso B /= D
andalso C /= D.This would be ridiculously long and easy to make mistake code, therefore I decided that it makes much more sense to use a property of set (sets module). That is when an element is added to a set multiple times it is stored only once. In other words, sets do not keep the duplicates of elements. Knowing that, if I decide to build a set from a list of a given number of elements, the size of this set will only be equal to the length of the list it was constructed from if all of the elements on the source list were different from each other. I know it sounds complicated, but let’s see the code and everything should be clear.
first_14_chars_are_all_different(Lst) ->
{First14Chars, _Rest} = lists:split(14, Lst),
sets:size(sets:from_list(First14Chars)) == 14.This solution can be easily generalised to work with a sequence of any length:
first_N_chars_are_all_different(N, Lst) ->
{FirstNChars, _Rest} = lists:split(N, Lst),
sets:size(sets:from_list(FirstNChars)) == N.
Then it would work for both the first and second puzzles by just changing parameter N, setting it to 4 or 14.
Complete code available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day6_puzzle2
Day 7
Today, both puzzles are about finding directories and the sizes of files and subdirectories they contain. The biggest challenge was how to change input into data representation. The issue is mostly about using `cd ..` as when creating any recursive data structure, the inner part often does not know about the outer part. I tried 2 approaches, which failed.
The first one was to use the Erlang digraph module: https://www.erlang.org/doc/man/digraph.html
I found that I was not able to traverse the tree conveniently, therefore I gave it up.
For the second approach, I was to create actual files and directories to represent the data given in the input. But then I came to the conclusion that it would be cheating, so I also gave up this idea quickly. I ended up parsing the given shell history into a list of files and directories, where each file and directory was represented by a tuple, like those:
[
{dir,["/","a"]},
{file,["/","b.txt"],14848514},
{file,["/","c.dat"],8504156},
{dir,["/","d"]}
]
With this representation of files and folders, there is a very easy way to check if a file should be added to the directories size:
If the directory’s path is the first part of the file’s path ,then this file is a part of this directory.
To make it more visually appealing, let’s see a few examples:
[
{dir,["/"]},
{dir,["/", "A"]},
{dir,["/", "B"]},
{file,["/","b.txt"],1},
{file,["/","c.txt"],2},
{file,["/", "A", "d.txt"],12},
{file,["/", "C", "e.txt"],42}
]
Let’s consider input like the above. We can see that the “/” directory should consider all of the files in its size. The [“/”, “A”] directory should only consider “d.txt” file’s size to know its own size, as it never matches its path’s second element with any of the other files. And directory [“/”, “B”] matches none of the files on its second element at all.
Such comparisons can be done by a surprisingly simple function:
contains([], _) -> true;
contains([Elem | DirRest], [Elem | FileRest]) ->
contains(DirRest, FileRest);
contains(_, _) -> false.Day 7 – Puzzle 1
We already know which files are to be counted when a directory size is calculated. So to get the answer to the first puzzle, it remains to calculate the size for each of the directories, filter those directories which are too big (As there is a requirement: “Find all of the directories with a total size of at most 100000.”) and then sum the sizes of the remaining once.
Complete code available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day7_puzzle1
Day 7 – Puzzle 2
The second part of the puzzle requires finding the smallest directory to be deleted to have enough free memory to install an update of the given size.
It is needed to know how much memory is taken. Fortunately, the amount of memory taken is the size of the “/” directory. To get how much memory is already available,we subtract taken memory from the total space available. To find the smallest folder that will release enough memory, it is necessary to calculate how much memory needs to be freed. To calculate that, subtract the free memory from how much memory needs to be freed.
Then last but not least, filter directories which are too small (deleting them will not free enough memory) and from big enough directories we pick the one with the smallest size (the directory’s name is dropped as the puzzle asks only about this directory’s size).
Complete code available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day7_puzzle2
Day 8
Today’s puzzle is about finding sequences in a 2-dimensional array (AKA matrix)
TreeHeights:
[3,0,3,7,3]
[2,5,5,1,2]
[6,5,3,3,2]
[3,3,5,4,9]
[3,5,3,9,0]For convenient representation and relatively quick and efficient access in Erlang, I would recommend using a map where each key is a tuple storing X and Y coordinates of position and the map value is the value of a given square.
#{{RowIndex, ColumnIndex} => TreeHeight}So the example array from above would be represented like this:
TreesMap:
#{{1,1} => 3,{1,2} => 0,{1,3} => 3,{1,4} => 7,{1,5} => 3,
{2,1} => 2,{2,2} => 5,{2,3} => 5,{2,4} => 1,{2,5} => 2,
{3,1} => 6,{3,2} => 5,{3,3} => 3,{3,4} => 3,{3,5} => 2,
{4,1} => 3,{4,2} => 3,{4,3} => 5,{4,4} => 4,{4,5} => 9,
{5,1} => 3,{5,2} => 5,{5,3} => 3,{5,4} => 9,{5,5} => 0}
Day 8 – Puzzle 1
Firstly, we need to find how many trees are visible from outside the grid. The puzzle defines this visibility as follows “A tree is visible if all of the other trees between it and an edge of the grid are shorter than it. Only consider trees in the same row or column; that is, only look up, down, left, or right from any given tree.” But we can easily tell that the tree is visible from outside the grid in a certain direction if between it and the grid’s edge there is no tree of its height or taller.
So, let’s write a function to find lists of trees in each of the directions (up, down, left, right). Then we need to check if any of the lists of visibility (up, down, left and right) have all of the elements smaller than the considered tree.
This is done by the code below:
is_visible(X, Y, GridWidth, GridHeight, TreesMap) ->
CurrentTreeHeight = maps:get({Y, X}, TreesMap),
VisibilitySides = [
[maps:get({Row, Col}, TreesMap) || Col <- lists:seq(1, X - 1), Row <- [Y]],
[maps:get({Row, Col}, TreesMap) || Col <- lists:seq(X + 1, GridWidth), Row <- [Y]],
[maps:get({Row, Col}, TreesMap) || Row <- lists:seq(1, Y - 1), Col <- [X]],
[maps:get({Row, Col}, TreesMap) || Row <- lists:seq(Y + 1, GridHeight), Col <- [X]]
],
lists:any(
fun(VisibilitySide) ->
lists:all(
fun(VisibilitySideTree) ->
VisibilitySideTree < CurrentTreeHeight
end, VisibilitySide)
end, VisibilitySides).Having this predicate defined, we just need to run it for all of the trees in the grid and count how many of them are visible from the outside.
The complete code is available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day8_puzzle1
Day 8 – Puzzle 2
The second puzzle of the day is finding the tree with the best scenic score.
Here’s how Puzzle explains finding a score:
“A tree’s scenic score is found by multiplying together its viewing distance in each of the four directions.” and “To measure the viewing distance from a given tree, look up, down, left, and right from that tree; stop if you reach an edge or at the first tree that is the same height or taller than the tree under consideration. (If a tree is right on the edge, at least one of its viewing distances will be zero.)”
We already have trees for each side view. We just need to reverse the views lists up and left (to look from the considered tree perspective). We will also need to define our own take_while function (similar to lists:takewhile/2) , which includes the first tree that did not meet the requirement of tree size being strictly smaller than the considered tree.
CurrentTreeHeight = 4,
VisibilitySide = [1, 2, 3, 4, 5],
day8_puzzle2:take_while(CurrentTreeHeight, VisibilitySide).
[1,2,3,4]
Now there is just a minor rearrangement of the checking views function:
count_scenic_score(X, Y, GridWidth, GridHeight, TreesMap) ->
CurrentTreeHeight = maps:get({Y, X}, TreesMap),
VisibilitySides = [
lists:reverse([maps:get({Row, Col}, TreesMap) || Col <- lists:seq(1, X - 1), Row <- [Y]]),
[maps:get({Row, Col}, TreesMap) || Col <- lists:seq(X + 1, GridWidth), Row <- [Y]],
lists:reverse([maps:get({Row, Col}, TreesMap) || Row <- lists:seq(1, Y - 1), Col <- [X]]),
[maps:get({Row, Col}, TreesMap) || Row <- lists:seq(Y + 1, GridHeight), Col <- [X]]
],
VisibilitySideScores = lists:map(
fun(VisibilitySide) ->
VisibleView = take_while(CurrentTreeHeight, VisibilitySide),
length(VisibleView)
end, VisibilitySides),
lists:foldl(fun(E, A) -> E * A end, 1, VisibilitySideScores).
So notice I know two of the `VisibilitySides` are being reversed to process them from the viewer’s perspective. The sooner the element is on the `VisibilitySide` list, the closer to the viewer this tree is.
The second thing that required changing is implementing the `SideScore` for each of the sides. Then, you just multiply those scores to get a scenic score for the considered tree.
Last but not least, to get the answer, it is enough to get the maximum value out of scenic scores.
The complete code is available here: https://github.com/aleklisi/AdventOfCode2022/tree/main/day8_puzzle2
Day 9
Today’s task is to implement a rope (snake-like) following its end (head). Whenever each next step is executed by the head, the following segment of the snake must follow.
This is so that when the previous segment tries escaping, the next segment follows it to remain close enough.
Let’s assume that the head goes 3 squares up, then 2 squares right and then 2 squares left. The input file would look like this:
R 3
U 2
L 2Now, let’s imagine an infinite rope (or at least a very long one) and let’s see how it will change with each next step:
RopeAfterStep1 = [{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},..., {0,0}]
RopeAfterStep2 = [{1,0},{0,0},{0,0},{0,0},{0,0},{0,0},..., {0,0}]
RopeAfterStep3 = [{2,0},{1,0},{0,0},{0,0},{0,0},{0,0},..., {0,0}]
RopeAfterStep4 = [{3,0},{2,0},{1,0},{0,0},{0,0},{0,0},..., {0,0}]
RopeAfterStep5 = [{3,1},{2,0},{1,0},{0,0},{0,0},{0,0},..., {0,0}]
RopeAfterStep6 = [{3,2},{3,1},{2,1},{1,1},{0,0},{0,0},..., {0,0}]
RopeAfterStep7 = [{2,2},{3,1},{2,1},{1,1},{0,0},{0,0},..., {0,0}]
To make it work for each step, there needs to be two actions:
- Based on input move the head. Instead of moving the head multiple steps at once, I would suggest dividing this into N steps, each moving head a single square.
- Starting from the second knot, all the way to the tail, check if the next knot/segment is close enough to the previous one, if it is not move it closer.
Now it is enough to save unique fields that the tail of the rope visited and count how many elements this set has.
Let’s see the code for those two actions:
execute_step(Direction, _Rope = [{HeadX, HeadY} | Rest ]) ->
NewHeadPos = case Direction of
"U" -> {HeadX, HeadY + 1};
"D" -> {HeadX, HeadY - 1};
"L" -> {HeadX - 1, HeadY};
"R" -> {HeadX + 1, HeadY}
end,
{Last, OthersRev} = lists:foldl(
fun(NextElem, {PrevElem, Moved}) ->
NewPrevPos = maybe_move_tail(PrevElem, NextElem),
{NewPrevPos, [PrevElem | Moved]}
end, {NewHeadPos, []}, Rest),
lists:reverse([Last | OthersRev]).
maybe_move_tail({HeadX, HeadY}, {TailX, TailY}) ->
DistanceSquared = distance_squared(HeadX, HeadY, TailX, TailY),
NewTailPos = if
DistanceSquared =< 2 ->
{TailX, TailY};
true ->
Moves = moves(TailX, TailY),
[{_, NewX, NewY} | _] = lists:keysort(1, [{distance_squared(HeadX, HeadY, X, Y), X, Y} ||{X, Y} <- Moves]),
{NewX, NewY}
end,
NewTailPos.
The distance function is basically Euclidian distance without using sqrt:
distance_squared(X1, Y1, X2, Y2) ->
(X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2).
And moves function generates Moore’s neighbourhood (https://en.wikipedia.org/wiki/Moore_neighborhood) for given coordinates.
Notice that the same solution works for both puzzle 1 and puzzle 2. The only difference that needs to be applied is the length of the rope/snake. In the first puzzle, the length is 2 and in the second puzzle, it is 10. Therefore, I will not discuss them separately.
A minor improvement from puzzle 1 to puzzle 2 I was:
moves(TailX, TailY) ->
[
{TailX + 1, TailY},
{TailX - 1, TailY},
{TailX, TailY + 1},
{TailX, TailY - 1},
{TailX + 1, TailY + 1},
{TailX + 1, TailY - 1},
{TailX - 1, TailY + 1},
{TailX - 1, TailY - 1}
].
To shorter version:
moves(TailX, TailY) ->
Shifts = [-1, 0, 1],
[{TailX + ShiftX, TailY + ShiftY} || ShiftX <- Shifts, ShiftY <- Shifts].
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day9_puzzle2
https://github.com/aleklisi/AdventOfCode2022/tree/main/day9_puzzle1
Day 10
Today’s puzzle is about processing a list of instructions for a simple processor with a single registry. As input, we get a list of the processor’s orders. We need to keep track of how the state of the registry changes after each operation.
Day 10 – Puzzle 1
In the first puzzle, we need to find signal strength (defined as “the cycle number multiplied by the value of the X register”) in the 20th, 60th, 100th, 140th, 180th, and 220th cycles.
To do this, we need to execute the program given as an input.
Here is the code executing the program and saving the history of execution in each next step of it:
build_cpu_execution_history(Instructions) ->
#{x := FinalX, history := TotalHistory}
= lists:foldl(
fun build_execution_step/2,
#{x => 1, history => [], cycle_counter => 1},
Instructions),
{FinalX, lists:reverse(TotalHistory)}.
build_execution_step(noop,
#{x := X, history := History, cycle_counter := Count}) ->
#{
x => X,
history => [{noop, Count, X} | History],
cycle_counter => Count + 1
};
build_execution_step({addx, V},
#{x := X, history := History, cycle_counter := Count}) ->
NewX = X + V,
#{
x => NewX,
history => [{addx, Count + 1, X}, {addx, Count, X} | History],
cycle_counter => Count + 2
}.
Notice that the history of execution is generally longer (unless the program consists of `noop` instructions only) than the input program.
This is because each `addx` operation takes 2 cycles. Having a history of execution saved now is enough to extract the values of the registry in expected cycles (20th, 60th, etc).
Calculate signal strength for each of those cycles and sum the calculated strengths to get the answer.
signal_strength({_Instruction, CycleNumber, XRegisterValue}) ->
CycleNumber * XRegisterValue.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day10_puzzle1
Day 10 – Puzzle 2
The second puzzle adds another element, which is a horizontal sprite. The sprite determines if a pixel drawn by CRT is drawn bright (`#`) or dark (`.`). The code checking if a pixel is drawn bright or dark:
render_pixel({{CRTX, CRTY}, {_, _, RegisterXValue}}) ->
SpritePixels = [RegisterXValue + Shift || Shift <- [-1, 0, 1]],
Char = case lists:member(CRTX, SpritePixels) of
false -> {{CRTX, CRTY}, $.};
true -> {{CRTX, CRTY}, $#}
end,
Char.Now we just need to apply it to all pixels one by one and render the final result:
run_crt(ExecutionHistory) ->
CRTPositions = [{X, Y} || Y <- lists:seq(1, 6), X <- lists:seq(0, 39)],
CRTMap = maps:from_list(
lists:map(
fun render_pixel/1,
lists:zip(CRTPositions, ExecutionHistory))),
[[maps:get({X, Y}, CRTMap) || X <- lists:seq(0, 39)] || Y <- lists:seq(1, 6)].
Notice that when doing list comprehensions in Erlang the order of generators matters. Let’s see this example:
1> [{X, Y} || X <- [1, 2, 3], Y <- [1, 2, 3, 4]].
[{1,1}, {1,2}, {1,3}, {1,4},
{2,1}, {2,2}, {2,3}, {2,4},
{3,1}, {3,2}, {3,3}, {3,4}]
2> [{X, Y} || Y <- [1, 2, 3, 4], X <- [1, 2, 3]].
[{1,1}, {2,1}, {3,1},
{1,2}, {2,2}, {3,2},
{1,3}, {2,3}, {3,3},
{1,4}, {2,4}, {3,4}]
You can clearly see that just changing the order of assigning variables in the list comprehension’s generator will effect if the final list of coordinates is iterating row by row or column by column.
To get the letters rendered like those:
Answer: ["####..##....##.###...##...##..####.#..#.",
"#....#..#....#.#..#.#..#.#..#.#....#.#..",
"###..#.......#.###..#....#....###..##...",
"#....#.##....#.#..#.#.##.#....#....#.#..",
"#....#..#.#..#.#..#.#..#.#..#.#....#.#..",
"####..###..##..###...###..##..#....#..#."]
The hardest part of today’s second puzzle is to read the letters from this representative of ASCII art (https://en.wikipedia.org/wiki/ASCII_art).
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day10_puzzle2
Day 11
Today’s puzzle is about monkeys moving and modifying numbers between them.
The numbers are moved around based on the condition that they are dividable by a predefined number. To be more precise, both of today’s puzzles are almost identical. The only two factors that differ between them are:
- In the first simulation, each time number is inspected it is divided by 5 and rounded (with the floor), while it is not the case in the second puzzle.
- The first puzzle requires the execution of only 20 steps while the second one requires 10_000 steps.
Day 11 – Puzzle 1
In this puzzle, we just need to keep track of the state, which is monkeys and their items and which monkey is passing which number to another monkey.
To get the answer, running the situation requires an extra parameter to keep track of how many items each monkey inspects.
For solving this puzzle it is very helpful to define a map (a data structure) of a monkey like this one:
Monkey = #{
items := Items,
operation := Operation,
test := TestPred,
if_true := IfTrue,
if_false := IfFalse,
items_inspected_count := InspectedItemsCount
}
Storing a predicate in the `test` and `operation` fields for each monkey allows for certain convenience of later usage. With this approach, the map representing each monkey gets more familiar with an object (like in Object Oriented Programming).
Running a whole simulation is just running a simulation round 20 times. Running each round is just modifying and redistributing the items of each monkey to other monkeys based on the predefined set of rules. Notice that for each of the operations, I use the fold (lists:foldl/3 to be more specific) function instead of the map function. This was used heavily in previous solutions, as each time some step is executed the data that is used in this step may modify all of the (no constant/changing) elements of the state.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day11_puzzle1
Day 11 – Puzzle 2
In this puzzle, the division by 3 with rounding (to a floor) is abandoned, when calculating the new worry level. This means that worry values for each of the items will raise significantly in each next step of the simulation (especially for the monkeys that multiply the item’s worry level). Since the decision of handing over the item is based on the fact that this item’s worry level is dividable by a constant number, we can actually only care about the rest of the divisions as modifications applied by each monkey is either addition or multiplication, but since different monkeys use different dividers, you have to care about at least smallest common divider. In practical terms. It is just easier to consider the divider to be a multiplication of all of the monkeys dividers (the one from the `test` field).
If the previous paragraph is confusing to you, let me give a simple example:
Example: Let’s consider 2 monkeys, first one is passing the item depending on the condition of the worry level is dividable by 3 and the second one is if the worry level is dividable by 5. Now let’s consider an item with worry level 16.
Firstly, notice that 3 times 5 is 15. The considered item (with worry level 16) will be handed in the terms (the results of the test for either of those monkeys will be the same) as the item with worry level 1.
Why does this observation matter? It matters because we could try using the same code as previously to run the simulation (with the division by 3 removed). But this simulation will slow down significantly after about 400 steps and reaching the 500th step took my machine over 2 minutes.
So based on the observation from the previous paragraphs, we can run a normalisation for each of the items. Since running the simulation for the first few hundred (~300) steps was instantaneous, I decided not to run the normalisation of items every single step. But every hundredth step of a simulation makes it fast enough to execute 10_000 steps in about a second (which for human is a blink of an eye).
normalize(SimulatedMonkeys) ->
Monkeys = maps:values(SimulatedMonkeys),
TestVals = lists:map(fun(#{test := Test}) -> Test end, Monkeys),
Rem = lists:foldl(fun(Elem, Acc) -> Elem * Acc end, 1, TestVals),
maps:map(fun(_, Monkey = #{items := Items}) ->
NormalizedItems = lists:map(fun(Item) -> Item rem Rem end, Items),
Monkey#{items := NormalizedItems}
end, SimulatedMonkeys).
Although it might look complex, the normalisation just limits the items to be somewhere between 0 and the multiplication of all test values (once that monkey makes the decision to hand the item on).
Last but not least, notice the similarity is almost stunning to the modulo idea from Diffy Hellman’s key exchange (https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange) algorithm.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day11_puzzle2
Day 12
Today’s puzzle is all about finding a path length in a given grid. The puzzle probably can be solved with some clever algorithm implementation. You can look at the grid as if it was a graph, which gives me a perfect excuse to finally use a library that I created to communicate with the neo4j graph database and that is https://github.com/aleklisi/eneo4j/.
You will notice that I am using `rebar3 app` and not `rebar3 escript. That is because starting eneo4j is easier that way. After the DB is up and running (I used docker compose), I need to start my Erlang application and set up eneo4j app.
Here is the code for how to do it:
setup_db_connection() ->
Eneo4jWorkerConfig = #{
url => "http://localhost:7470",
db => "neo4j"
},
persistent_term:put(eneo4j_worker_config, Eneo4jWorkerConfig),
persistent_term:put(eneo4j_workers_count, 5),
{ok, _} = application:ensure_all_started(eneo4j),
#{<<"neo4j_version">> := _} = eneo4j:discovery_api().
Notice that you can execute this function anywhere in your supervision tree and the DB will be started automatically for you when you run `rebar3 shell`.
As soon as the data is loaded into the database, finding the path in a graph should be blazing fast. Unfortunately, I am just an amateur. An enthusiastic one but still, an amateur in writing cypher queries (cypher is the query language for the neo4j database).
Loading the grid into the database takes a while, especially when it comes to creating relations. I had to divide that action into smaller parts,not to get transaction timeouts.
Firstl,y I created nodes which represent grid points. Then I run a query to create STEP relations between nodes.
The code to create nodes:
create_nodes(Grid) ->
Query = <<"MERGE (n:Point { x: $x, y: $y, value: $value });">>,
lists:map(
fun(Point) ->
Statement = create_node_statement(Point, maps:get(Point, Grid), Query),
eneo4j:begin_and_commit_transaction([Statement], ?TIMEOUT)
end, maps:keys(Grid)).
create_node_statement({X, Y}, Value, Query) ->
Params = #{
<<"x">> => X,
<<"y">> => Y,
<<"value">> => Value
},
eneo4j:build_statement(Query, Params).
Notice that if I have nodes in the database, I can delegate finding where I can take steps to the database. Tthis is what I do executing this Cypher statement:
MATCH
(from:Point {x: $x, y: $y}),
(to:Point)
WHERE
(
(from.x = to.x AND (from.y + 1 = to.y OR from.y - 1 = to.y)) OR
(from.y = to.y AND (from.x + 1 = to.x OR from.x - 1 = to.x))
) AND (to.value <= from.value + 1)
MERGE (from)-[r:STEP]->(to)
RETURN type(r);
This is done in the create_relations/2 function and x and y are passed parameters to divide the work into multiple smaller queries (as it helps with my impatience when waiting for query results).
For the example input:
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
The generated graph looks like this:
Day 12 – Puzzle 1
Finding the shortest path from start point to destination is as easy as running this cypher query:
MATCH
(from:Point {x: $from_x, y: $from_y} ),
(to:Point {x: $to_x, y: $to_y} ),
p = shortestPath((from)-[:STEP*]->(to))
RETURN length(p);Parametrised with coordinates of S and E points in the grid.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day12_puzzle1
Day 12 – Puzzle 2
Since loading data to the DB takes a while, I would highly recommend not to do it again from scratch, for the second puzzle. Especially because the data is the same as for the first today’s puzzle. Now finding the answer to the second puzzle is just the master of slightly modifying the query. For all the points that have the value `$a` ,we need to find their distance to point E, and then sort them by this distance, and then only pick the closest one.
Here is a cypher query doing exactly that:
MATCH
(from:Point {value: $value} ),
(to:Point {x: $to_x, y: $to_y} ),
p = shortestPath((from)-[:STEP*]->(to))
RETURN from, length(p) AS distance ORDER BY distance LIMIT 1;
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day12_puzzle2
Day 12 – Lesson learned
As the law of the instrument (https://en.wikipedia.org/wiki/Law_of_the_instrument) says: “If the only tool you have is a hammer, it is tempting to treat everything as if it were a nail.”
Today’s puzzles could be solved with bigger or smaller difficulties in pure Erlang, but I find it much more fun using dedicated tools for particular jobs.
Day 13
Today’s puzzle is about comparing and sorting nested lists of integers according to a given set of rules. Firstly, we need to parse the input data. This could be done by implementing a simple parser, but why bother if Erlang has this implemented for us already? Let’s use existing modules to parse raw string directly into the Erlang term.
to_term(Input) ->
String = binary:bin_to_list(Input) ++ ".",
{ok,Tokens,_EndLine} = erl_scan:string(String),
{ok,AbsForm} = erl_parse:parse_exprs(Tokens),
{value,Value,_Bs} = erl_eval:exprs(AbsForm, erl_eval:new_bindings()),
Value.
The code above takes any binary input and returns a parsed Erlang term. Notice that to make this code work for the given lists, a dot character had to be added at the end of each input to make it a complete Erlang term. DISCLAIMER: Do not use such a method of parsing data when the data you are about to parse comes from an untrusted source!
Both puzzles are about comparing the packets, which in the context of today’s puzzles are nested lists of integers. Not to get lost, when implementing the function to compare such packets, I would suggest taking the comparison description, dividing it into small chunks and implementing them one by one, starting with the direct once and then moving to the general once. Here is my function implementation doing the comparisons:
% If the left integer is lower than the right integer,
% the inputs are in the right order.
compare(Left, Right)
when is_integer(Left), is_integer(Right), Left < Right -> true;
% If the left integer is higher than the right integer,
% the inputs are not in the right order.
compare(Left, Right)
when is_integer(Left), is_integer(Right), Left > Right -> false;
% Otherwise, the inputs are the same integer;
% continue checking the next part of the input.
compare(Left, Right)
when is_integer(Left), is_integer(Right), Left == Right -> continue;
% If exactly one value is an integer,
% convert the integer to a list which contains that integer as its only value,
% then retry the comparison.
compare(Left, Right) when is_list(Left), is_integer(Right) ->
compare(Left, [Right]);
compare(Left, Right) when is_integer(Left), is_list(Right) ->
compare([Left], Right);
% % If the lists are the same length and no comparison makes a decision about the order, continue checking the next part of the input.
compare([], []) -> continue;
% If the left list runs out of items first, the inputs are in the right order.
compare([], _) -> true;
% If the right list runs out of items first, the inputs are not in the right order.
compare(_, []) -> false;
% If both values are lists,
% compare the first value of each list,
% then the second value, and so on.
compare([LeftHead | LeftTail], [RightHead | RightTail]) ->
case compare(LeftHead, RightHead) of
continue -> compare(LeftTail, RightTail);
true -> true;
false -> false
end.
Notice that I have left the parts of the description in the comments. This is done on purpose, so that I can easily track which requirement is met by which function closure.
When developing such code and trying to run it with an example input ,one can add `io:format`,`logger:info` or any other way of printing the intermediate steps.
But there is a much more convenient way to do it: using tracing. The compare function is a perfect example to demonstrate the power of tracing, but as Linus Torvalds says:
“Talk is cheap. Show me the code.” So here you are:
Just add:
% ...
dbg:tracer(),
dbg:p(all, c),
dbg:tpl(?MODULE, compare, x),
PacketsInOrder = find_packets_in_order(Packets),
% ...In the main/1 function. Let’s now take a look at a pair of packets compared. Here they are:
[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9] Now let’s see how the puzzle’s author describes a comparison of those two:
== Pair 8 ==
- Compare [1,[2,[3,[4,[5,6,7]]]],8,9] vs [1,[2,[3,[4,[5,6,0]]]],8,9]
- Compare 1 vs 1
- Compare [2,[3,[4,[5,6,7]]]] vs [2,[3,[4,[5,6,0]]]]
- Compare 2 vs 2
- Compare [3,[4,[5,6,7]]] vs [3,[4,[5,6,0]]]
- Compare 3 vs 3
- Compare [4,[5,6,7]] vs [4,[5,6,0]]
- Compare 4 vs 4
- Compare [5,6,7] vs [5,6,0]
- Compare 5 vs 5
- Compare 6 vs 6
- Compare 7 vs 0
- Right side is smaller, so inputs are not in the right order
Now the trace of function comapre/2 of for the same input:
(<0.9.0>) call day13_puzzle1:compare([1,[2,[3,[4,[5,6,7]]]],8,9],[1,[2,[3,[4,[5,6,0]]]],8,9])
(<0.9.0>) call day13_puzzle1:compare(1,1)
(<0.9.0>) returned from day13_puzzle1:compare/2 -> continue
(<0.9.0>) call day13_puzzle1:compare([[2,[3,[4,[5,6,7]]]],8,9],[[2,[3,[4,[5,6,0]]]],8,9])
(<0.9.0>) call day13_puzzle1:compare([2,[3,[4,[5,6,7]]]],[2,[3,[4,[5,6,0]]]])
(<0.9.0>) call day13_puzzle1:compare(2,2)
(<0.9.0>) returned from day13_puzzle1:compare/2 -> continue
(<0.9.0>) call day13_puzzle1:compare([[3,[4,[5,6,7]]]],[[3,[4,[5,6,0]]]])
(<0.9.0>) call day13_puzzle1:compare([3,[4,[5,6,7]]],[3,[4,[5,6,0]]])
(<0.9.0>) call day13_puzzle1:compare(3,3)
(<0.9.0>) returned from day13_puzzle1:compare/2 -> continue
(<0.9.0>) call day13_puzzle1:compare([[4,[5,6,7]]],[[4,[5,6,0]]])
(<0.9.0>) call day13_puzzle1:compare([4,[5,6,7]],[4,[5,6,0]])
(<0.9.0>) call day13_puzzle1:compare(4,4)
(<0.9.0>) returned from day13_puzzle1:compare/2 -> continue
(<0.9.0>) call day13_puzzle1:compare([[5,6,7]],[[5,6,0]])
(<0.9.0>) call day13_puzzle1:compare([5,6,7],[5,6,0])
(<0.9.0>) call day13_puzzle1:compare(5,5)
(<0.9.0>) returned from day13_puzzle1:compare/2 -> continue
(<0.9.0>) call day13_puzzle1:compare([6,7],[6,0])
(<0.9.0>) call day13_puzzle1:compare(6,6)
(<0.9.0>) returned from day13_puzzle1:compare/2 -> continue
(<0.9.0>) call day13_puzzle1:compare([7],[0])
(<0.9.0>) call day13_puzzle1:compare(7,0)
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
(<0.9.0>) returned from day13_puzzle1:compare/2 -> not_in_order
Take a look at side by side comparisons and how clearly described each comparison is reflected in the trace.
Day 13 – Puzzle 1
Finding the answer to the first puzzle is just parsing pairs of packets. You then filter out the ones that are not in order and then just sum the indexes of the pairs that are left.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day13_puzzle1
Day 13 – Puzzle 2
The second puzzle is literally to sort a list of all packets using compare function, which is as simple as changing atom `in_order` to `true and `not_in_order` to false everywhere in the compare/2 function and then just using this modified compare/2 function to sort all packets:
AllPacketsSorted = lists:sort(fun({A}, {B}) -> compare(A, B) end, AllPackets),
After packets are sorted, it is enough to find indexes of divider packets and multiply them to get the answer:
EnumeratedSortedPackets = lists:enumerate(AllPacketsSorted),
{FirstDivider, _} = lists:keyfind({[[2]]}, 2, EnumeratedSortedPackets),
{SecondDivider, _} = lists:keyfind({[[6]]}, 2, EnumeratedSortedPackets),
Answer = FirstDivider * SecondDivider,The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day13_puzzle2
Day 14
Today’s puzzle is about simulating falling sand, which can be done as a cellular automaton.
(https://en.wikipedia.org/wiki/Cellular_automaton)
There is no point in building and checking a full matrix, as only one square is reviewed or updated at a time. We need only to keep track of the border edges and where rocks and sand are placed. We do not have to keep track of empty squares, as all other squares are empty. For such data, the most convenient is a map with the following structure:
#{{X, Y} => RockOrSand}Day 14 – Puzzle 1
In the first puzzle, we assume that the only border is created by the rocks. We need to check if sand starts falling below the lowest rock. This happens if the falling sand’s Y coordinate is one below the minimal rock’s Y coordinate. We can introduce some optimisation and check if the sand’s X is smaller than the smallest X, or bigger than the biggest X.
We can formulate the condition of dropping the sand using nested case statements:
case X =< MinX orelse X >= MaxX orelse Y >= MaxY of
true ->
{finish, Board};
false ->
Down = maps:get({X, Y + 1}, Board, empty),
case Down of
empty ->
drop_send_unit(X, Y + 1, Board, MinX, MaxX, MaxY);
_ ->
DownLeft = maps:get({X - 1, Y + 1}, Board, empty),
case DownLeft of
empty ->
drop_send_unit(X - 1, Y + 1, Board, MinX, MaxX, MaxY);
_ ->
DownRight = maps:get({X + 1, Y + 1}, Board, empty),
case DownRight of
empty ->
drop_send_unit(X + 1, Y + 1, Board, MinX, MaxX, MaxY);
_ ->
{continue, maps:put({X, Y}, send, Board)}
end
end
end
end
But this code can be improved to a much shorter version:
Down = maps:get({X, Y + 1}, Board, empty),
DownLeft = maps:get({X - 1, Y + 1}, Board, empty),
DownRight = maps:get({X + 1, Y + 1}, Board, empty),
if
X =< MinX orelse X >= MaxX orelse Y >= MaxY -> {finish, Board};
Down == empty -> drop_send_unit(X, Y + 1, Board, MinX, MaxX, MaxY);
DownLeft == empty -> drop_send_unit(X - 1, Y + 1, Board, MinX, MaxX, MaxY);
DownRight == empty -> drop_send_unit(X + 1, Y + 1, Board, MinX, MaxX, MaxY);
true -> {continue, maps:put({X, Y}, send, Board)}
end.Getting the puzzle’s answer is just running a simulation until the stop condition is met and then counting grains of sand in the final board.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day14_puzzle1
Day 14 – Puzzle 2
The second puzzle is again about running simulation, but this time the stop condition is different and there is an infinite line of rocks at MaxY + 2 line.
To implement this puzzle, we need to modify the stop condition and then the logic of how the sand falls is checked.
Here is the code to run the modified simulation:
run_simulation(MaxY, Board) ->
case maps:get({500, 0}, Board, empty) of
empty ->
UpdatedBoard = drop_send_unit(500, 0, Board, MaxY),
run_simulation(MaxY, UpdatedBoard);
_ -> Board
end.
drop_send_unit(X, Y, Board, MaxY) ->
Down = get_square(X, Y + 1, Board, MaxY),
DownLeft = get_square(X - 1, Y + 1, Board, MaxY),
DownRight = get_square(X + 1, Y + 1, Board, MaxY),
if
Down == empty -> drop_send_unit(X, Y + 1, Board, MaxY);
DownLeft == empty -> drop_send_unit(X - 1, Y + 1, Board, MaxY);
DownRight == empty -> drop_send_unit(X + 1, Y + 1, Board, MaxY);
true -> maps:put({X, Y}, send, Board)
end.
We could add a very long, extra line of rocks to the board, but to make it work it would be better to extract checking the falling stop condition into sth like this:
get_square(X, Y, Board, MaxY) ->
case Y >= MaxY of
true ->
rock;
false ->
maps:get({X, Y}, Board, empty)
end.The code to get the answer from the board after running the simulation does not need to be changed.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day14_puzzle2
Day 15
Today’s puzzle is finding distances between points using the Manhattan metric.
For those of you who do not have time or will to read the link, let me include a graphic briefly reminding you how it works for two dimensions on a simple example:
Day 15 – Puzzle 1
In the first puzzle, we need to find all of the positions (in a given row) where the hidden beacon CANNOT be.
I prepared a visual to help understand how to determine those squares:
In the example above, there are three pairs of sensor + beacons. For each such pair, we can get an intersection between the “circle” (in Manhattan metric) and this row. To find all such squares for any given sensor beacon pair, we need to determine the height (Y) difference between the sensor and the row we are interested in,then cut out the respective section of the row each way.
So, we need to calculate the distance between the sensor and the beacon. Then we need to find the difference between the sensor’s Y coordinate and the row that we are interested in.
Now we need to calculate the difference between the distance between the sensor and beacon and the sensor and the row. This represents how many squares are “left to be used” going each way along the row starting from X being the sensor’s X.
Let’s now take a look at a few examples:
In example 1, the sensor is in position (3, 1), the beacon is in position (5, 1) and the row we are interested in is y = 3. The distance between the sensor and the beacon is 2. The distance between the sensor and the row is 2. There is only one square that the beacon cannot be in and there are no left steps to search left or right.
In example 1.1, the sensor is in position (3, 0), the beacon is in position (5, 0) and the row we are interested in is y = 2. The distance between the sensor and the beacon is 3. The distance between the sensor and the row is 2. After we reach the row, we have one more square left to be searched each way.
In example 2 the sensor’s search area does not overlap with the row.
In example 3 the sensor’s search area overlaps with the row, but there is a beacon in the overlap spot, so the field that we consider an intersection already has a beacon, so we have to eliminate that.
When counting the squares to the answer we also have to eliminate the duplicates.
Here is the code finding all overlapping positions:
find_positions_where_beacon_cannot_be(SensorsWithBeacons, BeaconsRowY) ->
lists:map(
fun({Sensor, Beacon}) ->
find_positions_for_beacon(Sensor, Beacon, BeaconsRowY)
end, SensorsWithBeacons).
find_positions_for_beacon(Sensor = {SensorX, SensorY}, Beacon, BeaconsRowY) ->
SensorToBeaconDistance = manhattan_distance(Sensor, Beacon),
VerticalDistance = case BeaconsRowY > SensorY of
true -> abs(BeaconsRowY - SensorY);
false -> abs(SensorY - BeaconsRowY)
end,
HorizontalDistanceLeft = SensorToBeaconDistance - VerticalDistance,
case HorizontalDistanceLeft < 1 of
true -> [];
false -> [{X, BeaconsRowY} || X <- lists:seq(SensorX - HorizontalDistanceLeft, SensorX + HorizontalDistanceLeft)]
end.
Here I remove duplicates and squares that already have a beacon in it:
Positions = find_positions_where_beacon_cannot_be(SensorsWithBeacons, BeaconsRowY),
Beacons = lists:map(fun({_, Beacon}) -> Beacon end, SensorsWithBeacons),
% we need to -- Beacon to eliminate positions where there already is a beacon
Answer = length(lists:uniq(lists:flatten(Positions)) -- Beacons),The puzzle is not the fastest one, but it finds results within 20 seconds or so.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day15_puzzle1
Day 15 – Puzzle 2
The second puzzle is about eliminating squares from a given area. The approach from the previous part of today’s puzzle is not going to work, as it is too slow. Checking all the squares one by one does not work either. We need a faster way to eliminate whole ranges of numbers. Let’s propose the representation of the board as a list of ranges (each range representing a row or its part.
Here is an example of a full board 21 x 21 (each dimension 0 to 20):
[
{{2, 0}, {20, 0}},
{{1, 1}, {20, 1}},
{{0, 2}, {20, 2}},
{{0, 3}, {20, 3}},
...
{{0, 20}, {20, 20}}
]
Now let’s take a look at 3 cases:
Let’s consider the first row in the first case X coordinate of the sensor is smaller the smallest X. Then we can cut away some elements from the beginning and proceed to the second row etc.
This is how the board is repeated after the area subtraction:
[
{{2, 0}, {20, 0}},
{{1, 1}, {20, 1}},
{{0, 2}, {20, 2}},
{{0, 3}, {20, 3}},
...
{{0, 20}, {20, 20}}
]
Respectively in the third case, we eliminate some elements from the row’s end for each of the given rows.
This is how the board is repeated after the area subtraction:
[
{{0, 0}, {18, 0}},
{{0, 1}, {19, 1}},
{{0, 2}, {20, 2}},
{{0, 3}, {20, 3}},
...
{{0, 20}, {20, 20}}
]
The most interesting is the second case as it divides a given row into 2 sub rows:
[
{{0, 0}, {1, 0}}, {{7, 0}, {20, 0}},
{{0, 1}, {2, 1}}, {{6, 1}, {20, 1}},
{{0, 2}, {3, 2}}, {{5, 2}, {20, 2}},
{{0, 3}, {20, 3}},
{{0, 4}, {20, 4}},
...
{{0, 20}, {20, 20}}
]
Notice that the row’s parts can be separated and still represent the ranges we need to search.
The code applying this logic is somewhat complex. It needs to remove empty ranges and do some checking not to get incorrect ranges like this one (the left X must be smaller or equal to the right one):
{{1, 1}, {-1, 1}}Here it is:
eliminate_impossible_positions(SensorsWithBeacons, PotentialDistressBeaconRow) ->
lists:foldl(fun(E, A) -> lists:flatten(cut_down_row(E, A)) end, PotentialDistressBeaconRow, SensorsWithBeacons).
cut_down_row({Sensor = {SensorX, SensorY}, Beacon}, PotentialDistressBeaconRows) ->
lists:map(
fun(Row = {From = {FromX, FromY}, To = {ToX, ToY}}) ->
if
SensorX < FromX ->
Shorten = manhattan_distance(Sensor, Beacon) - manhattan_distance(Sensor, From),
case Shorten >= 0 of
true ->
NewFromX = FromX + Shorten + 1,
case NewFromX >= ToX of
true -> [];
false -> {{NewFromX, FromY}, {ToX, ToY}}
end;
false -> Row
end;
SensorX > ToX ->
Shorten = manhattan_distance(Sensor, Beacon) - manhattan_distance(Sensor, To),
case Shorten >= 0 of
true ->
NewToX = ToX - Shorten - 1,
case NewToX =< FromX of
true -> [];
false -> {{FromX, FromY}, {NewToX, ToY}}
end;
false -> Row
end;
true ->
Shorten = manhattan_distance(Sensor, Beacon) - manhattan_distance({0, SensorY}, {0, FromY}) + 1,
case Shorten > 0 of
true ->
[
begin
NewX1 = SensorX - Shorten,
case FromX =< NewX1 of
false -> [];
true -> {{FromX, FromY}, {NewX1, ToY}}
end
end,
begin
NewX2 = SensorX + Shorten,
case NewX2 =< ToX of
false -> [];
true -> {{NewX2, FromY}, {ToX, ToY}}
end
end
];
false -> Row
end
end
end
, PotentialDistressBeaconRows).
be simplified, but I think it is good enough as it just works.
When running the solution for this puzzle it takes about 20 seconds to get the results.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day15_puzzle2
Day 16
Today’s puzzle is probably the hardest in this year’s Advent of Code so far.
It’s about finding the most effective way of moving between and opening valves to release the pressure.
In the first puzzle, the simulation takes 30 steps. In each step, we can either open a valve (if it is closed) or move to the next valve (there is a corridor connecting the next valve with the current one. We need to determine the best order to open the valves. take a list of valves, and the initial paths (that is a single path containing exactly one valve [“AA”] (our starting point)). Each path in the given list of paths generates a new list of paths with the last element (and intermediate path to it) added to the path that you started from.
Paths = [["AA"]]
Valves = ["BB", "CC"]
NewPaths = [["AA", "BB"], ["AA", "CC"]]
This idea almost works, but it takes way too long to execute. Let’s take a look at some ideas for optimisation to make the waiting time bearable.
Day 16 – Puzzle 1
Let’s start by looking at the input data. We can notice that there are some valves that release 0 pressure, so it does not matter if we visit them or not with regards to how much pressure we finally release.
So, let’s focus only on the valves that release pressure. We want to visit them all (if we are on time) so the question that remains now is in which order we should visit them.
Having done that, I wanted to generate all permutations of valves that matter, and fill the gaps between them with the shortest paths, for those paths calculate the pressure released and then get the max from those values to get the answer. Unfortunately, it turned out that it takes way too long to generate all of the permutations.
SoI had to change my approach. In my improved attempt, I am adding only one node (from not yet visited nodes that have release pressure greater than zero) and then from all of the paths find only N currently best scoring (most promising) and drop processing the rest of them. I also added a second parameter that pruning should happen only after some steps are done. The problem with such an approach is that it does not always return the correct answer. It may prune the path that should eventually generate the correct answer in the early stage as it is not promising enough in the early steps of the simulation. But this is not a great deal, as after a minute before you can submit another answer. To get initial values, I ran the example simulation and tuned the values until they returned a correct answer.
It turns out I was lucky and I got the correct answer on the first shot after waiting about 20 seconds or so.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day16_puzzle1
Day 16 – Puzzle 2
The second puzzle shortens simulation time but adds an elephant that can also move and close valves. This requires an insignificant code change, to build, store and process 2 paths instead of one. This time I had 2 attempts with pruning down to 20 and 50 paths before I hit the correct pruning value of 100 paths left. The simulation takes about a minute to complete.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day16_puzzle2
Day 17
Today’s puzzle is about simulating where there is a screen 7 pixels wide and the predefined shapes fall from a height moving sideways (if it is possible (and downwards), until they hit rocks (previously fallen shapes) or bottom of the screen.
Day 17 – Puzzle 1
In the first part of the simulation, we need to simulate 2022 rocks. This is where we can implement rocks falling by simulating what they do step by step. The task is insignificant, so I would like to focus on something slightly unusual, and that is how unusual formatting of code may improve readability sometimes. See this example:
% ####
shape(1, CurrentMaxY) ->
X = 3,
Y = CurrentMaxY + ?ABOVE,
[
{X, Y}, {X + 1, Y}, {X + 2, Y}, {X + 3, Y}
];
% .#.
% ###
% .#.
shape(2, CurrentMaxY) ->
X = 3,
Y = CurrentMaxY + ?ABOVE,
[
{X + 1, Y + 2},
{X, Y + 1}, {X + 1, Y + 1}, {X + 2, Y + 1},
{X + 1, Y}
]
;
% ..#
% ..#
% ###
shape(3, CurrentMaxY) ->
X = 3,
Y = CurrentMaxY + ?ABOVE,
[
{X + 2, Y + 2},
{X + 2, Y + 1},
{X, Y}, {X + 1, Y}, {X + 2, Y}
];
% #
% #
% #
% #
shape(4, CurrentMaxY) ->
X = 3,
Y = CurrentMaxY + ?ABOVE,
[
{X, Y + 3},
{X, Y + 2},
{X, Y + 1},
{X, Y}
];
% ##
% ##
shape(5, CurrentMaxY) ->
X = 3,
Y = CurrentMaxY + ?ABOVE,
[
{X, Y + 1}, {X + 1, Y + 1},
{X, Y}, {X + 1, Y}
];
shape(floor, _) ->
[{X, 0} || X <- lists:seq(1, 7)].
Function shape/2 takes the shape type (integer between 1 and 5) and the height of the bottom row of the new shape and returns the new shape. For each shape, there is a comment above on how the shape is drowned. Then the code formatting reflects the same shape so that it is much easier to check each of the coordinates.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day17_puzzle1
Day 17 – Puzzle 2
WIP
Day 18
Today’s puzzle is about searching 3D space with 1x1x1 cubes. In both puzzles, we are interested in counting the faces of the cubes.
Day 18 – Puzzle 1
In the first puzzle, we need to count the number of faces of cubes that are visible. A cube’s face is visible when there is no cube in the direction the wall is facing. Let’s take a look at the example. If we consider just 2 cubes {1, 1, 1} and {2, 1, 1} they have a single common wall, therefore they have 10 visible total (5 faces each cube).
To count the total visible faces, we need to calculate them for each of the cubes. For each cube, we need to check if there is a neighbour cube in one of 6 directions, it is something like the Von Neumann neighbourhood, but for 3 dimensions with max distance in Manhattan metrics of 1.
Here is the code doing that:
count_common_walls(Cubes) ->
AllCubesSet = sets:from_list(Cubes),
lists:sum(lists:map(
fun(Cube) ->
length(find_walls_not_touching_any_other_cube(Cube, AllCubesSet))
end, Cubes)).
find_walls_not_touching_any_other_cube(_Cube = {X, Y, Z}, AllCubesSet) ->
PotentialNeighbors = [
{X + 1, Y, Z},
{X - 1, Y, Z},
{X, Y + 1, Z},
{X, Y - 1, Z},
{X, Y, Z + 1},
{X, Y, Z - 1}
],
lists:filter(fun(Neighbor) ->
not sets:is_element(Neighbor, AllCubesSet)
end, PotentialNeighbors).The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day18_puzzle1
Day 18 – Puzzle 2
For the second puzzle, we need to calculate only the walls facing outwards. The face is facing outwards when it not only is not covered by another cube like in today’s puzzle 1. but also the wall can be reached from outwards moving only horizontally or vertically. To solve today’s puzzle we need to notice if the wall can be reached from outwards it means that the outwards can be reached from the wall. So now we need to repeat the calculations from the first puzzle adding the simulation of expanding steam. If the steam can reach outwards then the wall should be counted otherwise the wall is facing inwards.
Here is a simulation checking if any cube of steam is enclosed:
is_enclosed(_Neighbors, PrevCubesCount, CubesCount, _CubesLimits, _AllCubesSet) when PrevCubesCount == CubesCount ->
true;
is_enclosed(Neighbors, _PrevCubesCount, CubesCount, CubesLimits, AllCubesSet) ->
case lists:any(fun(Neighbor) -> has_reached_box_border(Neighbor, CubesLimits) end, Neighbors) of
true -> false;
false ->
NewNeighbors = lists:uniq(
lists:flatten(
lists:map(
fun(Neighbor) ->
lists:filter(fun(N) -> not sets:is_element(N, AllCubesSet) end, [Neighbor | potential_neighbors(Neighbor)])
end, Neighbors))),
is_enclosed(NewNeighbors, CubesCount, length(NewNeighbors), CubesLimits, AllCubesSet)
end.
has_reached_box_border({X, Y, Z}, [MinX, MaxX, MinY, MaxY, MinZ, MaxZ]) ->
X =< MinX orelse X >= MaxX orelse
Y =< MinY orelse Y >= MaxY orelse
Z =< MinZ orelse Z >= MaxZ.
Then it is just a matter of extending the condition checking if the wall should be counted into:
(not sets:is_element(Neighbor, AllCubesSet)) andalso (not is_enclosed([Neighbor], 0, 1, CubesLimits, AllCubesSet))
Notice that the CubesLimits are the edges of the simulation and they are calculated by finding minimal and maximal value for each dimension and then extending it by 1.
The simulation takes about a minute to calculate, but this can be improved by e.g. caching all of the previously checked doe being enclosed cubes of steam. The second thing I would attempt to improve the simulation would be to use a set for tracking already checked cubes of steam.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day18_puzzle2
Day 19
Today’s puzzle is about searching through possibilities of building one of a few robots in a given number of steps. We are given a single robot at the beginning which mines ore. If we gather enough ore we can build another ore robot or clay robot. Then when we gather enough clay we can build obsidian robots. When we gather enough obsidian and ore, we can build geode robots. When the robot is set, it produces one resource each turn. For a given number of inputs (which robot costs how much of resources, blueprints), we need to figure out how much geode we can crack at most after given number of steps in the simulation.
Day 19 – Puzzle 1
The first puzzle is about finding the best production plan (how many geodes they can produce at most in 24 steps for 30 blueprints.
The puzzle is actually about searching through possibilities of building a robot or not and which robot to build.
I implemented a DFS (https://en.wikipedia.org/wiki/Depth-first_search) algorithm, but the initial implementation was too slow.
To make it run faster I filtered out all of the branches where the robot cannot be built:
which_robots_can_be_build(Blueprint = {_ID, RobotsWithCosts}, Materials, Robots, MaxRobotsNeededPerResource) ->
Key = [which_robots_can_be_build, Blueprint, Materials, Robots, MaxRobotsNeededPerResource],
case cache_get(Key) of
[] ->
Filtered = lists:filter(
fun({RobotType, Costs}) ->
CurrentProduction = maps:get(RobotType, Robots),
MaxNeededProduction = maps:get(RobotType, MaxRobotsNeededPerResource),
(CurrentProduction =< MaxNeededProduction)
andalso
(maps:fold(
fun(CostType, CostValue, Acc) ->
Acc andalso (maps:get(CostType, Materials) >= CostValue)
end, true, Costs))
end, RobotsWithCosts),
Result = case lists:filter(fun({geode, _}) -> true; (_) -> false end, Filtered) of
[] -> Filtered;
[X] -> [X]
end,
cache_put(Key, Result),
Result;
[{_, Value}] -> Value
end.
The second optimisation was to produce robots only if the supply of the resources is no bigger than the maximal potential demand per round.
This is expressed in
CurrentProduction = maps:get(RobotType, Robots),
MaxNeededProduction = maps:get(RobotType, MaxRobotsNeededPerResource),
(CurrentProduction =< MaxNeededProduction)
condition.
I had to add the max demand for the geodes to be `infinity`.
The third optimisation I did was to cache partial results for some of the functions using ets tables:
f(Arg1, Arg2, Arg3) ->
Key = [f, Arg1, Arg2, Arg3],
case cache_get(Key) of
[] ->
...
Result = do_stuff(...)
cache_put(Key, Result),
Result;
[{_, Value}] -> Value
end.
start_cache(Table) ->
ets:new(Table, [set, named_table]).
clear_cache(Table) ->
ets:match_delete(Table, '_').
cache_put([Table | Key], Value) ->
ets:insert(Table, {Key, Value}).
cache_get([Table | Key]) ->
ets:lookup(Table, Key).
Thins limit searching each blueprint to a few seconds. So I got the answer after about a minute.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day19_puzzle1
Day 19 – Puzzle 2
The second part is about checking only the first 3 blueprints but with a search depth of 32. The same code should eventually return results. But it takes way too long for me to wait. If I find time later I will search for other improvements to solve this puzzle.
Day 20
Today’s puzzle is about moving elements one by one across the list based on their value. If they are negative, then move it left otherwise right. If you run out of indexes put the element back at the beginning (or end) of a list.
Day 20 – Puzzle 1
For this puzzle, it is tempted to pass the original list to C using a port or NIF and then use double-linked lists to traverse across the list. I ended up just traversing a normal list keeping track of the elements before and after me.
An interesting thing is that the function to travers backwards and forwards can be a single function:
move_forward(Before, Current, After, Moves, _) when Moves =< 0 ->
Before ++ [Current] ++ After;
move_forward(Before, Current, [], Moves, backwards) ->
move_forward([], Current, Before, Moves - 1, backwards);
move_forward(Before, Current, [], Moves, forward) ->
move_forward([], Current, Before, Moves, forward);
move_forward(Before, Current, After, Moves, Direction) when Moves > length(After) ->
move_forward(Before ++ After, Current, [], Moves - length(After), Direction);
move_forward(Before, Current, [AfterH | AfterT], Moves, Direction) ->
move_forward(Before ++ [AfterH], Current, AfterT, Moves - 1, Direction).
move_backwards(Before, Current, After, Moves) ->
lists:reverse(move_forward(lists:reverse(After), Current, lists:reverse(Before), abs(Moves) + 1, backwards)).
In short, reversing correctly whatever is before and after the current element makes those 2 functions work identically.
The complete code is available here:
https://github.com/aleklisi/AdventOfCode2022/tree/main/day20_puzzle1
Day 20 – Puzzle 2
WIP
Conclusion
Aleksander Lisiecki, the problem solver and author of this blog, will be the trainer for three online training courses in January next year. To find out more, visit our training website.
