Reconstruct Matrix from its diagonals

Question

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 code-golf, 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]]

• math scat: Sandbox
• mousetail: Can you output as a flattened array?
• math scat: @mousetail added that in too
• DLosc: Somewhat related
• Fatalize: Related (inverse problem)

Answer 1

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

• Jonah: "Times out for anything bigger than a 2x2 matrix." lol. take an upvote!

Answer 2

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.

• Mukundan314: -2 byrtes since you don't need to convert to a list (codegolf.meta.stackexchange.com/a/10753/91267)

Answer 3

J, ²¹ 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.

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

MathGolf, 21 bytes

h1⁄2)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)
 1⁄2 # 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)

Answer 9

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

• Kevin Cruijssen: z+b-a-1 can be z+b+~a for -1 byte.
• Mukundan314: 79 bytes output is no longer flattened
• 97.100.97.109: 78 bytes while keeping flattened list.

Answer 10

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

• tybocopperkettle: 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.
• Baby_Boy: @tybocopperkettle Thanks for the spot! I forgot about Ɗ lol

Answer 11

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

Answer 12

PARI/GP, 43 bytes

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

Attempt This Online!

Takes input from top-right to bottom-left.

Answer 13

Haskell + hgl, 25 bytes

lH(F~<zdm<<lpW[]<lg)<mm p

Attempt This Online!

Explanation

To build the matrix we use a fold, each step adding a new diagonal. So the bulk of this answer is the function that takes a partial matrix and adds a new diagonal.

The way this process works is that we want to zip the new diagonal with the matrix. If the diagonal is longer than the matrix so far (length of the matrix is the number of rows), then we want to start the zip with the two aligned at the front.

1 #### 1####
2 ### 2###
3 ## --> 3##
4 # 4#
5 5

If the diagonal is shorter we want to align it at the bottom:

 ##### #####
 ##### #####
1 #### --> 1####
2 ### 2###
3 ## 3##

To do this we pad the diagonal out to the length of the list with empty values. (lpW[]<lg) If it's longer this does nothing, but if it's shorter it aligns the two at the bottom.

Then we zip the two with zdm. This is the "monoidal" zip, so it pads the shorter value to the length of the longer and combines with the monoid operation.

The one hitch is that for this all to work we need to convert the integers in the diagonals to lists, that way we can have empty values in the padding.

Reflection

This is a very elegant solution, but it does suggest improvements.

• It hurts me to use lg. Because there's nothing to bind the type l won't work. lpW^.lg should probably be builtin, padding one list to the length of another seems like a useful operation. This would save 3 bytes here.
• fb F seems like a useful combinator. However it would need to be a 1 byte operator to save anything in this particular scenario.

Answer 14

Uiua, 15 bytes

⍜⊕□しろいしかく◌.⊞+⟜⇌⇡⌈÷2⧻.

Try it: Uiua pad

This should be 13 bytes because ⍜⊕□しろいしかく◌. could hypothetically be replaced by ⌝⊕□しろいしかく, but it hasn't been implemented yet.

Explanation:

⌈÷2⧻ - Get the side length by dividing the length by 2 and rounding up.

⊞+⟜⇌⇡ - Take the range to this number and it reversed, and create the addition table of those two lists.

For example if the side length was 5 the addition table would be:

 4 3 2 1 0
 ╭─ 
0 ╷ 4 3 2 1 0 
1 5 4 3 2 1 
2 6 5 4 3 2 
3 7 6 5 4 3 
4 8 7 6 5 4 
 ╯

As you can see, there is a number assigned to each diagonal, starting with zero at the top left.

⍜⊕□しろいしかく◌. (what should be ⌝⊕□しろいしかく) - Use this matrix to anti-group the input.

Answer 15

Curry (PAKCS), 73 bytes

foldl(!)[]
[]#[]=[]
(a:b)#(c:d)=(c:a):b#d
a!b=(a++[[]])#b
(a++b)!c=a++b#c

Try it online!

A port of @Wheat Wizard's Haskell + hgl answer.

• lesobrod: I'd like to learn Curry! Is there some friendly community with code sharing etc?
• alephalpha: @lesobrod I don't know any community. Here is a list of resources: codegolf.meta.stackexchange.com/questions/24640/…

Answer 16

Vyxal, 2 bytes

Þ„

Try it Online!

So apparently lyxal forgot there was a built in for this :p

Answer 17

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

Answer 18

Wolfram Language (Mathematica), 77 bytes

(n=⌊Length@#/2⌋;Total@MapThread[DiagonalMatrix[#1,#2]&,{#,Range[-n,n]}])&

Input from the bottom-left diagonal to the top-right diagonal

Try it online!

• att: 48 different input order
• att: or this works for the same input order