18
\$\begingroup\$

As part of its compression algorithm, the JPEG standard unrolls a matrix into a vector along antidiagonals of alternating direction:

enter image description here

Your task is to take the unrolled vector along with the matrix dimensions and reconstruct the corresponding matrix. As an example:

[1, 2, 5, 9, 6, 3, 4, 7, 1, 2, 8, 3], 4, 3

should yield

[1 2 3 4
 5 6 7 8
 9 1 2 3]

whereas dimensions 6, 2 would give

[1 2 6 3 1 2
 5 9 4 7 8 3]

Rules

You may choose to take only one of the dimensions as input. The individual inputs can be taken in any order. You may assume that the width and height are positive and valid for the given vector length.

You may assume that the vector elements are positive integers less than 10.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

The input vector may be given in any convenient, unambiguous, flat list or string format.

The output matrix may be in any convenient, unambiguous, nested list or string format, or as a flat list along with both matrix dimensions. (Or, of course, as a matrix type if your language has those.)

Standard rules apply.

Test Cases

Each test case is of the form vector width height => matrix.

[1] 1 1                        => [[1]]
[1 2 3 1] 2 2                  => [[1 2] [3 1]]
[1 2 3 1] 4 1                  => [[1 2 3 1]]
[1 2 5 9 6 3 4 7 1 2 8 3] 3 4  => [[1 2 3] [5 6 4] [9 7 8] [1 2 3]]
[1 2 5 9 6 3 4 7 1 2 8 3] 4 3  => [[1 2 3 4] [5 6 7 8] [9 1 2 3]]
[1 2 5 9 6 3 4 7 1 2 8 3] 6 2  => [[1 2 6 3 1 2] [5 9 4 7 8 3]]
[1 2 5 9 6 3 4 7 1 2 8 3] 12 1 => [[1 2 5 9 6 3 4 7 1 2 8 3]]
[1 2 5 9 6 3 4 7 1 2 8 3] 1 12 => [[1] [2] [5] [9] [6] [3] [4] [7] [1] [2] [8] [3]]

Related Challenges

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

Jelly, 18 13 bytes

pS€żị"¥pỤỤị⁵s

Takes number of rows, number of columns and a flat list as separate command-line arguments.

My code is almost identical to the one in the twin challenge. The only differences are an additional (which inverts the permutation of the indices) and an s (to split the output into a 2D array).

Try it online!

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

MATL, 29 bytes

:!i:+-1y^8MtsQ/*-X:4#S2$S1GZC

Input is height, width, vector separated by newlines.

This reuses part of the code in my answer to the related challenge.

Try it online!

Explanation

:!      % take number of rows, r, as input. Generate column vector [1;2;...;r]
i:      % take number of columns, c, as input. Generate row vector [1,2,...,c] 
+       % add with broadcast. Gives 2D array
-1      % push -1
y^      % duplicate previous 2D array. Compute -1 raised to that
8M      % push [1;2;...;r] again
tsQ/    % divide by its sum plus 1
*       % multiply
-       % subtract
X:      % linearize 2D array into column array
4#S     % sort and push the indices of the sorting. Gives a column vector
2$S     % take vector as input. Sort it according to previous column vector
1G      % push r
ZC      % reshape into columns of r elements
\$\endgroup\$
0
\$\begingroup\$

J, 24 bytes

]$({~[:/:@;[:<@|.`</.i.)

Also uses the oblique adverb /. to perform zigzagify as in the J answer from that challenge.

Usage

Input is with the array on the LHS and the dimensions [height, width] on the RHS.

   f =: ]$({~[:/:@;[:<@|.`</.i.)
   1 f 1 1
1
   1 2 3 1 f 2 2
1 2
3 1
   1 2 5 9 6 3 4 7 1 2 8 3 f 4 3
1 2 3
5 6 4
9 7 8
1 2 3
   1 2 5 9 6 3 4 7 1 2 8 3 f 3 4
1 2 3 4
5 6 7 8
9 1 2 3
   1 2 5 9 6 3 4 7 1 2 8 3 f 2 6
1 2 6 3 1 2
5 9 4 7 8 3
   1 2 5 9 6 3 4 7 1 2 8 3 f 1 12
1 2 5 9 6 3 4 7 1 2 8 3
   1 2 5 9 6 3 4 7 1 2 8 3 f 12 1
1
2
5
9
6
3
4
7
1
2
8
3

Explanation

]$({~[:/:@;[:<@|.`</.i.)  Input: list A (LHS), dimensions D (RHS)
                     i.   Range shaped to D
           [:<@|.`</.     Zigzagify that matrix
     [:   ;               Raze the boxes to get a zigzagify permutation
       /:@                Invert that permutation to get an unzigzagify permutation
   {~                     Apply that permutation to A
]                         Get D
 $                        Shape that permutation to D and return
\$\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.