Avatar of philinko

philinko's solution

to Spiral Matrix in the Prolog Track

Published at Jan 16 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

Source

Reddit r/dailyprogrammer 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_matrix_tests.plt

pending :-
    current_prolog_flag(argv, ['--all'|_]).
pending :-
    write('\nA TEST IS PENDING!\n'),
    fail.

:- begin_tests(spiral).
    test(empty_spiral, condition(true)) :-
      spiral(0, []).

    test(trivial_spiral, condition(pending)) :-
      spiral(1, [[1]]).
    test(spiral_of_size_2, condition(pending)) :-
      spiral(2, [[1,2],
                 [4,3]]).
    test(spiral_of_size_3, condition(pending)) :-
      spiral(3, [[1,2,3],
                 [8,9,4],
                 [7,6,5]]).
    test(spiral_of_size_4, condition(pending)) :-
      spiral(4, [[ 1, 2, 3, 4],
                 [12,13,14, 5],
                 [11,16,15, 6],
                 [10, 9, 8, 7]]).
    test(spiral_of_size_5, condition(pending)) :-
      spiral(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_tests(spiral).
spiral(0, []) :- !.
spiral(N, Matrix) :-
    proper_length(Matrix, N),
    length_of_all_members(Matrix, N),
    check_all_axis_rec(Matrix, row, 1, 1, 1, N, normal).

length_of_all_members([], _) :- !.
length_of_all_members([Head|Tail], N) :-
    proper_length(Head, N),
    length_of_all_members(Tail, N).

matrix_axis(_, _, _, [], []) :- !. 

matrix_axis(row, RowIdx, _, Matrix, Axis) :-
    nth1(RowIdx, Matrix, Axis).

matrix_axis(column, _, ColIdx, Matrix, Axis) :-
    Matrix = [FirstRow|OtherRows],
    nth1(ColIdx, FirstRow, FirstOfColumn),
    matrix_axis(column, _, ColIdx, OtherRows, RestOfColumn),
    append([FirstOfColumn], RestOfColumn, Axis).

check_all_axis_rec(_, _, _, _, _, 0, _) :- !.
check_all_axis_rec(Matrix, AxisType, RowIdx, ColIdx, StartValue, N, Direction) :-
    (AxisType = row -> 
        StartIdx is ColIdx;
        StartIdx is RowIdx),
    matrix_axis(AxisType, RowIdx, ColIdx, Matrix, Axis),
    check_axis(Axis, Direction, StartIdx, StartValue, N),
    other_axis(AxisType, OtherAxisType),
    next_direction(AxisType, Direction, NextDirection),
    next_index(AxisType, Direction, RowIdx, ColIdx, N, NextRowIdx, NextColIdx),
    NextValue is StartValue + N,
    next_n(AxisType, N, NextN),
    check_all_axis_rec(Matrix, OtherAxisType, NextRowIdx, NextColIdx, NextValue, NextN, NextDirection).

check_axis(_, _, _, _, 0) :- !.
check_axis(Axis, normal, StartIdx, StartValue, N) :-
    !,
    nth1(StartIdx, Axis, Value),
    StartValue = Value,
    NextIdx is StartIdx + 1,
    NextValue is StartValue + 1,
    NextN is N-1,
    check_axis(Axis, normal, NextIdx, NextValue, NextN).

check_axis(Axis, backwards, StartIdx, StartValue, N) :-
   !,
   reverse(Axis, InverseAxis),
   proper_length(Axis, AxisLen),
   NewStartIdx is AxisLen - StartIdx + 1,
   check_axis(InverseAxis, normal, NewStartIdx, StartValue, N).


other_axis(row, column).
other_axis(column, row).
next_direction(row, Dir, Dir).
next_direction(column, Dir, OtherDirection) :-
    Dir = normal -> OtherDirection = backwards;
    OtherDirection = normal.

next_index(row, normal, RowIdx, ColIdx, N, NextRowIdx, NextColIdx) :-
    NextRowIdx is RowIdx + 1,
    NextColIdx is ColIdx + N - 1.

next_index(row, backwards, RowIdx, ColIdx, N, NextRowIdx, NextColIdx) :-
    NextRowIdx is RowIdx - 1,
    NextColIdx is ColIdx - N + 1.

next_index(column, normal, RowIdx, ColIdx, N, NextRowIdx, NextColIdx) :-
    NextRowIdx is RowIdx + N - 1,
    NextColIdx is ColIdx - 1.

next_index(column, backwards, RowIdx, ColIdx, N, NextRowIdx, NextColIdx) :-
    NextRowIdx is RowIdx - N + 1,
    NextColIdx is ColIdx + 1.

next_n(column, N, N) :- !.
next_n(row, N, DecN) :-
    DecN is N - 1.

Community comments

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

philinko's Reflection

Can probably be simplified a bit. There is still a choice point somewhere, but I haven't figured out where.