The squeezing component in part 2 made this really interesting.
I had a thought on a naïve solution consisting of expanding the input grid, painting all the walked pipes, and then doing a flood fill from the outside of the expanded map. There are a lot cleverer ways to do it, but the idea stuck with me and so...
The code's a bit of a mess, but I actually kind of like the result. It visualizes really well and still runs both parts in under 8 seconds, so it's not even particularly slow considering how it does it.
E.g;
Ruby
A snippet from the expansion/flood fill;
def flood_fill(used: [])
new_dim = @dim * 3
new_map = Array.new(new_dim.size, '.')
puts "Expanding #{@dim} to #{new_dim}, with #{used.size} visited pipes." if $args.verbose
# Mark all real points as inside on the expanded map
(0..(@dim.y - 1)).each do |y|
(0..(@dim.x - 1)).each do |x|
expanded_point = Point.new x * 3 + 1, y * 3 + 1
new_map[expanded_point.y * new_dim.x + expanded_point.x] = 'I'
end
end
# Paint all used pipes onto the expanded map
used.each do |used_p|
expanded_point = Point.new used_p.x * 3 + 1, used_p.y * 3 + 1
new_map[expanded_point.y * new_dim.x + expanded_point.x] = '#'
offsets = @links[used_p].connections
offsets.shift
offsets.each do |offs|
diff = offs - used_p
new_map[(expanded_point.y + diff.y) * new_dim.x + (expanded_point.x + diff.x)] = '#'
end
end
puts "Flooding expanded map..." if $args.verbose
# Flood fill the expanded map from the top-left corner
to_visit = [Point.new(0, 0)]
until to_visit.empty?
at = to_visit.shift
new_map[at.y * new_dim.x + at.x] = ' '
(-1..1).each do |off_y|
(-1..1).each do |off_x|
next if (off_x.zero? && off_y.zero?) || !(off_x.zero? || off_y.zero?)
off_p = at + Point.new(off_x, off_y)
next if off_p.x < 0 || off_p.y < 0 \
|| off_p.x >= new_dim.x || off_p.y >= new_dim.y \
|| to_visit.include?(off_p)
val = new_map[off_p.y * new_dim.x + off_p.x]
next unless %w[. I].include? val
to_visit << off_p
end
end
end
return new_map, new_dim
end
