Ideas and Solutions for Advent of Code 2021 in Kotlin — Part 1/4
There are so many things to do before Christmas, so I was always wondering how people find extra time to solve a daily programming puzzle of Advent of Code. Well, this year I’m one of those lucky folks with a bunch of spare time.
Advent of Code is an annual event of Christmas-oriented programming challenges started December 2015. Every year since then, on the first day of December, a programming puzzle is published every day for twenty-four days. You can solve the puzzle and provide an answer using the language of your choice.
Extra reason by JetBrains in the form of the giveaway of some Kotlin care packages has certainly contributed to my motivation. But what’s the point of solving tasks without sharing your ideas and solutions with the community ;)
So here we are, the first six tasks. What’s special about this article? I won’t be sharing the complete editorial, but the key idea only, so you can still solve the task by yourself. And if you need more guidance, there is a source code linked.
Day 1: Sonar Sweep
We are given an array of heights of a seafloor. We need to calculate the number of times heights (sub-task one) and sliding triples of heights (sub-task two) are increasing. Complete task is here.
To solve both tasks we need to go from left to right and compare the previous element (or sliding triple) to the current one. That’s pretty simple, but challenge yourself to craft the beautiful code. In Kotlin we may consider using
foldIndexed functions for this.
Day 2: Dive!
The submarine can move in 2D space (horizontal position and depth) controlled by the set of commands. Moves mechanics are slightly different between subtasks, but the overall approach and goal are the same — model moves and find the resulting position. Complete task is here.
The first sub-task can be solved by folding horizontal position and depth changes, but the second sub-task should be modeled exactly as described.
Day 3: Binary Diagnostic
We are given an array of binary numbers on which we need to do some calculations to get the resulting values of epsilon and gamma rates (sub-task one), oxygen and CO2 levels (sub-task two). Complete task is here.
All 4 values are calculated differently, but in essence, they are just operations on binary numbers and their bits:
- to count the number of ones and zeros in columns when we have rows as input, we can use map and mapIndexed along with joinToString functions
- to filter out the binary number by each most or least popular bit, we can use a recursion based on the filter function
- finally, when we need to convert binary number to decimal one, there is a handy
Day 4: Giant Squid
The game of Bingo is a straightforward one — a set of boards (2D arrays of integers) is progressively filled with randomly drawn numbers, the first board to have the completely filled row or column wins. We need to find the board which wins first (sub-task one) and last (sub-task two). Complete task is here.
The solution is the same for both sub-tasks as we need to order boards by the order in which they win. This is another modeling task, but the solution can be made pretty beautiful with Kotlin’s indexOfFirst, count, and takeUnless functions. For example, you can find the row and column indexes of a drawn number on a board, and check only them for completion.
Day 5: Hydrothermal Venture
We are provided with a set of vertical/horizontal (sub-task one) and diagonal (sub-task two) segments, for which we need to count intersections. Complete task is here.
The easiest solution is to model the task on a 2D array (1000x1000 will do). Filling lines can be done by incrementing/decrementing start point coordinates while they both don’t match end coordinates. Incrementing/decrementing totally depends on the direction of a segment (is the start coordinate bigger than the end coordinate?).
Day 6: Lanternfish
Lanternfish spawn exponentially quickly (every 7 turns with the first turn increased to 9). We are provided with initial spawn counters (from 0 to 6) for the initial set of lanternfish. Our goal is to calculate how many lanternfish will be there in X days (X is the only difference between sub-tasks). Complete task is here.
While the first sub-task can be solved by modeling, the second one can’t. But this is a typical 1D dynamic programming task, where we can always say how many lanternfish will be there on day X by knowing the answers for all days from 0 to X-1.
Let’s solve the task for a single lanternfish that spawns on day 0. There is a simple formula to calculate how many fish will be spawned by the fish itself —
day/7 + 1. We need
+1 as the fish spawns another fish on day 0.
But every spawned fish will start spawning fish in 9 days with a period of 7 days, how do we take into account that? By simply adding up all the answers for days X-9, X-16, X-23, and so on to the current day. This is what dynamic programming is about ;)
The initial shift (spawn counter) value can be taken into account by subtracting it from X days to be modeled for each fish.
Those were the first 6 tasks for the Advent of Code. I hope that the ideas and solutions shared here will help you to get another perspective on solving algorithmic tasks with Kotlin.
If your solutions are based on different ideas or are written in different languages, or you simply want to share your solution as well, don’t hesitate to comment on this article. And good luck for the rest of the advent!