Day 17 is good, old graph problem. We are moving on 4x4 grid and trying to access the vault. This grid looks like this:
#########
#S| | | #
#-#-#-#-#
# | | | #
#-#-#-#-#
# | | | #
#-#-#-#-#
# | | |
####### V
We start at position S (0, 0) and we need to reach position V (3, 3). # character represents solid wall, but maybe it is better to think about this like moving between columns 0-3 and rows 0-3. We can move down, up, left and right. When we make a move we can store our current path. So if go right, right, down, right, up we can store our path as RRDRU. In the beginning our path is just an empty string.
This stored path is very important. If we calculate MD5 hash of a given passcode concatenated with our path, the first four characters of this hash will tell us which doors are open. Because when passing from one position to another we need to go through some security doors. First hash character tells us above door above, second about door below, third about left door and fourth about right door. If hash character is b, c, d, e or f it means the door is open.
We can implement this as a method:
def hash(path)
doors = Digest::MD5.hexdigest(@passcode + path)[0..3].chars.map do |char|
if %w[b c d e f].include?(char)
true
else
false
end
end
end
It returns array of boolean values representing status of door up, down, left and right. True means the door is open.
Then we can implement method to convert our string path into a (x, y) position:
def positionFromPath(path)
position = [0, 0]
path.chars.each do |char|
case char
when "D"
position[1] += 1
when "U"
position[1] -= 1
when "L"
position[0] -= 1
when "R"
position[0] += 1
end
end
position
end
We start with position (0, 0) and we iterate over our path and then adjust the position based on movements.
So far for a given path we can figure out our current position and which doors are open. Using this information we can calculate what are our neighbors or in other words what are the positions where we can move next.
def getNeighbors(path)
hash = hash(path)
x, y = positionFromPath(path)
[
[x, y - 1, "U"],
[x, y + 1, "D"],
[x - 1, y, "L"],
[x + 1, y, "R"]
].select.with_index do |(x, y, _), index|
x >= 0 && x < 4 && y >= 0 && y < 4 && hash[index]
end.map do |(_, _, direction)|
direction
end
end
There are 4 possible neighbors. We need to filter out those that are outside of grid and those that have closed doors.
Finally we can implement our BFS. Here is the full solution:
require "digest"
@passcode = "abcd"
@visited = {}
def hash(path)
doors = Digest::MD5.hexdigest(@passcode + path)[0..3].chars.map do |char|
if %w[b c d e f].include?(char)
true
else
false
end
end
end
def positionFromPath(path)
position = [0, 0]
path.chars.each do |char|
case char
when "D"
position[1] += 1
when "U"
position[1] -= 1
when "L"
position[0] -= 1
when "R"
position[0] += 1
end
end
position
end
def getNeighbors(path)
hash = hash(path)
x, y = positionFromPath(path)
[
[x, y - 1, "U"],
[x, y + 1, "D"],
[x - 1, y, "L"],
[x + 1, y, "R"]
].select.with_index do |(x, y, _), index|
x >= 0 && x < 4 && y >= 0 && y < 4 && hash[index]
end.map do |(_, _, direction)|
direction
end
end
queue = [""]
while !queue.empty?
current = queue.shift
if positionFromPath(current) == [3, 3]
puts "Arrived at destination with path = #{current}, steps = #{current.size}"
break
end
getNeighbors(current).each do |neighbor|
newPath = current + neighbor
queue.push(newPath)
end
end
In our queue we are storing our path strings. We don’t need any other information because we can calculate everything from the path.
Interestingly in the second part we need to find out what is the longest path we can take to reach the vault. We can use the same algorithm, we can just not break our loop when we first reach the destination. Instead we continue with our loop until we run out of items in our queue.
Here is the full solution:
require "digest"
@passcode = "abc"
@visited = {}
def hash(path)
doors = Digest::MD5.hexdigest(@passcode + path)[0..3].chars.map do |char|
if %w[b c d e f].include?(char)
true
else
false
end
end
end
def positionFromPath(path)
position = [0, 0]
path.chars.each do |char|
case char
when "D"
position[1] += 1
when "U"
position[1] -= 1
when "L"
position[0] -= 1
when "R"
position[0] += 1
end
end
position
end
def getNeighbors(path)
hash = hash(path)
x, y = positionFromPath(path)
[
[x, y - 1, "U"],
[x, y + 1, "D"],
[x - 1, y, "L"],
[x + 1, y, "R"]
].select.with_index do |(x, y, _), index|
x >= 0 && x < 4 && y >= 0 && y < 4 && hash[index]
end.map do |(_, _, direction)|
direction
end
end
queue = [""]
max = 0
while !queue.empty?
current = queue.shift
if positionFromPath(current) == [3, 3]
if current.size > max
max = current.size
end
next
end
getNeighbors(current).each do |neighbor|
newPath = current + neighbor
queue.push(newPath)
end
end
puts "Longest path is #{max}"