# Find the best immediate move in a “match-3” game

Your challenge today is to take input like this:

fbcfbee
ffcabbe
debceec
bccabbe
edcfbcd
daeaafc
eebcbeb


And output the best possible move in a Bejeweled-like game that will match three or more letters, like this (note the capital B and C):

fbcfbee
ffcabbe
deBCeec
bccabbe
edcfbcd
daeaafc
eebcbeb


Full specifications:

• The input will be n lines of n lowercase letters each (where n could be any number).
• The output will be the best move you could make in a match-3 game, with the two letters you want to swap capitalized.
• Matches should have the following priority (in these examples, . indicates a square that doesn't matter):

1. Five-in-a-row

xxYxx
..X..

2. Broken five-in-a-row

X..
Yxx
x..
x..


or

.X.
xYx
.x.
.x.

3. Four-in-a-row

xYxx
.X..

4. Three-in-a-row

xYx
.X.


You must find the match of the highest priority and output it.

• If there are multiple matches of the same priority, you can output any one of them.
• There will always be at least one match (your program can break if there are no matches, or do anything you want).
• I/O can be in any reasonable format (stdin/out, reading and writing files, function arguments/return values, dialog boxes, etc.) but NOT hardcoded (like x="[insert input here]").
• This is so shortest code in bytes wins. If you use any network access for some reason, all bytes downloaded from the network count against your score.
• +1, but I protest the title; there could be a better move. For instance, one that creates two fives, or one that causes a drop to create more stuff. – Justin Jan 26 '14 at 5:53
• Does broken five-in-a-row also cover ..x.\nxxYX\n..x.? – Peter Taylor Jan 26 '14 at 8:54
• @Peter Yes, it does. – Doorknob Jan 26 '14 at 14:12
• There are 2 broken 5 in a row pattern: the L pattern and the T pattern. Do you require both to be matched? – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jan 26 '14 at 15:01
• @nhahtdh Yes, I'll edit to clarify that. – Doorknob Jan 26 '14 at 15:02

Python3.4, 772

(Using tabs for indentation, instead of spaces.)

import sys,itertools as I
B=[]
for l in sys.stdin:
l=l.rstrip()
B.append(list(l))
Z=len(B[0])
F=T=None
R=range
N=min
X=max
P=I.product
S=0
def C(I,J,K,L):
global F,T,S
if K<0 or K>=Z or L<0 or L>=Z: return
B[I][J],B[K][L]=B[K][L],B[I][J]
h=v=1
m=B[K][L]
for i in R(K+1,N(Z,K+5)):
if B[i][L]!=m:break
v+=1
for i in R(K-1,X(0,K-5),-1):
if B[i][L]!=m:break
v+=1
for j in R(L+1,N(Z,L+5)):
if B[K][j]!=m:break
h+=1
for j in R(L-1,X(0,L-5),-1):
if B[K][j]!=m:break
h+=1
c=X(h,v)*2
if N(h,v)>=3:c+=N(h,v)
if c>S:S=c;F=I,J;T=K,L
B[I][J],B[K][L]=B[K][L],B[I][J]
for i,j in P(reversed(R(Z)),R(Z)):
for d,e in (1,0),(0,-1),(0,1),(-1,0):
C(i,j,i+d,j+e)
for i,j in P(R(Z),R(Z)):
c=B[i][j]
if (i,j)in(F,T):c=c.upper()
print(c,end=('',"\n")[j==Z-1])

• Instead of [c for c in l], you could just do list(l). – Doorknob Jan 26 '14 at 16:05
• Use (i,j)in(F,T) instead of two compares - 778 – aghast Jan 26 '14 at 17:05
• F=(i,j) -> F=i,j. Deglobalize 2 r/o syms - 770 – aghast Jan 26 '14 at 17:16
• Fixed bug: broken-5 should not beat true-5. – aghast Jan 26 '14 at 18:00