Day 3 - Rucksack Reorganization 🧳
Packing is a hassle for both Elves and humans alike. Today’s puzzle is all about helping the Elves rearrange the items in their rucksacks!
Analyzing the input
The given data is a list of rucksacks with the items contained inside. Each line represents the items inside a rucksack.
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDwInternally, every rucksack is divided into two compartments at exactly midway. For instance,
the first compartment of the first rucksack holds items vJrwpWtwJgWr and the hcsFMMfFFhFp
in the second.
Additionally, each item has a rearrangement priority value. a - z have priorities 1 - 26
and A - Z, 27 - 52.
Part 1
All items of the same type are supposed to be in the same compartment of a rucksack, which means there should not be items which appear in both compartments of the same rucksack. Part 1 involves finding the item commont to both the compartments of every rucksack and summing up their priority values.
Grouping items in compartments
For each line(l) the first step is to use
substring()
to group the items in two compartments. The first compartment contains items from index
0 to l.length/2 - 1 and second has the rest.
line.substring(0, l.length/2)
// substring is end exclusive so l.length/2 is not included
line.substring(l.length/2)
// equivalent to substring(l.length/2, l.length)Finding the common item
Now that items have been assigned their compartments, the next step is to find
the common item. Consider each compartment as a
Set
of elements. Does that give you an idea? Yes! The intersection of the two sets
should give the common element!
A String can be directly converted to a Set of characters using the
toSet()
function. Once that’s done, we can use intersect()
to get the common element.
l.substring(0, l.length / 2).toSet()
.intersect(l.substring(l.length / 2).toSet())But wait, the result is still a Set! This is because intersect() returns all the
elements common to the Sets. The question states that there’ll be only one item
which would appear in both compartments. Therefore we can take just the
first()
element.
l.substring(0, l.length / 2).toSet()
.intersect(l.substring(l.length / 2).toSet())
.first()Evaluating the priority
Priority for the character can be found through a few simple operations using ASCII
codes like how we solved day 2. If the character
isLowerCase
then you only have to substract code of 'a' from the char and then add 1. Otherwise,
subtract 'A' from the item and then add 27.
if (it.isLowerCase()) it - 'a' + 1 else it - 'A' + 27Combining these steps into one
Scope functions are great for running code in the context of the value of an object. The above steps can be tied together with let.
l.substring(0, l.length / 2).toSet()
.intersect(l.substring(l.length / 2).toSet())
.first()
.let {
if (it.isLowerCase()) it - 'a' + 1 else it - 'A' + 27
}sumOf() priorities
Since we have figured out how to process each line, all that is left is to add up the priorities. And that’s it for part 1!
input.sumOf { l ->
l.substring(0, l.length / 2).toSet()
.intersect(l.substring(l.length / 2).toSet())
.first()
.let {
if (it.isLowerCase()) it - 'a' + 1 else it - 'A' + 27
}
}Solution
val part1 = input.sumOf { l ->
l.substring(0, l.length / 2).toSet()
.intersect(l.substring(l.length / 2).toSet())
.first()
.let {
if (it.isLowerCase()) it - 'a' + 1 else it - 'A' + 27
}
}Part 2
Looks like the Elves are facing another problem - this time they seem to have lost their group badges. Elves are divided into groups of three and assigned a badge depending on the item common by all three of them.
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwgThis is the first group in the sample data. Their badge is r because that’s the only
item appearing in the rucksacks of all three Elves.
Part 2 involves summing up the priorities of the badges.
Finding the common item
Following the same principle we used in the part 1, we can
use sets to find the intersection in the three item Sets. This time we’ll need two
intersect calls. Assuming we have the three rucksacks available as a List<String>
we can implement this like so:
list[0].toSet()
.intersect(list[1].toSet())
.intersect(list[2].toSet())Since it is given that there’ll be only one item in common, we only need to take the first element of the Set and find its priority, just like how we did in part 1.
list[0].toSet()
.intersect(list[1].toSet())
.intersect(list[2].toSet())
.first()
.let {
if (it.isLowerCase()) it - 'a' + 1 else it - 'A' + 27
}All that remains is to divide the Elves into groups of three.
Dividing Elves into groups
Splitting the input into groups of three can be done with the
chunked()
function in the Collections API.
input.chunked(3)Summing it up
Finally, using sumOf()
we can find the total of all the priorities.
input.chunked(3)
.sumOf { list ->
list[0].toSet().intersect(list[1].toSet()).intersect(list[2].toSet()).first().let {
if (it.isLowerCase()) it - 'a' + 1 else it - 'A' + 27
}
}Solution
val part2 = input.chunked(3)
.sumOf { list ->
list[0].toSet().intersect(list[1].toSet()).intersect(list[2].toSet()).first().let {
if (it.isLowerCase()) it - 'a' + 1 else it - 'A' + 27
}
}Hats off to you for conquering day 3 of Advent of Code! Well done!
Full Solution
fun main() {
val input = readInput("Day03")
val part1 = input.sumOf { l ->
l.substring(0, l.length / 2).toSet()
.intersect(l.substring(l.length / 2).toSet())
.first()
.let {
if (it.isLowerCase()) it - 'a' + 1 else it - 'A' + 27
}
}
val part2 = input.chunked(3).sumOf { list ->
list[0].toSet()
.intersect(list[1].toSet())
.intersect(list[2].toSet())
.first()
.let {
if (it.isLowerCase()) it - 'a' + 1 else it - 'A' + 27
}
}
part1.println()
part2.println()
}