Square chunk my matrix

Question

Your challenge is to write a function/program that takes a matrix of integers m and a number n as input and:

Splits m into n by n chunks
Replaces each chunk with the most common value in that chunk (In case of a tie, any of the tied values is fine).
Outputs the resulting matrix.

Note: You can take either the size of a single chunk, or the number of chunks to a side.

Example:

Divide into chunks:

0 1|0 1
0 0|1 1
---+---
0 0|0 0
0 0|1 1

Take the most common value in each sub-matrix

0|1
-+-
0|0

So

0 1
0 0

is the result!

Note: You can assume that there will always be an integer amount of chunks with integer size.

Input will always be square.

Testcases

These are formatted as taking the size of a single chunk.

0 1 2 1 2 1
2 2 1 0 2 2
2 1 2 0 1 0
0 0 1 0 3 2
3 0 2 0 3 1
1 0 3 2 0 1, 
3 =>
2 1
0 0
(The 1 is a tie, any of 012 are fine)

0 1 2 1 2 1
2 2 1 0 2 2
2 1 2 0 1 0
0 0 1 0 3 2
3 0 2 0 3 1
1 0 3 2 0 1, 
2 =>
2 1 2
0 0 3
0 2 1
(The 3 is a tie, any of 0123 are fine)

1,
1 => 
1
(kinda obvious edgecase)

Scoring

This is code-golf, shortest wins!

"You can take either the size of a single chunk, or the number of chunks to a side." but can we take both? — Adám
– Adám, Commented Jun 16, 2021 at 11:46

Adám · Accepted Answer · 2021-06-17 10:04:25Z

APL (Dyalog Unicode), 40 38 bytes (SBCS)

Anonymous tacit infix function taking chunk size as left argument and the input matrix as right argument.

{(∪⊃⍨∘⊃∘⍒⊢∘≢⌸)∘,¨↑(⊂⊂¨⊂[1]∘⍵)(≢⍵)⍴⍺↑1}

Try it online!

{…} dfn; ⍺ is chunk size and ⍵ is matrix:
2 and
⎡0,1,0,1⎤
⎢0,0,1,1⎥
⎢0,0,0,0⎥
⎣0,0,1,1⎦

⍺↑1 take "chunk size" elements from 1, padding with zeros
[1,0]

(≢⍵)⍴ cyclically reshape that to the number of rows in the matrix
[1,0,1,0]

(…) apply the following tacit prefix function:

⊂[1]∘⍵ use the argument to partition the matrix vertically
⎡0,1,0,1⎤ ⎡0,0,0,0⎤
[⎣0,0,1,1⎦,⎣0,0,1,1⎦]

⊂⊂¨ use the entire argument to partition each of those horizontally
⎡0,1⎤ ⎡0,1⎤ ⎡0,0⎤ ⎡0,0⎤
[[⎣0,0⎦,⎣1,1⎦],[⎣0,0⎦,⎣1,1⎦]]

↑ mix into a matrix
⎡ ⎡0,1⎤ ⎡0,1⎤ ⎤
⎢ ⎣0,0⎦,⎣1,1⎦ ⎥
⎢ ⎡0,0⎤ ⎡0,0⎤ ⎥
⎣ ⎣0,0⎦,⎣1,1⎦ ⎦

(…)∘,¨ for each element, ravel (flatten) it and then apply the following tacit prefix function:
⎡ [0,1,0,0],[0,1,1,1] ⎤
⎣ [0,0,0,0],[0,0,1,1] ⎦

⊢∘≢⌸ for each unique element, count the indices it occurs at
⎡ [3,1],[1,3] ⎤
⎣ [4] ,[2,2] ⎦

∪… with the unique elements…
⎡ [0,1],[0,1] ⎤
⎣ [0] ,[0,1] ⎦

∘⊃∘⍒ get the index of the largest count (lit. first element of the permutation vector that would sort the counts descending), then…
⎡1,2⎤
⎣1,1⎦

