Avatar of davearonson

davearonson's solution

to Connect in the Elixir Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

Compute the result for a game of Hex / Polygon.

The abstract boardgame known as Hex / Polygon / CON-TAC-TIX is quite simple in rules, though complex in practice. Two players place stones on a rhombus with hexagonal fields. The player to connect his/her stones to the opposite side first wins. The four sides of the rhombus are divided between the two players (i.e. one player gets assigned a side and the side directly opposite it and the other player gets assigned the two other sides).

Your goal is to build a program that given a simple representation of a board computes the winner (or lack thereof). Note that all games need not be "fair". (For example, players may have mismatched piece counts.)

The boards look like this (with spaces added for readability, which won't be in the representation passed to your code):

. O . X .
 . X X O .
  O O O X .
   . X O X O
    X O O O X

"Player O" plays from top to bottom, "Player X" plays from left to right. In the above example O has made a connection from left to right but nobody has won since O didn't connect top and bottom.

Running tests

Execute the tests with:

$ elixir connect_test.exs

Pending tests

In the test suites, all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by commenting out the relevant @tag :pending with a # symbol.

For example:

# @tag :pending
test "shouting" do
  assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end

Or, you can enable all the tests by commenting out the ExUnit.configure line in the test suite.

# ExUnit.configure exclude: :pending, trace: true

For more detailed information about the Elixir track, please see the help page.

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

connect_test.exs

if !System.get_env("EXERCISM_TEST_EXAMPLES") do
  Code.load_file("connect.exs", __DIR__)
end

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)

defmodule ConnectTest do
  use ExUnit.Case

  def remove_spaces(rows) do
    Enum.map(rows, &String.replace(&1, " ", ""))
  end

  # @tag :pending
  test "empty board has no winner" do
    board =
      remove_spaces([
        ". . . . .",
        " . . . . .",
        "  . . . . .",
        "   . . . . .",
        "    . . . . ."
      ])

    assert Connect.result_for(board) == :none
  end

  @tag :pending
  test "1x1 board with black stone" do
    board = ["X"]
    assert Connect.result_for(board) == :black
  end

  @tag :pending
  test "1x1 board with white stone" do
    board = ["O"]
    assert Connect.result_for(board) == :white
  end

  @tag :pending
  test "convulted path" do
    board =
      remove_spaces([
        ". X X . .",
        " X . X . X",
        "  . X . X .",
        "   . X X . .",
        "    O O O O O"
      ])

    assert Connect.result_for(board) == :black
  end

  @tag :pending
  test "rectangle, black wins" do
    board =
      remove_spaces([
        ". O . .",
        " O X X X",
        "  O X O .",
        "   X X O X",
        "    . O X ."
      ])

    assert Connect.result_for(board) == :black
  end

  @tag :pending
  test "rectangle, white wins" do
    board =
      remove_spaces([
        ". O . .",
        " O X X X",
        "  O O O .",
        "   X X O X",
        "    . O X ."
      ])

    assert Connect.result_for(board) == :white
  end

  @tag :pending
  test "spiral, black wins" do
    board = [
      "OXXXXXXXX",
      "OXOOOOOOO",
      "OXOXXXXXO",
      "OXOXOOOXO",
      "OXOXXXOXO",
      "OXOOOXOXO",
      "OXXXXXOXO",
      "OOOOOOOXO",
      "XXXXXXXXO"
    ]

    assert Connect.result_for(board) == :black
  end

  @tag :pending
  test "spiral, nobody wins" do
    board = [
      "OXXXXXXXX",
      "OXOOOOOOO",
      "OXOXXXXXO",
      "OXOXOOOXO",
      "OXOX.XOXO",
      "OXOOOXOXO",
      "OXXXXXOXO",
      "OOOOOOOXO",
      "XXXXXXXXO"
    ]

    assert Connect.result_for(board) == :none
  end
end
_comment = """
  IDEA from Glenn Espinosa:
  - Start from desired edge, with desired color
    (eg, from top w/ O, or from left w/ X).
  - See where you can go from there (matching), that we haven't been.
  - For each such place
    * recurse with the current spot added to list of where we've been
  - If we hit opposite side, that color has won
  - If we can't go anywhere, end this exploration;
    automagically goes back to last fork-point
"""
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
    grid = board |> Enum.map(&String.graphemes/1)
    cond do
      # use tupleized version for easy cell access/substitution
      connect_to_bottom(tupleize(grid), "O") -> :white
      # transposing saves us the complex logic of
      # figuring out what direction we're going,
      # while figuring out if someone won
      connect_to_bottom(tupleize(transpose(grid)), "X") -> :black
      true -> :none
    end
  end


  defp tupleize(board), do: tupleize(board, {})
  defp tupleize([], acc), do: acc
  defp tupleize([head|tail], acc) do
    tupleize(tail, Tuple.append(acc, head |> List.to_tuple))
  end


  defp connect_to_bottom(board, who) do
    (0..tuple_size(elem(board, 0)) - 1)
    |> Enum.any?(&(connect_to_bottom(board, who, 0, &1)))
  end

  # did we try to go off the board?  no win here.
  defp connect_to_bottom(board, _who, row, col)
       when row < 0 or col < 0 or col >= tuple_size(elem(board, 0)),
       do: false

  # is this spot not this player's, or already seen?  no win here.
  defp connect_to_bottom(board, who, row, col)
       when elem(elem(board, row), col) != who,
       do: false

  # did we reach the bottom?  YAY!
  defp connect_to_bottom(board, _who, row, _col)
       when row == tuple_size(board) - 1,
       do: true

  # if not yet success or failure, try to progress via each surrounding spot.
  # board is tilted, so if we go up we can't go further left,
  # and if we go down, we can't go further right.
  @neighbor_deltas [{1,-1},{1,0},{0,-1},{0,1},{-1,0},{-1,1}]
  defp connect_to_bottom(board, who, row, col) do
    # "S" could be anything other than empty or a player;
    # making it one char helps debugging via IO.puts :-)
    new_row = elem(board, row) |> put_elem(col, "S")
    new_board = board |> put_elem(row, new_row)
    @neighbor_deltas
    |> Enum.any?(&(connect_to_bottom(new_board, who,
                                     row + elem(&1, 0),
                                     col + elem(&1, 1))))
  end


  defp transpose([head|tail]) do
    transpose(tail, Enum.map(head, &([&1])))
  end
  defp transpose([], acc), do: Enum.map(acc, &Enum.reverse/1)
  defp transpose([head|tail], acc) do
    transpose(tail,
              acc
              |> Enum.zip(head)
              |> Enum.map(fn({old, new}) -> [new|old] end))
  end

end

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?