Skip Navigation

❄️ - 2023 DAY 10 SOLUTIONS -❄️

Day 10: Pipe Maze

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ


🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Unlocked after 40 mins

26

You're viewing a single thread.

26 comments
  • 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;
    Picture of solution output

    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
    
26 comments