⊃⍨ use that to pick from the list of unique elements
⎡0,1⎤
⎣0,0⎦

xash · Accepted Answer · 2021-06-16 12:08:32Z

4

J, 23 bytes

(0{~.\:1#.=)@,;.3~2 2&$

Try it online!

J's u;.3 is pretty handy for this. It splits a matrix into rectangles. You just need to give the size of the rectangles and the offset between rectangles. So for 3x3-tiles the input would be [[3 3],[3 3]]. That is handled by 2 2&$ (if we can take width and height of a tile as input, that would be ;.~ for -2 bytes). For each tile ;.3~ we flatten the tile , and sort \: the unique values ~. by their occurences 1#.= and take the first one 0{.

edited Jun 16, 2021 at 12:08

answered Jun 16, 2021 at 11:56

xash

11.3k1 gold badge15 silver badges39 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2021-06-16 14:23:21Z

Japt `-h`, 17 bytes

2Æ=yòV)ËËc ü ñÊÌÌ

Try it

2Æ=yòV)ËËc ü ñÊÌÌ     :Implicit input of 2D-array U and integer V
2Æ                    :Map the range [0,2)
  =                   :Reassign to U
   y                  :  Transpose
    òV                :  Partition rows to length V
      )               :End reassignment
       Ë              :Map
        Ë             :  Map
         c            :    Flatten
           ü          :    Group & sort by value
             ñ        :    Sort by
              Ê       :      Length
               Ì      :    Last element
                Ì     :    Last element
                      :Implicit output of last element in the range

Luis Mendo · Accepted Answer · 2021-06-16 12:27:50Z

MATL, 11 bytes

thZCtvXM[]e

Try it online! Or verify all test cases.

How it works

th     % Implicit input: number n. Horizontally concatenate with itself to give [n n]
ZC     % Implicit input: matrix m. Im2col: arrange each [n n] block as a column of
       % length n*n
tv     % Vertically concatenate with itself. This makes columns twice as long without
       % affecting their mode. This is needed in case the previous result had a single
       % row (n=1), which would cause the subsequent mode function to compute the mode
       % of that row, instead of the mode of each column
XM     % Mode. This gives the mode of each column (the input has at least 2 rows)
[]e    % Reshape as a square matrix. Implicit display

caird coinheringaahing · Accepted Answer · 2021-06-16 11:40:46Z

2

Jelly, 13 bytes

Zs€Zs€ẎF€ÆṃḢ€

Try it online!

How it works

Zs€Zs€ẎF€ÆṃḢ€ - Main link. Takes M on the left and n on the right
Z             - Transpose M
 s€           - Slice each row into n pieces
   Z          - Transpose
    s€        - Split each group of columns into n pieces
      Ẏ       - Flatten into a list of n x n matrices
       F€     - Flatten each matrix
         ÆṃḢ€ - Get the first mode of each

edited Jun 16, 2021 at 11:40

answered Jun 16, 2021 at 11:28

caird coinheringaahing♦

50.9k11 gold badges133 silver badges364 bronze badges

1

\$\begingroup\$ when the footer is longer than the 13 byte answer \$\endgroup\$

Unrelated String
– Unrelated String

2021-06-16 11:32:03 +00:00
Commented Jun 16, 2021 at 11:32
\$\begingroup\$ These are also 13 bytes, if you can think of anywhere to go with them \$\endgroup\$

Unrelated String
– Unrelated String

2021-06-16 12:04:10 +00:00
Commented Jun 16, 2021 at 12:04

Add a comment |

Nick Kennedy · Accepted Answer · 2021-06-16 18:22:02Z

2

Jelly, 12 bytes

sZ€FÆṃḢƊ⁹ÐƤ€

Try it online!

After several 13s, I found a 12. A dyadic link taking the grid as a list of lists of integers on the left side and the size of the split on the right.

