Cassidoo’s Interview question of the week | 448

Learning Resources
1

Hello :waving_hand:

This week question is about finding min. distance. Here it is

You’re given a 2D grid representing a city where each cell is either empty (0), a fire station (1), or a building (2). Fire stations can serve buildings based on horizontal + vertical moves only. Return a 2D grid where each cell shows the minimum distance to the nearest fire station.

> fireStationCoverage([
  [2, 0, 1],
  [0, 2, 0],
  [1, 0, 2]
])
> [[2, 1, 0],  
   [1, 2, 1],
   [0, 1, 2]]

> fireStationCoverage([
  [1, 0, 0, 1],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [1, 0, 0, 1]
])
> [[0, 1, 2, 0],
   [1, 2, 2, 1],
   [1, 2, 2, 1],
   [0, 1, 2, 0]]

Happy coding!

2 Likes
2

Thanks for yet another broadcast of RWC IQOTW! :slight_smile:

Hm, I would expect that the 2D grid for the second example would look like this:

expected = [
  [0, 1, 1, 0],
  [1, 2, 2, 1],
  [1, 2, 2, 1],
  [0, 1, 1, 0],
]

and not:

expected = [
  [0, 1, 2, 0],
  [1, 2, 2, 1],
  [1, 2, 2, 1],
  [0, 1, 2, 0],
]

But I guess you can calculate the distance that way too?

3

It’s like a job interview question where a sneaky HR guy introduced a mistake to confuse you :joy:

Solution 
def fireStationCoverage city
  squares = (0...city.size).to_a.product((0...city.first.size).to_a)
  fire_stations = squares.filter{|x, y| city[x][y] == 1 }
  squares.each do |x, y|
    city[x][y] = fire_stations.map do |fx, fy| 
      (fx - x).abs + (fy - y).abs 
    end.min
  end
  city
end


p fireStationCoverage([
  [2, 0, 1],
  [0, 2, 0],
  [1, 0, 2]
]) # => [[2, 1, 0], [1, 2, 1], [0, 1, 2]]
2 Likes
4
Solution 
def fire_station_coverage(grid)
  fire_station_coordinates = []
  grid.each.with_index do |cols, row_i|
    cols.each.with_index do |col, col_i|
      fire_station_coordinates << [row_i, col_i] if col == 1
    end
  end

  grid.map.with_index { |cols, row_i|
    cols.map.with_index { |col, col_i|
      fire_station_coordinates.map { |station_row_i, station_col_i|
        (station_row_i - row_i).abs + (station_col_i - col_i).abs
      }.min
    }
  }
end
1 Like
5

Hahaha, exactly like that, or simply there was some traffic jam in some parts of the city, so only firefighters from the fire station further away were available. :smiley:

And again, I am amazed at how many hidden gems Ruby has, and how sometimes even if I know to use filter, it didn’t come to my mind to use it on a two-dimensional array. So thanks! :blush:

I thought this was a perfect opportunity to apply some Object-oriented design, but instead I (over)used lambdas:

Solution 
def fire_station_coverage(city_grid)
  city_grid_cell_legend           = { empty: 0, fire_station: 1, building: 2 }
  city_fire_station_locations     = []
  city_fire_station_coverage_grid = Array.new(city_grid.size) { Array.new(city_grid.size) }

  traverse_city_grid = lambda do |&action|
    city_grid.each_with_index do |street, street_number|
      street.each_with_index do |cell, cell_number|
        action.call(street_number, cell_number, cell)
      end
    end
  end

  distance_between_two_locations = lambda do |location_one, location_two|
    (location_one[:street_number] - location_two[:street_number]).abs +
      (location_one[:cell_number] - location_two[:cell_number]).abs
  end

  distance_to_the_nearest_fire_station_from = lambda do |location|
    city_fire_station_locations.map do |fire_station_location|
      return 0 if fire_station_location == location

      distance_between_two_locations.call(fire_station_location, location)
    end.min
  end

  traverse_city_grid.call do |street_number, cell_number, cell|
    city_fire_station_locations << { street_number:, cell_number: } if cell == city_grid_cell_legend[:fire_station]
  end

  traverse_city_grid.call do |street_number, cell_number|
    city_fire_station_coverage_grid[street_number][cell_number] =
      distance_to_the_nearest_fire_station_from.call(street_number:, cell_number:)
  end

  city_fire_station_coverage_grid
end
1 Like