Part One
How many characters need to be processed before the first start-of-packet marker is detected?
Today we need to run a sliding window over an array of bytes in order to find a “start-of-packet” marker, or a set of 4 consecutive bytes that are all unique within that window. My original solution used a ring buffer, sometimes also referred to as a circular buffer, which is essentially an array of a fixed length that’ll remove an element from the front when you push onto it, if its length is over the length after the push operation.
We can simplify the process, however, and instead just keep track of the upper and lower-bound indices of our window, taking a slice from the input between those bounds and checking for 4 unique characters
For example, using mjqjpqmgbljsphdztnvjfqwrcgsmlb we can start off with the first 4 characters:
[mjqj] pqmgbljsphdztnvjfqwrcgsmlb
This isn’t the start-of-packet as there are only 3 unique characters since j is repeated twice. Sliding our window forward by one:
m [jqjp] qmgbljsphdztnvjfqwrcgsmlb
This is not the packet, so we continue on with sliding the window forward by one, two more iterations:
mj [qjpq] mgbljsphdztnvjfqwrcgsmlb
mjq [jpqm] gbljsphdztnvjfqwrcgsmlb
Finally we’ve got a window where there are 4 distinct characters present, our start-of-message packet! We’ll return the index of the upper bound of the window as our solution, in this case 7.
Now that we’ve got that figured out, we need to get an array of characters out of our input. Thankfully, swift gives us an Array(_ str: String) initializer:
func parseLine(_ line: Substring) -> [Character] {
return Array(line)
}
And now we just have to create that sliding window. We’ll define the window size:
let windowSize = 4
let adjustedWindowSize = windowSize - 1
We have to make a small adjustment to make the window size usable within our arrays. If we were to do line[0...4] we’d actually get the first 5 characters instead of the first four that we need to start off with, as a result of the array being 0-indexed but our counting being 1-indexed. As a result we subtract one from our 1-indexed count in order to get a 0-indexed window.
Now we just iterate from our window size up to the line’s length. This’ll give us the upper-bound shifted forward by 1 each iteration, and we can compute the new lower-bound by subtracting our window size to get the slice of 4 characters within those bounds:
for upperBound in adjustedWindowSize..<line.count {
let lowerBound = upperBound - adjustedWindowSize
if Set(line[lowerBound...upperBound]).count == windowSize {
return upperBound + 1
}
}
Finally, we convert the slice into a Set to get the unique characters and take the count. If it’s 4, we can return our upper bound but we have to remember to convert it back to a 1-indexed bound for the answer!
Part Two
How many characters need to be processed before the first start-of-message marker is detected?
Now we’re looking for a second packet but the technique is the same, we need a sliding window of 14 characters over the input to find the first instance where the 14 characters are all distinct. Thankfully, since we’ve defined the window size as a standalone variable we can just adjust it from 4 up to 14 and that’s it!