# Advent of Code 2016, Day 22: Grid Computing

#ruby #advent of code 2016

## Part A

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:

• Node A is not empty (its Used is not zero).
• Nodes A and B are not the same node.
• The data on node A (its Used) would fit on node B (its Avail).

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.

## Part B

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
``````