Updated Dec 12, 2022 to remove shorthand argument names in the last reduce to help clarify what’s going on
Part One
Find the item type that appears in both compartments of each rucksack. What is the sum of the priorities of those item types?
So we’ve got an elf’s rucksack per line in our input. Each rucksack has two compartments and there is an item that is present in both compartments that we need to identify. Basically, we need to do an intersection between the two compartments and then convert the character representing the item into a “priority” number.
Unfortunately Swift doesn’t have a built-in intersection for Arrays, but does have intersections for Sets, so let’s parse our input into those. As we did for yesterday, let’s make a little container to hold our rucksack contents to make our code a little easier to read:
struct Rucksack {
let compartmentA: Set<Character>
let compartmentB: Set<Character>
}
As stated above, we’ll benefit from using Sets, so the first part reduces down to something like the following, using our new Rucksack struct:
let itemInBothCompartments = rucksack.compartmentA.intersection(rucksack.compartmentB)
Before we finish that thought, though, let’s finish parsing an elf’s line. Now that we’ve got our container struct we need to do two things: split a line from our input in half and then convert each half into a Set of Characters. Thankfully we can use swifts Array#prefix() and Array#suffix() methods to get the first half and the second half of the line in a fairly easy to read way. We can also map over the resulting arrays and initialize a Character before we initialize our Set:
func parseLine(_ line: Substring) -> Rucksack {
let halfLength = line.count / 2
let compartmentAArray = line.prefix(halfLength).map(Character.init)
let compartmentBArray = line.suffix(halfLength).map(Character.init)
return .init(
compartmentA: Set(compartmentAArray),
compartmentB: Set(compartmentBArray)
)
}
With this, one last part of the puzzle remains: Once we have the intersection, we have a character that needs to be mapped to a “priority” number using the following rules:
athroughzmaps to 1 - 26AthroughZmaps to 27 - 52
If you’re familiar with the ASCII representations for a-z and A-Z you’ll immediately see that even if we take the ASCII number value for our characters, A - Z maps to a lower range (65-90) than a - z (97-122) and neither of those align with our 1-52 range of values! We’ll have to subtract a fixed value, but we’ll also have to have two different fixed values, depending on if the character is upper-case or lower. Let’s remap A-Z first:
func remapCharToPriority(_ char: Character) -> Int {
let rawAsciiValue = Int(char.asciiValue!)
// A-Z have priority of 27 - 52
return rawAsciiValue - 38
}
A few things to note here: Character#asciiValue returns an optional. We’re going to force unwrap the result since we are trusting that our input falls only within ASCII values. You’d probably want to add some additional sanity checks here for real-world problems but since we know that our input is going to be well formed, we’ll get away with this. Secondly, Character#asciiValue returns an UInt8 instead of an Int which could be fine, but we’ll overflow UInt8, which can only store from 0 to 255, once we start adding together priorities from other elves’ rucksacks. To get around this we convert the UInt8 to an Int which has a far wider range that it can store (which means we don’t have to worry about this conversion going south at any point too). Finally, we subtract 38 which means that A will map to 27 (65 - 27 = 38) and Z to 52 as we expect.
We’ve got one case to handle here, however: a which is 97 in ASCII will currently map to 59 which isn’t what we want. We need to add an if branch for when the ASCII value is 97 or higher and return the ASCII value subtracting 96 in order to correctly map the lower-case characters:
func remapCharToPriority(_ char: Character) -> Int {
let rawAsciiValue = Int(char.asciiValue!)
// a-z have priority of 1 - 26
if rawAsciiValue >= 97 {
return rawAsciiValue - 96
}
// A-Z have priority of 27 - 52
return rawAsciiValue - 38
}
With that we’ve got all we need to solve this part of the puzzle:
rucksacks.map { sack in sack.compartmentA.intersection(sack.compartmentB).first! }
.map(remapCharToPriority)
.reduce(0, +)
For each rucksack, we find the item that exists in both compartments. We can force unwrap this because, again, we know that our input will have a duplicate per line but we’d want some better error handling for real-life applications. Then we remap each duplicate item into its priority and finally sum it all together.
Part Two
Find the item type that corresponds to the badges of each three-Elf group. What is the sum of the priorities of those item types?
Now, instead of finding the duplicated item across a single rucksack’s compartments, we’re looking for a duplicated item across three elfs’ rucksacks. It turns out that we can keep our mapping logic the same, and our only changes will be how we apply intersections across the rucksacks. The first thing we can change is unioning the two compartments of each rucksack together since we don’t care about duplicates for a single elf anymore:
rucksacks.map { sack in sack.compartmentA.union(sack.compartmentB) }
The next thing we need to do is divide the rucksacks into groups of three. Unfortunately swift doesn’t have a built in cons, pairs, or slicesOf function for any data structure, so we’ll have to make our own. We’ll do this using an extension onto Array so let’s write our signature that we’re aiming for first:
extension Array {
func chunked(into size: Int) -> [[Element]] {
return // something ...
}
}
Thankfully the swift standard library includes a neat little stride function:
func stride<T>(
from start: T,
to end: T,
by stride: T.Stride
) -> StrideTo<T> where T : Strideable
We can use this to produce a sequence of the starting index for each group:
> Array(stride(from: 0, to: 9, by: 3))
$R: [Int] = 3 values {
[0] = 0
[1] = 3
[2] = 6
}
With this we can map over this sequence, and take a slice from the Array self (since we’re in an extension of Array) and convert it to a standalone array for convenience in a few minutes with something like the following:
Array(self[$0 ..< ($0 + size)])
Leaving us with the final following implementation:
extension Array {
func chunked(into size: Int) -> [[Element]] {
return stride(from: 0, to: count, by: size).map {
Array(self[$0 ..< $0 + size])
}
}
}
It should be noted that this method will fail with an out-of-bounds error for arrays that are not nicely groupable, so an extra bit of safety would either be to implement that as a check and throw an error if count is not cleanly divisible by 3 or to use something like min($0 + size, count) to cut the last group into a smaller slice without failing.
With this in place, we can finish up our task as we can now group the elves into sets of 3. We’ll reduce each group, calling Set#intersection to compute the final intersection of the group to determine what they’ve gotten duplicated amongst themselves. After that, we’ll return to our first solution and map each item to the priority number and finally sum it all together:
rucksacks
.map { sack in sack.compartmentA.union(sack.compartmentB) }
.chunked(into: 3)
.map { chunk in
chunk[1..<chunk.count].reduce(chunk[0], { innerMemo, prioritySet in
innerMemo.intersection(prioritySet)
}).first!
}
.map(remapCharToPriority)
.reduce(0, +)
We’re using a reduce here so that our code is a little more configurable and maintainable, but it boils down to something like:
chunk[0].intersection(chunk[1]).intersection(chunk[2])
And with that our second star is within reach!