On Day 6 we have pattern detection in data. We have some mysterious communication device that is not working properly. To fix its communication system we need to add subroutine detecting start of packet marker which is indicated by four characters that are different. Any four characters.
For example, in the following data buffer mjqjpqmgbljsphdztnvjfqwrcgsmlb the first marker apears after seventh character. This marker is jpqm.
We need to output how many characters need to be processed before seeing the marker.
We can implement that by maintaing a moving window of four characters. We will start with the first 4 characters and convert them into a hash of counts of given character. For string mjqj we will have { "m" => 1, "j" => 2, "q" => 1 }. Now while moving this window we will decrease the count for the character on the left that is no longer in our window and increase the count for the character on the right that was just added to the window.
If the count will drop to zero we can remove character from the hash. We need to keep moving this window until we get four different characters, which is when all keys in our hash will have count of 1.
data = File.read("6.txt")
@chars = {}
def set_char(char)
@chars[char] ||= 0
@chars[char] += 1
end
def unset_char(char)
@chars[char] -= 1
if @chars[char] == 0
@chars.delete(char)
end
end
def has_start_packet?
@chars.keys.size == 4 && @chars.all? { |key, value| value == 1 }
end
data[0...4].chars.each { |char| set_char(char) }
offset = 3
while !has_start_packet?
offset += 1
unset_char(data[offset - 4])
set_char(data[offset])
end
puts "Start packet at #{offset + 1}"
In Part B we need to also find start of message marker, which is 14 characters that are different. It just requires a couple of changes in the code, basically replacing all 4 with 14 and 3 with 13 :)
data = File.read("6.txt")
@chars = {}
def set_char(char)
@chars[char] ||= 0
@chars[char] += 1
end
def unset_char(char)
@chars[char] -= 1
if @chars[char] == 0
@chars.delete(char)
end
end
def has_start_packet?
@chars.keys.size == 14 && @chars.all? { |key, value| value == 1 }
end
data[0...14].chars.each { |char| set_char(char) }
offset = 13
while !has_start_packet?
offset += 1
unset_char(data[offset - 14])
set_char(data[offset])
end
puts "Start packet at #{offset + 1}"