21
\$\begingroup\$

Given the diagonals of a matrix, reconstruct the original matrix.
The diagonals parallel to the major diagonal (the main diagonals) will be given.
matrix image

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

Rules

  • The matrix will be non-empty and will consist of positive integers
  • You get to choose how the input diagonals will be given:
    1. starting with the main diagonal and then alternating between the outer diagonals (moving outwards from the main diagonal)
    2. from the top-right diagonal to the bottom-left diagonal
    3. from the bottom-left diagonal to the top-right diagonal
  • The end matrix will always be a square
  • The order of the numbers in the diagonals should be from top-left to bottom-right
  • Input and output matrix can be flattened
  • This is , so the shortest answer wins

Test cases

[In]: [[5]]
[Out]: [[5]]

[In]: [[1, 69], [0], [13]]
[Out]: [[1, 0], [13, 69]]

[In]: [[25], [0, 1], [6, 23, 10], [420, 9], [67]]
[Out]: [[6, 0, 25], [420, 23, 1], [67, 9, 10]]
\$\endgroup\$
13
  • 1
    \$\begingroup\$ Sandbox \$\endgroup\$
    – mathcat
    Sep 20 at 14:15
  • 1
    \$\begingroup\$ Can you output as a flattened array? \$\endgroup\$
    – mousetail
    Sep 20 at 14:46
  • 2
    \$\begingroup\$ @mousetail added that in too \$\endgroup\$
    – mathcat
    Sep 20 at 14:50
  • 2
    \$\begingroup\$ Somewhat related \$\endgroup\$
    – DLosc
    Sep 21 at 4:33
  • 2
    \$\begingroup\$ Related (inverse problem) \$\endgroup\$
    – Fatalize
    Sep 21 at 11:15

13 Answers 13

13
\$\begingroup\$

Vyxal, 14 12 bytes

Ṗ'L√ẇÞDf?⁼;h

Try it Online!

Math? Sensible methods of putting things into arrays? Programs that finish in reasonable time? Couldn't be me.

Times out for anything bigger than a 2x2 matrix.

Takes input as a flattened list and outputs a flattened list.

Explained (old)

f₌ṖL√vẇ'ÞD?⁼;h
f₌ṖL√           # Push all permutations of the flattened input, as well as the square root of the length of the flattened input  
     vẇ         # Split each permutation into chunks of that length
       'ÞD?⁼;   # Keep those only where the diagonals equal the input (this basically means try each and every single possible matrix from the input until one is found with the same diagonals)
              h # Get the first (and only) item
\$\endgroup\$
1
  • 11
    \$\begingroup\$ "Times out for anything bigger than a 2x2 matrix." lol. take an upvote! \$\endgroup\$
    – Jonah
    Sep 20 at 16:40
10
\$\begingroup\$

Python, 60 bytes (@Mukundan314)

f=lambda x:x and zip(map(list.pop,x[::-2][::-1]),*f(x[:-1]))

Attempt This Online!

Python, 62 bytes

f=lambda x:x and[*zip(map(list.pop,x[::-2][::-1]),*f(x[:-1]))]

Attempt This Online!

Uses input format 1 (alternating upper and lower diagonals). Destroys the input.

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

J, 21 20 bytes

/:&;</.@i.@(,-)@%:@#

Attempt This Online!

Takes in flat, outputs flat.

  • %:@# Square root of list length, to get matrix side length. Call it n.

  • (,-) Create list n -n

  • i. Assuming n is 5, eg, this will create the matrix:

    4  3  2  1  0
    9  8  7  6  5
    14 13 12 11 10
    19 18 17 16 15
    24 23 22 21 20
    
  • </.@ Create the boxed diagonals of this matrix:

    ┌─┬───┬──────┬─────────┬────────────┬──────────┬────────┬─────┬──┐
    │4│3 9│2 8 14│1 7 13 19│0 6 12 18 24│5 11 17 23│10 16 22│15 21│20│
    └─┴───┴──────┴─────────┴────────────┴──────────┴────────┴─────┴──┘
    
  • /:&; Unbox that and use it to sort the original input, ie, whatever sort would put this into order, apply it to the original input. This does exactly what we want.

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

Pip -x, 22 bytes

Fi,YMX#*aFki+R,yPPOa@k

Inputs a nested list of diagonals, starting from the top right, as a command-line argument; outputs a flattened matrix in row-major order to stdout, one number per line. Try It Online!

Explanation

For an \$N\$ by \$N\$ matrix, the top row can be found by taking the first number from each of the first \$N\$ diagonals and reversing them. If we remove these numbers from their respective diagonals, the next row is the reverse of the first remaining number in the first \$N\$ non-empty diagonals, and so on.