Explanation

s            | Split into sublists of the length specified by the right argument
 Z€          | Transpose each
       Ɗ⁹ÐƤ€ | For each sublist, do the following for each non-overlapping infix of the length specified by the original right argument:
   F         | - Flatten
    Æṃ       | - Mode
      Ḣ      | - Head

answered Jun 16, 2021 at 18:22

Nick Kennedy

21.2k3 gold badges18 silver badges44 bronze badges

1

\$\begingroup\$ The 12 I found is similar, s⁹ZsFÆṃḢƊ€ɗ€ \$\endgroup\$

Jonathan Allan
– Jonathan Allan

2021-06-17 18:41:36 +00:00
Commented Jun 17, 2021 at 18:41

Add a comment |

att · Accepted Answer · 2021-06-16 22:17:08Z

2

Wolfram Language (Mathematica), 41 bytes

BlockMap[Commonest[Join@@#,1]&,#2,{#,#}]&

Try it online!

Input [n, m]. Returns a matrix of singleton lists.

answered Jun 16, 2021 at 22:17

att

22.8k2 gold badges19 silver badges70 bronze badges

Add a comment |

pajonk · Accepted Answer · 2021-06-17 19:42:51Z

2

R, 130 124 121 116 111 bytes

-5 bytes and another 3 thanks to @Dominic

function(M,n,k=dim(M))array(Map(function(x)el(names(sort(-table(x))):0),split(M,t(a<-(row(M)-1)%/%n)*k+a)),k/n)

Try it online!

Longer approach than @Dominic's, but I thought it's worth a try.

Builds matrix mask t(a<-(row(M)-1)%/%n)*dim(M)+a used then in split, for example for matrix \$6\times6\$ and \$n=2\$:

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    0    0    6    6   12   12
[2,]    0    0    6    6   12   12
[3,]    1    1    7    7   13   13
[4,]    1    1    7    7   13   13
[5,]    2    2    8    8   14   14
[6,]    2    2    8    8   14   14

edited Jun 17, 2021 at 19:42

answered Jun 16, 2021 at 20:00

pajonk

19.4k5 gold badges29 silver badges78 bronze badges

1

\$\begingroup\$ This may be a bit longer, but I'm glad you posted it: I tried for ages to get a split approach to work, without success. This is very neat. \$\endgroup\$

Dominic van Essen
– Dominic van Essen

2021-06-17 09:01:41 +00:00
Commented Jun 17, 2021 at 9:01
1

\$\begingroup\$ 116 bytes with a bit of cleaning... \$\endgroup\$

Dominic van Essen
– Dominic van Essen

2021-06-17 11:05:12 +00:00
Commented Jun 17, 2021 at 11:05
\$\begingroup\$ @DominicvanEssen, thanks, I always forget about Map... \$\endgroup\$

pajonk
– pajonk

2021-06-17 11:23:59 +00:00
Commented Jun 17, 2021 at 11:23
\$\begingroup\$ ...and another -3... \$\endgroup\$

Dominic van Essen
– Dominic van Essen

2021-06-17 12:09:04 +00:00
Commented Jun 17, 2021 at 12:09
1

\$\begingroup\$ @DominicvanEssen, that's nice golf for the mask matrix, thanks! I managed to shave off another two by replacing nrow with dim and further optimisation. \$\endgroup\$

pajonk
– pajonk

2021-06-17 19:46:01 +00:00
Commented Jun 17, 2021 at 19:46

Add a comment |

coltim · Accepted Answer · 2021-06-28 23:42:38Z

2

K (ngn/k), 29 28 bytes

-1 byte from @Traws

{(*>#'=,/)''2(+(0N;y)#/:)/x}

Try it online!

Based off of @Shaggy's Japt answer. Takes the input matrix as x and the chunk size as y.

2(...)/x set up a do-reduce, seeded with x and run twice
- (+(0N;y)#/:) slice each row into y-length chunks, then transpose them
(...)'' run the code in (...) on each chunk in the transformed matrix
- (*>#'=,/) group the flattened chunk contents, counting the number of times each distinct number appears, then sort descending and return the first value (i.e. the mode)

edited Jun 28, 2021 at 23:42

answered Jun 17, 2021 at 14:54

coltim

6,1838 silver badges13 bronze badges

1

\$\begingroup\$ I guess you could transpose after the slice, saving 1 byte \$\endgroup\$

Traws
– Traws

2021-06-28 20:30:09 +00:00
Commented Jun 28, 2021 at 20:30
\$\begingroup\$ Thanks, nice catch! \$\endgroup\$

coltim
– coltim

2021-06-28 23:42:53 +00:00
Commented Jun 28, 2021 at 23:42

Add a comment |

Arnauld · Accepted Answer · 2021-06-16 15:33:12Z

JavaScript (ES6), 136 135 bytes

Expects (matrix)(chunk_size).

m=>n=>m.slice(-m.length/n).map((_,y,a)=>a.map((_,x)=>eval("for(o=K={},i=n*n;i--;)(o[v=m[y*n+i/n|0][x*n+i%n]]=-~o[v])<K?0:K=o[V=v];V")))

Try it online!

Commented

This is a version without eval() for readability.

m => n =>                     // m[] = matrix; n = chunk size
m.slice(-m.length / n)        // get an array of m.length / n entries
.map((_, y, a) =>             // for each value at position y in this slice:
  a.map((_, x) => {           //   for each value at position x in this slice:
    for(                      //     chunk loop:
      o =                     //       o is used to store all counts
      K = {},                 //       K is used to store the highest count
      i = n * n;              //       start with i = n * n
      i--;                    //       stop when i = 0 / decrement it
    ) ( o[                    //
          v = m[              //       v is the value in m[]
            y * n + i / n | 0 //       at row y * n + floor(i / n)
          ][                  //       and column x * n + (i mod n)
            x * n + i % n     //
          ]                   //
        ] = -~o[v]            //       increment o[v]
      ) < K ? 0               //       do nothing if it's less than K
            : K = o[V = v];   //       otherwise update V to v and K to o[v]
    return V                  //     implicit end of for(); return V
  })                          //   end of inner map()
)                             // end of outer map()

kur0dama · Accepted Answer · 2021-06-16 18:27:44Z

1

Python 2, 174 bytes

Quite long, very ugly, possibly the most comprehensions I've used in one statement. There is undoubtedly a better way to do this but I can't look at this thing anymore.

def f(m,n):l=len(m);r=range(0,l,n);b=l/n;print('%s '*b+'\n')*b%tuple(max(v,key=v.count)for v in[sum([x[k][j:j+n]for k in range(n)],[])for x in[m[i:i+n]for i in r]for j in r])

Try it online!

answered Jun 16, 2021 at 18:27

kur0dama

614 bronze badges

Add a comment |

dingledooper · Accepted Answer · 2021-06-16 18:58:06Z

1

Python 3.8 (pre-release), 96 bytes

Takes as input an integer matrix \$ m \$, and an integer \$ n \$ denoting the chunk size.

lambda m,n:[[max(x:=sum(j,()),key=x.count)for j in zip(*[zip(*i)]*n)]for i in zip(*[iter(m)]*n)]

Try it online!

Very messy use of the split into chunks golfing tip.

answered Jun 16, 2021 at 18:58

dingledooper

23.4k1 gold badge40 silver badges130 bronze badges

Add a comment |

Adám · Accepted Answer · 2021-06-17 10:23:47Z

APL (Dyalog Extended), 37 (SBCS)

Anonymous tacit infix function taking chunk count as right argument and the input matrix as right argument.

((∪⊃⍨∘⊃∘⍒⊢∘≢⌸)∘,⍤2)1 3 2 4⍉⊣⍴⍨4⍴⊢,≢⍛÷

Try it online!

{…} dfn; ⍺ is matrix and ⍵ is chunk size:
⎡0,1,0,1⎤
⎢0,0,1,1⎥
⎢0,0,0,0⎥
⎣0,0,1,1⎦
and 2

≢⍛÷ the matrix size divided by the chunk size
2

⊢, prepend the matrix size
[2,2]

4⍴ cyclically reshape to size 4
[2,2,2,2]

⊣⍴⍨ use that to reshape the matrix
⎡ ⎡0,1⎤ ⎡0,0⎤ ⎤
⎢ ⎣0,1⎦,⎣1,1⎦ ⎥
⎢ ⎡0,0⎤ ⎡0,0⎤ ⎥
⎣ ⎣0,0⎦,⎣1,1⎦ ⎦

1 3 2 4⍉ switch the middle two axes
⎡ ⎡0,1⎤ ⎡0,1⎤ ⎤
⎢ ⎣0,0⎦,⎣1,1⎦ ⎥
⎢ ⎡0,0⎤ ⎡0,0⎤ ⎥
⎣ ⎣0,0⎦,⎣1,1⎦ ⎦

(…)∘,⍤2 on each 2D leaf, ravel (flatten) it and then apply the following tacit prefix function:
⎡ [0,1,0,0],[0,1,1,1] ⎤
⎣ [0,0,0,0],[0,0,1,1] ⎦

⊢∘≢⌸ for each unique element, count the indices it occurs at
⎡ [3,1],[1,3] ⎤
⎣ [4] ,[2,2] ⎦

∪… with the unique elements…
⎡ [0,1],[0,1] ⎤
⎣ [0] ,[0,1] ⎦

∘⊃∘⍒ get the index of the largest count (lit. first element of the permutation vector that would sort the counts descending), then…
⎡1,2⎤
⎣1,1⎦

⊃⍨ use that to pick from the list of unique elements
⎡0,1⎤
⎣0,0⎦

Dominic van Essen · Accepted Answer · 2021-06-17 10:59:09Z

1

R, 113 111 108 bytes

Edit: -2 bytes, and then -3 more bytes, thanks to pajonk

(or 105 bytes by outputting a matrix of text strings representing the integers)

function(m,n)outer(o<-0:(nrow(m)/n-1)*n,o,Vectorize(function(x,y)el(names(sort(-table(m[x+1:n,y+1:n]))):0)))

Try it online!

edited Jun 17, 2021 at 10:59

answered Jun 16, 2021 at 14:57

Dominic van Essen

37.2k2 gold badges24 silver badges61 bronze badges

1

\$\begingroup\$ -2 with el(.:0) trick converting to integer. \$\endgroup\$

pajonk
– pajonk

2021-06-16 19:51:49 +00:00
Commented Jun 16, 2021 at 19:51
1

\$\begingroup\$ Another -3 - we don't need to select the first element from sort, as : will do that for us (with a warning). \$\endgroup\$

pajonk
– pajonk

2021-06-17 10:19:18 +00:00
Commented Jun 17, 2021 at 10:19
\$\begingroup\$ @pajonk - Thanks again, although I really should've noticed that myself... \$\endgroup\$

Dominic van Essen
– Dominic van Essen

2021-06-17 11:01:17 +00:00
Commented Jun 17, 2021 at 11:01

Add a comment |

Kevin Cruijssen · Accepted Answer · 2021-08-12 10:14:06Z

05AB1E, 12 bytes

2F¹δôø}εε˜.M

First input is chunk-size \$n\$, second input is matrix \$m\$.

Try it online or verify all test cases.

Explanation:

2F       # Loop two times:
   δ     #  Map over each row of the second (implicit) input-matrix:
  ¹ ô    #   Split it into parts equal to the first input-integer
     ø   #  Zip/transpose; swapping rows/columns
 }ε      # After the loop: map over each row of matrices:
   ε     #  Inner map over each matrix:
    ˜    #   Flatten this matrix to a list
     .M  #   Pop and only leave the most frequent integer in this list
         # (after which the mapped matrix is output implicitly as result)

score 0 · Accepted Answer · 2021-06-16 12:51:28Z

0

JavaScript (Node.js), 159 bytes

n=>k=>n.flatMap((e,i)=>i%k?[]:e.flatMap((h,j)=>j%k?[]:(M=n.slice(i,i+k).map(K=>K.slice(j,j+k)).flat()).sort((a,b)=>(X=Y=>M.map(Z=>z+=Z==Y,z=0)|z)(b)-X(a))[0]))

Try it online!

Golfing languages which have built-ins for occurrence count or chunks have concise programs. Mine is 159 bytes long.

edited Jun 16, 2021 at 12:51

answered Jun 16, 2021 at 12:27

user100690

Add a comment |

Neil · Accepted Answer · 2021-06-16 22:07:11Z

Charcoal, 54 bytes

Ｆ⪪Ｅθ⪪ιηη«≔⟦⟧ζＦＬ§ι⁰«≔⟦⟧εＦι≔⁺ε§λκε≔Ｅε№ελδ⊞ζ§ε⌕δ⌈δ»⊞υζ»Ｉυ

Try it online! Link is to verbose version of code. Explanation:

Ｆ⪪Ｅθ⪪ιηη«

Split each column into chunks of size n, then split the rows into chunks of size n and loop over the chunks.

≔⟦⟧ζ

Start collecting the results for this chunk of rows.

ＦＬ§ι⁰«

Loop over the number of chunks of columns.

≔⟦⟧εＦι≔⁺ε§λκε

Collect all of the values in this chunk of matrix into a single array.

≔Ｅε№ελδ

Get the frequencies of all the values.

⊞ζ§ε⌕δ⌈δ

Collect the value with the greatest frequency (chooses the first such value in case of a tie).

»⊞υζ

Save the results for this chunk of rows.

»Ｉυ

Output all of the results using Charcoal's default array output format.

Stack Exchange Network

Square chunk my matrix

Testcases

Scoring

17 Answers 17

APL (Dyalog Unicode), 40 38 bytes (SBCS)

J, 23 bytes

Japt `-h`, 17 bytes

MATL, 11 bytes

How it works

Jelly, 13 bytes

How it works

Jelly, 12 bytes

Explanation

Wolfram Language (Mathematica), 41 bytes

R, 130 124 121 116 111 bytes

K (ngn/k), 29 28 bytes

JavaScript (ES6), 136 135 bytes

Commented

Python 2, 174 bytes

Python 3.8 (pre-release), 96 bytes

APL (Dyalog Extended), 37 (SBCS)

R, 113 111 108 bytes

05AB1E, 12 bytes

JavaScript (Node.js), 159 bytes

Charcoal, 54 bytes

Your Answer

Linked

Hot Network Questions

Square chunk my matrix

Testcases

Scoring

17 Answers 17

APL (Dyalog Unicode), 40 38 bytes (SBCS)

J, 23 bytes

Japt -h, 17 bytes

MATL, 11 bytes

How it works

Jelly, 13 bytes

How it works

Jelly, 12 bytes

Explanation

Wolfram Language (Mathematica), 41 bytes

R, 130 124 121 116 111 bytes

K (ngn/k), 29 28 bytes

JavaScript (ES6), 136 135 bytes

Commented

Python 2, 174 bytes

Python 3.8 (pre-release), 96 bytes

APL (Dyalog Extended), 37 (SBCS)

R, 113 111 108 bytes

05AB1E, 12 bytes

JavaScript (Node.js), 159 bytes

Charcoal, 54 bytes

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Hot Network Questions

Japt `-h`, 17 bytes