Ruby implementation for Hacker Rank connected cells in a grid

Question

https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem

problem statement:

Consider a matrix where each cell contains either a 1 or a 0. Any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. In the following grid, all cells marked X are connected to the cell marked Y.

XXX
XYX
XXX
If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to zero or more cells in the region but is not necessarily directly connected to all the other cells in the region.

Given an matrix, find and print the number of cells in the largest region in the matrix. Note that there may be more than one region in the matrix.

For example, there are two regions in the following matrix. The larger region at the top left contains cells. The smaller one at the bottom right contains .

110
100
001

my solution:

# Complete the connectedCell function below.
def connectedCell(matrix)
    highest_count = 0
    visited = {}

    (0...matrix.length).each do |i|
        (0...matrix[0].length).each do |j|
        next if visited[[i,j]]
            if matrix[i][j] == 1
                res = get_area_count([i,j], matrix)
                if res[0] > highest_count
                    highest_count = res[0]
                end

                visited = visited.merge(res[1])
            end
        end
    end

    highest_count
end

def get_area_count(pos, matrix)
    q = [pos]
    visited = {}
    count = 0
    while q.length > 0
        tile_pos = q.shift
        if !visited[tile_pos]
            count += 1
            visited[tile_pos] = true
            q += nbrs(tile_pos, matrix)
        end 
    end

    return [count, visited]
end

def nbrs(pos, matrix)
    right = [pos[0], pos[1] + 1]
    left = [pos[0], pos[1] - 1]
    top = [pos[0] + 1, pos[1]]
    bottom = [pos[0] - 1, pos[1]]
    top_right = [top[0], right[1]]
    bottom_right = [bottom[0], right[1]]
    top_left = [top[0], left[1]]
    bottom_left = [bottom[0], left[1]]
    positions = [right, left, top, bottom, top_right, bottom_right, top_left, bottom_left]
    positions.select{|npos| in_bounds?(npos, matrix.length, matrix[0].length) && matrix[npos[0]][npos[1]] == 1}
end

def in_bounds?(pos, m, n)
    pos[0] >= 0 && pos[0] < m && pos[1] >= 0 && pos[1] < n    
end

thought process: My thought was to iterate through each cell in the matrix and then if it was a 1 I would do a depth-first traversal to find all other cells that had a 1and were connected to the parent cell. then I would add 1 to the count whenever I visited a cell and add it to the visited hash so that it wouldn't be added to the count. I added helper methods for in_bounds? and nbrsmostly for better readability in the get_area_count method(which is the dfs implementation). The nbrs method is pretty verbose, but I kept it that on purpose because I'm preparing for technical interviews, where accuracy is important, and I thought actually listing out each direction would help in debugging / explaining it to the interviewer.

Answer 1

I really like clear and speaking method names, I quickly tried to refactor the first method but have had not much time, I hope this helps anyway.

I have not understand the other initialization of the visited hash in the area_count method (yet).

The new neighbors method indeed looks some kind of overloaded with information, no good idea yet how to change it, if needed at all as you described.

require 'json'
require 'stringio'

def connectedCell(matrix, visited = {})
    (0...matrix.length).each do |row|
        (0...matrix[0].length).each do |col|
        next if visited[[row, col]]
            if matrix[row][col] == 1
              return update_count_stats(row, col, matrix, visited)
            end
        end
    end
end

def update_count_stats(row, col, matrix, visited)
    result = area_count([row, col], matrix)
    visited.merge(result[1])
    result[0] > 0 ? result[0] : 0
end

def area_count(pos, matrix)
    q = [pos]
    visited = {}
    count = 0
    while q.length > 0
        tile_pos = q.shift
        if !visited[tile_pos]
            count += 1
            visited[tile_pos] = true
            q += neighbors(tile_pos, matrix)
        end 
    end

    return [count, visited]
end

def neighbors(pos, matrix)
    right = [pos[0], pos[1] + 1]
    left = [pos[0], pos[1] - 1]
    top = [pos[0] + 1, pos[1]]
    bottom = [pos[0] - 1, pos[1]]

    top_right = [top[0], right[1]]
    bottom_right = [bottom[0], right[1]]
    top_left = [top[0], left[1]]
    bottom_left = [bottom[0], left[1]]

    positions = [right, left, top, bottom, top_right, bottom_right, top_left, bottom_left]
    positions.select{|npos| in_bounds?(npos, matrix.length, matrix[0].length) && matrix[npos[0]][npos[1]] == 1}
end

def in_bounds?(pos, number_of_columns, number_of_rows)
    pos[0] >= 0 && pos[0] < number_of_columns && pos[1] >= 0 && pos[1] < number_of_rows   
end

number_of_rows = 4 # just for testing, was gets.to_i
number_of_columns = 4 # just for testing, was gets.to_i
matrix = Array.new(number_of_rows)

# sample input
# 1 1 0 0
# 0 1 1 0
# 0 0 1 0
# 1 0 0 0

number_of_rows.times do |i|
    matrix[i] = gets.rstrip.split(' ').map(&:to_i)
end
result = connectedCell matrix
puts result
```

Answer 2

Rubocop Report

connectedCell

Avoid nested code blocks if clean alternative statements are available. For instance, in method connectedCell you have the following block:

if matrix[i][j] == 1
  # .. code omitted
end

Replace the if-statement with next unless matrix[i][j] == 1 and you'll be able to reduce nesting with 1 level.

The next part has a similar avoidable nesting, only this time we can use an inline if-statement.

if res[0] > highest_count
    highest_count = res[0]
end

This could be replaced with highest_count = res[0] if res[0] > highest_count.

And prefer to use snake_case for method names: connected_cell.

The complete method could then be written as:

def connected_cell(matrix)
  highest_count = 0
  visited = {}

  (0...matrix.length).each do |i|
    (0...matrix[0].length).each do |j|
      next if visited[[i, j]]

      next unless matrix[i][j] == 1

      res = get_area_count([i, j], matrix)
      highest_count = res[0] if res[0] > highest_count

      visited = visited.merge(res[1])
    end
  end

  highest_count
end

get_area_count

The while condition while q.length > 0 should be replaced by until q.empty? because it's considered a negative condition (pseudo: while !empty).

We have another case of avoidable nesting: replace the if !visited[tile_pos] block with next if visited[tile_pos].

The method rewritten:

def get_area_count(pos, matrix)
  q = [pos]
  visited = {}
  count = 0
  until q.empty?
    tile_pos = q.shift
    next if visited[tile_pos]

    count += 1
    visited[tile_pos] = true
    q += nbrs(tile_pos, matrix)
  end

  [count, visited]
end