Determine if a move exists in a Bejeweled/match 3 game

Original Solution: JavaScript - 261 255 228 227 179 153 Characters

/(\d)(\1(\d|.{6}|.{9})|(\d|.{6}|.{9})\1|.{7}\1(.|.{9})|(.|.{9})\1.{7}|(.{7,9}|.{17})\1.{8}|.{8}\1(.{7,9}|.{17}))\1/.test(s.replace(/\n/g,'A'))?'yes':'no'

Assuming that the string to test is in the variable s (to make it a function f then add f=s=> to the beginning of the code or, otherwise, to take input from a prompt then replace s with prompt()).

Outputs is to the console.

3^rd Solution: JavaScript (ECMAScript 6) - 178 Characters

p=x=>parseInt(x,36);for(t="2313ab1b8a2a78188h9haj9j8iaiir9r",i=v=0;s[i];i++)for(j=0;t[j];v|=s[i]==s[i+a]&s[i]==s[i+b]&i%9<8&(b>3|(i+b-a)%9<8))a=p(t[j++]),b=p(t[j++]);v?'yes':'no'

I took the 2^nd solution, below, (which uses regular expressions to check for characters in certain configurations) and reworked it to just check the string for identical characters in the same configurations without using regular expressions.

The Base-36 string "2313ab1b8a2a78188h9haj9j8iaiir9r" gives pairs of offsets to check - i.e. the pair 23 results in the check if i^th character is identical to the (i+2)^th character and the (i+3)^th character (the equivalent of the regular expression (.).\1\1 - with some additional checks to ensure that the non-identical character is not a newline).

2^nd Solution: JavaScript (ECMAScript 6) - 204 Characters

p=x=>parseInt(x,18);g=a=>a?a>1?"(.|\\n){"+a+"}":".":"";f=(x,a,b)=>RegExp("(.)"+g(a)+"\\1"+g(b)+"\\1").test(x);for(t="10907160789879h8",i=v=0;t[i];v|=f(s,x,y)||f(s,y,x))x=p(t[i++]),y=p(t[i++]);v?'yes':'no'

Builds multiple regular expressions (see below for more details) using pairs of values taken from the Base-18 string 10907160789879h8 and takes the OR of all the tests. To reduce it further you can note that the regular expressions come in pairs where one is the "reverse" of the other (ignoring the Regular Expressions for 3-in-a-row horizontally and vertically as the OP states they will never be present - if you want to add those tests back in the append 0088 to the Base-18 string).

Explanation

Start with 16 regular expressions covering all the possible configurations of valid moves:

REs=[
    /(\d)\1\1/,                 // 3-in-a-row horizontally
    /(\d).\1\1/,                // 3-in-a-row horizontally after left-most shifts right
    /(\d)\1.\1/,                // 3-in-a-row horizontally after right-most shifts left
    /(\d)(?:.|\n){9}\1\1/,  // 3-in-a-row horizontally after left-most shifts down
    /(\d)(?:.|\n){7}\1.\1/, // 3-in-a-row horizontally after middle shifts down
    /(\d)(?:.|\n){6}\1\1/,  // 3-in-a-row horizontally after right-most shifts down
    /(\d)\1(?:.|\n){6}\1/,  // 3-in-a-row horizontally after left-most shifts up
    /(\d).\1(?:.|\n){7}\1/, // 3-in-a-row horizontally after middle shifts up
    /(\d)\1(?:.|\n){9}\1/,  // 3-in-a-row horizontally after right-most shifts up
    /(\d)(?:.|\n){7,9}\1(?:.|\n){8}\1/, // 3-in-a-row vertically (with optional top shifting left or right)
    /(\d)(?:.|\n){7}\1(?:.|\n){9}\1/,   // 3-in-a-row vertically after middle shifts right
    /(\d)(?:.|\n){9}\1(?:.|\n){7}\1/,   // 3-in-a-row vertically after middle shifts left
    /(\d)(?:.|\n){8}\1(?:.|\n){7}\1/,   // 3-in-a-row vertically after bottom shifts right
    /(\d)(?:.|\n){8}\1(?:.|\n){9}\1/,   // 3-in-a-row vertically after bottom shifts left
    /(\d)(?:.|\n){17}\1(?:.|\n){8}\1/,  // 3-in-a-row vertically after top shifts down
    /(\d)(?:.|\n){8}\1(?:.|\n){17}\1/,  // 3-in-a-row vertically after bottom shifts up
];

(Note: the regexs for 3-in-a-row horizontally (0^th) and vertically (part of the 9^th) are irrelevant as the OP states that inputs matching these will never be present.)

Testing each of those against the input will determine if a valid move of that configuration can be found.

However, the regular expressions can be combined to give these 6:

