Search adjacent cells of the same color.

adjacent_cells.ex

defmodule AdjacentCells do
  @moduledoc """
  This module is a way to search, mark and count the adjacent cells based on
  the post published by Kevin Ghadyani originally in JavaScript and showing
  that using Elixir the code could be simpler and powerful.

  https://medium.com/free-code-camp/bet-you-cant-solve-this-google-interview-question-4a6e5a4dc8ee

  Indeed, the original code run by Kevin is spending in the better case 229 ms
  with 3 random colors and more than 1 second with only one color.

  For the implementation in Elixir, it's taking 93ms for 3 colors and 84ms for
  only one color.
  """

  @num_colors 3
  @matrix_x 100
  @matrix_y 100

  @doc "generate a random number of colors"
  def colors do
    Enum.to_list(1..@num_colors)
  end

  @doc """
       generate a random matrix of 100x100 elements. Note that
       the size actually depends on `@matrix_x` and `@matrix_y`
       module attributes.
       """
  def gen_matrix do
    colors = colors()
    Enum.map(1..@matrix_y,
             fn _ -> Enum.map(1..@matrix_x,
                              fn _ -> Enum.random(colors) end) end)
  end

  ## @doc helper to make easier to print the color selected for
  ##      the element inside of the matrix
  defp color(c) do
    "#{IO.ANSI.color_background(c)} #{IO.ANSI.reset()}"
  end

  ## @doc show the matrix in the console/terminal output. The terminal
  ##      should have at least 100 cols to show properly the output.
  def output(matrix) do
    Enum.each(matrix, fn row -> Enum.map(row, &(color(&1)))
                                |> IO.puts() end)
    matrix
  end

  ## @doc calculate the max adjacent cells. This is checking one by
  ##      one each position in the table and then, keeping in mind
  ##      if it's a real value or `nil` then proceed to search for
  ##      adjacent ones.
  ##
  ##      One advantage for us is we need only the maximum value.
  ##      We accept as parameter the matrix generated by `gen_matrix/0`.
  def max_adjacent(matrix) do
    total = @matrix_x * @matrix_y
    {max, _} = Enum.reduce(1..total, {0, matrix}, &check_matrix/2)
    max
  end

  ## @doc starting in a specific point (`r`) we trace up, right, down,
  ##      and left searching recursively for adjacent cells with the
  ##      same color, counting and marking as `nil` each found cell.
  defp check_matrix(r, {i, m}) do
    x = rem((r - 1), @matrix_x)
    y = div((r - 1), @matrix_y)
    v = Enum.at(Enum.at(m, y), x)
    case check_adjacent({0, m}, x, y, v) do
      {j, m} when j > i -> {j, m}
      {_, m} -> {i, m}
    end
  end

  ## @doc this function is used by `check_matrix/2` to check the adjacent
  ##      cells, mark them up as `nil` and continue searching for a new
  ##      adjacent cell of the same color up, right, down and left.
  def check_adjacent({i, m}, _, _, nil), do: {i, m}
  def check_adjacent({i, m}, -1, _, _), do: {i, m}
  def check_adjacent({i, m}, _, -1, _), do: {i, m}
  def check_adjacent({i, m}, @matrix_x, _, _), do: {i, m}
  def check_adjacent({i, m}, _, @matrix_y, _), do: {i, m}
  def check_adjacent({i, m}, x, y, v) do
    row = Enum.at(m, y)
    case Enum.at(row, x) do
      ^v ->
        row = List.replace_at(row, x, nil)
        m = List.replace_at(m, y, row)

        {i+1, m}
        |> check_adjacent(x, y-1, v)
        |> check_adjacent(x-1, y, v)
        |> check_adjacent(x, y+1, v)
        |> check_adjacent(x+1, y, v)
      _other ->
        {i, m}
    end
  end
end