24
\$\begingroup\$

Given an integer \$N\$, you must print a \$N\times N\$ integer involute with the numbers increasing in a clockwise rotation. You can start with either 0 or 1 at the top left, increasing as you move towards the centre.

Examples

Input => 1
Output => 
0

Input => 2
Output => 
0 1
3 2

Input => 5
Output => 
 0  1  2  3 4
15 16 17 18 5
14 23 24 19 6
13 22 21 20 7
12 11 10  9 8 

Input => 10
Output => 
 0  1  2  3  4  5  6  7  8  9
35 36 37 38 39 40 41 42 43 10
34 63 64 65 66 67 68 69 44 11
33 62 83 84 85 86 87 70 45 12
32 61 82 95 96 97 88 71 46 13
31 60 81 94 99 98 89 72 47 14
30 59 80 93 92 91 90 73 48 15
29 58 79 78 77 76 75 74 49 16
28 57 56 55 54 53 52 51 50 17
27 26 25 24 23 22 21 20 19 18

You may output a 2 dimensional array, or a grid of numbers.

Challenge inspired by Article by Eugene McDonnell

This is so the goal is to minimize your source code with answers being scored in bytes.

\$\endgroup\$
1

18 Answers 18

15
\$\begingroup\$

Jelly, 13 bytes

⁸JW;ṚZ+LƲƲ2¡¡

Try it online!

A nilad function or full program that takes a number from stdin and returns the 1-based involute of size n × n.

How it works

⁸JW;ṚZ+LƲƲ2¡¡
⁸                Empty list ([])
          2¡¡    Take n from stdin and repeat 2n times starting from the above:
                   Given previous matrix m,
    ṚZ+LƲ          Rotate m and add the number of rows of m
 JW;     Ʋ         Prepend a row of 1..(number of rows of m)

The involute can be constructed iteratively as follows:

Start with m = [] (think of it as 0-row, 0-col matrix)
Repeat 2n times:
    If m has r rows, add r to every cell of m
    Rotate m 90deg clockwise
    Attach 0..r-1 (or 1..r) as a new row at the top of m

After every step, the matrix m is always an involute for some rectangular size (square at even steps). For example, using 1-based indexing, doing a single step on

1 2 3
8 9 4
7 6 5

gives

 1  2  3
10 11  4
 9 12  5
 8  7  6

and then

 1  2  3  4
12 13 14  5
11 16 15  6
10  9  8  7
\$\endgroup\$
3
  • \$\begingroup\$ Ah, that vectorised addition of adding the row count to every element, that's the mathematical insight I was missing! \$\endgroup\$
    – Neil
    Jan 27 at 13:07
  • \$\begingroup\$ Ah, much more like the Jelly I know and love! \$\endgroup\$ Jan 27 at 18:42
  • \$\begingroup\$ ...and, of course, nice insight :) \$\endgroup\$ Jan 27 at 18:50
11
\$\begingroup\$

MATL, 12 11 bytes

UG1YL-GoQ&P

Try it online!

MATL (like MATLAB) has a spiral matrix which spirals clockwise from the center, so this performs the necessary flips and subtracts the matrix from N^2.

Probably Luis Mendo knows how to golf this... Thanks to Luis Mendo for −1 byte.

	% Implicit input N
U	% Square
G1YL	% Push the N×N spiral matrix (S)
	% clockwise from the center, starting at 1
-	% N^2 - S, element-wise
GoQ	% Push mod(N,2)+1
&P	% Flip along that dimension:
	% for odd N, flips the rows; for even N, flips the columns
	% Implicit output