Fi,YMX#*aFki+R,yPPOa@k
        a               Command-line argument, evaluated (-x flag)
      #*                Length of each sublist
    MX                  Maximum (this gives the size of the desired matrix)
   Y                    Store in y
Fi,                     For i in range(y):
         Fk               For k in
              ,y          range(y)
             R            reversed
           i+             with i added to each element:
                   a@k      Sublist at that index
                 PO         Pop its first element
                P           Print the popped element
\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6), 65 bytes

Expects the diagonals from top-right to bottom-left.

a=>a[w=a.length>>1].map((_,y,A)=>A.map((_,x)=>a[w+y-x][x<y?x:y]))

Try it online!

Also 65 bytes:

a=>[...a[w=a.length>>1]].map((_,y,A)=>A.map(_=>a[w+y--].shift()))

Try it online!


Flatten format, 89 bytes

This version expects a flatten array of the diagonals from top-right to bottom-left and returns another flatten array.

The only benefit is that there's only one map(). But the math is much more verbose. So yeah ... that's a bit silly. :-) There may be a better/shorter formula, though.

a=>a.map((_,x)=>a[y=x/w|0,x%=w,n=y+w+~x,(q=n>w&&n-w)*~q-n*~n/2+(x<y?x:y)],w=a.length**.5)

Try it online!

Given an input array of length \$N\$, we define for each index \$0\le i \lt N\$:

$$x=i\bmod w\\ y=\lfloor i/w \rfloor\\ n=y+w-x-1\\ q=\max(n-w,0)$$

where \$w\$ is the width of the matrix, i.e. \$\sqrt{N}\$.

The output value at this position is the value stored in the input array at the following index:

$$\frac{n\times(n+1)}{2}-q\times(q+1)+\min(x,y)$$

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

Ruby, 62 bytes

f=->d{(w=0..l=d.size/2).map{|r|w.map{|c|d[l+r-c][[r,c].min]}}}

Try it online!

Takes input as top-right to bottom-left.

Maps 2d indexes to input, for example a 4X4 matrix:

3,0  2,0  1,0  0,0
4,0  3,1  2,1  1,1
5,0. 4,1  3,2  2,2
6,0  5,1  4,2  3,3
\$\endgroup\$
5
\$\begingroup\$

APL(Dyalog Unicode), 21 22 bytes SBCS

⊖w↑i⊖↑⌽⍨≢↑⍥-i←⍳w←≢∘⍉∘↑

Try it on APLgolf!

∘↑ mix the lists into a matrix, padding on the right with 0s, then…

∘⍉ transpose, then…

   tally the number of rows (this gives the size of the matrix)

w← store as w (for width)

 generate indices from 0 to that − 1

i← store as i (for indices)

⍥- negate the argument length and that, then:

 take arg-length elements from (because negative; the rear) of the indices, padding with 0s

⌽⍨ use those numbers to rotate left (because negative; right) the rows of:

 the original argument lists mixed into a matrix, padded on the right with 0s

i⊖ rotate the columns up by the amounts i

w↑ take the first w rows of that

 flip upside-down

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

MathGolf, 21 bytes

h½)r■_@mÅε-_╙+§\mÄ╓m§

Input expected as option 2: top-right to bottom-left 2D list.
Output as a flattened list.

Try it online.

Explanation:

h          # Push the input-length (without popping)
 ½         # Integer-divide it by 2
  )        # Increase it by 1
   r       # Pop and push a list in the range [0,length(input)//2+1)
    ■      # Get the cartesian product of this list, creating pairs
_          # Duplicate this list of pairs
 @         # Triple swap input,pairs,pairs -> pairs,input,pairs
  m        # Map over each pair,
   Å       # using 2 characters as inner code-block:
    ε      #  Reduce the pair by:
     -     #   Subtracting
      _    # Duplicate this list
       ╙   # Pop and push the maximum (which is length(input)//2+1)
        +  # Add it to each integer in the list
         § # Get the inner lists of the input at those indices
 \         # Swap so the other pairs-list is at the top again
  m        # Map over each pair,
   Ä       # using 1 character as inner code-block:
    ╓      #  Pop and push the minimum of the pair
     m     # Map over both lists:
      §    #  Index these minima into the inner lists
           # (after which the entire stack is output implicitly as result)
\$\endgroup\$
5
\$\begingroup\$

Python, 84 79 bytes

-1 byte thanks to Kevin Cruijsen
-5 bytes thanks to Mukundan314 and 07.100.97.109

