On Day 22 we are doing some grid computing. We have a list of nodes and some information about their used and available disk storage. Our input looks like this:
Filesystem Size Used Avail Use%
/dev/grid/node-x0-y0 10T 8T 2T 80%
/dev/grid/node-x0-y1 11T 6T 5T 54%
/dev/grid/node-x0-y2 32T 28T 4T 87%
/dev/grid/node-x1-y0 9T 7T 2T 77%
/dev/grid/node-x1-y1 8T 0T 8T 0%
/dev/grid/node-x1-y2 11T 7T 4T 63%
/dev/grid/node-x2-y0 10T 6T 4T 60%
/dev/grid/node-x2-y1 9T 8T 1T 88%
/dev/grid/node-x2-y2 9T 6T 3T 66%
We need to find out how many viable pairs of nodes there are. Viable pair (A, B) means:
Here is the solution:
data = File.readlines("22.txt", chomp: true)
data.shift(2)
nodes = []
data.each do |line|
x, y = line.match(/\/dev\/grid\/node-x(\d+)-y(\d+)/).captures.map(&:to_i)
params = line.split(" ")
nodes.push({ x: x, y: y, used: params[2].to_i, available: params[3].to_i })
end
size = nodes.size
pairs = []
size.times do |i|
size.times do |j|
next if nodes[i][:used] == 0
next if i == j
pairs.push([i, j]) if nodes[i][:used] <= nodes[j][:available]
end
end
puts pairs.size
It is pretty simple. We read, parse data and then check how many pairs meet the requirements.
Second part is much more difficult. This time our task is to move data from the top, right most node to to the top, left most node. It is possible to copy data only between neighboring nodes. And because almost all nodes are somehow full except one, we can’t just copy data easily. We first need to free space on neighboring node, move data there, then free space on another neighbor and so on. You can check puzzle page for more detailed description.
It looks like Sokoban game. So we probably should use graphs to solve it.
My layout looks like this:
(.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . _ . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Not sure if this is visible, but the only empty node is near the bottom right, specified by _ character. In my solution I will make some assumptions about the layout, so it may not work for other layouts. The assumption is that we don’t have any blockers on the path from right most to left most node in the top row.
Now imagine that our empty node, specified by _ character is the player. To move data from node G to (.), we first need to move our player to the left of point G. Then player can move to position G, this will move data from G node to the left.
We will have the following situation:
Player is on the left of point G
. . _ G
. . . .
Then player moves right
. . G _
. . . .
Now we need to repeat this process, so the player needs to go again to the left of point G, but it cannot pass through G. It needs to go around like this:
. . G .
. . . _
. . G .
. . _ .
. . G .
. _ . .
. _ G .
. . . .
And then swap positions
. G _ .
. . . .
And then repeat the process until G is at our (.) position.
The goal of our task is to tell what is the fewest number of steps to move data from G to (.). It will be the sum of reaching the left neighbor of G and then one more step to swap nodes. And this needs to be repeated until we reach desired position. So it will be a sum of different paths. We can use BFS to calculate the length of each path. Here is the full solution:
data = File.readlines("22.txt", chomp: true)
data.shift(2)
@nodes = {}
@width = 0
@height = 0
@max_free_space = 0
@start = nil
data.each do |line|
x, y = line.match(/\/dev\/grid\/node-x(\d+)-y(\d+)/).captures.map(&:to_i)
params = line.split(" ")
@nodes[[x, y]] = { size: params[1].to_i, used: params[2].to_i, available: params[3].to_i }
if params[3].to_i > @max_free_space
@max_free_space = params[3].to_i
end
if params[2].to_i == 0
@start = [x, y]
end
@width = x if x > @width
@height = y if y > @height
end
@width += 1
@height += 1
@target = [@width - 1, 0]
def draw
@height.times do |j|
row = []
@width.times do |i|
value = if @nodes[[i, j]][:used] == 0
" _ "
elsif !movable?([i, j])
" # "
else
" . "
end
if i == 0 && j == 0
value = "(#{value[1]})"
end
if i == @width - 1 && j == 0
value = " G "
end
row.push(value)
end
puts row.join
end
end
def neighbors(node)
x, y = node
results = []
results.push([:left, [x - 1, y]]) if x > 0
results.push([:right, [x + 1, y]]) if x < @width - 1
results.push([:top, [x, y - 1]]) if y > 0
results.push([:bottom, [x, y + 1]]) if y < @height - 1
results
end
def movable?(node)
@nodes[node][:used] <= @max_free_space
end
def left_neighbor(node)
x, y = node
[x - 1, y]
end
def bfs(nodes, start, target)
queue = [[start, 0]]
visited = { start => true }
while !queue.empty?
current, time = queue.shift
if current == target
return time
end
neighbors(current).each do |(direction, neighbor)|
next unless movable?(neighbor)
next if direction == :left && neighbor == @target
if !visited[neighbor]
queue.push([neighbor, time + 1])
visited[neighbor] = true
end
end
end
end
total = 0
draw
exit
while @target != [0, 0]
# Reach left side of target node
total += bfs(@nodes, @start, left_neighbor(@target))
# copy data, move target node one position left
@start = left_neighbor(@target)
@start, @target = @target, @start
total += 1
end
puts total