Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Background

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.

Task

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.

Input

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.

Output

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.

Rules

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.

Examples

Input:

12314131
13224145
54762673
61716653
61341144
23453774
27645426
75575656

Output: yes

Input:

35261546
76421754
15743271
62135642
35617653
64565476
54427254
15635465

Output: no

See MT0's answer below for additional test cases.

share|improve this question
    
Is it just rows, or columns too. –  TheDoctor May 2 at 2:18
    
@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. –  bdr9 May 2 at 2:20
    
@bdr9 you might want to edit that in –  Jan Dvorak May 2 at 2:24
    
@JanDvorak Done. –  bdr9 May 2 at 2:26
    
Also might want to edit in if 4+ in a row is allowed. –  Quincunx May 2 at 5:11

5 Answers 5

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.

3rd 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 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

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 (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:

/(\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).
share|improve this answer
1  
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. –  bdr9 May 2 at 12:35
    
Thanks for the additional test cases, I added a link to your answer so other people can see them. –  bdr9 May 2 at 12:50
    
Whoa. +1 for regex –  Zove Games May 2 at 13:01
    
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. –  VadimR May 2 at 15:26
1  
@VadimR Thanks but you can go even further replacing .{8}|.{9} with .{8,9} and .{7}|.{8} with .{7,8} –  MT0 May 5 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!)

share|improve this answer
1  
Upvoted for incomprehensible comprehensions :) –  ali0sha May 2 at 10:21

Python3, 314B

import itertools as T,copy
r=[]
K=range(8)
J=[list(input())for w in K]
P=T.product
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]):
 t=j+1-x
 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)))
r+=["no"]
print(r[0])

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:

absdefgh
sdkljahs
lsdfjasd
fjdhsdas
dkjhfasd
sdfhaskd
sdkfhkas
weriuwqe

and it will return yes.

Annotations

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())
P=T.product
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
 t=j+1-x
 if i+x<8and t<8: 
            # don't want out-of-bounds errors at the edges
  B=copy.deepcopy(J) 
            # preserve the reference array
  B[i][j],B[i+x][t]=B[i+x][t],B[i][j] 
            # do the switch
  r+=f(B)+f(list(zip(*B))) 
            # 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
share|improve this answer

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();
        if(i!=0){
            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
            if(testBoard(newboard))yay();
            newboard=board.clone();
        }
        if(i!=board.length-1){
            newboard[i+1][j]=newboard[i+1][j]^newboard[i][j];
            newboard[i][j]=newboard[i+1][j]^newboard[i][j];
            newboard[i+1][j]=newboard[i+1][j]^newboard[i][j];
            if(testBoard(newboard))yay();
            newboard=board.clone();
        }
        if(j!=0){
            newboard[i][j-1]=newboard[i][j-1]^newboard[i][j];
            newboard[i][j]=newboard[i][j-1]^newboard[i][j];
            newboard[i][j-1]=newboard[i][j-1]^newboard[i][j];
            if(testBoard(newboard))yay();
            newboard=board.clone();
        }
        if(j!=board[i].length-1){
            newboard[i][j+1]=newboard[i][j+1]^newboard[i][j];
            newboard[i][j]=newboard[i][j+1]^newboard[i][j];
            newboard[i][j+1]=newboard[i][j+1]^newboard[i][j];
            if(testBoard(newboard))yay();
            newboard=board.clone();
        }
    }
}
nay();
share|improve this answer
    
Hah I actually missed the first post by 10 minutes. I kinda like this though... –  Zove Games May 2 at 5:03
    
Ah, exact same method I used (naive but small code!). +1 for being much more descriptive than me –  KSab May 2 at 5:24
    
I wonder if there's a more efficient algorithm... –  Zove Games May 2 at 11:27

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.

:a
$!N
s/\n/ /g
ta
:b
/^((\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
s/\w(\w*)/\1/g
tb
c\no

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'
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.