13
\$\begingroup\$

Given a matrix, sum its values up/down or left/right to form an X, fold it up, and return the list. I describe the algorithm here:

Algorithm

Your input will be a odd-sized square matrix of integers within your language's reasonable numerical capacity.

Let's take the following matrix as an example:

1 2 3 2 1
0 3 2 3 0
4 2 5 6 3
7 4 7 9 4
0 6 7 2 5

First, add every number to the closest number that is on the main diagonal or antidiagonal. That is, divide the matrix into four sections along the main diagonal and antidiagonal, and then sum all of the numbers in each section towards the center, like so:

1   2   3   2   1
    ↓   ↓   ↓    
0 → 3   2   3 ← 0
        ↓        
4 → 2 → 5 ← 6 ← 3
        ↑        
7 → 4   7   9 ← 4
    ↑   ↑   ↑    
0   6   7   2   5

This step gives the following result:

1        1
  5    5
    39
  17  15
0        5

Then, we fold it by flattening the X and interweaving the elements with the top-left first and the bottom left last. This gives the following result:

1, 0, 5, 17, 39, 5, 15, 1, 5

You can imagine this as stretching the main diagonal and rotating it counterclockwise.

This is the final result.

Challenge

Implement this algorithm. Standard loopholes apply. All reasonable I/O formats acceptable.

Test Cases

Input
Output

1 2 3 2 1
0 3 2 3 0
4 2 5 6 3
7 4 7 9 4
0 6 7 2 5

1, 0, 5, 17, 39, 5, 15, 1, 5

1 2 3 4 5
5 4 3 2 1
1 3 5 7 9
0 9 8 7 6
6 7 8 9 0

1, 6, 11, 16, 47, 7, 22, 5, 0

1 3 7 4 8 5 3
8 4 7 5 3 8 0
0 6 3 6 9 8 4
2 6 5 8 7 4 2
0 6 4 3 2 7 5
0 6 7 8 5 7 4
8 5 3 2 6 7 9

1, 8, 15, 11, 23, 20, 62, 32, 25, 13, 18, 3, 9
\$\endgroup\$
7
\$\begingroup\$

JavaScript, 113 bytes

s=>(l=s.length-1,a=[],s.map((v,y)=>v.map((n,x)=>a[q=2*[x,y,l-y].sort((u,v)=>u-v)[1]+(y>l/2),q-=q>l]=~~a[q]+n)),a)

f=

s=>(l=s.length-1,a=[],s.map((v,y)=>v.map((n,x)=>a[q=2*[x,y,l-y].sort((u,v)=>u-v)[1]+(y>l/2),q-=q>l]=~~a[q]+n)),a)
<p><textarea id="i" style="width: 400px; height: 120px">1 2 3 2 1
0 3 2 3 0
4 2 5 6 3
7 4 7 9 4
0 6 7 2 5</textarea></p>
<p><button onclick="o.value=f(i.value.trim().split`\n`.map(l=>l.trim().split(/\s+/).map(v => parseInt(v,10)))).join` `">Run</button></p>
<p><output id="o"></output></p>

\$\endgroup\$
  • \$\begingroup\$ Umm.. why the ~~? They neutralize each other, so there is no need for them. \$\endgroup\$ – Kevin Cruijssen Oct 11 '17 at 9:48
  • 2
    \$\begingroup\$ @KevinCruijssen ~~undefined==0, so this is golfier than (a[q]||0). \$\endgroup\$ – Neil Oct 11 '17 at 10:02
  • \$\begingroup\$ @Neil Ah, hadn't thought about undefined. When I copied the test case tsh used, I noticed it worked without the ~~. And since ~~x is similar -(-x) neutralizing each other, I figured it was somehow put there by accident. Thanks for the correction. \$\endgroup\$ – Kevin Cruijssen Oct 11 '17 at 10:45
5
\$\begingroup\$

Jelly, 25 23 21 bytes

AṂ×ṠṚ
LHŒRṗ2Ç€ḅLĠịFS€

Try it online!

Alternate version, 19 bytes

AṂ×ṠṚ
LHŒRṗ2Ç€ĠịFS€

This didn't use to work because Ġ behaved improperly for nested arrays. The only difference is that the pairs [q, p] mentioned in How it works are sorted lexicographically instead of mapping them to p + nq before sorting.

Try it online!

Background

We start by replacing its elements with coordinates, increasing leftwards and downwards and placing (0, 0) in the center of the matrix.

For a 7x7 matrix M, we get the following coordinates.

(-3,-3) (-3,-2) (-3,-1) (-3, 0) (-3, 1) (-3, 2) (-3, 3)
(-2,-3) (-2,-2) (-2,-1) (-2, 0) (-2, 1) (-2, 2) (-2, 3)
(-1,-3) (-1,-2) (-1,-1) (-1, 0) (-1, 1) (-1, 2) (-1, 3)
( 0,-3) ( 0,-2) ( 0,-1) ( 0, 0) ( 0, 1) ( 0, 2) ( 0, 3)
( 1,-3) ( 1,-2) ( 1,-1) ( 1, 0) ( 1, 1) ( 1, 2) ( 1, 3)
( 2,-3) ( 2,-2) ( 2,-1) ( 2, 0) ( 2, 1) ( 2, 2) ( 2, 3)
( 3,-3) ( 3,-2) ( 3,-1) ( 3, 0) ( 3, 1) ( 3, 2) ( 3, 3)

We now compute the minimum absolute value of each coordinate pair and multiply the signs of both coordinate by it, mapping (i, j) to (sign(i)m, sign(j)m), where m = min(|i|, |j|).

