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
