Avatar of mpodkorytov

mpodkorytov's solution

to Spiral Matrix in the Prolog Track

Published at Mar 05 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(Size, Matrix) :- spiral(1, Size, Matrix).

spiral(_, 0, []) :- !.
spiral(X, 1, [[X]]) :- !.

spiral(Start, Size, Matrix) :- 
    upper_side(Start, Size, Matrix, Us),
    valid_upper_side(Start, Size, Us),
    right_side(Size, Matrix, Rs),
    valid_right_side(Start, Size, Rs),
    bottom_side(Size, Matrix, Bs),
    valid_bottom_side(Start, Size, Bs),
    left_side(Matrix, Ls),
    valid_left_side(Start, Size, Ls),
    inner_matrix(Start, Size, Matrix, Nstart, Nsize, Im),
    spiral(Nstart, Nsize, Im).

valid_upper_side(Start, Size, Us) :-
    consequent(Start, Size, Us).

valid_right_side(Start, Size, Rs) :-
    Rstart is Start + Size - 1,
    consequent(Rstart, Size, Rs).

valid_bottom_side(Start, Size, Bs) :-
    Bstart is Start + 2 * Size - 2,
    consequent(Bstart, Size, Bs).

valid_left_side(Start, Size, Ls) :-
    Lstart is Start + 3 * Size - 3,
    Lsize is Size - 1,
    consequent(Lstart, Lsize, Ls).

consequent(_, 0, []) :- !.
consequent(X, 1, [X]) :- !.
consequent(Start, Size, [Start|Rest]) :-
    Nstart is Start + 1,
    Nsize is Size - 1,
    consequent(Nstart, Nsize, Rest). 

upper_side(_, _, [], []) :- !.
upper_side(_, _, Matrix, Us) :-
    Matrix = [Row | _],
    Us = Row.

right_side(_, [], []) :- !.
right_side(_, Matrix, Rs) :-
    Matrix = [Row | Rows],
    Rs = [X | Xs],
    last(Row, X),
    right_side(_, Rows, Xs).

bottom_side(_, [], []) :- !.
bottom_side(_, Matrix, Bs) :-
    last(Matrix, Lr),
    reverse(Lr, Bs).

left_side([], []) :- !.
left_side(Matrix, Ls) :-
    Matrix = [_ | Rows],
    reverse(Rows, Rrows),
    build_left_side(Rrows, Ls).

build_left_side([], []) :- !.
build_left_side(Rows, Ls) :-
    Rows = [First | Rest],
    First = [FirstInARow | _],
    Ls = [FirstInARow | RestLs],
    build_left_side(Rest, RestLs).    

inner_matrix(Start, Size, Matrix, Nstart, Nsize, Im) :-
    Nstart is Start + 4 * Size - 4,
    Nsize is Size - 2,
    trim(Matrix, Rows),
    trim_all(Rows, Im).

trim_all([], []) :- !.
trim_all(Rows, Inner) :-
    Rows = [R | Rs],
    trim(R, I),
    Inner = [I | Is],
    trim_all(Rs, Is).

trim([], []) :- !.
trim([_], []) :- !.
trim([_, _], []) :- !.
trim(List, Out) :-
    List = [_ | Tail],
    reverse(Tail, Reversed),
    Reversed = [_ | Rtail],
    reverse(Rtail, Out).

Community comments

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

mpodkorytov's Reflection

Took much longer than all other exercises. I wonder if it's possible to generate spiral matrices, as currently I was only able to check if a matrix is spiral.