This image is generated using Dall-EPrompt: Generate an image of elves walking through the forest carrying big green backpacks in a minimalistic flat style
Preface
Now that we have the following data structure from our previous post, we can start by thinking about the business logic to retrieve the code that’s inside all the rucksacks.
The data structure our sanitizer provides, looks like this.
1
2
3
4
5
6
7
8
[
{ "vJrwpWtwJgWr" , "hcsFMMfFFhFp" }, // Rucksack 1
{ "jqHRNqRjqzjGDLGL", "rsFMfFZSrLrFZsSL" }, // Rucksack 2
{ "PmmdzqPrV" , "vPwwTWBwg" }, // Rucksack 3
{ "wMqvLMZHhHMvwLH" , "jbvcjnnSBnvTQFn" }, // Rucksack 4
{ "ttgJtRGJ" , "QctTZtZT" }, // Rucksack 5
{ "CrZsJsPPZsGz" , "wwsLwLmpwMDw" } // Rucksack 6
]
Design
So now that we have our rucksacks with each compartment seperated, we can think about how we want to setup our business logic. For this part we need to identify the matching character that’s present in the three concurrent backpacks. This means that we need to group all rucksacks by three rucksacks, and get the concurrent character for all three rucksacks.
flowchart LR
subgraph rsOne["Rucksack One"]
direction LR
rsOneCompartmentOne["vJrwpWtwJgWr"]
rsOneCompartmentTwo["hcsFMMfFFhFp"]
end
subgraph rsTwo["Rucksack Two"]
direction LR
rsTwoCompartmentOne["jqHRNqRjqzjGDLGL"]
rsTwoCompartmentTwo["rsFMfFZSrLrFZsSL"]
end
subgraph rsThree["Rucksack Three"]
direction LR
rsThreeCompartmentOne["PmmdzqPrV"]
rsThreeCompartmentTwo["vPwwTWBwg"]
end
subgraph rsFour["Rucksack Four"]
direction LR
rsFourCompartmentOne["wMqvLMZHhHMvwLH"]
rsFourCompartmentTwo["jbvcjnnSBnvTQFn"]
end
subgraph rsFive["Rucksack Five"]
direction LR
rsFiveCompartmentOne["ttgJtRGJ"]
rsFiveCompartmentTwo["QctTZtZT"]
end
subgraph rsSix["Rucksack Six"]
direction LR
rsSixCompartmentOne["CrZsJsPPZsGz"]
rsSixCompartmentTwo["wwsLwLmpwMDw"]
end
rsOneMatchingCharacter["r"]
rsTwoMatchingCharacter["Z"]
sum["Sum()"]
rsOne --> findCharacterOne["FindMatchingCharacter(rucksackA, rucksackB, rucksackC)"]
rsTwo --> findCharacterOne["FindMatchingCharacter(rucksackA, rucksackB, rucksackC)"]
rsThree --> findCharacterOne["FindMatchingCharacter(rucksackA, rucksackB, rucksackC)"]
rsFour --> findCharacterTwo["FindMatchingCharacter(rucksackA, rucksackB, rucksackC)"]
rsFive --> findCharacterTwo["FindMatchingCharacter(rucksackA, rucksackB, rucksackC)"]
rsSix --> findCharacterTwo["FindMatchingCharacter(rucksackA, rucksackB, rucksackC)"]
findCharacterOne --> rsOneMatchingCharacter
findCharacterTwo --> rsTwoMatchingCharacter
rsOneMatchingCharacter --> getPriorityOne["GetPriority(char)"]
rsTwoMatchingCharacter --> getPriorityTwo["GetPriority(char)"]
rsOnePriority["18"]
rsTwoPriority["52"]
getPriorityOne --> rsOnePriority
getPriorityTwo --> rsTwoPriority
rsOnePriority --> sum
rsTwoPriority --> sum
sum --> total["<b>Total</b> 70"]
The priority is based on this information.
Lowercase item types a through z have priorities 1 through 26.
Uppercase item types A through Z have priorities 27 through 52.
And if we sum up each priority of our item types, we get the expected output of 70
Implementation
Business logic
Now we know what we want our code to do, let’s start implementing it in our PartTwo class. For this to work we use the chunked method on our items iterable. The chunked method
can be used for splitting a collection into smaller a collection of smaller collections (Jetbrains, n.d.).
So this means our test data will get the following data structure.
1
2
3
4
5
6
7
8
9
10
11
12
[
[
{ "vJrwpWtwJgWrhcsFMMfFFhFp" }, // Rucksack 1
{ "jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL" }, // Rucksack 2
{ "PmmdzqPrVvPwwTWBwg" }, // Rucksack 3
],
[
{ "wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn" }, // Rucksack 4
{ "ttgJtRGJQctTZtZT" }, // Rucksack 5
{ "CrZsJsPPZsGzwwsLwLmpwMDw" } // Rucksack 6
]
]
As you can see, we have added the two compartments togheter in our data structure, because there’s no need for the two compartments to be different for each rucksack. This can be seen in step 1 in our PartTwo implementation. Wereas in step 2 we ‘chunk’ our list into sublists with three strings each and find the matching character between the three strings. Which we finally sum up in step 3.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class PartTwo(
private val sanitizer: Sanitizer
) {
fun getResult(): Int {
val result = sanitizer.getItems()
?.map { // Step 1
"${it.first}${it.second}"
}?.chunked(3) { // Step 2
val rucksackA = it[0]
val rucksackB = it[1]
val rucksackC = it[2]
findMatchingCharacter(rucksackA, rucksackB, rucksackC)
}?.sumOf { // Step 3
getPriority(it)
}
return result ?: -1
}
/**
* Find the first character in compartment A that is also
* present in compartment B
*
* @param compA the first compartment of the rucksack
* @param compB the second compartment of the rucksack
* @return the character that is present in both compartments
* or an empty char
*/
private fun findMatchingCharacter(compA: String, compB: String): Char {
compA.forEach {
if (compB.contains(it)) {
return it
}
}
return Char.MIN_VALUE
}
/**
* Get the priority of a character based on the following information
*
* Lowercase item types a through z have priorities 1 through 26.
* Uppercase item types A through Z have priorities 27 through 52.
*
* @param character the character for which to get the property
* @return the priority of the given character
*/
private fun getPriority(character: Char): Int {
val priorityAlphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
return priorityAlphabet.indexOf(character) + 1
}
}
As you can see, our getPriority method is exactly the same as for Part One of todays advent of code. However, findMatchingCharacter has changed quite a bit. Instead of searching for the
same character in two lists, we search in three lists. We only iterate over the first item and validate if each character is present in the other two strings. We can even streamline this code a bit
by only iterating over the smallest string. Because all three strings are checked for the matching character, we don’t need to check characters that aren’t available in one string.
So with the optimization, our findMatchingCharacter now looks like this.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Find the first character in rucksack A that also
* present in rucksacks B and C
*
* @param rucksackA the first rucksack
* @param rucksackB the second rucksack
* @param rucksackC the last rucksack
* @return the character that is present in all three
* rucksacks or an empty char
*/
private fun findMatchingCharacter(rucksackA: String, rucksackB: String, rucksackC: String): Char {
if (rucksackA.length > min(rucksackB.length, rucksackC.length)) {
return findMatchingCharacter(rucksackB, rucksackC, rucksackA)
}
rucksackA.forEach {
if (rucksackB.contains(it) && rucksackC.contains(it)) {
return it
}
}
return Char.MIN_VALUE
}
In the if-statement will check if rucksackA is bigger than the smallest rucksackB or rucksackC, if the statement is true it will call the findMatchingCharacter again but with the rucksacks in a different order.
This will generate the following call-stack based on our test input.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// First three items
// ---
// vJrwpWtwJgWrhcsFMMfFFhFp -> Rucksack 1: 24 items
// jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL -> Rucksack 2: 32 items
// PmmdzqPrVvPwwTWBwg -> Rucksack 3: 18 items
findMatchingCharacter(rucksack1, rucksack2, rucksack3) // if (24 > min(32, 18) = 18) -> true
findMatchingCharacter(rucksack2, rucksack3, rucksack1) // if (32 > min(18, 24) = 18) -> true
findMatchingCharacter(rucksack3, rucksack1, rucksack2) // if (18 > min(24, 32) = 24) -> false
// Second three items
// ---
// wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn -> Rucksack 4: 30 items
// ttgJtRGJQctTZtZT -> Rucksack 5: 16 items
// CrZsJsPPZsGzwwsLwLmpwMDw -> Rucksack 6: 24 items
findMatchingCharacter(rucksack4, rucksack5, rucksack6) // if (30 > min(16, 24) = 16) -> true
findMatchingCharacter(rucksack5, rucksack6, rucksack4) // if (16 > min(24, 30) = 24) -> false
Test case
Now that we’ve established that the expected test output is 70 we can start setting up our test case.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class PartTwoTest {
@Test
fun testGetResult() {
// Arrange
val resource = {}::class.java.getResource("/input.txt")
val sanitizer = Sanitizer(resource)
val sut = PartTwo(sanitizer)
val expectedNumberOfPoints = 70
// Act
val result = sut.getResult()
// Assert
assertEquals(expectedNumberOfPoints, result)
}
}
Categories
Related articles
Advent of Code 2022, Day three - Sanitizer
Turn the input into a list of rucksacks.