(-3,-3) (-2,-2) (-1,-1) ( 0, 0) (-1, 1) (-2, 2) (-3, 3)
(-2,-2) (-2,-2) (-1,-1) ( 0, 0) (-1, 1) (-2, 2) (-2, 2)
(-1,-1) (-1,-1) (-1,-1) ( 0, 0) (-1, 1) (-1, 1) (-1, 1)
( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0) ( 0, 0)
( 1,-1) ( 1,-1) ( 1,-1) ( 0, 0) ( 1, 1) ( 1, 1) ( 1, 1)
( 2,-2) ( 2,-2) ( 1,-1) ( 0, 0) ( 1, 1) ( 2, 2) ( 2, 2)
( 3,-3) ( 2,-2) ( 1,-1) ( 0, 0) ( 1, 1) ( 2, 2) ( 3, 3)

Matrix elements that correspond to the same pair have to be summed. To determine the order of the sums, we map each pair (p, q) to p + nq, where n is the number of rows/columns of M.

-24 -16  -8   0   6  12  18
-16 -16  -8   0   6  12  12
 -8  -8  -8   0   6   6   6
  0   0   0   0   0   0   0
 -6  -6  -6   0   8   8   8
-12 -12  -6   0   8  16  16
-18 -12  -6   0   8  16  24

The order of sums corresponds to the order of integers the correspond to its summands.

How it works

LHŒRṗ2Ç€ḅLĠịFS€  Main link. Argument: M (matrix)

L                Compute n, the length (number of rows) of M.
 H               Halve it.
  ŒR             Symmetric range; map t to [-int(t), ..., 0, int(t)].
    ṗ2           Compute the second Cartesian power, yielding all pairs [i, j]
                 with -t ≤ i, j ≤ t.
      ǀ         Map the helper link over the resulting array of pairs.
         L       Yield n.
        ḅ        Unbase; map each pair [q, p] to (p + nq).
          Ġ      Group the indices of the resulting array of n² integers by their
                 corresponding values, ordering the groups by the values.
            F    Flatten M.
           ị     Index into the serialized matrix.
             S€  Compute the sum of each group.


AṂ×ṠṚ            Helper link. Argument: [i, j] (index pair)

A                Absolute value; yield [|i|, |j|].
 Ṃ               Minimum; yield m := min(|i|, |j|).
   Ṡ             Sign; yield [sign(i), sign(j)].
  ×              Multiply; yield [p, q] := [sign(i)m, sign(j)m].
    Ṛ            Reverse; yield [q, p].
\$\endgroup\$
  • 5
    \$\begingroup\$ this is brilliant. \$\endgroup\$ – Uriel Oct 15 '17 at 19:48
5
\$\begingroup\$

Python, 159 158 bytes

def f(m):l=len(m)-1;r=range(1,l);return m[0][::l]+f([[sum(m[x][1%y*y:(y>l-2)-~y])+m[0][y]*(x<2)+m[l][y]*(x>l-2)for y in r]for x in r])+m[l][::l]if l else m[0]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ y+1+(y>l-2) can be (y>l-2)-~y. \$\endgroup\$ – Jonathan Frech Oct 15 '17 at 17:54
3
\$\begingroup\$

Dyalog APL, 101 99 64 62 59 bytes

3 bytes saved by @Adám

{+/∘,¨⍵∘רd∘=¨k[⍋k←↑∪/,d←∘.((+/1x×××⌊/∘|),)⍨(⍳x)-⌈.5×x←≢⍵]}

Try it online!

Using Dennis' awesome algorithm.

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog), 60 bytes*

In collaboration with my colleague Marshall.

Anonymous prefix lambda. Takes matrix as argument and returns vector. Assumes ⎕IO (Index Origin) to be zero, which is default on many systems.

{(,⍉{+/,(s×-×⍺)↓⍵×i∊¨⍨s←⌊⊃r÷2}⌺r⊢⍵)/⍨,(⊢∨⌽)=/¨i←⍳r←⍴⍵}

Try it online!

{} anonymous lambda; is right argument (as rightmost letter of the Greek alphabet):

⍴⍵ shape of the argument (list of two identical elements)

r← store as r (as in rho)

 all ɩndices of an array of that size, i.e. (0 0),(0 1)

i← store in i (as in iota)

=/¨ Boolean where the coordinates are equal (i.e. the diagonal)

() apply this anonymous tacit prefix function:

   reverse the argument

  ⊢∨ OR that with the unmodified argument

, ravel (straighten into simple list)

 We now have a Boolean mask for the diagonals.

()/⍨ use that to filter the following:

  ⊢⍵ yield (to separate from r) the argument

  {}⌺r call the following anonymous infix lambda on each element, with the r-neighbourhood (padded with zeros as needed) as right argument (), and a two element list of number padded rows,columns (negative for bottom/right, zero for none) as left argument ():

   r÷2 divide r with two

    pick the first element (they are identical)

    floor it

   s← store as s (for shape)

   i∊⍨¨ for each element of i, Boolean if s is a member thereof

   ⍵× multiply the neighbourhood therewith

   ()↓ drop the following number of rows and columns (negative for bottom/right):

    ×⍺ signum of the left argument (i.e. the direction of paddings)

    - negate

     multiply s therewith

   , ravel (straighten into list)

   +/ sum (plus reduction)

Now we have full matrix of sums, but we need to filter all the values read columnwise.

   transpose

  , ravel (straighten into simple list)


* By counting as ⎕U233A . Try it online!

\$\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.