11
\$\begingroup\$

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.


It's time to prepare an advent calendar, but I've only got a large sheet of rectangular paper, randomly colored red and green like this:

GRRRGRRGRG
GGRGGGRRGR
GRRGRGRGRG
GGRRGRGRGG
GRGGRGRGGG
RRGRGRGRRG
RRRGRGRGGG
RGGRGGRRRG
RGGGRRRRRG
GRGRRRGRRG

Out of this paper, I want to cut out a 5-by-5 region which is colored in a checkerboard fashion:

GRRRGRRGRG
GGRGGGRRGR
GRRGRGRGRG
GGRRGRGRGG
GRGGRGRGGG
RRGRGRGRRG
RRRGRGRGGG
RGGRGGRRRG
RGGGRRRRRG
GRGRRRGRRG

The exact coloring doesn't matter (the top left cell can be either green or red).

But if I'm unlucky, the piece of paper might not have such a region at all. In that case I will have to repaint some cells; I want to cut out a region which minimizes the amount of paint to make it checkered.

Task: Given a sheet of paper, output the minimum number of cells I need to recolor to get a checkered 5-by-5 grid.

Assume that both the width and height of the given paper are at least 5. You may choose to use any two distinct characters or numbers instead of R and G respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

RGRGR
GRGRG
RGRGR
GRGRG
RGRGR => 0

GRRRGRRGRG
GGRGGGRRGR
GRRGRGRGRG
GGRRGRGRGG
GRGGRGRGGG
RRGRGRGRRG
RRRGRGRGGG
RGGRGGRRRG
RGGGRRRRRG
GRGRRRGRRG => 0

RGRGRG
GRGRGR
RGRGRG
RRRRRR
RGRGRG => 2

RRRRR
RRRRG
RRRGG
RRGGG
RGGGG => 10

GGGGG
GGGGG
GGGGG
GGGGG
GGGGG => 12

RRGGGRRRGR
RRRGGRRRGR
RGGGGRRRGG
GRRGRRRRGG
GGGRGGRRGR
RRGGRGGGGG
GGRRRRRGRR
GGRGRRRRGR
GGRRRGGGGR
GRRGGGRGRR => 9
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Last test case has a chequered grid at [2:7, 3:8]. \$\endgroup\$
    – Neil
    Dec 5, 2022 at 0:48
  • \$\begingroup\$ @Neil Duh, thanks. Likely I messed up with copy-pasting :/ Fixed now. \$\endgroup\$
    – Bubbler
    Dec 5, 2022 at 2:19

14 Answers 14

6
\$\begingroup\$

J, 45 41 40 39 38 bytes

