islands.rb

islands.rb

# find the number of islands (1's) in a n x m matrix
# islands are only connected by cells in the up, down, left and right directions.

input = "
1 1 1 1 1 \n
0 0 1 0 0 \n
0 0 0 0 0 \n
1 1 0 0 1 \n
1 0 0 0 1 \n
"

input2 = "
0 0 0 0 \n
0 1 0 0 \n
0 0 1 0 \n
0 0 0 0 \n
"

input3 = "
1 0 0 1 \n
1 1 0 0 \n
0 0 1 0 \n
0 0 1 0 \n
"

class Islands 

  attr_accessor :collection

  def initialize(input)
    @matrix = input
      .split("\n")
      .reject(&:empty?)
      .map { |row| row.strip.split(" ").map(&:to_i) }
  end

  def count
    island_count, r_idx, c_idx = 0, 0, 0
    n, m = @matrix.length, @matrix.first&.length || 0 

    while r_idx < n && c_idx < m
      q = []

      if @matrix[r_idx][c_idx] == 1
        # BFS, mutate cell after traversal
        island_count += 1
        q.push([r_idx, c_idx])
        until q.empty?
          vec = q.shift
          @matrix[vec[0]][vec[1]] = 0
          q.concat(linked_cells(vec))
        end
      end

      # increment to next row or col
      c_idx, r_idx = (c_idx == m - 1) ? [0, r_idx + 1] : [c_idx + 1, r_idx]
    end

    island_count
  end

  private

  def linked_cells(vec)
    vecs = [
      [vec[0] - 1, vec[1]],
      [vec[0], vec[1] - 1],
      [vec[0] + 1, vec[1]],
      [vec[0], vec[1] + 1]
    ]
    vecs.select do |vec| 
      @matrix.dig(vec[0], vec[1]) == 1 && 
        vec[0] >= 0 && 
        vec[1] >= 0
    end
  end

end

islands = Islands.new(input3)
p islands.count # => 3