Advent of Code 2022, Day six - Part Two

Preface

Now that we have the following data structure from our previous post, we can create the logic to retrieve the start of the packet marker.

The start of the packet is a sequence of four unique characters that are all different.

Design

We now that we need to get the position of the first character after the start of packet sequence. So we need to iterate through the stream while checking if the subsequent four characters are all unique. Which in pseudo-code could look like this

1
2
3
4
5
6
7
8
9
10
11
12
datastream = "mjqjpqmgbljsphdztnvjfqwrcgsmlb"

for (int i = 0; i < datastream.length - 3; i++) {
    char1 = datastream[i]
    char2 = datastream[i + 1]
    char3 = datastream[i + 2]
    char4 = datastream[i + 3]

    firstCharMatches = char1 == char2 || char1 == char3 || char1 == char4
    secondCharMatches = char2 == char3 || char2 == char4
    thirdCharMatches = char3 == char4
}

However, if we start digging trough the Kotlin documentation for character or list operations we see the windowed method.

Returns a list of snapshots of the window of the given size sliding along this collection with the given step, where each snapshot is a list.

• Jetbrains

So this means we can use the windows method to slide across our list by one character at a time, while validating that the fourteen characters we retrieve are all unique.

To check if characters are unique we can use the toSet method on the CharSequence we get inside the windowed lambda. In Kotlin a Set has the benefit of not supporting duplicate elements (Jetbrains, n.d.).

So if we take our CharSequence of fourteen elements and turn it into a set, we should only get a set of fourteen items when all fourteen chars are unique. So with that knowledge, lets rewrite the psuedo-code again.

1
2
3
4
5
6
7
datastream = "mjqjpqmgbljsphdztnvjfqwrcgsmlb"

datastream.windowed(size = 14, step = 1) { charSequence ->
    if (charSequence.toSet().size == 14) {
        // We now have fourteen unique characters
    }
}

This does look a lot cleaner, so let’s start implementing it in actual Kotlin code.

Implementation

Business logic

Now we have an idea of our design, let’s start implementing it in our PartTwo class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class PartTwo(
    private val sanitizer: Sanitizer
) {
    fun getFirstMessagePosition(): Int {
        val chunkSize = 14
        var currentIndex = -1
        var firstMarkerPosition = -1

        sanitizer.getDatastreamBuffers()?.windowed(size = chunkSize, step = 1, partialWindows = true) {
            currentIndex++

            if (it.toSet().size == chunkSize && firstMarkerPosition <= 0) {
                firstMarkerPosition = currentIndex + chunkSize
            }
        }

        return firstMarkerPosition
    }
}

At Step 1 we declare all variables which we need outside of our windowed method. The chunkSize is the size of the marker packet, which was 4 according to the assignment. To get the first marker position, we need to keep a count of the current index, which will start at -1 because at the first iteration before any check, it’s incremented at Step 3.

Then at Step 2 we iterate through our data stream buffers using the windowed method. In the method we give the chunkSize, which is the size of the marker, the step, which is the number of elements we shift each iteration, and finally we set partialWindows to true, this ignores the chunkSize at the end of the list when there are less than fourteen items (Jetbrains, n.d.).

To check if our current window of chars are unique, we turn them into a set at Step 4 and validate that the set size is equal to the chunkSize, which was the number of characters needed to determine the start of packet marker. We also validate that the firstMarkerPosition hasn’t a value higher than 0 to make sure we only update that variable once. So if there are more than one sequences of fourteen characters that are unique, we only get the index of the first one. At Step 5 we set the firstMarkerPosition to the currentIndex plus the chunkSize, because the currentIndex is the index that the marker starts at but to retrieve the index of the first message we need to add the start of packet marker size to the index.

Test case

We have written our business logic, and for our test input we now that the expected output for the test data is 7. So we can start to write our test case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class PartTwoTest {
    @Test
    fun testGetFirstMarkerPosition() {
        // Arrange
        val resource = {}::class.java.getResource("/input_part_two.txt")
        val sanitizer = Sanitizer(resource)
        val sut = PartTwo(sanitizer)
        val expectedPosition = 19

        // Act
        val result = sut.getFirstMessagePosition()

        // Assert
        assertEquals(expectedPosition, result)
    }
}