Diamondize a Matrix

Question

Given a matrix, output a representation of the matrix where the top left element is on top, the anti-diagonal is the central row and the bottom right element is at the bottom.

For example, consider the following matrix:

1 2 3
4 5 6
7 8 9

The diamond version of this matrix is:

  1
 4 2
7 5 3
 8 6
  9

Inputs and outputs

An input matrix will be given as a list of lists (or anything similar in your language of choice). The output shall be a list of lists as well.

The matrices will only contain positive integers.

The input matrix will not necessarily be square.

The input matrix will be at least 1×1.

Test Cases

Input:  [[1]]
Output: [[1]]

Input:  [[1,2],[3,4]]
Output: [[1],[3,2],[4]]

Input:  [[1,2,3],[4,5,6]]
Output: [[1],[4,2],[5,3],[6]]

Input:  [[11,2,5],[3,99,3],[4,8,15],[16,23,42]]
Output: [[11],[3,2],[4,99,5],[16,8,3],[23,15],[42]]

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

J, 6 bytes

<@|./.

This is an unnamed a monadic verb which takes a matrix and returns a list of antidiagonals:

   input =. i.3 4
   input
0 1  2  3
4 5  6  7
8 9 10 11

   <@|./. input
┌─┬───┬─────┬─────┬────┬──┐
│0│4 1│8 5 2│9 6 3│10 7│11│
└─┴───┴─────┴─────┴────┴──┘

Test it here.

Explanation

• /. is J's built-in to apply a function to each anti-diagonal. Unfortunately, these anti-diagonals are given in the opposite order of what we want here.
• In <@|., we first apply |. which reverses the anti-diagonal and then < to box it (which is the only way to return a ragged array in J, since normal arrays are always rectangular, so the antidiagonals would be padded with zeroes).

Answer 2

Python, 91 bytes

e=enumerate
lambda M:[[r[n-i]for i,r in e(M)if-1<n-i<len(r)][::-1]for n,_ in e(M[1:]+M[0])]

Test it on Ideone.

---

Python + NumPy, 69 bytes

import numpy
lambda M:map(M[::-1].diagonal,range(1-len(M),len(M[0])))

Expects a 2D NumPy array as input and returns a list of NumPy arrays. Test it on Ideone.

Answer 3

Jelly, 7 bytes

ṚŒDṙZL$

Try it online!

Explanation

Ṛ         Reverse the matrix vertically.
 ŒD       Get its diagonals. However these start from 
          the main diagonal, not the corners.
    ZL$   Get the width of the input matrix.
   ṙ      Rotate the list of diagonals left by that many 
          places to obtain the correct order.

Answer 4

Mathematica, 58 56 bytes

a=Length;Reverse@#~Diagonal~b~Table~{b,1-a@#,a@#&@@#-1}&

Anonymous function, takes nested arrays.

Answer 5

Python 2, 88 87 bytes

lambda L:[filter(None,x)[::-1]for x in map(None,[],*[i*[0]+r for i,r in enumerate(L)])]

Prepend 0s, zip, then remove falsy elements. Returns a list of tuples. This uses map(None,...) to perform zip_longest (padding missing spots with None) and filter(None,...) to remove falsy elements.

Annoyingly, we need to add an extra [] row to the map to guarantee that a list of tuples is returned, since map(None,*[[1]]) returns [1] rather than [(1,)] for a 1x1 matrix. The extra row gets stripped out by the filter though.

(Thanks to @Dennis for -1 byte)

Answer 6

CJam, 17 bytes

{eeSf.*::+W%zSf-}

An unnamed block (function) which expects the matrix on the stack and replaces it with its antidiagonals.

Test it here.

This (found by Sp3000) works for the same byte count:

{_,,Sf*\.+W%zSf-}

Explanation

This is best explained with an example. Consider the input:

[[0  1  2  3]
 [4  5  6  7]
 [8  9 10 11]]