/(\d)(?:.|(?:.|\n){9}|(?:.|\n){6})?\1\1/            // Tests 0,1,3,5
/(\d)\1(?:.|(?:.|\n){9}|(?:.|\n){6})?\1/            // Tests 0,2,6,8
/(\d)(?:.|\n){7}\1(?:.|(?:.|\n){9})\1/              // Tests 4,10
/(\d)(?:.|(?:.|\n){9})\1(?:.|\n){7}\1/              // Tests 7,11
/(\d)(?:(?:.|\n){7,9}|(?:.|\n){17})\1(?:.|\n){8}\1/ // Tests 9,14
/(\d)(?:.|\n){8}\1(?:(?:.|\n){7,9}|(?:.|\n){17})\1/ // Tests 9a,12,13,15

These can then be combined into a single regular expression:

/(\d)(?:.|(?:.|\n){9}|(?:.|\n){6})?\1\1|(\d)\2(?:.|(?:.|\n){9}|(?:.|\n){6})?\2|(\d)(?:.|\n){7}\3(?:.|(?:.|\n){9})\3|(\d)(?:.|(?:.|\n){9})\4(?:.|\n){7}\4|(\d)(?:(?:.|\n){7,9}|(?:.|\n){17})\5(?:.|\n){8}\5|(\d)(?:.|\n){8}\6(?:(?:.|\n){7,9}|(?:.|\n){17})\6/

Which just needs to be tested against the input.

Test Cases

Some test cases which other people might find useful (doesn't comply with the input format of using only digits 1-7 but that's easily corrected and is only an 8x4 grid - since that is the minimum required for a test of all the valid inputs).

In the format of a map from input string to which of the 16 regular expressions above it matches.

Tests={
    "12345678\n34567812\n56781234\n78123456": -1, // No Match
    "12345678\n34969912\n56781234\n78123456": 1,    // 3-in-a-row horizontally after left-most shifts right 
    "12345678\n34567812\n59989234\n78123456": 2,    // 3-in-a-row horizontally after right-most shifts left
    "12345978\n34567899\n56781234\n78123456": 3,    // 3-in-a-row horizontally after left-most shifts down
    "12345978\n34569892\n56781234\n78123456": 4,    // 3-in-a-row horizontally after middle shifts down
    "12345678\n34967812\n99781234\n78123456": 5,    // 3-in-a-row horizontally after right-most shifts down
    "12399678\n34967812\n56781234\n78123456": 6,    // 3-in-a-row horizontally after left-most shifts up
    "12345678\n34597912\n56789234\n78123456": 7,    // 3-in-a-row horizontally after middle shifts up
    "12345998\n34567819\n56781234\n78123456": 8,    // 3-in-a-row horizontally after right-most shifts up
    "12945678\n34597812\n56791234\n78123456": 9,    // 3-in-a-row vertically after top shifts right
    "12349678\n34597812\n56791234\n78123456": 9,    // 3-in-a-row vertically after top shifts left
    "12345978\n34569812\n56781934\n78123456": 10,   // 3-in-a-row vertically after middle shifts right
    "92345678\n39567812\n96781234\n78123456": 11,   // 3-in-a-row vertically after middle shifts left
    "12945678\n34967812\n59781234\n78123456": 12,   // 3-in-a-row vertically after bottom shifts right
    "12349678\n34569812\n56781934\n78123456": 13,   // 3-in-a-row vertically after bottom shifts left
    "12395678\n34567812\n56791234\n78193456": 14,   // 3-in-a-row vertically after top shifts down
    "12345698\n34567892\n56781234\n78123496": 15,   // 3-in-a-row vertically after bottom shifts up
    "12345678\n34567899\n96781234\n78123456": -1,   // No match - Matches (.)\1.\1 but not 3 in a row
    "12345679\n99567812\n56781234\n78123456": -1,   // No match - Matches (.).\1\1 but not 3 in a row
};

Edit 1

Replace \ds with . - saves 6 characters.

Edit 2

Replace (?:.|\n) with [\s\S] and removed extra non-capturing groups and updated back references (as suggested by m-buettner) and added in yes/no output.

Edit 3

Added ECMAScript 6 solution to build the individual Regular Expressions from a Base-18 string.
Removed the tests for 3-in-a-row horizontally (as suggested by m-buettner).

Edit 4

Added another (shorter) solution and two more non-matching tests cases.

Edit 5

Shortened original solution by replacing newlines with a non-numeric character (as suggested by VadimR).

Edit 6

Shortened original solution by combining bits of the regular expression (as suggested by VadimR).

Python 383

Just a single* line of Python!

