# Reconstruct Matrix from its diagonals

Given the diagonals of a matrix, reconstruct the original matrix.
The diagonals parallel to the major diagonal (the main diagonals) will be given. Diagonals: [, [4, 10], [3, 9, 15], [2, 8, 14, 20], [1, 7, 13, 19, 25], [6, 12, 18, 24], [11, 17, 23], [16, 22], ]

## 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]: []
[Out]: []

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

[In]: [, [0, 1], [6, 23, 10], [420, 9], ]
[Out]: [[6, 0, 25], [420, 23, 1], [67, 9, 10]]

• Sandbox Sep 20 at 14:15
• Can you output as a flattened array? Sep 20 at 14:46
• @mousetail added that in too Sep 20 at 14:50
• Somewhat related Sep 21 at 4:33
• Related (inverse problem) Sep 21 at 11:15

# 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

• In the sandbox mathcat said you could take a flattened array as input Sep 20 at 14:43
• @Seggan that doesn't help much, as the shape of the diagonals is important in the filter Sep 20 at 14:46
• ah. never mind then Sep 20 at 14:46
• "Times out for anything bigger than a 2x2 matrix." lol. take an upvote! Sep 20 at 16:40

# 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.

# 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.

# 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


# 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)$$

# 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


# 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

# 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)


# 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

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

# 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.

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.

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


# 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.

# 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

• 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. Sep 21 at 8:14
• @tybocopperkettle Thanks for the spot! I forgot about Ɗ lol Sep 21 at 14:53

# Charcoal, 18 bytes

Ｉ⮌Ｅ⊘⊕ＬθＥ⊘⊕Ｌθ⊟§θ⁺ιλ


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

      θ             Input array
Ｌ              Length
⊕               Incremented
⊘                Halved
Ｅ                 Map over implicit range
θ        Input array
Ｌ         Length
⊕          Incremented
⊘           Halved
Ｅ            Map over implicit range
θ     Input array
§      Indexed by
ι   Outer index
⁺    Plus
λ  Inner index
⊟       Pop from list
⮌                  Reversed
Ｉ                   Cast to string
Implicitly print