8
\$\begingroup\$

Context

Consider square matrices with n columns and rows containing the first n^2 (i.e. n squared) positive integers, where n is odd. The elements of the matrices are arranged such that the integers 1 through n^2 are placed sequentially in a counterclockwise spiral starting at the center and initially moving to the left. Call these matrices M(n)

For n=1 this simply gives the one element matrix M(1)=[[1]].

M(3) is the matrix

9 8 7
2 1 6
3 4 5

M(5) is the matrix

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

and M(7) is the matrix

49 48 47 46 45 44 43
26 25 24 23 22 21 42
27 10  9  8  7 20 41
28 11  2  1  6 19 40
29 12  3  4  5 18 39
30 13 14 15 16 17 38
31 32 33 34 35 36 37

Now consider flattening this matrix into a list/array by concatenating its rows starting from the top and moving down. Call these lists L(n). L(3), L(5) and L(7) are represented below, with their elements delimited by spaces.

9 8 7 2 1 6 3 4 5     (n=3)
25 24 23 22 21 10 9 8 7 20 11 2 1 6 19 12 3 4 5 18 13 14 15 16 17    (n=5)  
49 48 47 46 45 44 43 26 25 24 23 22 21 42 27 10 9 8 7 20 41 28 11 2 1 6 19 40 29 12 3 4 5 18 39 30 13 14 15 16 17 38 31 32 33 34 35 36 37    (n=7)

We can find the index i(n) of L(n) in a lexicographically sorted list of permutations of L(n). In Jelly, the Œ¿ atom gives this index for the list it acts on.

Challenge

Your challenge is to take an positive odd integer n as input and output the index i(n).

The first few values are

n  i(n)
-------
1  1
3  362299
5  15511208759089364438087641
7  608281864033718930841258106553056047013696596030153750700912081

Note that i(n) ~= (n^2)!. This is not on OEIS.

This is code golf per language, so achieve this in the fewest bytes possible.

Sandbox post.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 21 19 bytes

-;,N$ṁx"RFḣNṙ-+\ỤŒ¿

Try it online!

Based on the method from a J article on volutes.

Explanation

-;,N$ṁx"RFḣNṙ-+\ỤŒ¿  Main link. Input: integer n
-;                   Prepend -1. [-1, n]
  ,N$                Pair with its negated value. [[-1, n], [1, -n]]
     ṁ               Mold it to length n.
        R            Range. [1, 2, ..., n]
      x"             Vectorized copy each value that many times.
         F           Flatten
           N         Negate n
          ḣ          Head. Select all but the last n values.
            ṙ-       Rotate left by -1 (right by 1).
              +\     Cumulative sum.
                Ụ    Grade up.
                 Œ¿  Permutation index.
\$\endgroup\$
2
\$\begingroup\$

J, 48 38 Bytes

-10 bytes thanks to @miles !

[:A.@/:_1+/\@|.(2#1+i.)#&}:+:$_1,],1,-

Old:

3 :'A.,(,~|.@(>:@i.@#+{:)@{.)@|:@|.^:(+:<:y),.1'

Note that the result is 0-indexed, so i(1) = 0 and i(5) = 15511208759089364438087640

Explanation (old):

3 :'                                           ' | Explicit verb definition
                                            ,.1  | Make 1 into a 2d array
                                     (+:<:y)     | 4*n, where y = 2*n + 1
                                   ^:            | Repeat 4*n times
                              |:@|.              | Clockwise rotation
       (                    )@                   | Monadic Hook:
             (          )@{.                     | To the first row, apply...
                      {:                         | The last and largest item
                     +                           | Added to...
              >:@i.@#                            | The list 1, 2, ..., n; where n is the row length
          |.@                                    | Reverse
        ,~                                       | Append to the top of the array
      ,                                          | Ravel
    A.                                           | Permutation index

Making the spiral could be quicker, but the orientation would get messed up.

I don't know how J is optimizing this, but it only takes 0.000414 seconds to calculate for n=7 (on a fresh J console session).

\$\endgroup\$
  • \$\begingroup\$ Maybe J does something similar to how I made Jelly do it (code)? \$\endgroup\$ – Jonathan Allan Feb 9 '18 at 20:25
  • \$\begingroup\$ I golfed your method to 39 bytes [:A.@,,.@*0&((,~(#\.+{:)@{.)@|:|.)~2*<:. I also golfed a version of the method in the volute article to 38 bytes [:A.@/:_1+/\@|.(2#1+i.)#&}:+:$_1,],1,-. \$\endgroup\$ – miles Feb 10 '18 at 14:11
1
\$\begingroup\$

Jelly, 27 bytes

ZUðẎṀ+ṚW;⁸µJ
1WÇẎ⁸²¤ḟ$$¿ẎŒ¿

Try it online!

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

MATL, 16 15 14 bytes

lYL!PletY@wXmf

Fails for test cases larger than 3 due to both floating-point inaccuracies and memory limitations.

Try it online!

Explanation

lYL    % Implicit input n. Spiral matrix of that side length
!P     % Transpose, flip vertically. This is needed to match the orientation
       % of columns in the spiral with that of rows in the challenge text
le     % Convert to a row, reading in column-major order (down, then across)
t      % Duplicate
Y@     % All permutations, arranged as rows of a matrix, in lexicographical
       % order
w      % Swap
Xm     % Row membership: gives a column vector containing true / false,
       % where true indicates that the corresponding row in the first input 
       % matches a row from the second output. In this case the second input
       % consists of a single row
f      % Find: gives indices of nonzeros. Implicit display
\$\endgroup\$
  • \$\begingroup\$ Does MATL have built-ins for spirals? \$\endgroup\$ – Erik the Outgolfer Feb 8 '18 at 21:55
  • \$\begingroup\$ @EriktheOutgolfer It may have one \$\endgroup\$ – Luis Mendo Feb 8 '18 at 22:19
  • \$\begingroup\$ Explanation added \$\endgroup\$ – Luis Mendo Feb 8 '18 at 22:25

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.