Determinar si existe un movimiento en un juego Bejeweled / match 3

20

Antecedentes

En Bejeweled y juegos similares, el jugador debe intercambiar dos gemas adyacentes (sin diagonales) en una cuadrícula de gemas de 8x8 para que coincida con tres del mismo color en una fila. Las gemas se pueden combinar horizontal o verticalmente. La jugabilidad continúa hasta que no exista ningún movimiento que pueda realizarse, lo que resulta en tres seguidos, momento en el cual el juego termina.

Tarea

El objetivo es escribir un programa que determine si un juego de Bejeweled aún no ha terminado. En otras palabras, debe verificar para ver si hay un posible movimiento que haga al menos tres seguidos. Puede haber más de tres gemas seguidas y sigue siendo un movimiento válido.

Entrada

Su programa debe aceptar mediante entrada estándar una representación 8x8 de una cuadrícula Bejeweled. Cada uno de los siete colores de gemas estará representado por un dígito del 1 al 7. Cada línea contendrá una fila y se ingresarán 8 líneas, cada una con 8 dígitos. Ver los ejemplos. Puede suponer que la entrada siempre seguirá este formato y nunca contendrá tres seguidas.

Salida

Luego, el programa debe generar (a la salida estándar) yeso nodependiendo de si existe o no al menos un movimiento válido que resulte en tres o más gemas seguidas. Su programa no debe generar nada más que una sola instancia de yeso no.

Reglas

Su programa no debe usar ningún archivo o recurso externo, argumentos de línea de comandos o requerir un nombre de archivo determinado. El programa con el menor número de bytes en su código fuente gana.

Ejemplos

Entrada:

12314131
13224145
54762673
61716653
61341144
23453774
27645426
75575656

Salida: yes

Entrada:

35261546
76421754
15743271
62135642
35617653
64565476
54427254
15635465

Salida: no

Consulte la respuesta de MT0 a continuación para ver casos de prueba adicionales.

code-golf game grid bdr9
fuente
¿Son solo filas o columnas también?
TheDoctor
@TheDoctor Columns también. Cuando uso la frase "tres en una fila" quiero decir que deben estar alineados en una dirección horizontal o vertical.
bdr9
@ bdr9 es posible que desee editar eso en
John Dvorak
@ JanDvorak Hecho.
bdr9
También es posible que desee editar si se permite 4+ en una fila.
Justin

Respuestas:

12

Solución original: JavaScript - 261 255 228 227 179 153 caracteres

/(\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'

Suponiendo que la cadena a probar está en la variable s(para que sea una función, fluego agregue f=s=>al comienzo del código o, de lo contrario, tome la entrada de un indicador y luego reemplace scon prompt()).

Las salidas son a la consola.

3 RD Solución: JavaScript (ECMAScript 6) - 178 caracteres

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'

Tomé la segunda solución, a continuación, (que usa expresiones regulares para verificar los caracteres en ciertas configuraciones) y la modifiqué para verificar la cadena de caracteres idénticos en las mismas configuraciones sin usar expresiones regulares.

La cadena Base-36 "2313ab1b8a2a78188h9haj9j8iaiir9r"proporciona pares de desplazamientos para verificar, es decir, el par 23da como resultado la comprobación de si el carácter i th es idéntico al carácter (i + 2) th y al carácter (i + 3) th (el equivalente de la expresión regular (.).\1\1- con algunas comprobaciones adicionales para garantizar que el carácter no idéntico no sea una nueva línea).

2 nd Solución: JavaScript (ECMAScript 6) - 204 caracteres

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'

Crea múltiples expresiones regulares (ver más abajo para más detalles) usando pares de valores tomados de la cadena Base-18 10907160789879h8y toma ORtodas las pruebas. Para reducirlo aún más, puede observar que las expresiones regulares vienen en pares donde una es la "inversa" de la otra (ignorando las expresiones regulares para 3 en una fila horizontal y verticalmente ya que el OP indica que nunca estarán presentes) si desea agregar esas pruebas nuevamente en el anexo 0088a la cadena Base-18).

Explicación

Comience con 16 expresiones regulares que cubren todas las configuraciones posibles de movimientos válidos:

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
];

( Nota: las expresiones regulares para 3 en una fila horizontalmente ( 0º ) y verticalmente (parte del noveno ) son irrelevantes ya que el OP establece que las entradas que coincidan con estas nunca estarán presentes ) .

