Avatar of wolfgangshi

wolfgangshi's solution

to Spiral Matrix in the Elixir Track

Published at Mar 11 2019 · 0 comments
Instructions
Test suite
Solution

Given the size, return a square matrix of numbers in spiral order.

The matrix should be filled with natural numbers, starting from 1 in the top-left corner, increasing in an inward, clockwise spiral order, like these examples:

Spiral matrix of size 3
1 2 3
8 9 4
7 6 5
Spiral matrix of size 4
 1  2  3 4
12 13 14 5
11 16 15 6
10  9  8 7

Running tests

Execute the tests with:

$ elixir spiral_matrix_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

If you're stuck on something, it may help to look at some of the available resources out there where answers might be found.

Source

Reddit r/dailyprogrammer challenge #320 [Easy] Spiral Ascension. https://www.reddit.com/r/dailyprogrammer/comments/6i60lr/20170619_challenge_320_easy_spiral_ascension/

Submitting Incomplete Solutions

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

spiral_test.exs

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

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

defmodule SpiralTest do
  use ExUnit.Case

  # @tag :pending
  test "empty spiral" do
    assert Spiral.matrix(0) == []
  end

  @tag :pending
  test "trivial spiral" do
    assert Spiral.matrix(1) == [[1]]
  end

  @tag :pending
  test "spiral of side length 2" do
    assert Spiral.matrix(2) == [
             [1, 2],
             [4, 3]
           ]
  end

  @tag :pending
  test "spiral of side length 3" do
    assert Spiral.matrix(3) == [
             [1, 2, 3],
             [8, 9, 4],
             [7, 6, 5]
           ]
  end

  @tag :pending
  test "spiral of side length 4" do
    assert Spiral.matrix(4) == [
             [1, 2, 3, 4],
             [12, 13, 14, 5],
             [11, 16, 15, 6],
             [10, 9, 8, 7]
           ]
  end

  @tag :pending
  test "spiral of size 5" do
    assert Spiral.matrix(5) == [
             [1, 2, 3, 4, 5],
             [16, 17, 18, 19, 6],
             [15, 24, 25, 20, 7],
             [14, 23, 22, 21, 8],
             [13, 12, 11, 10, 9]
           ]
  end
end
defmodule Spiral do
  @doc """
  Given the dimension, return a square matrix of numbers in clockwise spiral order.

  This is another solution for this problem, inspired by the Clojure version by fj2010
  on https://www.reddit.com/r/dailyprogrammer/comments/6i60lr/20170619_challenge_320_easy_spiral_ascension/.

  This solution works from inside out, starting from the largest number, and expand the matrix according and
  through the matrix rotation operation. The key is if a matrix is a spiraling one, then to rotate it won't
  break the "spiraling" property of the matrix.

  In the case of clockwise, starting from [[n*n]], where n is the dimension, we add one row at time, and
  here are some key points and observations.
  p1. Each time a row is added, the smallest number is at the left-bottom corner (see below),
      then the added row starting from "min - 1" and decreasing with a length of k ,
      where k is the columns number of the old matrix.
      When a row is added the in such a way, the "spiraling" property is preserved.
  p2. Since when a new row is added, the smallest number is at the bottom right corner (p1), by rotating the
      matrix 90deg clockwise, we can preserve the property that the smallest number is at the left-bottom corner.
  Thus by rotate and add row, we can grow the matrix. To see a example with dimension = 9.

  1. Start
     [[9]]

  2. Rotate and add new row:
     [[9]
      [8]]

  3. Rotate and add new row:
     [[8 9]] -> [[8 9]]
                 [7 6]]
     (The small spiral has begun to appear)

  4. Rotate and add new row:
     [[7 8]
      [6 9]]
      -> [[7 8]
          [6 9]
          [5 4]]
     (spiraling property preserved after rotating and adding new row)

  5. Rotate and add new row:
     [[5 6 7]
      [4 9 8]]
      -> [[5 6 7]
          [4 9 8]
          [3 2 1]]

  Till now, we have already acquired a clockwise spiral matrix. To move the smallest value to the top-left corner
  (currently at bottom right), we further rotate the matrix by 90deg twice.

  Implementation note: add the new row at the beginning of the matrix, not as demonstrated in the above example,
  to take advantage Exlir's list property.
  """

  @spec matrix(dimension :: integer) :: list(list(integer))
  def matrix(dimension, opts \\ [direction: :clockwise])
  def matrix(0, _), do: []
  def matrix(dimension, direction: direction) do
    seed = [[dimension * dimension]]
    total_steps = 2*dimension - 1
    step_fun = case direction do
                 :clockwise ->
                   fn m -> m |> rotate_90_cw |> add_new_row_cw end
                 :counter_clockwise ->
                   fn m -> m |> rotate_90_ccw |> add_new_row_ccw end
               end
    result =
      Stream.iterate(seed, step_fun)
      |> Stream.drop(total_steps - 1)
      |> Enum.take(1)
      |> List.first

    case direction do
      :clockwise -> result
      :counter_clockwise -> result |> rotate_90_ccw
    end
  end

  defp rotate_90_ccw(matrix) do
    matrix
    |> Enum.zip
    |> Enum.map(fn t -> :erlang.tuple_to_list(t) end)
    |> Enum.reverse
  end

  defp rotate_90_cw(matrix) do
    matrix
    |> Enum.zip
    |> Enum.map(fn t -> :erlang.tuple_to_list(t) |> Enum.reverse end)
  end

  defp add_new_row_cw([row | _] = m) do
    column_number = length(row)
    smallest = row |> List.last ## top right

    new_row =
      Stream.iterate(smallest-1, &(&1 - 1))
      |> Enum.take(column_number)
      |> Enum.reverse

    [new_row | m]
  end

  defp add_new_row_ccw([row | _] = m) do
    column_number = length(row)
    smallest = row |> List.first ## top left

    new_row =
      Stream.iterate(smallest-1, &(&1 - 1))
      |> Enum.take(column_number)

    [new_row | m]
  end
end

Community comments

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

wolfgangshi's Reflection

Iteration 1 and iteration 3 presents two different solutions to this problem; whereas iteration 2 was submitted by mistake and it is incomplete.