# Code Review Request -- Exercism Connect Exercise

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

board
end

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 ->
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 ->
end)
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

``````

Do you know about mentored mode in exercism?

1 Like

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.

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.

1 Like

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.