Probar cada uno de ellos contra la entrada determinará si se puede encontrar un movimiento válido de esa configuración.

Sin embargo, las expresiones regulares se pueden combinar para dar estos 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

Estos se pueden combinar en una sola expresión regular:

/(\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/

Que solo necesita ser probado contra la entrada.

Casos de prueba

Algunos casos de prueba que otras personas pueden encontrar útiles (no cumple con el formato de entrada de usar solo los dígitos 1-7, pero eso se corrige fácilmente y es solo una cuadrícula de 8x4, ya que es el mínimo requerido para una prueba de todas las entradas válidas )

En el formato de un mapa desde la cadena de entrada a cuál de las 16 expresiones regulares anteriores coincide.

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
};

Editar 1

Reemplazar \ds con .: guarda 6 caracteres.

Editar 2

Reemplace (?:.|\n)con [\s\S]y elimine grupos no capturadores adicionales y referencias de respaldo actualizadas (como lo sugiere m-buettner ) y agregue en la salida sí / no.

Editar 3

  • Se agregó la solución ECMAScript 6 para construir las expresiones regulares individuales a partir de una cadena Base-18.
  • Se eliminaron las pruebas para 3 en fila horizontalmente (como lo sugiere m-buettner ).

Editar 4

Se agregó otra solución (más corta) y dos casos de pruebas no coincidentes más.

Editar 5

  • Solución original acortada mediante la sustitución de nuevas líneas con un carácter no numérico (como lo sugiere VadimR ).

Editar 6

  • Solución original acortada mediante la combinación de bits de la expresión regular (como lo sugiere VadimR ).
MT0
fuente
1
Buena solución! No hubiera pensado que regex podría funcionar. Incluya el ?'yes':'no'recuento en su personaje para ser justos, porque está en los requisitos y todos los demás lo están usando.
bdr9
Gracias por los casos de prueba adicionales, agregué un enlace a su respuesta para que otras personas puedan verlos.
bdr9
Whoa +1 para
expresiones
H-mm, no hay modificador en JS para .que coincida con cualquier personaje, incluida la nueva línea Con Perl, la expresión regular combinada es solo una cadena de 129 bytes (que, siendo flojo, compilé con Regexp :: Assemble ), por lo que todo el programa Perl tiene aproximadamente 150 bytes.
user2846289
1
@VadimR Gracias, pero puedes ir aún más lejos reemplazando .{8}|.{9}con .{8,9}y .{7}|.{8}con.{7,8}
MT0
3

Python 383

¡Solo una línea * de 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)]))

* Bueno, con punto y coma, pero eso todavía no es trivial en Python (¡las frases de Python son divertidas! )

KSab
fuente
3
Votado por una comprensión incomprensible :)
alexander-brett
2

Node.js - Solución ingenua - 905 bytes

Bueno, todavía no hay respuestas, así que publicaré una solución realmente ingenua en Node.js

Realiza todos los movimientos posibles y luego prueba el tablero resultante para ver si hay 3 seguidos.

Golfé (con el compilador de cierre de Google) (algunas cosas extrañas como! 0 y! 1; ni siquiera estoy seguro de lo que hizo con mi intercambio XOR)

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");

Tenga en cuenta que escribí todo esto en mi móvil y no tengo tiempo para probarlo ni nada. Comenta si ves algún error, lo comprobaré yo mismo más tarde.

La versión legible humana pre golf

// 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();
DankMemes
fuente
Ja, en realidad me perdí el primer post por 10 minutos. Sin embargo, me gusta un poco ...
DankMemes
Ah, exactamente el mismo método que usé (¡código ingenuo pero pequeño!). +1 por ser mucho más descriptivo que yo
KSab
Me pregunto si hay un algoritmo más eficiente ...
DankMemes
2

Perl, 114 96 95 93 92 87 86 85 bytes

Incluye + para -a0p

Ejecutar con la entrada en STDIN:

bejeweled.pl
12314131
13224145
54762673
61716653
61341144
23453774
27645426
75575656
^D

bejeweled.pl:

#!/usr/bin/perl -a0p
$i/s%.%chop$F[$i++&7]%eg>3|/(.)((.|\H{6}|\H{9})\1|\H{7}\1.)\1/||redo;$_=$1?yes:n.o

