Question Finally, we move out of camp! As we start heading out of the camp one of the elves gives us a communication device, it will come as no surprise that we got the only malfunctioning device…
The device receives streams of signals that are built from a list of chars, to fix our device we need to be able to find the start-of-packet marker.
We are told that the start of the packet is defined as a series of four different consecutive chars. Given our signle, we need to determine how many chars should be processed before the first marker appears or in other words the index at the end of our marker.
<end>represents the start and end of the marker accordingly
meaning the answer should be 7 (index of
Basically what we need to accomplish here is to find 4 consecutive chars in a row, there are multiple ways of doing this but we will use
Sets to count the number of unique chars within a given range i.e i -> i+4
In each position of that range, we will take the char and add it to our set, at the end of the range if the set size is 4 then we got a winner and we can return our current index
i + 4.
Set is a data structure that guarantees the uniqueness of each key, in Go, there isn’t a built-in type for that but we can easily create a set using a
map[rune]booltype to make this a bit more interesting let’s create a generic set package
We will create a package called
set and in it, a struct named
SimpleSet that will support a basic set of operations
Here is the code for our
I’m using generics to have this set useful in days to come, you can read more about it here
I don’t get how come Go didn’t have generics until recently, imagine repeating the same code for our set for every type!
Armed with our new set, lets solve part 1!
Exactly like part 1 but now the marker needs to be 14 consecutive chars We can take our part 1 solution and have it accept an offset to fit both parts
Our part 2 solution will be
The solution can be optimized a bit by returning early if a char is already in our set, before we do anything we first need to measure our current solution.
This can be easily done using Go benchmarks capabilities.
Create a new file
main_test.go and write our benchmarks there
go test -bench=. -count 3 results in
Now let’s add the following
if to our inner loop
re-run the benchmark
we can see that for part 1 there is barely an improvement but for part 2 that early return does make a noticeable difference, awesome!
That’s it for today, we created our very own Set data structure and used go benchmarks to optimize our solution.
I hoped you enjoyed and learned something new cause I sure did!
You can find the complete code here Thanks for reading!
This post is number 7 of a 13 posts series > Learning Go.