a=[list(l)for l in raw_input().split('\n')];z=any;e=enumerate;c=lambda b:z(all(p==b[y+v][x+u]for(u,v)in o)for y,r in e(b[:-2])for x,p in e(r[:-2])for o in [[(0,1),(0,2)],[(1,0),(2,0)]]);print z(c([[q if(i,j)==(m,n)else a[m][n]if(i,j)==(y+1,x+1)else p for j,p in e(r)]for i,r in e(a)])for y,t in e(a[1:-1])for x,q in e(t[1:-1])for n,m in((x+u,y+v)for u,v in[(1,0),(1,2),(0,1),(2,1)]))

*Well, with semicolons, but that's still non-trivial in python (python one-liners are fun!)

APL (Dyalog Unicode), 71 bytes

'no' 'yes'⊃⍨{∨/∊{((3≤1⊥⊃=⊢)¨4,/⍵)({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)}¨⍵(⍉⍵)}↑{⍞}¨⍳8

Try it online!

Nice challenge to show off some extreme array-processing capabilities of APL.

Without the I/O restriction, it is 55 52 bytes as a function taking a 8-by-8 matrix of chars and returning a boolean (therefore without 7-bytes pre-processing ↑{⍞}¨⍳8 and 12-bytes post-processing 'no' 'yes'⊃⍨):

{∨/∊{((3≤1⊥⊃=⊢)¨4,/⍵)({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)}¨⍵(⍉⍵)}

Try it online!

The basic idea is that we can test for 1x4 and 2x3 sub-boxes if each sub-box has a valid Bejeweled move:

(1x4 box)
OxOO    OOxO

(2x3 box)
OOx     OxO     xOO
xxO     xOx     Oxx

Oxx     xOx     xxO
xOO     OxO     OOx

For 1x4 boxes, we can check if the first item appears at least 3 times. For 2x3 boxes, we can check if at least one item in the first column appears in every column. For 4x1 and 3x2 boxes, we can check for 1x4 and 2x3 on the board transposed.

How it works: the code

'no' 'yes'⊃⍨{∨/∊{((3≤1⊥⊃=⊢)¨4,/⍵)({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)}¨⍵(⍉⍵)}↑{⍞}¨⍳8

↑{⍞}¨⍳8  ⍝ Take 8 lines of input and form a 8x8 matrix
     ⍳8  ⍝ A dummy length-8 vector
 {⍞}¨    ⍝ Map "take a line of input" over the dummy vector
↑        ⍝ Promote a vector of vectors to a matrix (M)

{∨/∊{...}¨⍵(⍉⍵)}  ⍝ Pass the matrix onto the inline function
          ⍵(⍉⍵)   ⍝ M and transpose of M
    {...}¨        ⍝ Test over M and transposed M for Bejeweled moves
                  ⍝ (explained below)
 ∨/∊              ⍝ Enlist all booleans and check if any is true

{((3≤1⊥⊃=⊢)¨4,/⍵)({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)}  ⍝ Test over all possible sub-boxes
((3≤1⊥⊃=⊢)¨4,/⍵)  ⍝ Test over 1x4 boxes
           4,/⍵   ⍝ Extract 1x4 boxes
 (    ⊃=⊢)¨       ⍝ For each box, test if each item equals first item
  3≤1⊥            ⍝ Is the count at least 3?
({∨⌿∧⌿∨⌿⍵∘.=⊣/⍵}⌺2 3⊢⍵)  ⍝ Test over 2x3 boxes
 {             }⌺2 3⊢⍵   ⍝ Ditto
        ⍵∘.=⊣/⍵          ⍝ Compare each item with the first column
  ∨⌿                     ⍝ Does there exist an item from the first column
    ∧⌿                   ⍝ that appears on every column
      ∨⌿                 ⍝ at least once?

'no' 'yes'⊃⍨  ⍝ Map 0/1 to no/yes respectively

Determine if a move exists in a Bejeweled/match 3 game

Original Solution: JavaScript - 261 255 228 227 179 153 Characters

3^rd Solution: JavaScript (ECMAScript 6) - 178 Characters

2^nd Solution: JavaScript (ECMAScript 6) - 204 Characters

Python 383

APL (Dyalog Unicode), 71 bytes

How it works: the code

Tags:

Grid

Code Golf

Game

Related

Recent Posts

Determine if a move exists in a Bejeweled/match 3 game

Original Solution: JavaScript - 261 255 228 227 179 153 Characters

3rd Solution: JavaScript (ECMAScript 6) - 178 Characters

2nd Solution: JavaScript (ECMAScript 6) - 204 Characters

Python 383

APL (Dyalog Unicode), 71 bytes

How it works: the code

Tags:

Grid

Code Golf

Game

Related

3^rd Solution: JavaScript (ECMAScript 6) - 178 Characters

2^nd Solution: JavaScript (ECMAScript 6) - 204 Characters