On Day 18 we can work with tiny little cubes placed on the 3D grid. Our input file looks like this:
2,2,2
1,2,2
3,2,2
2,1,2
2,3,2
2,2,1
2,2,3
2,2,4
2,2,6
1,2,5
3,2,5
2,1,5
2,3,5
Those are positions of our tiny cubes that together make a larger 3D block or shape, whatever it’s called. Our task is to calculate the surface area of this block. In other words we need to calculate how many cube walls are exposed.
For example if we have just two cubes 1,1,1 and 2,1,1, they are connected on one side, so each one has 5 walls exposed giving us 10 surface area in total.
We can use naive solution to solve this:
data = File.readlines("18.txt", chomp: true).map { |line| line.split(",").map(&:to_i) }
@max_x = data.map { |cube| cube[0] }.max
@max_y = data.map { |cube| cube[1] }.max
@max_z = data.map { |cube| cube[2] }.max
data.sort! do |cube_a, cube_b|
Math.sqrt(cube_a[0] ** 2 + cube_a[1] ** 2 + cube_a[2] ** 2) <=> Math.sqrt(cube_b[0] ** 2 + cube_b[1] ** 2 + cube_b[2] ** 2)
end
def neighbors(x, y, z)
[
[x + 1, y, z],
[x - 1, y, z],
[x, y + 1, z],
[x, y - 1, z],
[x, y, z + 1],
[x, y, z - 1]
]
end
def cube_key(x, y, z)
"#{x}:#{y}:#{z}"
end
def area(data)
cubes = {}
data.each do |cube|
cubes[cube_key(*cube)] = true
end
sum = cubes.size * 6
0.upto(@max_x) do |x|
0.upto(@max_y) do |y|
0.upto(@max_z) do |z|
if cubes[cube_key(x, y, z)]
count = neighbors(x, y, z).select do |neighbor|
cubes[cube_key(*neighbor)] == true
end.size
sum -= count
end
end
end
end
sum
end
puts area(data)
We parse our input data and create 3D map with true or false values, meaning if there is a cube at that position or not. Then we can iterate over each position in this 3D space and if we get a position with a cube we can check how many neighbors it has. For each neighbor we need to subtract one from our total area. Our total area was initiated in the beginning by multiplying number of cubes times 6.
In second part we still need to calculate surface area, but we need to exclude any empty bubbles inside the main block.
I didn’t write the fastest solution here. It took about 15 seconds to calculate, but it was ok for me. The idea is that we can first create a set of all outside positions that are surrounding our block. We can just calculate min and max values for each dimension and then consider 3D that is slightly larger than that.
I used BFS algorithm to create a set of positions:
empty_exterior = []
queue = []
queue.push([0, 0, 0])
visited = { [0, 0, 0] => true }
while !queue.empty?
current = queue.pop
empty_exterior.push(current)
neighbors(*current).each do |neighbor|
if !cubes[cube_key(*neighbor)] && !visited[neighbor]
queue.push(neighbor)
visited[neighbor] = true
end
end
end
I started with position (0, 0, 0) and then started to explore it’s neighbor skipping those that were part of our measured block.
Then we can just iterate over each cube in our bigger block. All walls that are connected to the external interior are part of it’s surface area:
sum = 0
data.each do |cube|
neighbors(*cube).each do |neighbor|
if empty_exterior.include?(neighbor)
sum += 1
end
end
end
puts sum
Here is the full code:
data = File.readlines("18.txt", chomp: true).map { |line| line.split(",").map(&:to_i) }
@max_x = data.map { |cube| cube[0] }.max
@max_y = data.map { |cube| cube[1] }.max
@max_z = data.map { |cube| cube[2] }.max
def cube_key(x, y, z)
"#{x}:#{y}:#{z}"
end
def neighbors(x, y, z)
[
[x + 1, y, z],
[x - 1, y, z],
[x, y + 1, z],
[x, y - 1, z],
[x, y, z + 1],
[x, y, z - 1]
].reject do |(x, y, z)|
x < -1 || y < -1 || z < -1 || x > @max_x + 1 || y > @max_y + 1 || z > @max_z + 1
end
end
cubes = {}
data.each do |cube|
cubes[cube_key(*cube)] = true
end
empty_exterior = []
queue = []
queue.push([0, 0, 0])
visited = { [0, 0, 0] => true }
while !queue.empty?
current = queue.pop
empty_exterior.push(current)
neighbors(*current).each do |neighbor|
if !cubes[cube_key(*neighbor)] && !visited[neighbor]
queue.push(neighbor)
visited[neighbor] = true
end
end
end
sum = 0
data.each do |cube|
neighbors(*cube).each do |neighbor|
if empty_exterior.include?(neighbor)
sum += 1
end
end
end
puts sum