Esto combina una solución de expresión regular horizontal de una sola dirección con rotaciones

Explicación:

En esta solución, rotaré repetidamente y haré las siguientes 4 pruebas:

/(.).\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

Dónde \Cestá "cualquier personaje" (a diferencia de .esto incluye nueva línea). Excepto que \Cestá en desuso y da lugar a advertencias, por lo que uso \H(espacio no horizontal) en su lugar, que es lo suficientemente bueno como para capturar todos los dígitos y la nueva línea.

Después de 4 rotaciones, esto habrá realizado las 16 pruebas necesarias

-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)
Ton Hospel
fuente
1

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

Cambie el 8, el 5 en la línea 6 y los 8 en la línea 9 para manejar tamaños de entrada arbitrariamente grandes; tampoco le importa cuál es cada valor, por lo que puede alimentarlo:

absdefgh
sdkljahs
lsdfjasd
fjdhsdas
dkjhfasd
sdfhaskd
sdkfhkas
weriuwqe

y volverá yes.

Anotaciones

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
alexander-brett
fuente
1

GNU sed 255 + 2 = 257B

Pensé que esto no iba a ser tan bueno como Python, pero ahora es: - / He estado sin acceso a Internet hoy, así que me ocupé de resolver esto en sed :). Debe llamarse con la bandera -r, es decir sed -rf command.sed < input, agregué 2 a mi puntaje.

: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

Cómo funciona:

  1. Lea la cuadrícula en una sola línea de caracteres separados por espacios
  2. Use la expresión regular motherload para averiguar si hay una coincidencia en la primera columna *: en caso afirmativo, cambie la línea completa por 'sí' (finalizando el programa)
  3. Tira el primer personaje de cada columna y pasa a 2 si lo hicimos
  4. Si no lo hicimos (la línea está vacía) reemplace toda la línea con 'no'
alexander-brett
fuente
1

Ruby, 201 bytes

Me decepcionó no ver ninguna solución a este gran desafío que no utiliza una expresión regular o fuerza bruta (aunque son geniales), así que escribí una. Toma entrada en STDIN.

El algoritmo aritmético a nivel de bit se deriva de esta fantástica respuesta en Game Development Stack Exchange de @leander.

s=$<.read
$><<(?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}}?"yes":"no"

Ruby lambda, 181 bytes

Aquí es como una lambda que toma una cadena y devuelve trueo false:

->s{(?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}}}

Véalo en repl.it: https://repl.it/ColJ/2

Sin golfos y explicación

->s{
  (?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
    }
  }
}

El código itera sobre los dígitos "1" a "9." Cada iteración tiene dos pasos discretos:

El primer paso es la transformación de la placa, que puede ver en el s.scan(n)bloque en el código no protegido. Transforma el tablero en una matriz de 8 enteros, uno para cada fila, tratando los dígitos coincidentes como 1 y todos los demás como 0 en una cadena binaria. Por ejemplo, toma la fila 12231123. En la primera iteración, esto se convertirá en la cadena binaria 10001100(todos los 1 se convierten en, er, se quedan 1 y todos los demás dígitos se convierten en 0), que es el número decimal 140. En la segunda iteración, la misma fila se convierte 01100010(los 2 se convierten en 2 y todos los demás dígitos se convierten en 0), o decimal 98.

Simultáneamente realiza una segunda transformación, que es la misma que la primera pero con el tablero girado 90 grados. Esto nos permite usar la misma lógica para hacer coincidencias horizontales que verticales. Para simplificar, concatena las dos tablas en una sola larga con un cero al principio, en el medio (para separar las dos tablas) y al final para el relleno.

El segundo paso es buscar posibles coincidencias, que puedes ver en el each_cons(3).any?bloque. Las filas transformadas (que ahora son enteros de 8 bits) se verifican en grupos (superpuestos) de tres filas ( x , y , z ) utilizando aritmética bit a bit. Cada grupo se verifica para ver si se puede hacer una coincidencia en la fila y , ya sea cambiando una pieza en la fila y o cambiando una pieza a y desde x o z . Como hay una "fila" cero antes y después de las filas de los tableros originales y rotados, no tenemos que verificar si estamos en la primera o última fila de un tablero.

Si no se encontraron coincidencias, continúa con la siguiente iteración.

Jordán
fuente