In Bejeweled and similar games, the player must swap any two adjacent gems (no diagonals) in an 8x8 grid of gems in order to match three of the same color in a row. The gems can be matched horizontally or vertically. Gameplay continues until there no move exists that can be made resulting in three in a row, at which point the game is over.


The goal is to write a program that determines whether a game of Bejeweled is not over yet. In other words, it must check to see if there is a possible move that makes at least three in a row. There can be more than three gems in a row and it is still a valid move.


Your program must accept via standard input an 8x8 representation of a Bejeweled grid. Each of the seven gem colors will be represented by a digit from 1 to 7. Each line will contain one row, and 8 lines, each consisting of 8 digits, will be input. See the examples. You can assume that the input will always follow this format, and will never already contain three in a row.


The program must then output (to standard output) yes or no depending on whether or not at least one valid move exists that would result in three or more gems in a row. Your program must not output anything other than a single instance of either yes or no.


Your program must not use any external files or resources, command-line arguments, or require a certain file name. The program with the least number of bytes in its source code wins.




Output: yes



Output: no

See MT0's answer below for additional test cases.

  • \$\begingroup\$ Is it just rows, or columns too. \$\endgroup\$
    – TheDoctor
    Commented May 2, 2014 at 2:18
  • \$\begingroup\$ @TheDoctor Columns too. When I use the phrase "three in a row" I mean that they must be lined up in a horizontal or vertical direction. \$\endgroup\$
    – bdr9
    Commented May 2, 2014 at 2:20
  • \$\begingroup\$ @bdr9 you might want to edit that in \$\endgroup\$ Commented May 2, 2014 at 2:24
  • \$\begingroup\$ @JanDvorak Done. \$\endgroup\$
    – bdr9
    Commented May 2, 2014 at 2:26
  • \$\begingroup\$ Also might want to edit in if 4+ in a row is allowed. \$\endgroup\$
    – Justin
    Commented May 2, 2014 at 5:11

9 Answers 9


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


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.

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


I took the 2nd 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 ith 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).

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


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).


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

    /(\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 (0th) and vertically (part of the 9th) 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:


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.

    "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).
  • 1
    \$\begingroup\$ Nice solution! I wouldn't have thought that regex could work. Please include the ?'yes':'no' in your character count for fairness, because it is in the requirements and everyone else is using it. \$\endgroup\$
    – bdr9
    Commented May 2, 2014 at 12:35
  • \$\begingroup\$ Thanks for the additional test cases, I added a link to your answer so other people can see them. \$\endgroup\$
    – bdr9
    Commented May 2, 2014 at 12:50
  • \$\begingroup\$ Whoa. +1 for regex \$\endgroup\$
    – DankMemes
    Commented May 2, 2014 at 13:01
  • \$\begingroup\$ H-mm, no modifier in JS for . to match any character including newline? With Perl, combined regexp is mere 129 bytes string (which, being lazy, I compiled with Regexp::Assemble), so the whole Perl program is about 150 bytes. \$\endgroup\$ Commented May 2, 2014 at 15:26
  • 1
    \$\begingroup\$ @VadimR Thanks but you can go even further replacing .{8}|.{9} with .{8,9} and .{7}|.{8} with .{7,8} \$\endgroup\$
    – MT0
    Commented May 5, 2014 at 0:18

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!)

  • 4
    \$\begingroup\$ Upvoted for incomprehensible comprehensions :) \$\endgroup\$
    – alyx-brett
    Commented May 2, 2014 at 10:21

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

Perl, 114 96 95 93 92 87 86 85 bytes

Includes + for -a0p

Run with the input on STDIN:



#!/usr/bin/perl -a0p

This combines a single direction horizontal regex solution with rotations


In this solution I will repeatedly rotate and do the following 4 tests:

/(.).\1\1/,      // 3-in-a-row horizontally after left-most shifts right
/(.)\C{9}\1\1/,  // 3-in-a-row horizontally after left-most shifts down
/(.)\C{7}\1.\1/, // 3-in-a-row horizontally after middle shifts down
/(.)\C{6}\1\1/,  // 3-in-a-row horizontally after right-most shifts down