[:<./@(,,25-,)5 5+/@,@(=2|#\+/#\);._3]

Try it online!

Perfect problem for J's subarray, or tiling verb:

  • 5 5...;._3]For every 5 x 5 tiling of the input (which we take as a binary matrix), do the following
  • =2|#\+/#\ Create a template checkerboard 2|#\+/#\ and return where the current tile is equal to that =. (see penultimate step to understand why checking equal instead of not-equal is ok here)
  • +/@,@ And sum
  • [:...(,,25-,) Cat that result with 25 minus that result. This gives us "both possible checkerboards", because if one checkerboard misses in x places, the other will miss in 25 - x places.
  • <./@ Take the min
\$\endgroup\$
5
\$\begingroup\$

Pip -x, 68 54 bytes

-12 thanks to Dlosc's suggestions

Fx,#g-4Fz,#@g-4lAL:[25-Y$+:%_=BMEFL:_@>zH5Mg@>xH5y];Nl

Input is a binary matrix.

Try It Online!

Here's some code to convert a matrix of R and G to a binary matrix that can be used in Pip.

How? (Outdated until I find time to update)

T#g-5<Uv{. . .}: Repeat until T the length # of the input matrix g minus 5 -5 is less than v incremented (modify in-place) <Uv. The initial value of v is -1. This essentially loops from v=0 to v=#g-5.

Y-1T#@g-5<Uy{. . .}: Set Y the variable y to -1. Then repeat until T the length # of the first element @ of the input matrix g minus 5 -5 is less than y incremented (modify in-place) <Uy.This essentially loops from y=0 to y=#@g-5.

FL:_@>yH5Mg@>vH5: Get all the elements starting from index v (@>v) of the input matrix g and then get the first 5 elements of the resulting matrix H5. For each M row _ in the resulting matrix, get all the elements starting from index y (@>y) of the row _ and then get the first 5 elements of the resulting list H5. Then flatten FL the resulting matrix. This essentially creates a flattened 5-by-5 sub-matrix with g[v][y] (not real Pip code, just pseudocode) as the top left corner.

z:_%2=BMZ,25. . .: Zip MZ the range , from 0 to 25 with the flattened sub-matrix described previously, and map the zipped pairs to the block _%2=B, with values from ,25 being _ and values from the flattened matrix being B. Test if the value from the range _ modulo 2 (%2) is equal to = the value from the flattened matrix B. Set : the resulting list to z: This essentially tests the 5-by-5 sub-matrix against a checkered 5-by-5 matrix (which, when flattened, is the alternating list 0,1,0,...,1, represented by taking the range ,25 and taking modulo 2 of that list), and sees how many places it "misses". This will give how many values need to change within the 5-by-5 submatrix in order to get a checkered matrix.

lAL:[$+:z25-z]: Extend AL the list l with the list [$+:z25-z], which consists of two values $+:z and 25-z. Sum $+ the list z, modifying in-place :. 25-z takes the sum and subtracts it from 25. The initial value of l is the empty list []. This essentially keeps track of how many changes are needed to change from the specific 5-by-5 submatrix to a checkered matrix. The reason we also append 25-z to the list is to handle the fact that there are two possible checkered matrices that we can change the sub-matrix into, and that changing the submatrix into one of the checkered matrices may be more efficient than changing it to the other checkered matrix. It just so happens that the number of changes needed in order to change the sub-matrix into one possible checkered matrix is 25 minus the numbers of changes needed for the other possible checkered matrix.

Nl: Takes the minimum of the list l and implicitly outputs the result.

\$\endgroup\$
3
  • \$\begingroup\$ 1) "loops from v=0 to v=#g-5" can be Fv,#g-4 for -1 byte, and similarly for the inner loop. The loop variable can be anything, which frees y up for other purposes. 2) Instead of MZ,25, you can use ME. 3) %_ is the same as _%2. 4) I think you can save some bytes by calculating the sum of the number of misses and assigning it to z inside the list: [z:$+:(...)25-z]. \$\endgroup\$
    – DLosc
    Dec 5, 2022 at 23:07
  • \$\begingroup\$ Ok good golfing tips, I'll golf my answer when i get the chance \$\endgroup\$
    – Aiden Chow
    Dec 6, 2022 at 8:47
  • \$\begingroup\$ @DLosc ok thanks for the help i updated it with all your tips, hopefully I didn't miss anything. also i'm not entirely sure why I need the semicolon in my code, it breaks without it, hoping you have some insight into that cuz i couldn't understand the debugger. \$\endgroup\$
    – Aiden Chow
    Dec 7, 2022 at 2:39
4
\$\begingroup\$

Python, 130 128 111 bytes

  • -2 bytes thanks to Neil, thanks to order of operations
  • -9 bytes thanks to 72.100.97.109

Python is extraordinarily bad at working with multidimensional arrays without numpy. Or maybe I just missed something obvious.

lambda a:min(sum(y+a[x+i//5][y//2+i%5]+i&1for i in r(25))for x in r(len(a)-4)for y in r(2*len(a[0])-8))
r=range

Attempt This Online!

Short Explanation

Basically there are 4 loops. The outer loop for x in r(len(a)-4)for y in r(len(a[0])-4) find the top left corner of every 5 by 5 square. We multiply this by 2 to get a extra bit.

The inner loop sums the number of squares in that area that do not fit the grid. We add a lot of terms and then &1 them. This basically is equivolent to XORing all their last bits. We need to swap based on the position within the square as well as the last binary digit of y. If this is not equal to the grid at that position (also XOR) we include it in the sum.

Finally, we get the minimum value of all of this.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ d+a[x+i][y+j]+i+j&1 saves 2 bytes. \$\endgroup\$
    – Neil
    Dec 5, 2022 at 10:32
  • \$\begingroup\$ I'm surprised by your answer, would you explain it? \$\endgroup\$ Dec 5, 2022 at 19:47
  • 1
    \$\begingroup\$ 126 bytes. \$\endgroup\$ Dec 5, 2022 at 20:21
4
\$\begingroup\$

Python, 111 bytes (@att)

lambda A:25-max(map(abs,sum(map(g,*map(g,*A)),[])))>>1
g=lambda*a,c=0:[c:=x+y-c for x,y in zip(a,5*(0,)+a)][4:]

Attempt This Online!

Python, 115 bytes

lambda A:25-max(map(abs,sum(map(g,zip(*map(g,A))),[])))>>1
g=lambda a,c=0:[c:=x+y-c for x,y in zip(a,5*(0,)+a)][4:]

Attempt This Online!

Takes a list of tuples of spins (+/-1).

How?

The standard tool for matching a pattern that may be shifted is convolution. Using "spins" (+1,-1) instead of "booleans" (1, 0) and convolving the input with a 5x5 checkerboard template yields 25 at each offset that has a perfect match (and -25 for a perfect anti-match). Each mismatched square removes 2; when the value becomes negative it will be more economical to match the negative template. This hopefully explains the (25-|x|) / 2 in f.

In addition, we use the fact that the checkerboard made of 1s and -1s is a "rank-1-matrix" meaning that it can be written as the outer product of two vectors which in this case, conveniently, happen to be the same vector v=[1,-1,1,-1,1]. Using this the 2D convolution with the checkerboard template can be broken down into two 1d convolutions, one for each axis.

Further, because of the special structure of v we can write the convolution as a running difference. This is essentially what g does.

\$\endgroup\$
7
  • \$\begingroup\$ nice and short answer, would you explain it? \$\endgroup\$ Dec 5, 2022 at 19:49
  • \$\begingroup\$ Would 12.5-max(...) work with "spins" (\$\frac{\pm 1}{2}\$)? \$\endgroup\$ Dec 5, 2022 at 20:18
  • \$\begingroup\$ @AmirrezaRiahi I've given it a try. \$\endgroup\$
    – loopy walt
    Dec 5, 2022 at 21:04
  • \$\begingroup\$ @JonathanAllan I don't see a reason why it shouldn't. But it saves only 1 byte as far as I can tell while requiring a rather non-standard input format. \$\endgroup\$
    – loopy walt
    Dec 5, 2022 at 21:11
  • \$\begingroup\$ -4 \$\endgroup\$
    – att
    Dec 5, 2022 at 21:53
3
\$\begingroup\$

R, 106 104 bytes

\(x,g=12){for(i in 5:ncol(x))for(j in 5:nrow(x))g=min(g,m<-sum(x[j-4:0,i-4:0]==matrix(1:0,5,5)),25-m);g}

Attempt This Online!

Based on Jonah's explanation in the J answer.

Takes input as a binary matrix.

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

JavaScript (ES6), 115 bytes

Expects a matrix filled with "0"'s and "1"'s.

f=(m,x=0,[r,...a]=m)=>m[4]?r[x+4]?Math.min((g=n=>t=n--&&(r[x]+n-m[n/5|0][x+n%5]&1)+g(n))(25),25-t,f(m,x+1)):f(a):25

Try it online!

Commented

Nested map() loops tend to be lengthy. So we don't use any explicit loop and go 100% recursive instead.

f = (                  // f is a recursive function taking:
  m,                   //   m[] = input matrix
  x = 0,               //   x = position in the current row
  [ r,                 //   r[] = current row
    ...a ] = m         //   a[] = remaining rows
) =>                   //
m[4] ?                 // if there's still at least 5 rows:
  r[x + 4] ?           //   if there's still at least 5 columns:
    Math.min(          //     get the minimum:
      ( g = n =>       //       g is a recursive function taking a counter n
        t =            //         save the result in t
        n-- && (       //         if n is not 0 (decrement it afterwards):
          r[x] +       //           take the value at the top-left corner
          n -          //           add n
          m[n / 5 | 0] //           subtract the value of the cell at
          [x + n % 5]  //           (x + (n mod 5), floor(n / 5))
          & 1          //           isolate the least significant bit
        ) + g(n)       //           add the result of a recursive call
      )(25),           //       initial call to g with n = 25
      25 - t,          //       also try 25 - t
      f(m, x + 1)      //       do a recursive call to f with x + 1
    )                  //     end of Math.min()
  :                    //   else:
    f(a)               //     do a recursive call to f for the next row
:                      // else:
  25                   //   stop the recursion
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 57 56 bytes

WS⊞υEι﹪⁺℅κ⁺λLυ²≔⟦⟧ηF⁻Lυ⁴F⁻Lθ⁴⊞ηΣE✂υι⁺⁵ι¹Σ✂λκ⁺⁵κ¹I⌊⁺η⁻²⁵η

Try it online! Takes input as a list of newline-terminated strings of Gs and Rs (although 0s and 1s also work). Explanation:

WS⊞υEι﹪⁺℅κ⁺λLυ²

Read in the strings, but replace each character with a bit according to the parity of the sum of its character code, row and column.

≔⟦⟧θF⁻Lυ⁴F⁻Lθ⁴⊞θΣE✂υι⁺⁵ι¹Σ✂λκ⁺⁵κ¹

Collect all of the 5×5 regions and count the bits in each region.

I⌊⁺θ⁻²⁵θ

Subtract all of the counts from 25 and output the minimum of both sets of counts.

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

Jelly, 19 18 17 bytes

Z5ƤẎ5Ƥ€Ẏ;¬$¬Ðe€§Ṃ

Try it online!

-1 thanks to Jonathan Allan

Expects a binary matrix. Feels... inelegant.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think JḂ=Ɗ€ -> ¬Ðe€ should work to save a byte. \$\endgroup\$ Dec 5, 2022 at 13:56
3
\$\begingroup\$

Octave, 79 bytes

@(a)min([b=conv2(mod(a+(1:rows(a))'+(1:rows(a')),2),~~e(5,5),"valid"),25-b](:))

Try it online!

Takes input as a binary matrix.


Octave, 56 bytes, by @Luis Mendo

@(x)min(25-abs(conv2(x,j.^((t=0:2:8)+t'),'valid'))(:))/2

Try it online!

Takes input as a matrix with 1 and -1.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Similar approach, using input with 1 / -1: 56 bytes \$\endgroup\$
    – Luis Mendo
    Dec 5, 2022 at 12:32
2
\$\begingroup\$

05AB1E, 20 bytes

2Fø€ü5}εε˜Â«āÉα2äO]ß

Input as a binary-matrix.

Try it online or verify all test cases.

Explanation:

2Fø€ü5}       # Create all overlapping 5x5 blocks of the (implicit) input-matrix:
2F    }       #  Loop 2 times:
  ø           #   Zip/transpose; swapping rows/columns
              #   (which will use the implicit input-matrix in the first iteration)
   €          #   Map over each inner list:
    ü5        #    Create overlapping quintuplets
εε         ]  # Nested map over each block:
  ˜           #   Flatten the 5x5 block to a single list
   Â          #   Bifurcate it; short for Duplicate & Reverse copy
    «         #   Merge the reversed copy to the list
     ā        #   Push a list in the range [1,length] (without popping): [1,50]
      É       #   Convert it to a list of [1,0,1,0,1,0,...] with an is_odd check
       α      #   Get the absolute difference at the same positions of the two lists
        2ä    #   Split the list back into two parts of length 25 each
          O   #   Sum each inner list, resulting in a pair [c,25-c]
              #   (where `c` is the amount of bits that has to be changed to get a
              #   checkered 5x5 block with 1s at the corners)
           ]ß # After the nested map: pop and push the flattened minimum
              # (which is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Retina, 145 bytes