\$\endgroup\$
5
  • \$\begingroup\$ Nice! I came up with the same solution, except you can use U instead of 2^ \$\endgroup\$
    – Luis Mendo
    Jan 26 at 23:03
  • 1
    \$\begingroup\$ @LuisMendo I knew that U existed but couldn't search the docs efficiently...my MATL is rusty! \$\endgroup\$
    – Giuseppe
    Jan 26 at 23:35
  • \$\begingroup\$ Please feel free to incorporate my suggestion if you want to reduce the byte count \$\endgroup\$
    – Luis Mendo
    Jan 27 at 12:12
  • \$\begingroup\$ @LuisMendo thanks! I was waiting to add an explanation as well and that's a lot tougher to do on mobile. \$\endgroup\$
    – Giuseppe
    Jan 27 at 14:12
  • 1
    \$\begingroup\$ Ah :-) I fixed a couple of small things (I'm on the computer now) \$\endgroup\$
    – Luis Mendo
    Jan 27 at 15:40
7
\$\begingroup\$

Python, 73 bytes (@ovs)

f=lambda n,m=0,p=-1:n*[n]and((*range(m,n),),*zip(*f(2*n-m+p,n,~p)[::-1]))

Attempt This Online!

Old Python, 74 bytes (@DialFrost)

f=lambda n,m=0,p=-1:n and((*range(m,n),),*zip(*f(2*n-m+p,n,~p)[::-1]))or()

Attempt This Online!

Old Python, 76 bytes

f=lambda n,m=0,p=-1:n>m and((*range(m,n),),*zip(*f(2*n-m+p,n,~p)[::-1]))or()

-15 by reversing order of recursion.

Attempt This Online!

Old Python, 91 bytes

lambda n:g((n*n-1,))
g=lambda*s:(l:=s[0][0])and g((*range(l-len(s),l),),*zip(*s[::-1]))or s

Attempt This Online!

Builds the spiral from inside to out by recursively rotating 90° and adding a row on the top.

\$\endgroup\$
2
7
\$\begingroup\$

APL (Dyalog Unicode), 18 17 16 bytes

(⍉⍳⍨,⊖+≢)⍣2⍣⎕⊤⍨⍬

Try it online!

Full program. TIO uses instead of for easier test case demonstration. For the core algorithm, refer to my Jelly answer.

The only additional trick here is the ⊤⍨⍬, which is one of the shortest expressions that give a 0-by-0 matrix (0 0⍴0). This one in particular is handy because it doesn't mess up by stranding with the input value.

-1 byte using ⍳∘≢ → ⍳⍨; the rows are guaranteed to be distinct, so finding indices of items in itself gives the vector of indices for the leading axis.

Also -1 byte by moving to the end of the train to save a . Add first row to a transposed matrix == Add first column and then transpose it.

\$\endgroup\$
1
6
\$\begingroup\$

BQN, 29 bytesSBCS

{⍉⌽∘⍉∘∾´≍¨⌽(/«⥊2↕↕𝕩+1)⊔⌽↕𝕩⋆2}

Run online!

A port of Bubbler's Jelly answer comes in at 20 bytes:

{(⊒˜∾⍉∘⌽+≠)⍟2⍟𝕩↕0‿0}

Run online!

\$\endgroup\$
5
\$\begingroup\$

Charcoal, 48 41 40 bytes

F⊗N≔⁺⟦Eυλ⟧E∧υ⌊υ⁺LυE⮌υ§μλυEυ⪫Eι◧IλL⌈Eυ⌈ν 

Try it online! Link is to verbose version of code. Edit: Saved 4 bytes by porting @Bubbler's observation that you can vectorised add the current length of the array to all of its elements on each iteration, 3 bytes by special-casing an empty array to avoid having to perform the first step manually, and 1 byte by golfing my rotation code. Explanation:

F⊗N

Repeat 2n times.

≔⁺⟦Eυλ⟧E∧υ⌊υ⁺LυE⮌υ§μλυ

Rotate the spiral while adding its length to it values and prefix an additional row of numbers from 0 up to its length. (Unfortunately Charcoal won't let me vectorised add the length to the whole matrix at once but fortunately I can at least do it a row at a time as part of the rotation.) Also handle the edge case of the initially empty spiral which produces a zero-length array.

Eυ⪫Eι◧IλL⌈Eυ⌈ν 

Display the final spiral as a grid.

\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog Unicode), 35 bytes

{(⍵*2)-⌽{⍉⌽⍵,(⌈/,⍵)+⍳≢⍵}⍣(2×⍵-1)⍪0}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 20 by porting my Jelly answer. Would be 18 as a full program. \$\endgroup\$
    – Bubbler
    Jan 27 at 4:52
  • \$\begingroup\$ @Bubbler Nice. Are you sure you don't want to post that separately? \$\endgroup\$
    – Adám
    Jan 27 at 8:01
4
\$\begingroup\$

JavaScript (Node.js), 91 bytes

f=(n,s=[[n*n-1]],[l]=t=s[0])=>l?f(n,[0,...t].map((_,i)=>s.map(r=>r[i-1]||--l).reverse())):s

Try it online!

A port of loopy walt's Python answer. Although I don't really understand what happening.

\$\endgroup\$
4
\$\begingroup\$

R, 78 bytes

function(n)matrix(order(cumsum(rep(rep(c(n,1,-n,-1),,x<-2*n-1),n-1:x%/%2))),n)

Try it online!

Direct construction of the matrix, no rotations required.

\$\endgroup\$
4
\$\begingroup\$

R, 84 81 67 bytes

Or R>=4.1, 60 bytes by replacing the word function with a \.

Edit: -14 bytes thanks to @Giuseppe inspired by @Bubbler's Jelly answer.

function(n){m=t(1)
while(T<n)m=rbind(1:n,(T=nrow(m))+t(m[T:1,]))
m}

Try it online!

Uses the common "rotate and add a row on top" approach.

See also @Giuseppe's direct construction of the matrix.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 67 bytes by porting Bubbler's answer more closely. \$\endgroup\$
    – Giuseppe
    Jan 28 at 16:27
  • \$\begingroup\$ @Giuseppe, thanks! I felt that starting with \$n^2\$ may be sub-optimal and you proved me right. \$\endgroup\$
    – pajonk
    Jan 28 at 18:45
3
\$\begingroup\$

JavaScript (ES7),  111  101 bytes

Saved 9 bytes thanks to @tsh

Returns a matrix. The results are 1-indexed.

n=>[...Array(n)].map((x=-n/2,y,a)=>a.map(_=>n*n-(i=4*(++x*x>y*y?x:y)**2)+(x>y||-1)*(i**.5+x+y),y+=x))

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ n=>[...Array(n)].map((x=-n/2,Y,a,y=Y+x)=>a.map(_=>n*n+~(i=4*(++x*x>y*y?x:y)**2)+(x>y||-1)*(i**.5+x+y))) \$\endgroup\$
    – tsh
    Jan 27 at 7:02
  • \$\begingroup\$ Also, since 1-indexed is allowed. You may change +~ to -. \$\endgroup\$
    – tsh
    Jan 27 at 7:14
2
\$\begingroup\$

Jelly,  34 33  32 bytes

I would have thought Jelly would be better at this, maybe a more mathematical approach will triumph?

ŒMḢḢ
+þ`¬ZṚ$ṛ¬Ç$¦€Ç¦‘ɼ$ḣÇȦƊ?ƬȦƇṂ

A monadic Link accepting a positive integer that yields a list of lists of positive integers (top-left 1 option).

Try it online!

How?

Start with an \$N\times N\$ table of zeros, then repeatedly either fill in the next number in the first zero of the first row that contains a maximal value, unless that row is filled in which case rotate. This process terminates with a full table but rotated further than we want, so we collect all the states along the way then pick the one we need out (using ȦƇṂ).

ŒMḢḢ - Helper Link: list of list of integers (current state)
ŒM   - multidimensional indices of maximal elements
  Ḣ  - head
   Ḣ - head -> row index containing the maximum value

+þ`¬ZṚ$ṛ¬Ç$¦€Ç¦‘ɼ$ḣÇȦƊ?ƬȦƇṂ - Link: positive integer, N
+þ`                         - [1..N] addition table with [1..N]
   ¬                        - logical NOT -> N×N table of zeros
                       Ƭ    - collect inputs while distinct applying:
                      ?     -   if...
                     Ɗ      -   ...condition: last three links as a monad:
                   Ç        -     call our helper link
                  ḣ         -     head (the current state) to that index
                    Ȧ       -     all truthy when flattened?
      $                     -   ...then: last two links as a monad:
    Z                       -     transpose
     Ṛ                      -     reverse
                                  - this rotates when we've finished a row
                 $          -   ...else: last two links as a monad:
                ɼ           -     apply to the register (initially 0) & yield:
               ‘            -       increment
              ¦             -     sparse application...
             Ç              -     ...to indices: call our helper link
            €               -     ...apply: for each:
           ¦                -       sparse application...
          $                 -       ...to indices: last two links as a monad:
        ¬                   -         logical NOT (vectorises)
         Ç                  -         call our helper link
       ṛ                    -       ...apply: the incremented register value
                         Ƈ  - filter keep those for which:
                        Ȧ   -   all truthy when flattened?
                          Ṃ - minimum (of the rotate tables we have left)

Another approach, but even more lengthy at 39:

RµṚĖm€0F;Ɱ"ḊṚ’$ṖṚ4ƭ³’Ḥ¤Ð¡UÐeẎIƇŒṬ€×"J$S

Try this one

This one works by building a list of the two-dimensional indices ordered by their final value then composing the table by adding up tables that are all zeros except the bottom-rightmost entry which is the number we want there in the end.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 13 bytes

¯I·FāUøí¬g+Xš

1-based.

Port of @Bubbler's Jelly answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

¯             # Start with an empty list []
 I·           # Push the input and double it
   F          # Pop and loop that many times:
    ā         #  Push a list in the range [1,length] (without popping the matrix)
     U        #  Pop and store this list in variable `X`
      øí      #  Rotate the matrix 90 degrees clockwise:
      ø       #   Zip/transpose; swapping rows/columns
       í      #   Reverse each row
        ¬     #  Push the first row (without popping the matrix)
         g    #  Pop and push its length
          +   #  Add that to each value in the matrix
           Xš #  Prepend `X` as first row
              # (after the loop, the resulting matrix is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

R, 187 183 151 bytes

function(n){w=which
X=diag(0,n)
X[n,]=m=n:1
while(!min(X)){i=w(!X)[1]
j=w(!!X[-1:-i])
X[i-1+1:j]=max(X)+j:1
X=t(X)[m,]}
`if`(n%%2,t(t(X)[m,])[m,],X)-1}

Try it online!

A clumsier version of rotate and fill!

\$\endgroup\$
2
\$\begingroup\$

Julia, 46 bytes

m\n=[1:n n.+rotl90(m')]'
!n=[n<2||!~-n\~-n\n;]

Try it online!

the simple rotate and add row, with some trickery with ' (transpose)
starts with 1

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 108 bytes

n=>[...Array(n)].map((_,Y,a)=>a.map(g=(y=Y,x,_,s=n)=>y?--s-x?s-y?x?s*4+g(y-1,x-1,_,s-1):4*s-y:3*s-x:s+y:x));

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Factor + math.matrices, 82 79 bytes

[ 2 * { } [ dup length [ m+n flip [ reverse ] map ] keep iota prefix ] repeat ]

Try it online!

Port of @Bubbler's excellent Jelly answer.

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 52 bytes

-8 bytes thanks to @att.

Nest[Join[{l=0;l++&/@#},Reverse@#+l]&,{{}},2#-1]&

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 52 bytes \$\endgroup\$
    – att
    Feb 16 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.