Ruby DFS with printout showing the state


  • 0
    T

    This is a DFS solution, pretty straightforward but with a few caveats that took me a while to Iron out.

    Some of the things that got me stuck:

    • originally stopped after the first overlap, found that it doesn't guarantee that the first overlap of all buildings is optimal
    • originally returned -1 after first building ran out of nodes, but that breaks if a building is located near the middle with other buildings on the edges.
    • then changed it to keep going until all the buildings ran out of nodes, this caused time limit exceeded errors, the fix was to only run up to twice as long as the first building that stopped since in the worst case, there's a building in the middle with two buildings equidistance on opposite sides.

    Here is the code:

    def shortest_distance(grid)
      @test= false
      buildings=[]
      @grid = grid
      @n = @grid.length
      @m = @grid[0].length if @grid[0]
      (0...@n).each do |i|
        (0...@m).each do |j|
          buildings << [i,j] if @grid[i][j] == 1
        end
      end
      @building_count = buildings.count
      seen, queue = [], []
      distances, counts, completed = {}, {}, {}
      count = 0
      shortest, first_finish = nil, nil
      loop do
        count += 1
        break if (first_finish && (count > first_finish * 2))
        buildings.each_with_index do |b, i|
          next if completed[i]
    
          seen[i] ||= {b.to_s => true}
          queue[i] ||= [b]
          new_queue = []
          queue[i].each do |node|
            new_queue += calc_neighbors(node[0], node[1], seen[i])
          end
          if new_queue.length == 0
            completed[i] = true
            first_finish ||= count
            next
          end
    
          new_queue.each do |node|
            counts[node.to_s] ||= 0
            counts[node.to_s] += 1
            distances[node.to_s] ||= 0
            distances[node.to_s] += count
            if counts[node.to_s] == @building_count
              shortest ||= distances[node.to_s]
              shortest = [shortest, distances[node.to_s]].min
            end
          end
          queue[i] = new_queue
        end
        break if completed.count == @building_count
      end
      print_seen(seen, counts, distances) if @test
      return shortest || -1
    end
    
    def print_seen(seen_set, counts, distances)
      seen_set.each_with_index do |seen, index|
        puts "printing seen set for #{index}"
        (0...@n).each do |i|
          row = ""
          (0...@m).each do |j|
            row += "=   " && next if @grid[i][j] != 0
            row += ".   " && next if !seen[[i,j].to_s]
            row += "X   " && next if counts[[i,j].to_s] != @building_count
            num = distances[[i,j].to_s].to_s
            num += " "*(4 - num.length)
            row += num
          end
          puts row
        end
      end
    end
    
    def calc_neighbors(i, j, seen)
      options = [[i-1,j], [i,j-1], [i+1,j], [i,j+1]]
      set = []
      options.each do |p|
        next if !valid?(p[0], p[1]) || seen[p.to_s]
        set << p
        seen[p.to_s] = true
      end
      return set
    end
    
    def valid?(i, j)
      i >= 0 && j >= 0 && i < @n && j < @m && @grid[i][j] == 0
    end
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.