Spiral printing a matrix in Erlang

readme.md

Spiral printing a matrix in Erlang

This Erlang module implements a function that returns the elements of a 2D matrix (list of lists) in a spiral order. The spiral order starts from the top-left corner and proceeds in a spiral pattern, moving right across the top row, down the right column, left across the bottom row, and up the left column, and continues until all elements are traversed.

Module Overview

-module(spiral).

Defines the module name as spiral.

Functions

spiral_test/0

This function tests the spiral/1 function with different 2D matrices. It does not return any value; its purpose is to invoke the spiral/1 function and check that it works as expected.

spiral_test() ->
  spiral([[1,2,3],[8,9,4],[7,6,5]]),
  spiral([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]),
  spiral([[1,2,3],[8,9,4],[7,6,5]]).

• The first matrix is a 3x3 grid.
• The second matrix is a 4x4 grid.
• The third matrix is the same as the first.

spiral/1

This is the main function that performs the spiral traversal. It takes a 2D list (matrix) and returns a list of elements in spiral order.

spiral(L) ->
  spiral_int(L, []).

It calls the helper function spiral_int/2, passing the matrix L and an empty list [] to accumulate the result.

spiral_int/2

This recursive function handles the actual traversal. It processes the matrix layer by layer, traversing the outermost elements and then recursively processing the inner layers.

spiral_int([[]|_], Acc) ->
  Acc;
spiral_int([Head|[]], Acc) ->
  Acc ++ Head;
spiral_int([Head | Tail], Acc) ->
  spiral_int(lists:reverse(transpose(Tail)), Acc ++ Head).

• Base case 1: If the matrix is empty ([[]|_]), the traversal is complete, and it returns the accumulated list Acc.
• Base case 2: If there's only one row left ([Head|[]]), it appends this row to the accumulator.
• Recursive case: If there are multiple rows ([Head | Tail]), the function:
  • Adds the top row (Head) to the accumulator.
  • Transposes the remaining rows (Tail), reverses them, and recursively calls spiral_int/2 with the new list and updated accumulator.

transpose/1

This helper function is used to rotate the matrix, converting rows into columns, which is an essential part of navigating the spiral.

transpose([[]|_]) -> [];
transpose(M) ->
    [lists:map(fun hd/1, M) | transpose(lists:map(fun tl/1, M))].

• Base case: If the matrix is empty ([[]|_]), it returns an empty list.
• Recursive case: It takes the head of each row to form the first column of the transposed matrix, then applies the function recursively to the rest of the matrix.

---

Example

Given the matrix:

[[1, 2, 3],
 [8, 9, 4],
 [7, 6, 5]]

The spiral traversal proceeds as follows:

1. Take the top row: [1, 2, 3]
2. Take the right column: [4, 5]
3. Take the bottom row: [6, 7]
4. Take the left column: [8]
5. Finally, the center element [9]

The output of the spiral/1 function for this matrix is:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Running the Tests

To test the spiral traversal:

1. Compile the module using erlc:

   erlc spiral.erl

2. Start an Erlang shell:

   erl

3. Load the compiled module:

   c(spiral).

4. Call the test function:

   spiral:spiral_test().

This will run the spiral traversal on the test matrices and check if the function works correctly.

spiral.erl

-module(spiral).

-author('[email protected]').

-export([spiral_test/0, spiral/1]).

spiral_test() ->
  spiral([[1,2,3],[8,9,4],[7,6,5]]),
  spiral([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]),
  spiral([[1,2,3],[8,9,4],[7,6,5]]).


spiral(L) ->
  spiral_int(L, []).

spiral_int([[]|_], Acc) ->
  Acc;
spiral_int([Head|[]], Acc) ->
  Acc ++ Head;
spiral_int([Head | Tail], Acc) ->
  %% io:format("Head ~w Tail ~w~n", [Head, Tail]),
  spiral_int(lists:reverse(transpose(Tail)), Acc ++ Head).

transpose([[]|_]) -> [];
transpose(M) ->
    [lists:map(fun erlang:hd/1, M) | transpose(lists:map(fun erlang:tl/1, M))].