Where \C is "any character" (unlike . this includes newline). Except that \C is deprecated and leads to warnings, so I use \H (non-horizontal space) instead which is good enough to capture all digits and newline.

After 4 rotation this will have done all 16 tests that are needed

-p                            Read lines from STDIN, print $_ at the end
-0                            No line ending => slurp ALL of STDIN
-a                            Split $_ into @F. Since there are no spaces
                              on the rows this means each element of @F is
                              1 row

    s%.%chop$F[$i++&7]%eg     Replace each row by the removed last column
                              This is therefore a left rotation. Very short
                              but at the cost of using @F. To make sure that
                              @F gets refilled from $_ each time I won't be
                              able to use while, until, eval or do$0 for the
                              loops but have to use redo. That costs a few
                              bytes but less than having to do my own split
$i/                      >3   The previous regex replacement always
                              returns 64 and each time through the loop $i is
                              increased by 64. So if this division reaches
                              4 all rotations have been done

/(.)((.|\H{6}|\H{9})\1|\H{7}\1.)\1/ This is the 4 regexes mentioned above
  ||redo                      Stop the loop if the regex matches or we
                              rotated 4 times
$_=$1?yes:n.o                If the regex matched $1 will be one of the
                              color digits (which cannot be 0) and this will
                              assign "yes" to $_. If the regex didn't match
                              in 4 times $1 will get its value from the last
                              succesful regex in scope which will be the one
                              from the rotation, but that one doesn't have
                              any () so $1 will be unset. So in case there
                              is no move $_ will be set to "no" (which needs
                              to be constructed because "no" is a keyword)

Node.js - Naive solution - 905 bytes

Well, no answers yet so I'll post a really naive solution in Node.js

It goes through every possible move and then tests the resulting board to see if there's 3 in a row.

