5 votes

Day 20: Donut Maze

Today's problem description: https://adventofcode.com/2019/day/20


Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

1 comment

  1. Crespyl
    Link
    Having done day 18 made this a good deal easier. Part 1 The trickiest bit was really just parsing the input and detecting the labels correctly. I ended up scanning over the map and looking for...

    Having done day 18 made this a good deal easier.

    Part 1

    The trickiest bit was really just parsing the input and detecting the labels correctly. I ended up scanning over the map and looking for uppercase letters, then checking all the neighbors to see if I could find both a second letter and an open/walkable '.' tile, which would be the portals actual location. Once I had all the labels, I could link up the pairs in a table and use that in my tile neighbors method.

    A simple BFS search worked well enough to find the solution.

    Part 2

    This was also pretty straightforward, but again managing the portals themselves was rather tricky, detecting whether a portal lead "in" or "out" kept failing and causing the pathfinder to get lost down infinite one-way holes. Eventually it turned out that I wasn't accounting for the whitespace in the margins of the input correctly, and my map thought its width was much less than it actually was.

    I updated the solver to work in three dimensions, and changed the neighbors method to return portal neighbors as either one step lower or higher.

    Once I fixed that, a simple BFS was still too slow, so I switched to A* and had a quick solution. My solver is still examining every tile individually, but it runs in about 1s on my input.

    Interestingly, on the second sample, my solver does get stuck with too many different paths, so I want to go back and fix it with a smarter approach.

    Similar to Day 18, it should be possible to build a map of which portals are directly connected to which other portals, and then do a graph search over that to determine the best order to traverse the portals in.

    Day 20 - Crystal
    #!/usr/bin/env crystal
    require "colorize"
    require "../lib/utils.cr"
    include Utils
    
    input = File.read(Utils.cli_param_or_default(0,"day20/sample.txt"))
    
    grid = input.lines.map { |l| l.chars.to_a }
    
    map = Map.new(grid)
    map.print_map
    
    path = bfs_path(->(loc : Vec2) { map.walkable_neighbors(loc) },
                    map.start,
                    map.goal)
    
    map.print_map_path(path)
    puts "Part 1: %i\n" % (path.size-1) # -1 to exclude the starting tile
    
    path = astar_path(->(loc : Vec3) { map.recursive_walkable_neighbors(loc) },
                      ->(loc : Vec3) { loc.dist(map.goal) },
                      Vec3.new(map.start),
                      Vec3.new(map.goal))
    
    map.print_map_path(path)
    puts "Part 2: %i" % (path.size-1)
    
    def bfs_path(neighbors : Proc(Vec2, Array(Vec2)), start : Vec2, goal : Vec2)
      open = Set(Tuple(Vec2, Array(Vec2))).new
      open.add({ start, [start] })
      visited = Set(Vec2).new
    
      iterations = 0
      while !open.empty?
        iterations += 1
        #puts "BFS Iterations: %i" % [iterations] if iterations % 100 == 0
    
        frontier = Set(Tuple(Vec2, Array(Vec2))).new
    
        open.each do |state|
          loc, path = state
          next if visited.includes? loc
          visited.add(loc)
    
          #map.print_map_path(path)
    
          return path if loc == goal
    
          neighbors.call(loc).each do |n|
            next if visited.includes? n
            frontier.add({n, path.clone << n})
          end
        end
    
        open = frontier
      end
    
      return [] of Vec2
    end
    
    def astar_path(get_neighbors : Proc(Vec3, Array(Vec3)), heuristic : Proc(Vec3, Int32), start : Vec3, goal : Vec3)
      open = Set(Vec3).new
      open.add(start)
    
      # map of the best known route to each node
      prev = Hash(Vec3, Vec3).new
    
      # distance from start to each node
      gscore = Hash(Vec3, Int32).new(Int32::MAX)
      gscore[start] = 0
    
      # heuristic scores for each node
      fscore = Hash(Vec3, Int32).new(Int32::MAX)
      fscore[start] = heuristic.call(start)
    
      # helper proc to produce an Array(Vec3) from the prev map
      reconstruct_path = ->(node : Vec3) {
        path = [node] of Vec3
        while (node = prev[node]?)
          path << node
        end
        return path
      }
    
      iterations = 0
      while !open.empty?
        iterations += 1
    
        # select the open node with the best heuristic score
        loc = open.min_by { |loc| fscore[loc] }
        open.delete(loc)
    
        # if iterations % 100000 == 0
        #   puts "A* Iterations: %i (%i)" % [iterations, open.size]
        #   map.print_map_path(reconstruct_path.call(loc))
        # end
    
        if loc == goal
          #puts "A* search ended: #{path}"
          return reconstruct_path.call(loc)
        end
    
        get_neighbors.call(loc).each do |n|
          # see if reaching n from this route is better than any previous route we
          # took to get here; if so, update the prev table and heuristic scores
          alt = gscore[loc] + loc.dist(n)
          if alt < gscore[n]
            prev[n] = loc
            gscore[n] = alt
            fscore[n] = gscore[n] + heuristic.call(n)
    
            open.add(n) unless open.includes? n
          end
        end
      end
    
      return [] of Vec3
    end
    
    # up, right, down, left
    DIRS = [Vec2.new(0,-1), Vec2.new(1,0), Vec2.new(0,1), Vec2.new(-1,0)]
    
    alias Tile = Char
    
    class Map
      property grid : Array(Array(Tile))
      property portals : Hash(Vec2, Vec2)
      property start : Vec2
      property goal : Vec2
      property width : Int32
      property height : Int32
    
      def initialize(grid)
        @depth = 0
        @grid = grid
        @portals = Hash(Vec2, Vec2).new
        @start = Vec2.new(0,0)
        @goal = Vec2.new(0,0)
    
        @height = @grid.size
        @width = @grid.map{ |row| row.size }.max # width calc is trickier since the
                                                 # padding whitespace gets in the
                                                 # way
    
        parse_portal_locs
    
        #puts "Map Ready (#{@width}x#{@height})"
      end
    
      def parse_portal_locs
        found_labels = Array(Tuple(String, Vec2)).new
    
        each_loc do |loc, tile|
          next unless tile.ascii_uppercase?
          # we found part of a portal, we need to find the upper-case neighbor,
          # and the attached actual grid point
    
          portal_loc = loc
          other_tile = tile
    
          normal_neighbors(loc).each do |neighbor|
            tile_neighbor = get(neighbor)
            #puts "   neighbor: #{tile_neighbor} (#{neighbor})"
    
            if tile_neighbor == '.'
              portal_loc = neighbor
            end
    
            next unless tile_neighbor.ascii_uppercase?
    
            other_tile = tile_neighbor
            #puts "   Tile Pair #{tile}, #{other_tile}; #{loc}"
          end
    
          if portal_loc != loc
            name = [tile, other_tile].sort.join
            found_labels << { name, portal_loc }
            #puts "Found Portal #{name} at #{portal_loc}"
          end
        end
    
        while !found_labels.empty?
          name, loc = found_labels.pop
    
          if name == "AA"
            @start = loc
            next
          elsif name == "ZZ"
            @goal = loc
            next
          end
    
          # find the other end
          other = found_labels.find { |pair| pair[0] == name }
          raise "Couldn't find other end of portal #{name}!" unless other
    
          # remove the other end from our set
          found_labels.reject!(other)
          _, other_loc = other
    
          @portals[loc] = other_loc
          @portals[other_loc] = loc
          #puts "Registered portal %s: %s -- %s" % [name, loc.to_s, other_loc.to_s]
        end
      end
    
      def each_loc(&block)
        @grid.each_with_index do |row, y|
          row.each_with_index do |tile, x|
            yield(Vec2.new(x,y),tile)
          end
        end
      end
    
      def walkable_neighbors(loc : Vec2) : Array(Vec2)
        portal_neighbors(loc).select { |l| get(l) == '.' }
      end
    
      def recursive_walkable_neighbors(loc : Vec3)
        recursive_portal_neighbors(loc).select { |l| get(l.xy) == '.' }
      end
    
      # n/e/s/w neighbors, but also check for portals
      def portal_neighbors(loc : Vec2)
        normal_neighbors(loc) + [@portals[loc]?].compact
      end
    
      # n/e/s/w neighbors and portals, but portals lead one layer in or out (z-axis)
      def recursive_portal_neighbors(loc : Vec3)
        neighbors = normal_neighbors(loc)
    
        if portal = @portals[loc.xy]?
          # inner or outer portal?
          if (loc.x > 2 && loc.y > 2 && loc.x < (@width-3) && loc.y < (@height-3))
            neighbors << Vec3.new(portal.x, portal.y, loc.z + 1)
          elsif loc.z > 0 && (loc.x <= 2 || loc.y <= 2 || loc.x >= @width-3 || loc.y >= @height-3)
            neighbors << Vec3.new(portal.x, portal.y, loc.z - 1)
          end
    
        end
        return neighbors
      end
    
      # n/e/s/w neighbors, ignoring portals
      def normal_neighbors(loc : Vec2)
        DIRS.map { |d| d + loc }
      end
    
      # "3d" neighbors, same z
      def normal_neighbors(loc : Vec3)
        DIRS.map { |d| Vec3.new(d.x+loc.x, d.y+loc.y, loc.z) }
      end
    
      def get(loc : Vec2)
        get_grid(loc.x, loc.y)
      end
    
      def get_grid(x, y) : Tile
        if @grid.size > y && y >= 0
          if @grid[y].size > x && x >= 0
            return @grid[y][x]
          end
        end
        return ' '
      end
    
      def print_map
        @grid.each_with_index do |row, y|
          row.each_with_index do |tile, x|
            if tile == '#'
              print tile.to_s.colorize(:red).mode(:dim)
            else
              print tile
            end
          end
          print "\n"
        end
      end
    
      def print_map_path(path : Array(Vec2))
        print_map_path(path.map { |l| Vec3.new(l) })
      end
    
      def print_map_path(path : Array(Vec3))
        @grid.each_with_index do |row, y|
          row.each_with_index do |tile, x|
            if l = path.find { |l| l.x == x && l.y == y }
              print ("%i" % (l.z % 10)).colorize(:green).mode(:bright)
            elsif tile == '#'
              print "#".colorize(:red).mode(:dim)
            else
              print tile
            end
          end
          print "\n"
        end
      end
    end
    
    2 votes