Ideas and Solutions for Advent of Code 2021 in Kotlin — Part 2/4

The second week of Advent of Code introduces us to more difficult tasks, some of which require fundamental knowledge in algorithms and data structures. Do you need an idea or a tiny hint to get that gold star?

Here we are, the second 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.

Ideas and Solutions for tasks 1 to 6 can be found here.

Day 7: The Treachery of Whales

We are provided with an array of different values, which we need to align to a single value with the lowest possible cost. The cost function is different for the two sub-tasks. Here is the complete task.

The solution is as simple as checking all possible values to align from min value to max value in the original array and choosing one with the lowest cost. The cost function (array of cost of moving value by 0, 1, 2 … N) can be passed as an argument to your solution.

Here is my solution.

Day 8: Seven Segment Search

Malfunctioning seven-segment digital display sends us some signals, which we need to decode knowing the representation of the full set of digits and which segments are used for each entry. Here is the complete task.

The first sub-task requires you to parse only four digits — 1, 4, 7, 8. All of them are unique in terms of segments used, so guessing them is relatively simple.

The second sub-task asks you to guess the other 6 digits. I’m sure there are many different sequences in which you can guess them, but in my case, I’ve done the following:

• segments b and d are present in digit 4, but not in digit 1
• segment bd is present only in digit 5 between all digits that use 5 segments
• then we can decode segments c and f by looking on the intersection of digits 1 and 5
• using newly discovered segments, we find digits 3, 2, and 6
• segment d can be found as an intersection of bd and digit 2
• finally, we found digits 9 and 0 as 6-segment digits having or not having the segment d

Here is my solution.

Day 9: Smoke Basin

The 2D array of digits gives us a map on which we need to find the lowest points, where all adjacent points are higher than the current point, and calculate basins for each of them. Here is the complete task.

The first graph-theory task in this year Advent of Code. You can check the very point to locate of lowest points, and then launch the Breadth-first search or Depth-first search from those points to find basins.

Here is my solution.

Day 10: Syntax Scoring

The “correct parenthesis sequences” would be a more appropriate title for this task — yes, another typical algorithm. I like the way people can discover these elegant algorithms while making fun! Here is the complete task.

In short, this classical task is usually solved by a stack where you add opening brackets while moving through the input from left to right, and from where you pop them when encountering closing brackets. If the stack is empty when you try to pop something out of it, or it’s not empty after input is handled, the parenthesis sequence is incorrect. See more details here.

As for sorting the results, take a look at a standard Kotlin’s sorted and sortedDescending functions ;)

Here is my solution.

Day 11: Dumbo Octopus

Another 2D array of digits represents a map with values increasing by one on each iteration to eventually flash when reaching the value of 10. Flashing means that the value is being reset to 1, while all adjacent values are increased by one immediately. Here is the complete task.

And this is the graph task again, a typical BFS (Breadth-first search) task where you use all flashpoints during each as starting points, and iterate through them while there are no more points to flash during the current step.

There is an interesting trick to check all adjacent cells in Kotlin — create the list of all adjacent cells and filter out those which are out of the array or already flashed.

Here is my solution.

Day 12: Passage Pathing

Here we are giving a graph that contains two types of nodes — those which can be visited only once, and those which can be visited an unlimited number of times. How many different paths are there from the start to the end? Here is the complete task.

Here we are, the DFS (Depth-first search) folk. It’s a recursive algorithm, so we need to pass the current path for each call as an argument to be able to check if we already visited some nodes (those which can be visited only once).

But how to be with a second sub-task where we, exceptionally, can visit a single non-multiple-times-visitable node the second time? Actually, the same solution can be applied for both sub-tasks if we introduce the concept of tolerance meaning how many second attempts we have at the current iteration of search (zero for the first sub-task, one for the second sub-task).

Kotlin’s isLowerCase simplifies the solution a lot when we need to check which type of node we’ve got now.

Here is my solution.

Bottom line

Those were the second 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!