Golfed (with google closure compiler) (some hacky stuff in there like !0 and !1; I'm not even sure what it did with my XOR swap)

Array.prototype.a=function(){for(var f=[],d=0;d<this.length;d++)f[d]=this[d].a?this[d].a():this[d];return f};for(var a=[],b=0;8>b;b++)a[b]=[];for(b=2;b<process.argv.length;b++)for(var c=process.argv[b].split(""),e=0;e<c.length;e++)a[b-2][e]=parseInt(c[e],10);function h(){for(var d=l,f=0;f<d.length-2;f++)for(var g=0;g<d[f].length-2;g++){var k=d[f][g];if(k==d[f+1][g]&&k==d[f+2][g]||k==d[f][g+1]&&k==d[f][g+2])return!0}return!1}function m(){console.log("yes");process.exit()}for(b=0;b<a.length;b++)for(e=0;e<a[b].length;e++){var l=a.a();0!=b&&(l[b-1][e]^=l[b][e],l[b][e]^=l[b-1][e],l[b-1][e]^=l[b][e],h()&&m(),l=a.a());b!=a.length-1&&(l[b+1][e]^=l[b][e],l[b][e]^=l[b+1][e],l[b+1][e]^=l[b][e],h()&&m(),l=a.a());0!=e&&(l[b][e-1]^=l[b][e],l[b][e]^=l[b][e-1],l[b][e-1]^=l[b][e],h()&&m(),l=a.a());e!=a[b].length-1&&(l[b][e+1]^=l[b][e],l[b][e]^=l[b][e+1],l[b][e+1]^=l[b][e],h()&&m(),l=a.a())}console.log("no");

Note that I wrote this all on my mobile and don't have time to test it or anything. Comment if you see any bugs, I'll check it myself later.

The pre-golfed human readable version

// set it up
Array.prototype.clone = function() {
    var arr = [];
    for( var i = 0; i < this.length; i++ ) {
        if( this[i].clone ) {
             arr[i] = this[i].clone();
        } else {
             arr[i] = this[i];
var board=[];
for(var i=0;i<8;i++)board[i]=[];
for(var i=2;i<process.argv.length;i++){
    var row=process.argv[i].split("");
    for(var j=0;j<row.length;j++)board[i-2][j]=parseInt(row[j], 10);
// function to test
function testBoard(arr){
    for(var i=0;i<arr.length-2;i++){
        for(var j=0;j<arr[i].length-2;j++){
            var val=arr[i][j];
            if(val==arr[i+1][j] && val==arr[i+2][j])return true;
            if(val==arr[i][j+1] && val==arr[i][j+2])return true;
    return false;
// functions to exit
function yay(){console.log("yes");process.exit();}
function nay(){console.log("no");}
// super slow naive solution time
for(var i=0;i<board.length;i++){
    for(var j=0;j<board[i].length;j++){
        var newboard=board.clone();
            newboard[i-1][j]=newboard[i-1][j]^newboard[i][j];// whoa, it's a
            newboard[i][j]=newboard[i-1][j]^newboard[i][j];  // cool algorithm
            newboard[i-1][j]=newboard[i-1][j]^newboard[i][j];// at least this 
                                                             // isn't all naive
  • \$\begingroup\$ Hah I actually missed the first post by 10 minutes. I kinda like this though... \$\endgroup\$
    – DankMemes
    Commented May 2, 2014 at 5:03
  • \$\begingroup\$ Ah, exact same method I used (naive but small code!). +1 for being much more descriptive than me \$\endgroup\$
    – KSab
    Commented May 2, 2014 at 5:24
  • \$\begingroup\$ I wonder if there's a more efficient algorithm... \$\endgroup\$
    – DankMemes
    Commented May 2, 2014 at 11:27

05AB1E, 51 bytes


Port of the approach used by @Bubbler in his APL answer, so make sure to upvote him!!

Try it online.


„€¸…Ü                 # Push dictionary string "no yes"
     #                # Split it on spaces: ["no","yes"]
|                     # Push all input-lines as list
 €S                   # Convert each line to a list of digits
   2F                 # Loop 2 times:
     Ð                #  Triplicate the matrix
      €               #  For each row:
       ü3             #   Create overlapping triplets
         ø            #  Zip/transpose; swapping rows/columns
          €           #  For each overlapping 3-sized column:
           ü2         #   Create overlapping pairs
     s                #  Swap to get the initial matrix again
      €               #  For each row:
       ü4             #   Create overlapping quadruplets
         «            #  Merge this list of 4x1 blocks to the list of 2x3 blocks
     s                #  Swap again to get the initial matrix
      ø               #  Zip/transpose; swapping rows/columns
    }\                # After the loop: discard the top item
      «               # Merge the two lists together
       €`             # Flatten it one level down
         ʒ            # Filter this list of 4x1 and 2x3 blocks by:
          Ð           #  Triplicate the block
           g          #  Get its length (either 4 or 2)
            ;i        #  If this length is 2:
              ø       #   Zip/transpose; swapping rows/columns,
                      #   to make the 2x3 block a 3x2 block
               ć      #   Extract head; pop and push the remainder 2x2 columns and
                      #   first 2x1 column separated to the stack
                δ     #   Apply double-vectorized:
                 å    #    Check if the value is in the list
                  ø   #   Zip/transpose; swapping rows/columns,
                      #   so the checks per value are in the same inner list
                   P  #   Check for both lists whether all checks were truthy
                    à #   And check if either of the two checks is truthy
             ë        #  Else (the length is 4 instead):
              ¢       #   Count how many times each value occurs in the 4x1 block
               3å     #   And check if the counts contain a 3
         ]            # Close both the if-else statement and filter
          g           # Get the amount of remaining blocks
           Ā          # Check that at least one block is remaining
                      # (1 if truthy; 0 if falsey)
            è         # And use that to index into the ["no","yes"] list
                      # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to use the dictionary?) to understand why „€¸…Ü is "no yes".


Python3, 314B

import itertools as T,copy
J=[list(input())for w in K]
f=lambda A:["yes"for b in[A[m][n:]for m,n in P(K,K[:6])]if b[0]==b[1]==b[2]]
for i,j,x in P(K,K,[0,1]):
 if i+x<8and t<8:B=copy.deepcopy(J);B[i][j],B[i+x][t]=B[i+x][t],B[i][j];r+=f(B)+f(list(zip(*B)))

Change the 8, the 5 on line 6, and the 8s on line 9 to handle arbitrarily large input sizes; also doesn't care what each value is, so you can feed it:


and it will return yes.


import itertools as T,copy 
            # itertools.product is going to save us lots of for loops
r=[]        # result
K=range(8)  # we can use range(8) everywhere, so this saves more than the usual R=range
J=[list(input())for w in K] 
            # input handling: keep everything as a length-1 string to avoid map(int,input())
f=lambda A:["yes"for b in[A[m][n:]for m,n in P(K,K[:6])]if b[0]==b[1]==b[2]] 
            # check the condition horiontally only. K[:6] is the same as range(5)
            # A[m][n:n+3] would be neater, but not actually needed
for i,j,x in P(K,K,[0,1]): 
            # <3 itertools.product! 3 for-loops without it.
            # NB we're only going right and downwards
 if i+x<8and t<8: 
            # don't want out-of-bounds errors at the edges
            # preserve the reference array
            # do the switch
            # do the test. you could end up with lots of 'yes's in r.
            # zip(*B) takes the transpose, so that f checks the columns too
r+=["no"]   # happens to ensure that r is nonempty
print(r[0]) # only prints no if r was empty before the last line

GNU sed 255+2 = 257B

I thought this wasn't going to be as good as python but it is now :-/ I've been without internet access today so I occupied myself with solving this in sed :). Needs to be called with the -r flag, i.e. sed -rf command.sed < input so I added 2 to my score.

s/\n/ /g
/^((\w)(\w\2\2|\2\w\2|\w\2\w* \w\2|\2\w* \w\w\2|\w* (\2\w* \w* \2|\w* \2\w* \2|\w\2\2|\w\2\w* \2|\2\w* \w\2|\w\2\w* \w\2))|\w((\w)(\w* \6\w\6|\6\w* \6|\w* (\6\w \w\6|\w\6\w* \6|\6\w* \6))|\w(\w)\w* \9\9))/c\yes

How it works:

  1. Read the grid into a single line of space-separated characters
  2. Use the motherload regex to find out whether there's a match in the first column* - if yes, swap the entire line for 'yes' (ending the program)
  3. Strip the first character from each column and goto 2 if we did
  4. If we didn't (the line is empty) replace the whole line with 'no'

Ruby, 201 bytes

I was disappointed not to see any solutions to this great challenge that don't use a regex or brute force (although those are great), so I wrote one. It takes input on STDIN.

The core bitwise arithmetic algorithm is derived from this fantastic answer on Game Development Stack Exchange by @leander.


Ruby lambda, 181 bytes

Here it is as a lambda that takes a string and returns true or false:


See it on repl.it: https://repl.it/ColJ/2

Ungolfed & explanation

  (?1..?9).any? {|n|
    a = [0] * 19

    s.scan(n) {
      i = $`.size
      a[i/9+1] += 2**(i%9)
      a[i%9+10] += 2**(i/9)

    a.each_cons(3).any? {|x,y,z|
      q = y & y << 1
      l = q << 1
      q >>= 2
      y & (l << 1 | q >> 1) |
        (q | l | (y & y << 2) >> 1) &
        (x | z) > 0

The code iterates over the digits "1" to "9." Each iteration has two discrete steps:

The first step is board transformation, which you can see in the s.scan(n) block in the ungolfed code. It transforms the board into an array of 8 integers, one for each row, by treating matching digits as 1s and all others as 0s in a binary string. For example, take the row 12231123. In the first iteration, this will become the binary string 10001100 (all 1s become—er, stay—1s and all other digits become 0s), which is the decimal number 140. In the second iteration the same row becomes 01100010 (all 2s become 2s and all other digits become 0s), or decimal 98.

It simultaneously performs a second transformation, which is the same as the first but with the board rotated 90 degrees. This lets us use the same logic for making horizontal matches as vertical ones. For simplicity, it concatenates the two boards into a single long one with a zero at the beginning, middle (to separate the two boards), and end for padding.

The second step is searching for possible matches, which you can see in the each_cons(3).any? block. The transformed rows (which are now 8-bit integers) are checked in (overlapping) groups of three rows (x, y, z) using bitwise arithmetic. Each group is checked to see if a match can be made in row y, either by shifting a piece in row y or by shifting a piece into y from x or z. Since there is a zero "row" before and after both the original and rotated boards' rows, we don't have to check if we're on the first or last row of a board.

If no matches were found, it continues to the next iteration.


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.