L$v`(?<=(.)*)(.{5}).*¶(?<7-1>.)*(.{5}).*¶(?<1-7>.)*(.{5}).*¶(?<7-1>.)*(.{5}).*¶(?<1-7>.)*(.{5})
00$2$3$4$5$6
,T,2,`d`10
%O`.
01
0¶1
N$`
$.&
\G.\B

Try it online! Takes input as a newline-separated list of binary strings but header converts from strings of G and R for convenience. Explanation:

L$v`(?<=(.)*)(.{5}).*¶(?<7-1>.)*(.{5}).*¶(?<1-7>.)*(.{5}).*¶(?<7-1>.)*(.{5}).*¶(?<1-7>.)*(.{5})
00$2$3$4$5$6

Extract all of the 5×5 regions as flattened strings, but prefix two 0s because it's golfier not to have any zero-length strings later.

,T,2,`d`10

Toggle alternate bits. The ideal case is now either one 0 bit or one 1 bit (one of the 0 bits added above would have been toggled to 1).

%O`.

Sort the bits within each string of 25 bits.

01
0¶1

Separate the strings of 0 and 1 bits.

N$`
$.&

Sort ascending by length.

\G.\B

Subtract 1 and convert the minimum to decimal.

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

PARI/GP, 70 bytes

a->(25-vecmax(abs(g(g(a)))))/2
g(a)=Mat(Vec(x^5\(x+1)*Pol(a~))[5..-5])

Attempt This Online!

Takes input as a matrix with 1 and -1. Based on @Luis Mendo's comment of my Octave answer.


PARI/GP, 82 bytes

a->vecmin(concat(m=matrix(#a~-4,#a-4,x,y,sum(j=0,24,(a[x+j\5,y+j%5]+j)%2)),-m)%25)

Attempt This Online!

Takes input as a binary matrix.

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

APL(Dyalog Unicode), 18 bytes SBCS

{12.5-⌈/|,5-/5-⌿⍵}

Try it on APLgolf!

Input a matrix with 0.5 and ¯0.5.

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

C (clang), 142 138 bytes

-4 bytes thanks to @ceilingcat

#define l(n,m)for(int n=m;n--;)
c;j;f(*r,*t,w,h){*r=99;l(y,h-4)l(x,w-4)l(i,2){j=i,c=0;l(Y,5)l(X,5)c+=t[(Y+y)*w+X+x]!=j,j=!j;*r>c?*r=c:0;}}

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Suggest l(X,25)c+=t[(X/5+y)*w+X%5+x]!=j instead of l(Y,5)l(X,5)c+=t[(Y+y)*w+X+x]!=j \$\endgroup\$
    – ceilingcat
    Feb 1 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.