lambda x:(z:=len(x)//2+1)and[x[z+c%z+~c//z][min(c%z,c//z)]for c in range(z*z)]

Attempt This Online!

Ported from Arnauld's JS answer

\$\endgroup\$
3
  • 1
    \$\begingroup\$ z+b-a-1 can be z+b+~a for -1 byte. \$\endgroup\$ Sep 20 at 14:49
  • 2
    \$\begingroup\$ 79 bytes output is no longer flattened \$\endgroup\$ Sep 20 at 15:26
  • 1
    \$\begingroup\$ 78 bytes while keeping flattened list. \$\endgroup\$ Sep 20 at 20:17
4
\$\begingroup\$

05AB1E, 20 18 bytes

g;ÝDδ-Z+èεNUεNX‚ßè

-2 bytes porting @Arnauld's JavaScript answer (somewhat). I have the feeling the εNUεNX‚ßè could perhaps be golfed some more.

Input expected as option 2: top-right to bottom-left 2D list.
Output as a matrix.

Try it online or verify all test cases.

Original 20 bytes answer:

g>;©FD®£€нR,¦ε®N>›i¦

Input expected as option 2: top-right to bottom-left 2D list.
Outputs each inner row-list on separated newlines to STDOUT.

Try it online or verify all test cases.

Explanation:

g               # Get the length of the (implicit) input 2D list
 ;              # Halve it
  Ý             # Push a list in the range [0, length(input)//2]
   Dδ-          # Pop and push its subtraction table:
   D            #  Duplicate the list
    δ           #  Apply double-vectorized over the two lists:
     -          #   Subtract
      Z         # Push the flattened maximum (without popping),
                # which is the length(input)//2
       +        # Add it to each integer
        è       # Index each inner-most integer into the (implicit) input
ε               # Map over each inner list of lists:
 NU             #  Store the map-index in variable `X`
 ε              #  Map over each inner list:
  NX‚ß          #   Push the minimum of the inner and outer indices:
  N             #    Push the inner map-index
   X            #    Push the outer map-index from variable `X`
    ‚           #    Pair them together
     ß          #    Pop and push the minimum
      è         #   Index that minimum into the list
                # (after which the resulting matrix is output implicitly)

Extracted from this 05AB1E answer of mine, where I've used 45 degree matrix rotations for a word-search solver:

g;              # Same as above
  î             # Ceil it
   ©            # Store this matrix-size in variable `®` (without popping)
    F           # Pop and loop this many times:
     D          #  Duplicate the current 2D list:
      ®£        #  Only keep the first `®` amount of inner lists:
        €н      #  Get the first item from each
          R     #  Reverse it
           ,    #  Pop and print it with trailing newline
      ¦         #  Remove the first inner list
       ε        #  Map over each remaining lists:
            i   #   If
        ®       #   dimension `®`
           ›    #   is larger than
         N>     #   the 1-based map-index:
             ¦  #    Remove the first item from this list
\$\endgroup\$
4
\$\begingroup\$

PARI/GP, 43 bytes

a->matrix(w=#a\2+1,,i,j,a[w+i-j][min(i,j)])

Attempt This Online!

Takes input from top-right to bottom-left.

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

Jelly, 9 8 bytes

ṙLHĊƊṚŒḌ

Attempt This Online!

How?

ṙLHĊƊṚŒḌ : Main Link
 L       : length; used to count the number of elements
  H      : Halve; divides by 2 
   Ċ     : Rounds up (ceil)
    Ɗ    : Last three links as a monad
ṙ        : Rotate x y times (x is implied input)
     Ṛ   : Reverse element
      ŒḌ : Reconstruct matrix from its diagonals
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'm still new to Jelly, but I'm pretty sure that because you only use the helper link once, ṙLHĊƊṚŒḌ works for 8 bytes. \$\endgroup\$ Sep 21 at 8:14
  • \$\begingroup\$ @tybocopperkettle Thanks for the spot! I forgot about Ɗ lol \$\endgroup\$
    – Baby_Boy
    Sep 21 at 14:53
2
\$\begingroup\$

Charcoal, 18 bytes

I⮌E⊘⊕LθE⊘⊕Lθ⊟§θ⁺ιλ

Try it online! Link is to verbose version of code. Takes input from bottom left to top right. Explanation:

      θ             Input array
     L              Length
    ⊕               Incremented
   ⊘                Halved
  E                 Map over implicit range
           θ        Input array
          L         Length
         ⊕          Incremented
        ⊘           Halved
       E            Map over implicit range
              θ     Input array
             §      Indexed by
                ι   Outer index
               ⁺    Plus
                 λ  Inner index
            ⊟       Pop from list
 ⮌                  Reversed
I                   Cast to string
                    Implicitly print
\$\endgroup\$

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.