CGAC2022 Day 5: Preparing an advent calendar

Question

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 code-golf 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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

Charcoal, 57 56 bytes

ＷＳ⊞υＥι﹪⁺℅κ⁺λＬυ²≔⟦⟧ηＦ⁻Ｌυ⁴Ｆ⁻Ｌθ⁴⊞ηΣＥ✂υι⁺⁵ι¹Σ✂λκ⁺⁵κ¹Ｉ⌊⁺η⁻²⁵η

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

ＷＳ⊞υＥι﹪⁺℅κ⁺λＬυ²

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.

≔⟦⟧θＦ⁻Ｌυ⁴Ｆ⁻Ｌθ⁴⊞θΣＥ✂υι⁺⁵ι¹Σ✂λκ⁺⁵κ¹

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

Ｉ⌊⁺θ⁻²⁵θ

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

Answer 8

Jelly, 19 18 17 bytes

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

Try it online!

-1 thanks to Jonathan Allan

Expects a binary matrix. Feels... inelegant.

Answer 9

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.

Answer 10

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)

Answer 11

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.

Answer 12

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.

Answer 13

APL(Dyalog Unicode), 18 bytes ^SBCS

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

Try it on APLgolf!

Input a matrix with 0.5 and ¯0.5.

Answer 14

C (clang), 142 bytes

#define l(n,m)for(int n=0;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)t[(Y+y)*w+X+x]^j&&c++,j=!j;*r>c?*r=c:0;}}

Try it online!