Auto Added by WPeMatico

Tips and Tricks for Solving Advent of Code

Advent Of Code is currently ongoing and many people all over the world are taking part. We’d like to share some tips and tricks for solving the puzzles in Kotlin – we hope you find some of them helpful! Feel free to add your favorite tips or thoughts in the comments!.

If you’re solving the puzzles in Kotlin, don’t forget to add the aoc-2021-in-kotlin topic to your repo to take part in our giveaway! If you’re starting from scratch, consider using our prepared Github template.

How do you usually go about solving the puzzles? First of all, you read and parse the input data. Let’s start with some tips for this process, and then discuss tips for writing the actual solutions in Kotlin.

1. Jumping between sample and real input

All of the Advent of Code puzzles provide your own “personal” input and the sample input to check your solution. You often need to switch back and forth between the sample and real input. If the solution for the first part works for the sample input, you then need to run it on the real input to get your result. If the solution then works on the real input, you likely switch back to the sample input to start solving the second part of the puzzle.

One of the ways to switch between two inputs quickly is by using comments with the IntelliJ IDEA action “Comment with Line Comment”. This changes the line state and removes the comment from the commented line, rather than simply adding a comment.

You can put the sample and real inputs in different files and toggle between comments for the file names by pressing the Ctrl+/ shortcut twice:

Comment line action

These small things make a difference and make working with IntelliJ IDEA a pleasure!

2. Parsing input

The next thing to do after reading the input is to parse it. You can either use the Kotlin library functions for working with strings or regular expressions. Library functions like substringBefore() and substringAfter() cover lots of cases and are often enough. Use String.toInt() and Char.digitToInt() to convert the string content or characters into integers.

For more complicated scenarios, there are regular expressions. Use the destructured function to assign the output to different variables right away:

val inputLineRegex = """(d+),(d+) -> (d+),(d+)""".toRegex()

val (startX, startY, endX, endY) = inputLineRegex
    .matchEntire(s)
    ?.destructured
    ?: throw IllegalArgumentException("Incorrect input line $s")

The action “Check RegExp” in IntelliJ IDEA allows you to quickly check whether the sample input satisfies your regular expression.

Comment line action

3. Storing input

It’s often helpful to introduce domain types, even for smaller tasks like these puzzles. Solving the task for Cells and Boards, or for Segments and SevenSegmentDigits can be much easier than working directly with Ints, List of Lists of Ints, or Chars and Sets of Chars. Types help to direct your thinking to the heart of the problem.

Kotlin makes this really easy – define a one-line data class and that’s it. You don’t need a separate file, like in Java, since it’s in your main file with the rest of your solution code:

data class Step(val direction: Direction, val units: Int)

In Kotlin, you can use an extension to convert an input line directly to a required type:

fun String.toStep(): Step
fun String.toTicket(): Ticket
fun String.toSevenSegmentDigitList(): List<SevenSegmentDigit>

Then your typical starter code will look like this:

val steps = readInput(fileName).map(String::toStep)

You can either use the function reference String::toStep or the lambda expression map { it.toStep() }.

4. Enumerations instead of strings

It might be tempting to manipulate the string literals directly, but making them enum constants makes it easier to write the code and reason about how it works. You never know what comes in the second part of the puzzle!

enum class Direction { UP, DOWN, FORWARD }
data class Step(val direction: Direction, val units: Int)

It is easy to convert an input string to an enum and use the EnumClassName.valueOf("") function to get the constant by name:

// "forward 8"
fun String.toStep() = Step(
   Direction.valueOf(substringBefore(" ").uppercase()),
   substringAfter(" ").toInt()
)

With when expressions you can check all of the options and you don’t need to include the else branch:

Comment line action

IntelliJ IDEA can generate all the branches automatically.

for ((direction, units) in steps) {
   when (direction) {
       UP -> depth -= units
       DOWN -> depth += units
       FORWARD -> horizontalPosition += units
   }
}

