14
\$\begingroup\$

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:

0 1 0 1
0 0 1 1
0 0 0 0
0 0 1 1, 
2

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 , shortest wins!

\$\endgroup\$
10
  • \$\begingroup\$ Can we take the matrix transposed? \$\endgroup\$ – caird coinheringaahing Jun 16 at 11:28
  • \$\begingroup\$ How does that help? It's the same thing... \$\endgroup\$ – A username Jun 16 at 11:28
  • 4
    \$\begingroup\$ Is the matrix guaranteed to be square? \$\endgroup\$ – Arnauld Jun 16 at 11:38
  • 2
    \$\begingroup\$ Can we take the width and height of the matrix as input too \$\endgroup\$ – StackMeter Jun 16 at 11:43
  • 3
    \$\begingroup\$ "You can take either the size of a single chunk, or the number of chunks to a side." but can we take both? \$\endgroup\$ – Adám Jun 16 at 11:46

16 Answers 16

2
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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⎦

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

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{.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
0
2
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ when the footer is longer than the 13 byte answer \$\endgroup\$ – Unrelated String Jun 16 at 11:32
  • \$\begingroup\$ These are also 13 bytes, if you can think of anywhere to go with them \$\endgroup\$ – Unrelated String Jun 16 at 12:04
2
\$\begingroup\$

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
\$\endgroup\$
1
2
\$\begingroup\$

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
\$\endgroup\$
5
  • 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 Jun 17 at 9:01
  • 1
    \$\begingroup\$ 116 bytes with a bit of cleaning... \$\endgroup\$ – Dominic van Essen Jun 17 at 11:05
  • \$\begingroup\$ @DominicvanEssen, thanks, I always forget about Map... \$\endgroup\$ – pajonk Jun 17 at 11:23
  • \$\begingroup\$ ...and another -3... \$\endgroup\$ – Dominic van Essen Jun 17 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 Jun 17 at 19:46
2
\$\begingroup\$

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I guess you could transpose after the slice, saving 1 byte \$\endgroup\$ – Traws Jun 28 at 20:30
  • \$\begingroup\$ Thanks, nice catch! \$\endgroup\$ – coltim Jun 28 at 23:42
1
\$\begingroup\$

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()
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 41 bytes

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

Try it online!

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

\$\endgroup\$
1
\$\begingroup\$

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⎦

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ -2 with el(.:0) trick converting to integer. \$\endgroup\$ – pajonk Jun 16 at 19:51
  • \$\begingroup\$ @pajonk - Thanks! \$\endgroup\$ – Dominic van Essen Jun 16 at 20:37
  • 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 Jun 17 at 10:19
  • \$\begingroup\$ @pajonk - Thanks again, although I really should've noticed that myself... \$\endgroup\$ – Dominic van Essen Jun 17 at 11:01
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 54 bytes

F⪪Eθ⪪ιηη«≔⟦⟧ζFL§ι⁰«≔⟦⟧εFι≔⁺ε§λκε≔Eε№ελδ⊞ζ§ε⌕δ⌈δ»⊞υζ»Iυ

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

F⪪Eθ⪪ιηη«

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.

FL§ι⁰«

Loop over the number of chunks of columns.

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

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

≔Eε№ελδ

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.

»Iυ

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

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