Avatar of davearonson

davearonson's solution

to Saddle Points 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.

Detect saddle points in a matrix.

So say you have a matrix like so:

    0  1  2
  |---------
0 | 9  8  7
1 | 5  3  2     <--- saddle point at (1,0)
2 | 6  6  7

It has a saddle point at (1, 0).

It's called a "saddle point" because it is greater than or equal to every element in its row and less than or equal to every element in its column.

A matrix may have zero or more saddle points.

Your code should be able to provide the (possibly empty) list of all the saddle points for any given matrix.

Note that you may find other definitions of matrix saddle points online, but the tests for this exercise follow the above unambiguous definition.

Running tests

Execute the tests with:

$ elixir saddle_points_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.

Source

J Dalbey's Programming Practice problems http://users.csc.calpoly.edu/~jdalbey/103/Projects/ProgrammingPractice.html

Submitting Incomplete Solutions

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

saddle_points_test.exs

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

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

defmodule SaddlePointsTest do
  use ExUnit.Case

  # @tag :pending
  test "extract rows" do
    rows = SaddlePoints.rows("1 2\n10 20")
    assert rows == [[1, 2], [10, 20]]
  end

  @tag :pending
  test "extract a row" do
    rows = SaddlePoints.rows("9 7\n8 6")
    assert Enum.at(rows, 0) == [9, 7]
  end

  @tag :pending
  test "extract other row" do
    rows = SaddlePoints.rows("9 8 7\n19 18 17")
    assert Enum.at(rows, 1) == [19, 18, 17]
  end

  @tag :pending
  test "extract other row again" do
    rows = SaddlePoints.rows("1 4 9\n16 25 36")
    assert Enum.at(rows, 1) == [16, 25, 36]
  end

  @tag :pending
  test "extract a column" do
    columns = SaddlePoints.columns("1 2 3\n4 5 6\n7 8 9\n8 7 6")
    assert Enum.at(columns, 0) == [1, 4, 7, 8]
  end

  @tag :pending
  test "extract another column" do
    columns = SaddlePoints.columns("89 1903 3\n18 3 1\n9 4 800")
    assert Enum.at(columns, 1) == [1903, 3, 4]
  end

  @tag :pending
  test "no saddle point" do
    saddle_points = SaddlePoints.saddle_points("2 1\n1 2")
    assert saddle_points == []
  end

  @tag :pending
  test "a saddle point" do
    saddle_points = SaddlePoints.saddle_points("1 2\n3 4")
    assert saddle_points == [{0, 1}]
  end

  @tag :pending
  test "another saddle point" do
    saddle_points = SaddlePoints.saddle_points("18 3 39 19 91\n38 10 8 77 320\n3 4 8 6 7")
    assert saddle_points == [{2, 2}]
  end

  @tag :pending
  test "multiple saddle points" do
    saddle_points = SaddlePoints.saddle_points("4 5 4\n3 5 5\n1 5 4")
    assert saddle_points == [{0, 1}, {1, 1}, {2, 1}]
  end
end
defmodule Matrix do
  @doc """
  Parses a string representation of a matrix
  to a list of rows
  """
  @spec rows(String.t()) :: [[integer]]
  def rows(str) do
    str
    |> String.split("\n")
    |> Enum.map(&String.split/1)
    |> Enum.map(&array_of_strings_to_ints/1)
  end

  defp array_of_strings_to_ints(arr) do
    do_array_of_strings_to_ints(arr, []) |> Enum.reverse
  end

  defp do_array_of_strings_to_ints([], acc), do: acc
  defp do_array_of_strings_to_ints([str|more], acc) do
    do_array_of_strings_to_ints(more, [String.to_integer(str)|acc])
  end

  @doc """
  Parses a string representation of a matrix
  to a list of columns
  """
  @spec columns(String.t()) :: [[integer]]
  def columns(str) do
    rows(str) |> List.zip |> Enum.map(&Tuple.to_list/1)
  end

  @doc """
  Calculates all the saddle points from a string
  representation of a matrix
  """
  @spec saddle_points(String.t()) :: [{integer, integer}]
  def saddle_points(str) do
    MapSet.intersection(find_candidates(rows(str),
                                        &Enum.max/1,
                                        &itself/1),
                        # would more efficient to derive from memoized rows
                        find_candidates(columns(str),
                                        &Enum.min/1,
                                        &reverse_tuple/1))
    |> MapSet.to_list
  end

  # "view" meaning, the array of arrays, be it by rows or columns
  defp find_candidates(view, extreme_finder, loc_maker) do
    view |> Enum.with_index
         |> Enum.flat_map(&(make_extreme_locs(&1,
                                              extreme_finder,
                                              loc_maker)))
         |> Enum.into(%MapSet{})
  end

  defp make_extreme_locs(list_with_index, extreme_finder, loc_maker) do
    # assignments just to memoize and simplify....
    vals = elem(list_with_index, 0)
    extreme = apply(extreme_finder, [vals])
    list_num = elem(list_with_index, 1)
    vals |> Enum.with_index
         |> Enum.filter(&(elem(&1, 0) == extreme))
         |> Enum.map(&(apply(loc_maker, [{list_num, elem(&1, 1)}])))

  end

  defp itself(whatever), do: whatever

  defp reverse_tuple({col, row}), do: {row, col}

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?