Note that in the destructuring declaration syntax in the for loop, you automatically assign two properties, the contents of each Step, into two loop variables.

5. From typealias to a class

If working with primitives is easier at first, and defining a separate class looks too cumbersome, consider defining a typealias. You can convert it into a class later, if needed. When you replace a typealias with a class, most of the code continues to compile, and you immediately see which functions are missing.

typealias Segment = Char
data class SevenSegmentDigit(val segments: Set<Segment>) {
   constructor(s: String): this(s.toSet())
   override fun toString() = segments.toList().sorted().joinToString("")
}

For example, the characters from 'a' to 'g' used to encode the seven-segment display can be referred to as Segments in the code and be regular Chars underneath. You can define the SevenSegmentDigit class first as a typealias for Set and later convert it to a class, for example, if you want to replace a default toString with a custom one.

6. Building lists and maps

In addition to the standard listOf(), mutableListOf(), and similar functions, you can use other methods to build collections.

You can call the List function that looks like a constructor (but is not!) to provide a way to calculate each element:

List(4) { it * it } // [0, 1, 4, 9]

Use buildList and buildMap functions to build data structures imperatively:

val monsters: List<Position> = buildList {
   for (y in 0..tile.size - Monster.height) {
       for (x in 0..tile.size - Monster.width) {
           if (monsterAt(tileRotation, x, y)) {
               add(Position(x, y))
           }
       }
   }
}

In this example, we call add on a MutableList inside the lambda, and the resulting type is the read-only List.

The similar sequence {..} function builds a Sequence lazily yielding values one by one.

7. Associate and group

The task of building a map from a list occurs quite often, and associate and groupBy functions make this operation straightforward. You can group elements by the provided property with groupBy, use elements as map keys to provide a way to build values (associateWith), use elements as values (associateBy), or provide a way to build a key-value pair from each element (associate).

The groupBy function groups the elements with the specified value used as a map key:

val occurrences: Map<Int, List<Segment>> =
   segments.groupBy { countSegmentInAllDigits(it) }
// {8=[a, b], 9=[c], 7=[d, g], 4=[e], 6=[f]}

The result of calling countSegmentInAllDigits in this example becomes the key in the map.

If you don’t need the groups directly, but you need to find the size of each group, use a lazy counterpart to groupBy: the groupingBy function. It doesn’t return a map straightaway, but it allows you to analyze the groups in a lazy manner:

listOf("abc", "c", "ad", "bc", "ab", "ca")
   .groupingBy(String::first)
   .eachCount() // {a=3, e=2, d=1}

If the property you’re using to group the elements is unique, use associateBy. For instance, if you need to access elements by their indexes, associateBy will build a map from indexes to elements for you:

val rulesMap: Map<Int, Rule> = rules.associateBy { it.index }

Let’s imagine you need to build a map representing an initial state by associating each of the input numbers with the corresponding Node. Use associateWith:

val initialState: Map<Int, Node> = numbers.associateWith { Node(it) }

If you need more complicated keys and values, use associate:

val bagRuleMap: Map<Bag, List<Content>> = bagRules.associate { it.bag to it.contentList }

If you don’t remember which associate function you need, choose the general associate one, and IntelliJ IDEA will suggest a better one automatically:

Comment line action

8. Sliding by windows

Sliding a list to get chunks of a given size is often useful, like in this year’s first puzzle.

numbers.windowed(2).count { (first, second) -> first < second }
"abcde".windowed(2) // [ab, bc, cd, de]

An alternative to building a list of chunks of size 2 is to use zipWithNext().

9. Sum of, min of

You don’t need to map the elements first to later find the resulting sum – the sumOf function combines these two operations. IntelliJ IDEA even suggests these replacements automatically:

Comment line action

There are similar functions maxOf and minOf for finding the maximum and minimum among the transformed values.

10. Adding index

