/* 

  Spiral order in Picat.

  Spiral of a matrix.

  Adapted from https://www.enjoyalgorithms.com/blog/print-matrix-in-spiral-order

  Matrix:
  [1,2,3,4]
  [5,6,7,8]
  [9,10,11,12]
  [13,14,15,16]

  Spiral order:
  [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

  Matrix:
  [1,2,3,4,5,6]
  [7,8,9,10,11,12]
  [13,14,15,16,17,18]

  Spiral order:
  [1,2,3,4,5,6,12,18,17,16,15,14,13,7,8,9,10,11]


  See go2/0 for printing the spiral.

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.
main => go.

go =>
  member(S,1..2),
  spiral(S,Mat),
  println("Matrix:"),
  foreach(Row in Mat)
    println(Row)
  end,
  nl,
  println("Spiral order:"),
  println(spiralOrder(Mat)),
  nl,
  fail,
  nl.


/*

  Here is a spiral matrix for a 15x15 matrix:

   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
  56  57  58  59  60  61  62  63  64  65  66  67  68  69  16
  55 104 105 106 107 108 109 110 111 112 113 114 115  70  17
  54 103 144 145 146 147 148 149 150 151 152 153 116  71  18
  53 102 143 176 177 178 179 180 181 182 183 154 117  72  19
  52 101 142 175 200 201 202 203 204 205 184 155 118  73  20
  51 100 141 174 199 216 217 218 219 206 185 156 119  74  21
  50  99 140 173 198 215 224 225 220 207 186 157 120  75  22
  49  98 139 172 197 214 223 222 221 208 187 158 121  76  23
  48  97 138 171 196 213 212 211 210 209 188 159 122  77  24
  47  96 137 170 195 194 193 192 191 190 189 160 123  78  25
  46  95 136 169 168 167 166 165 164 163 162 161 124  79  26
  45  94 135 134 133 132 131 130 129 128 127 126 125  80  27
  44  93  92  91  90  89  88  87  86  85  84  83  82  81  28
  43  42  41  40  39  38  37  36  35  34  33  32  31  30  29

*/
go2 =>
  N = 15,
  X = (1..N*N).chunks_of(N),
  print_spiral(X),
  nl.


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

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

%
% Print a spiral matrix in the spiral order.
%
% Note: This uses spiralOrder/1.
% It would be faster to adjust spiralOrder/1 to
% to do the printing but I prefer this approach for generality.
% 
print_spiral(X) =>
  N = X.len,
  SpiralOrder = spiralOrder(X),
  println(spiralOrder=SpiralOrder),
  M = new_array(N,N),
  foreach({V,K} in zip(SpiralOrder,1..N*N))
    [I2,J2] = [[I,J] : I in 1..N, J in 1..N, X[I,J] == V].first,
    M[I2,J2] := K
  end,
  Format = "% " ++ ((N*N).to_string.len+1).to_string ++ "d", 
  foreach(I in 1..N)
    foreach(J in 1..N)
      printf(Format,M[I,J])
    end,
    nl
  end,
  nl.

%
% Return the spiral order of X.
% Adapted from https://www.enjoyalgorithms.com/blog/print-matrix-in-spiral-order
%
spiralOrder(X) = Spiral =>
  M = X.len,
  N = X[1].len,
  RowStart = 1,
  RowEnd = M,
  ColStart = 1,
  ColEnd = N,
  Spiral = [],
  while (RowStart <= RowEnd, ColStart <= ColEnd)
    foreach(I in ColStart..ColEnd)
      Spiral := Spiral ++ [X[RowStart,I]],
    end,
    RowStart := RowStart + 1,
    foreach(I in RowStart..RowEnd)
      Spiral := Spiral ++ [X[I,ColEnd]]
    end,
    ColEnd := ColEnd - 1,
    if RowStart <= RowEnd then
      foreach(I in ColEnd..-1..ColStart)
        Spiral := Spiral ++ [X[RowEnd,I]]
      end,
      RowEnd := RowEnd - 1
    end,
    if ColStart <= ColEnd then
      foreach(I in RowEnd..-1..RowStart)
        Spiral := Spiral ++ [X[I,ColStart]]      
      end,
      ColStart := ColStart + 1
    end,
  end.