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”. 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.

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