Need to perform computations with an element index? In addition to the withIndex() extension that returns a list of pairs to iterate through, you can use many “indexed” counterparts for standard library functions, such as forEachIndexed, filterIndexed, mapIndexed, foldIndexed, and so on.

In the following example, the final calculateScore function uses the indexed version of fold to include an index into a computation of the result:

fun RoundConfiguration.calculateScore(): Long {
   val winner = listOf(playerA, playerB).maxByOrNull { it.size }!!
   return winner
       .cards()
       .foldIndexed(0L) { index, acc, element ->
           acc + (winner.size - index) * element
       }
}

Note how we marked 0 as a Long constant here (0L) to perform the computation on Long values.

11. Also logging

If the puzzle answer isn’t correct and you want to track the intermediate results step by step, you can print or log the intermediate values. The also function allows you to include println or log directives in the middle of the call chain or display the function result if you use an expression-body syntax.

In this example, we return the result of the function and also do some logging:

private fun checkRow(row: List<Int>, visited: Set<Int>) =
   row.all { elem -> elem in visited }
       .also { result -> log("Checking row $row $visited: $result") }

Here, we insert also calls in the middle of the call chain to observe the intermediate results of the computation:

val differences = input
   .windowed(2)
   .also(::log)
   .map { (first, second) -> second - first }
   .also(::log)
   .sorted()

If you need to print each list element on a separate line, you can include .onEach(::println) to the middle of the call chain. onEach performs an operation on each element and returns the unmodified list.

To avoid commenting on the lines with println, make a habit of using your own small log function instead. This way, you only need to change it in one place to stop printing all of the intermediate values for your solution.

12. Queue and stack together

Need a queue or a stack to implement an algorithm when solving the puzzle? Use ArrayDeque, a double-ended queue that provides quick access to both ends. It can be used either as a queue or a stack when needed.

For instance, in a classic implementation of a depth-first search, create a queue as an ArrayDeque and call its add and removeFirst methods inside:

fun dfs(board: Board, initial: Cell): Set<Cell> {
   val visited = mutableSetOf<Cell>()
   val queue = ArrayDeque<Cell>()
   queue += initial
   while (queue.isNotEmpty()) {
       val cell = queue.removeFirst()
       visited += cell
       queue += board.getUpperNeighbors(cell)
   }
   return visited
}

In this example, we use the short syntax += to call the plusAssign(element: T) and plusAssign(elements: Iterable) operators, which simply redirect to the corresponding add functions.

Of course, the ArrayDeque structure is useful any time you need quick access to both the start and end of the list of elements.

13. Operators

Operator overloading, which looks like mostly library or DSL-magic functionality, might also be useful when solving such small puzzles.

Consider overloading get and set operators to simplify the code for working with your class. For instance, by providing the get operator that takes Cell as an argument for the following class you can access its content more easily:

dataclass Board(val content: List<List<Int>>) {
   operator fun get(cell: Cell) =
       content.getOrNull(cell.i)?.getOrNull(cell.j)
}

Instead of writing board.content[cell.i][cell.j] for all invocations, you write

board[cell]. You can provide the set operator for mutable content accordingly.

Using the contains operator might make the code cleaner:

data class Line(val start: Point, val end: Point) {
   operator fun contains(point: Point): Boolean { … }
}

Then you can call it via the in keyword:

inputLines.count { line -> point in line }

If your elements are comparable, you can make them implement the Comparable interface, and then compare the elements using the standard <, <=, >, and >= operations.

———

Last but not least, consider creating a collection of your utilities specifically for solving Advent of Code puzzles. For example, you’ll definitely find a task that requires a point with two integer coordinates and uses its neighboring points!

That’s all for now! We hope that you enjoy solving the AdventOfCode puzzles as much as we do, and find these small tips useful!

Continue ReadingTips and Tricks for Solving Advent of Code

End of content

No more pages to load