ee    e# Enumerate matrix, turning each row [x ... z] into [i [x ... z]] where
      e# i is the vertical index from the top.

[[0 [0  1  2  3]]
 [1 [4  5  6  7]]
 [2 [8  9 10 11]]]

Sf.*  e# Replace each i with a string of i spaces.

[[""   [0  1  2  3]]
 [" "  [4  5  6  7]]
 ["  " [8  9 10 11]]]

::+   e# Prepend these strings to the rows.

[[0  1  2  3]
 ['  4  5  6  7]
 ['  '  8  9 10 11]]   e# Note that each '  corresponds to a space character.

W%    e# Reverse the rows.

[['  '  8  9 10 11]
 ['  4  5  6  7]
 [0  1  2  3]]

z     e# Zip/transpose.

[[ '  '  0]
 [ '  4  1]
 [ 8  5  2]
 [ 9  6  3]
 [10  7]
 [11]]

Sf-   e# Remove spaces from each row.

[[ 0]
 [ 4  1]
 [ 8  5  2]
 [ 9  6  3]
 [10  7]
 [11]]

Answer 7

Ruby, 68 66 bytes

Anonymous function.

->l{i=-1;k=[];l.map{|r|i-=j=-1;r.map{|e|k[i+j+=1]=[e,*k[i+j]]}};k}

• Because of how the splat operator works, I was able to save 2 bytes by forgoing the array addition.

Answer 8

Husk, 3 2 bytes

∂T

-1 byte thanks to @mypronounismonicareinstate.

Try it online.

Explanation:

 T  # Transpose the (implicit) matrix-argument; swapping rows/columns
∂   # Take the anti-diagonals of this transposed matrix
    # (after which the result is output implicitly)

Answer 9

JavaScript (Firefox), 86 75 bytes

a=>a.concat(a[0]).slice(1).map((_,i)=>[for(v of a)if(n=v[i--])n].reverse())

Saved 11 bytes thanks to @Neil!

Works in Firefox 30+. Takes an array of arrays.

Answer 10

Prolog (SWI), 111 bytes

A*B*C:-append(A,B,C).
s(A,B,C):-A*[B]*C.
N+B:-N=[A|X],X+R,Z*Q*R,maplist(s,[[]|Z],A,Y),Y*Q*B,!;maplist(=([]),B).

Try it online!

Explanation

Let's first look a version of the code that not nearly so condensed.

snoc(Init,Last,List) :-
  append(Init,[Last],List).

diamondize([],Soln) :-
  maplist(=([]),Soln).
diamondize([FirstRow|Rest],Soln):-
  diamondize(Rest,RestSoln),
  append(BeginRestSoln,EndSoln,RestSoln),
  maplist(snoc,[[]|BeginRestSoln],FirstRow,BeginSoln),
  append(BeginSoln,EndSoln,Soln),
  !.

The diamondize/2 predicate (+/2 in the golfed version) is responsible for calculating what the diamond version of the input matrix is. The predicate works recursively as follows: first it calculates the diamond version of the input matrix with its first row removed (diamondize(Rest,RestSoln)); then to calculate the diamond version of the entire input matrix it uses the fact that adding an initial row changes the diamond version by prepending a singleton list of the first element of the initial row and then pairing up each remaining element in the initial row with the first however many lists in the diamond and adding each initial row element to the end of its paired list, leaving the remaining lists in the diagonal unchanged. To do this in Prolog I use append to split RestSoln into a beginning, BeginRestSoln, and an end, EndSoln. Then I use the the builtin maplist/4 to assert a relation between BeginRestSoln, the new initial row, FirstRow, and a new list BeginSoln. The maplist/4 predicate asserts that all triples of elements of equal indices from the lists in its second, third, and fourth arguments will satisfy the predicate given as its first argument when it is called on them (note that this requires all the lists given as arguments to be of equal length). The predicate I use is snoc/3 which asserts that when its second argument is added to the end of the list in its first argument, you get its third argument. Furthermore I add an empty list to the start of BeginRestSoln which means that when I snoc that with the first element of FirstRow the resulting first element ofBeginSoln will be a singleton list of that aforementioned first element. The rest of BeginSoln will be the lists that began the diagonal version of the remainder of the matrix with the remaining elements of the first row added to the end, just as desired in the process described above. Finally to get the solution for the entire matrix we append BeginSoln with the unchanged EndSoln.

We have now covered the behavior of diamondize/2 when the matrix is not empty, but the base case is the empty matrix. In that case the "solution" is considered to be a list of some undetermined length with [] for all its elements. This list is constructed using the maplist/2 predicate which asserts that each element of the list given in its second argument satisfies the predicate given in its first argument. The predicate we use is =([])/1 which is the partially applied =/2 predicate which asserts that its two arguments unify, so our partially applied version asserts that its singular argument unifies with (ie is equal to) the empty list. However, since we do not specify a length, Prolog will attempt to satisfy the future goals with the shortest list containing only empty lists, backtracking and trying a longer such list if the future goals can't be satisfied. This behavior is very useful since in our first inductive case the predicates won't be satisfied unless the previous solution is at least one less than the length of the rows of the matrix, but we run into an issue in that longer lists of empty lists would also result in solutions that the program would consider valid, but would be invalid for this challenge. To avoid producing these solutions, we add a cut (!) to the end of the recursive case of diamondize/2, which will tell Prolog not to backtrack once we have a working solution.

Finally to golf the whole thing I used a number of tactics. First off, of course we can eliminate excess whitespace, and give variables and predicates shorter names. Then since append/3 is being used a lot I can save a couple bytes by creating a copy of it with a shorter name, using an operator to name both it and what was the diamondize/2 predicate (unfortunately since operator predicates technically can have at most two arguments, I cannot give s/3 an operator name since I need to pass it to maplist/4). Finally I can consolidate the two cases of +/2 into a single case with a disjunction.

Answer 11

BQN, 11 bytes

⌽¨+´¨∘↕∘≢⊸⊔

Anonymous tacit function. Takes a 2D array and returns a list of lists. Try it at BQN online!

Explanation

⌽¨+´¨∘↕∘≢⊸⊔
        ≢     Get the shape of the array (a list of two integers)
      ↕∘      Range (a 2D array of coordinate pairs)
  +´¨∘        Sum each of those pairs
              We now have an array in which the top left element is 0, the two elements
              in the next antidiagonal are 1, and so forth
         ⊸    With that as left argument and the original array as right argument,
          ⊔   Group the values of the right argument into buckets based on the
              corresponding number in the left argument
⌽¨            Reverse each antidiagonal

Answer 12

Mathematica, 60 bytes

#&@@@#&/@GatherBy[Join@@MapIndexed[List,#,{2}],Tr@*Last]&

where  is a Unicode character which Mathematica reads as the postfix \[Transpose] operator.

This is a bit longer than the other Mathematica solution but I figured I'd post it because it doesn't use the Diagonals built-in and uses a completely different approach.

Explanation

MapIndexed[List,#,{2}]

This first transposes the matrix (such that the antidiagonals appear in the correct order if the matrix was flattened). Then we map List over the cells of the matrix together with the index, which turns each matrix element i into {i, {x, y}} where x and y are the coordinates of the element in the matrix.

Join@@...

This flattens the outermost dimension, so that we now have a flat list of the matrix elements (with their coordinates) in column-major order.

GatherBy[..., Tr@*Last]

This groups those elements by the sum of their coordinates. Note that antidiagonals are lines of constant x+y, so this does exactly the grouping we want. The order within each group is preserved. Now we just need to get rid of the coordinates again. This is done via the rather cryptic:

#&@@@#&/@...

This maps the function #&@@@#& over each group, which itself applies #& to each element in the group, and # is simply the first argument, i.e. the original matrix element.

Answer 13

Octave, 77 bytes

With a little abuse of the accumarray function:

@(M)char(accumarray(((1:size(M,1))+(0:size(M,2)-1)')(:),M(:),[],@(x){num2str(x')}))

This defines an anonymous function. To use it, assign to a varible or use ans.

Input is the matrix with : as row separator. Output is a cell array containing an array for each row (Octave's equivalent to jagged arrays). This is displayed by Octave showing the indices of the cell array and the contents of each cell. Try it here.

To display the result separated by spaces and newlines only: 83 bytes

@(M)char(accumarray(((1:size(M,1))+(0:size(M,2)-1)')(:),M(:),[],@(x){num2str(x')}))

You can also try it here.

Answer 14

Octave, 63 62 bytes

Removed one byte thanks to @DonMue... @LuisMendo!

@(a)cellfun(@(x)x(x>0)',num2cell(spdiags(flipud(a)),1),'un',0)

I went the boring route and munged the antidiagonals.

Sample run on ideone.

Answer 15

Haskell, 83 82 bytes

r=zip[0..]
\o->fst$span(any(>0))[reverse[e|(x,t)<-r o,(v,e)<-r t,x+v==a]|a<-[0..]]

nimi saved a byte. Thanks!

Answer 16

[C#], 100 bytes

for(r=0;r<l;r++)for(c=0;c<i[r].Length;c++)o[c+r]=o[c+r]?.Prepend(i[r][c]).ToArray()??new[]{i[r][c]};

Try It online!

Maybe there's a shorter way of inserting elements. Prepend and ToArray seems verbose, but that's the best I found.

Answer 17

Haskell, 56 bytes

a!b=zipWith(++)([]:b)$a++repeat[]
foldr1(!).map(pure<$>)

Try it online!

Answer 18

Pip, 19 bytes

_RMxMZD:xRL_AL BMEa

Try It Online!

I'm a bit rusty. There might be a shorter way to do this with loops but oh well.

                ME  # Map [index item] for each item of...
                  a # Input
        --------ME  # Block
         RL         # Repeat...
        x           # The empty string
           _        # By the index
            AL      # Concatenate to...
               B    # The item
     ZD:            # Transpose, filling with ""
----M               # Map over each...
_RM                 # Remove
   x                # The empty string

Answer 19

R, 102 94 bytes

\(L,N=length(L),`>`=rep)apply(t(mapply(\(j,n)c(0>n-1,j,0>N-n),L,1:N)),2,\(a)list(rev(a[0<a])))

Attempt This Online!

Outputs a list of lists, accordingly to the challenge requirements.

A large amount takes it t is used here to produce a matrix - for the case with one single element. Otherwise the logic is simple: prepend zeroes, turn list to a matrix, remove zeroes and output a list of rows.

Answer 20

Python, 128 bytes (numpy)

(lambda A: (lambda A,S:[[A[U][I-U] for U in range(min(S[1]-1,I),max(I-S[0]+1,0)-1,-1)] for I in range(S[1]+S[0]-1)])(A,A.shape))

Answer 21

Pyth, 41 17 bytes

tm_<dx+dYk.T+LaYk

Try it online!

Inspired by @Doorknob's solution to another problem.

How it works:

tm_<dx+dYk.T+LaYk
            +L      prepend to each subarray...
              aYk   (Y += ''). Y is initialized to [],
                    so this prepends [''] to the first
                    subarray, ['', ''] to the second, etc.
                    ['' 1  2  3
                     '' '' 4  5  6
                     '' '' '' 7  8  9
                     '' '' '' '' 10 11 12
                     '' '' '' '' '' 13 14 15]
          .T        transpose, giving us
                    ['' '' '' '' ''
                     1  '' '' '' ''
                     2  4  '' '' ''
                     3  5  7  '' ''
                     6  8  10 ''
                     9  11 13
                     12 14
                     15]
 m_<dx+dYk          removes all empty strings in the
                    subarrays while reversing each one
t                   remove the first subarray

---

Previous attempt:

JlQKlhQm_m@@Qk-dk}h.MZ,0-dtKh.mb,tJdUt+JK

Try it online!

How it works:

JlQKlhQm_m@@Qk-dk}h.MZ,0-dtKh.mb,tJdUt+JK    input array stored as Q
JlQ                                          J = len(Q)
   KlhQ                                      K = len(Q[0])
       m                            Ut+JK    list for d from 0 to J+K-1:
        _m       }AAAAAAAAAABBBBBBBB             reversed list for k from A to B, where:
                  h.MZ,0-dtK                       A = max(0, d-(K-1))
                       0-dtK                               0  d-(K-1)
                            h.mb,tJd               B = min(J-1, d)
                                 tJd                       J-1  d
          @@Qk-dk                                    Q[k][d-k]

Answer 22

Groovy, 77 73 75

{i->o=[].withDefault{[]};a=0;i.each{b=0;it.each{o[a+b++].add(0,it)};a++};o}

Takes array of arrays as input and returns array of arrays.

Try it

EDIT: I forgot to output the anwser, after adding it score goes up to 75.

Answer 23

APL (Dyalog Unicode), 78 bytes

{{⍵/⍨×≢¨⍵}{⍵/⍨×⍵}¨↓⍉(-⍳≢⍵)⌽⍵↑⍨1 2×≢⍵}

Try it online!

Answer 24

Perl 5, 67 bytes

sub{map{[grep$_,map{shift@{$_[-$_]}}-$_..0]}0..$#_,($#_)x$#{$_[0]}}

Try it online!

Answer 25

05AB1E (legacy), 17 16 bytes

εD0*«NFÁ]øí0δKʒOĀ

Unfortunately 05AB1E only has a builtin for the main (anti)diagonal, and not one for all (anti)diagonals, so we'll have to do things manually..

-1 byte by switching to the legacy version of 05AB1E, so the 0δK can be 0K.

Try it online or verify all test cases.

Explanation:

ε        # Map each row in the (implicit) input-matrix to:
 D       #  Duplicate the current row
  0*     #  Multiply each by 0, so we have a list of 0s the same length of the row
    «    #  Append the lists together
         #   i.e. [[1,2,3],[4,5,6],[7,8,9]] → [[1,2,3,0,0,0],[4,5,6,0,0,0],[7,8,9,0,0,0]]
     NF  #  Loop the (0-based) map-index amount of times:
       Á #   And rotate the row with appended 0s once towards the right each iteration
         #    → [[1,2,3,0,0,0],[0,4,5,6,0,0],[0,0,7,8,9,0]]
]ø       # After the map and inner loop: zip/transpose; swapping rows/columns
         #  → [[1,0,0],[2,4,0],[3,5,7],[0,6,8],[0,0,9],[0,0,0]]
  í      # And reverse each inner row
         #  → [[0,0,1],[0,4,2],[7,5,3],[8,6,0],[9,0,0],[0,0,0]]
0K       # Remove all 0s from each inner row
         #  → [[1],[4,2],[7,5,3],[8,6],[9],[]]
  ʒOĀ    # And filter out any empty rows
         #  → [[1],[4,2],[7,5,3],[8,6],[9]]
         # (after which the result is output implicitly)

Answer 26

Japt, 11 bytes

Takes input as an array of space delimited strings, outputs a 2D array of integer strings.

ËiEç)¸ÃÕËÔf

Try it (header converts 2D arrays to the required input format) or run all test cases

ËiEç)¸ÃÕËÔf     :Implicit input of array
Ë               :Map each element at 0-based index E
 i              :  Prepend
  Eç            :    E spaces
    )           :  End prepend
     ¸          :  Split on spaces
      Ã         :End map
       Õ        :Transpose
        Ë       :Map
         Ô      :  Reverse
          f     :  Filter

Answer 27

Vyxal, 22 bits^v2, 2.75 bytes

Þ`R

Try it Online!

Bitstring:

0010101000111101000010