9
\$\begingroup\$

Background

Match Land is a mobile game that falls into the Match-3 genre (think Bejeweled or Candy Crush Saga series): swap two orthogonally adjacent pieces to make a 3-in-a-row or longer. However, Match Land has an additional rule that makes the game much more interesting.

Once you make a valid match-3 move, the matched blocks are not removed immediately; instead, you get a small time window where you can create more/longer match-3 chains by swapping not-yet-matched blocks. If you make a wrong swap (that does not create a new match or extend existing matches), your turn ends immediately.

Exact rules for this challenge are as follows (I don't play this game right now, so the details might be different from the actual game. And the details not relevant to this challenge are omitted):

  • The game is played on a rectangular board. It is turn-based, and the player can make one or more moves in a turn.

  • The board is filled with tiles, each of which has one of six different types (denoted 1 to 6 in the examples later).

  • The player makes a "match" (three or more same tiles in a row, horizontally or vertically) by swapping two orthogonally (horizontally or vertically) adjacent tiles. The action of swapping two tiles is called a "move".

  • After the initial match, the player can make an additional move if the move extends the length of an existing match or it creates at least one new match (3-in-a-row).

    In the following example, B4-C4 and B3-B4 are valid moves but A3-B3 is not (simply moving the 4 adjacent to an existing match without creating a 3-in-a-row is not valid):

      | 1  2  3  4 
    --+------------
    A | 2  1  4  3 
    B | 1  2  3  4 
    C |(4)(4)(4) 5 
    
  • The player cannot move already matched tiles.

For example, consider the following 5x7 board (with coordinates for ease of explanation):

  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  4  3  5  2  4
B | 3  2  1  4  1  3  5
C | 4  2  4  4  3  1  4
D | 2  4  3  1  4  2  3
E | 2  4  2  2  3  3  4

The player can make a move at A3-A4 to match three 4's:

  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  3 (4) 5  2  4
B | 3  2  1 (4) 1  3  5
C | 4  2  4 (4) 3  1  4
D | 2  4  3  1  4  2  3
E | 2  4  2  2  3  3  4

Then D7-E7 to match some 3's:

  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  3 (4) 5  2  4
B | 3  2  1 (4) 1  3  5
C | 4  2  4 (4) 3  1  4
D | 2  4  3  1  4  2  4
E | 2  4  2  2 (3)(3)(3)

Then C5-D5 (note that a match is extended only if the new tile to be matched is aligned with the existing match, so the 3 moving into D5 is not matched with the existing E5-E7):

  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  3 (4) 5  2  4
B | 3  2  1 (4) 1  3  5
C | 4  2 (4)(4)(4) 1  4
D | 2  4  3  1  3  2  4
E | 2  4  2  2 (3)(3)(3)

You can continue this until you run out of possible moves.

I found a sequence of 9 moves from the initial state that matches 26 tiles in total (not confirmed yet if it is optimal):

C1-C2 B1-B2 A2-B2 C5-D5 D6-E6 E5-E6 D3-D4 B6-C6 B3-B4

  | 1  2  3  4  5  6  7
--+---------------------
A |(2) 3 (4) 3  5  2  4
B |(2)(4)(4)(1)(1)(1) 5
C |(2)(4)(4)(4)(4)(3) 4
D |(2)(4) 1 (3)(3)(3)(3)
E |(2)(4)(2)(2)(2)(3) 4

Challenge

Given a board state in Match Land, output the maximum number of tiles that can be matched in a single turn.

The input is a 2D array of integers from 1 to 6 inclusive. You can use any equivalent representation of a rectangular 2D array in your language, and any 6 distinct values in place of the integers. You can further assume that the input does not already have any 3-in-a-rows (as is the case in the actual game), and it has at least one valid initial move.

Standard rules apply. Shortest code in bytes wins. Imaginary brownie points for a solution that is provably correct and works reasonably fast in practice.

Test cases

Input:
1 1 2 1 1
Output: 4

Input:
1 1 2
2 2 3
3 3 1
Output: 9

Input:
2 2 1 2 1
2 1 2 1 2
3 2 1 2 1
Output: 14 (A3-A4, B4-B5, B2-B3, B3-B4, C3-C4)

Input:
3 2 1 2 2
2 1 2 1 2
3 2 1 2 1
Output: 12 (B4-C4, B2-C2, A2-A3)
(I believe matching 13 tiles is impossible without breaking existing matches)
\$\endgroup\$
6
  • \$\begingroup\$ "works reasonably fast in practice" - Do you know the lowest time complexity possible? \$\endgroup\$ – Jonah Mar 18 at 1:52
  • 1
    \$\begingroup\$ @Jonah No, I don't. But I know that naive backtracking would definitely explode exponentially :) \$\endgroup\$ – Bubbler Mar 18 at 1:58
  • 2
    \$\begingroup\$ @Arnauld The latter is correct. One way to think of it is to ignore the word "extend" -- every move should create at least one new 3-in-a-row. (In your example, if you make D2-D3 move, a new vertical match of B2-C2-D2 is created in this sense.) \$\endgroup\$ – Bubbler Mar 18 at 7:58
  • \$\begingroup\$ I think this might've been cooler as a fastest code challenge than code-golf. \$\endgroup\$ – Manish Kundu Mar 18 at 8:02
  • \$\begingroup\$ Does the final configuration need to be a single connected region? \$\endgroup\$ – Jonah Mar 18 at 18:56
6
\$\begingroup\$

JavaScript (ES6),  315 307  303 bytes

Brute force, but quite fast on the test cases.

f=(m,T=M=0,C=c=>m.map((r,y)=>r.map((_,x)=>c(x,y,1,0)|c(x,y,0,1))))=>C((x,y,X,Y,r=m[y],v=r[x],R=m[y+Y]||0,V=R[X+=x])=>V<8&v<8&&(Y=m.map(r=>[...r]),r[x]=V,R[X]=v,a=[n=0,1,2],C((x,y,w,z)=>a.some(p=i=>p-(p=(m[y+z*i]||0)[x+w*i]&7))||a.map(i=>n+=(R=m[y+z*i])[i=x+w*i]<(R[i]|=8)))|n&&f(m,T+n),m=Y),M=T>M?T:M)|M

Try it online!

Commented and speed-optimized

By adding a cache, we can make it fast enough to solve the 7x5 example given in the challenge in a few seconds.

A solution for 30 tiles in 11 moves is:

A4-B4 B5-C5 C4-D4 C3-D3 B3-C3 B1-B2 D7-E7 A7-B7 E1-E2 D1-E1 C1-C2
f = (
  // m[] is the input grid
  m,
  // T is the current score, M is the best score
  T = M = 0,
  // ungolfed version only: keep track of the moves and use a cache
  P = [],
  S = new Set,
  // C is a helper function that walks through all cells and invokes a callback
  // function with the position (x, y) and a vector (+1, 0) or (0, +1)
  C = c => m.map((r, y) => r.map((_, x) => c(x, y, 1, 0) | c(x, y, 0, 1))),
  B
) =>
// cache hit? (ungolfed version only)
( S.has(key = JSON.stringify(m))
  ||
  // look for all pairs of cells that can be swapped
  C((x, y, X, Y, r = m[y], v = r[x], R = m[y + Y] || 0, V = R[X += x]) =>
    // valid only if none of them already belongs to a match
    // ungolfed version only: also make sure they're not equal
    V < 8 && v < 8 && v ^ V && (
      // make a backup of the grid
      B = m.map(r => [...r]),
      // swap the cells
      r[x] = V,
      R[X] = v,
      // check the grid
      a = [n = 0, 1, 2],
      C((x, y, w, z) =>
        // 3 cells in a row?
        a.some(p = i =>
          p - (p = (m[y + z * i] || 0)[x + w * i] & 7)
        ) ||
        // if yes, mark them as matched and increment n for each new cell
        a.map(i =>
          n += (R = m[y + z * i])[i = x + w * i] < (R[i] |= 8)
        )
      ) | n &&
      // do a recursive call if at least one new cell was added
      f(m, T + n, [...P, [[x, y], [X, y + Y]]], S),
      // restore the grid
      m = B
    ),
    // update M to max(M, T)
    M = T > M ? (best = P, T) : M,
    // update the cache (ungolfed version only)
    S.add(key)
  ),
  [ best, M ]
)

Try it online!

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

R, 239 bytes

f=function(m,x=!m,w=nrow(m),`+`=sum,`/`=c){for(i in seq(m))for(j in 0:1){l=m
k=i--(i%%w&!j)-j*w*(i>w)
l[i/k]=l[k/i]
n=0
for(d in 1:2)n=t(n|apply(l,d,function(v,r=rle(v)$l)unlist(Map(rep,r>2,r)))&!+x[i/k])
if(+n>+x)F=max(F,+n,f(l,t(n)))}
F}

Try it online!

Semi-ungolfed

# m - input matrix
# x - matrix of existing matches initialized with FALSEs of the shape of m
# w - number of rows
f = function(m, x=!m, w=nrow(m)) {
  # loop through each cell in m twice: 
  # once for a vertical match and once for a horizontal one
  for(i in seq(m)) for(j in 0:1) {
    # Work on a copy of m
    l = m
    # The index of the cell to swap:
    # one cell down from i (except the last row), or
    # one cell left from i (except the first column)
    k = i + (i%%w&!j) - j*w*(i>w) 
    # Swap ith and kth cell
    l[c(i,k)] = l[c(k,i)]
    # Record new matches, start with 0
    n = 0
    # If neither i, nor k was matched earlier, check both dimensions:
    if(!any(x[c(i,k)])) for(d in 1:2) {
      # Find runs of 3-in-a-row across the given dimension:
      # take Run Length Encoding of a row/column,
      # expand it so that runs longer than 2 get mapped to TRUE
      # e.g.: 1 2 2 2 3 3 => F T T T F F,
      # then logical OR with previous n
      n = n | apply(l, d, function(v, r=rle(v)$l)unlist(Map(rep, r>2, r)))
      # Apply always collects the results columnwise, so that
      # a transpose is necessary to make the results conformable
      n = t(n)
    }
    # If there are new matches compared to previous iteration
    if(sum(n)>sum(x))
      # Call itself recursively with the modified input l, and
      # n transposed to original shape, as new existing matches
      # The maximum of all iterations will be the final result
      F = max(F, sum(n), f(l,t(n)))
  }
  F
}
\$\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.