Daily Coding Problem: Problem #23 [Easy]

coding_problem_23.rb

# You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on.

# Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board.

# For example, given the following board:

# [[f, f, f, f],
# [t, t, f, t],
# [f, f, f, f],
# [f, f, f, f]]
# and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps required to reach the end is 7, since we would need to go through (1, 2) because there is a wall everywhere else on the second row.

@matrix = [
  [0, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
]

start_tile = [3, 0]
end_tile = [0,0]

# find all possible tiles, not being walls nor on previous path 
def find_adjacents_tiles(tile, path)
   p "find adj for #{tile}"
  possible_tiles = [
    [tile[0] - 1, tile[1]],
    [tile[0], tile[1] - 1],
    [tile[0], tile[1] + 1],
    [tile[0] + 1, tile[1]],
  ]
  valid_ones = []
  possible_tiles.each do |new_tile|
    p "new_tile: #{new_tile}"
    is_inside = new_tile[0] >= 0 && new_tile[1] >= 0 && new_tile[0] < @matrix.length && new_tile[1] < @matrix[0].length
    p "is_inside:#{is_inside}"
    if is_inside
      is_wall = @matrix[new_tile[0]][new_tile[1]] == 1
      p "is_wall:#{is_wall}"
      p "previously seen:#{path.include?(new_tile)}"
      if !is_wall && !path.include?(new_tile)
        valid_ones << new_tile  && !is_wall
      end
    end
  end
  p "valid_ones: #{valid_ones}"
  valid_ones
end

def discover(path = [], tile, end_tile)
  p "path:#{path} - tile:#{tile}" 
  if tile[0] == end_tile[0] && tile[1] == end_tile[1]
    return path
  else
    next_tiles = find_adjacents_tiles(tile, path)
    if next_tiles.empty?
      return nil
    else
      next_tiles.each do |tile|
        new_path = path + [tile]
        return discover(new_path, tile, end_tile)
      end
    end
  end
end

def run(start_tile, end_tile)
  res = discover([start_tile], start_tile, end_tile)
  return res ? res.length - 1 : res
end

run(start_tile, end_tile)