# Code Review Request -- Exercism Connect Exercise

**URL:** <https://forum.elixirforum.com/t/code-review-request-exercism-connect-exercise/39729>\
**Category:** Discussions\
**Tags:** code-review\
**Created:** [May 16, 2021, 4:25pm UTC](https://forum.elixirforum.com/t/code-review-request-exercism-connect-exercise/39729 "2021-05-16T16:25:05Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![stevensonmt](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/stevensonmt/32/20503_2.png) [@stevensonmt](https://forum.elixirforum.com/u/stevensonmt)\
**Post date:** [May 16, 2021, 4:25pm UTC](https://forum.elixirforum.com/t/code-review-request-exercism-connect-exercise/39729/1 "2021-05-16T16:25:05Z")

</div>

Was hoping someone could take a look at this code and advise me on any organizational pitfalls or algorithm inefficiencies. I would also appreciate if someone could confirm that what I think is a depth first search algorithm is actually so. Thanks in advance for taking the time to look.

This was a solution to the [exercism exercise “Connect”](https://exercism.io/my/solutions/b6c49695ea31437d82dcd65dd6dbbee3). I’m somehow locked from requesting mentor feedback on exercism because some request from probably two years ago is still unanswered and there is no way to cancel it that I can find.

```elixir
defmodule Connect do
  @doc """
  Calculates the winner (if any) of a board
  using "O" as the white player
  and "X" as the black player
  """
  @spec result_for([String.t()]) :: :none | :black | :white
  def result_for(board) do
    board
    |> process_input()
    |> find_winner()
  end

  defmodule Board do
    @moduledoc """
    Creates graph consisting of vertices with edges. Build Paths with respect to obstacles (vertices of other color or empty).
    """

    defstruct vertices: %{}, edges: %{}, rows: 0, cols: 0

    @type path :: [{integer, integer}]

    @type player :: :black | :white | :none

    @spec add_vertex(% __MODULE__ {}, {integer, integer, player}) :: % __MODULE__ {}
    def add_vertex(board \\ % __MODULE__ {}, {x, y, player}) do
      % __MODULE__ {
        board
        | vertices: Map.update(board.vertices, player, [{x, y}], fn curr -> [{x, y} | curr] end)
      }
    end

    @spec add_edge(% __MODULE__ {}, player, {{integer, integer}, {integer, integer}}) ::
            % __MODULE__ {}
    def add_edge(board, player, edge = {{x1, y1}, {x2, y2}}) do
      cond do
        # same row, one col on either side ok
        x1 == x2 and :erlang.abs(y1 - y2) == 1 ->
          update_edges(board, player, edge)

        # comparing to row above, one col to left or same col ok
        x1 - x2 == 1 and (y1 - y2 == 0 or y1 - y2 == 1) ->
          update_edges(board, player, edge)

        # comparing to row below, one col to right or same col ok
        x1 - x2 == -1 and (y1 - y2 == 0 or y1 - y2 == -1) ->
          update_edges(board, player, edge)

        true ->
          board
      end
    end

    def update_edges(board, player, {{x1, y1}, {x2, y2}}) do
      % __MODULE__ {
        board
        | edges:
            Map.update(board.edges, player, [{{x1, y1}, {x2, y2}}], fn curr ->
              [{{x1, y1}, {x2, y2}} | curr]
            end)
      }
    end

    def add_edge(board, _) do
      board
    end

    @spec add_edges(% __MODULE__ {}) :: % __MODULE__ {}
    def add_edges(board) do
      board.vertices
      |> Enum.map(fn {player, vrtcs} ->
        {player,
         for v1 <- vrtcs,
             v2 <- vrtcs,
             :uniq do
           {v1, v2}
         end}
      end)
      |> Enum.reduce(board, fn {player, edges}, bd ->
        edges
        |> Enum.reduce(bd, fn edge, b ->
          add_edge(b, player, edge)
        end)
      end)
    end

    @spec rows([{integer, integer, player}]) :: integer
    def rows(vertices) do
      vertices
      |> Enum.group_by(fn {x, _, _} -> x end)
      |> Enum.count()
    end

    @spec cols([{integer, integer, player}]) :: integer
    def cols(vertices) do
      vertices
      |> Enum.group_by(fn {x, _, _} -> x end)
      |> Enum.take(1)
      |> Enum.map(fn {_, row} -> length(row) end)
      |> hd
    end

    @spec build_board([{integer, integer, player}]) :: % __MODULE__ {}
    def build_board(vertices) do
      rows = rows(vertices)
      cols = cols(vertices)

      vertices
      |> Enum.reduce(% __MODULE__ {rows: rows, cols: cols}, fn v, acc ->
        add_vertex(acc, v)
      end)
      |> add_edges()
    end

    @spec find_winner(% __MODULE__ {}) :: path | nil
    def find_winner(board) do
      Enum.find([:black, :white], :none, fn player ->
        try do
          dfs(board, player)
          |> hd
        rescue
          _ -> false
        end
      end)
    end

    def dfs(board, player) do
      potential_starting_points = starting_points(board, player)

      potential_end_points = end_points(board, player)

      board.edges
      |> Map.get(player)
      |> Stream.filter(fn {v1, _v2} ->
        Enum.member?(potential_starting_points, v1)
      end)
      |> Stream.flat_map(fn {v1, v2} ->
        __MODULE__.build_path(board, player, [v2, v1], potential_end_points)
      end)
      |> Enum.take(1)
    end

    defp starting_points(board, :black) do
      0..(board.rows - 1)
      |> Enum.map(fn i -> {i, i} end)
    end

    defp starting_points(board, :white) do
      0..(board.cols - 1)
      |> Enum.map(fn c -> {0, c} end)
    end

    defp end_points(board, :black) do
      rows = board.rows
      cols = board.cols
      0..(rows - 1) |> Enum.zip((cols - 1)..(cols - 1 + rows - 1))
    end

    defp end_points(board, :white) do
      rows = board.rows
      cols = board.cols

      (rows - 1)..(cols + rows - 2)
      |> Enum.map(fn c -> {rows - 1, c} end)
    end

    @spec build_path(% __MODULE__ {}, player, path, [{integer, integer}]) :: path | nil
    def build_path(board, player, path, potential_end_points) do
      start_from = hd(path)

      if Enum.any?(potential_end_points, fn {a, b} -> Enum.member?(path, {a, b}) end) do
        [%{winner: player, winning_path: path}]
      else
        board.edges
        |> Map.get(player)
        |> Stream.filter(fn {v1, v2} ->
          not Enum.member?(path, v2) and v1 == start_from
        end)
        |> Stream.flat_map(fn {_v1, v2} ->
          build_path(board, player, [v2 | path], potential_end_points)
          # doesn't recurse infinitely b/c eventually the filter yields empty 
          # data to the flat_map call
        end)
      end
    end
  end

  @spec process_input(String.t()) :: % __MODULE__.Board{}
  defp process_input(input) do
    input
    |> Enum.with_index()
    |> Enum.flat_map(fn {line, row} ->
      line
      |> String.graphemes()
      |> Enum.with_index()
      |> Enum.map(fn {c, col} ->
        {row, row + col, c}
      end)
      |> chars_to_players
    end)
    |> Board.build_board()
  end

  @spec chars_to_players([{integer, integer, String.t()}]) :: [{integer, integer, atom}]
  defp chars_to_players(positions) do
    positions
    |> Enum.map(fn {x, y, char} ->
      {x, y,
       case char do
         "X" -> :black
         "O" -> :white
         _ -> :none
       end}
    end)
  end

  defp find_winner(board) do
    cond do
      # no edges implies single vertex, just return the player that owns that vertex
      board.edges == %{} ->
        winner =
          board.vertices
          |> Map.keys()
          |> hd

      # if the only vertex owner is :none, the winner is :none
      board.vertices |> Map.keys() == [:none] ->
        :none

      # find the winner or return :none if no winning path found
      true ->
        Board.find_winner(board)
    end
  end
end

```

---

<div class="post-metadata">

**Author:** ![Sebb](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/sebb/32/21818_2.png) [@Sebb](https://forum.elixirforum.com/u/Sebb)\
**Post date:** [May 17, 2021, 5:29pm UTC](https://forum.elixirforum.com/t/code-review-request-exercism-connect-exercise/39729/2 "2021-05-17T17:29:45Z")

</div>

Do you know about mentored mode in exercism?  
[https://exercism.io/mentored-mode-vs-independent-mode](https://exercism.io/mentored-mode-vs-independent-mode)

---

<div class="post-metadata">

**Author:** ![stevensonmt](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/stevensonmt/32/20503_2.png) [@stevensonmt](https://forum.elixirforum.com/u/stevensonmt)\
**Post date:** [May 17, 2021, 5:43pm UTC](https://forum.elixirforum.com/t/code-review-request-exercism-connect-exercise/39729/3 "2021-05-17T17:43:22Z")

</div>

Yes, but in general I prefer to work through the exercises on my own in a random order. I know that for other tracks mentors can be overwhelmed by the queue of exercises awaiting mentoring. I’d prefer not to contribute to that issue if possible.

---

<div class="post-metadata">

**Author:** ![tovarchristian21](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/tovarchristian21/32/25743_2.png) [@tovarchristian21](https://forum.elixirforum.com/u/tovarchristian21)\
**Post date:** [May 17, 2021, 6:19pm UTC](https://forum.elixirforum.com/t/code-review-request-exercism-connect-exercise/39729/4 "2021-05-17T18:19:40Z")

</div>

I think that is the jist of exercism, if you are looking for people who are actually willing to review your code and give you advice, there is not a better place than the actual mentored mode in exercism.

---

<div class="post-metadata">

**Author:** ![stevensonmt](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/stevensonmt/32/20503_2.png) [@stevensonmt](https://forum.elixirforum.com/u/stevensonmt)\
**Post date:** [May 17, 2021, 7:05pm UTC](https://forum.elixirforum.com/t/code-review-request-exercism-connect-exercise/39729/5 "2021-05-17T19:05:08Z")

</div>

It’s rare for me to encounter an exercise where I want that feedback. I appreciate the suggestion, but I really do understand how exercism works. The fact that I am locked from requesting feedback on this particular exercise because of an outstanding request from at least 7 months ago reinforces my desire not to clutter up the mentoring queue. Again thanks for your suggestion but this is not an XY problem.
