Un desafío 4x4

6

Existe un juego mental llamado Enumerate (que hice, basado en Takuzu ). Tu desafío es jugar este juego.


Tarea

Resuelve un juego de 4x4 Enumerate / Takuzu.

  • Reciba una grilla inicial a través de STDIN o línea de comando.
  • Salida de la cuadrícula resuelta a través de STDOUT o escribiendo en el archivo.

Reglas

Un juego se caracteriza por un tablero de 4x4, formado por celdas rojas y moradas.

  • Debe haber el mismo número de celdas rojas y moradas en cada fila y columna (2 rojas y 2 moradas en cada una).

  • No debe haber filas o columnas idénticas.


Entrada

La parrilla de salida será dado como una cadena de 16 caracteres / byte que consiste en solamente 0, 1y 2. Aquí hay un ejemplo:

0001100002001200

1representa una celda roja y 2representa una celda púrpura. Todas las placas de entrada serán solucionables.


Nota: Si su idioma no admite la entrada literal de cadenas , puede tomar la entrada como una matriz de enteros. Indique en su respuesta que este es el caso. Entonces no hay confusión, así es como debería verse dicha matriz:

[0, 0, 0, 1, 1, 0, 0, 0, 0, 2, 0, 0, 1, 2, 0, 0]

No se permiten matrices anidadas.


Salida

La placa resuelta debe salir en el mismo formato que el anterior; una cadena de 16 caracteres / byte, que consta de solo 1y 2. Aquí está la solución para la entrada anterior:

2121112222111212

Nuevamente, 1representa una celda roja y 2representa una celda púrpura.


Bonos

Se ofrece una bonificación de -25 bytes por cualquier respuesta que genere la placa resuelta como una cuadrícula ASCII. Aquí hay un ejemplo del tablero mencionado anteriormente.

2|1|2|1
-+-+-+-
1|1|2|2
-+-+-+-
2|2|1|1
-+-+-+-
1|2|1|2

Se ofrece una bonificación de -50 bytes por cualquier respuesta que muestre la placa resuelta en color. Esto se puede generar como una imagen o texto en color.

Si se elige texto en color, el resultado debería verse así:

2121
1122
2211
1212

Sin embargo, si una imagen es el método de salida elegido, el archivo resultante debe tener 20x20 píxeles, donde cada celda es un bloque de color de 5x5 píxeles. Aquí hay un ejemplo:

Aquí están los códigos de colores:

Red      -   #a73cba   OR   (167,  60, 186)
Purple   -   #f94a32   OR   (249,  74,  50)

Muestras

In:  0020010100000100
Out: 1221212112122112

In:  0010000200121000
Out: 2211112221121221

In:  1000100102000000
Out: 1122122122112112
Puertas de Zach
fuente
1
Este rompecabezas se conoce como Takuzu , por cierto.
Pomo de la puerta
¡Gracias! No sabía que había un nombre formal para eso. Agregó eso a la introducción :) @Doorknob
Zach Gates
Podemos tomar la entrada como una matriz de 0, 1y 2? ¿Qué pasa con una matriz bidimensional?
lirtosiast el
Solo si su idioma no admite la entrada literal de cadena (si hay alguna). Agregaré eso a la pregunta. @ThomasKwa
Zach Gates
1
Puede suponer que habrá suficientes celdas proporcionadas en cada entrada para producir una solución única. @ edc65
Zach Gates

Respuestas:

9

CJam (puntaje 13)

Con bonificación de texto en color, solo caracteres imprimibles: 64 caracteres - 50 = 14

l:~:L,Eb2*e!4m*_:z&{_M*L1$.e|.=1-!*_&,4=},~{27c'[@_4*27+'m@}f%N*

Esto puede mejorarse con un carácter utilizando un carácter no imprimible: se 27c'[@convierte en "^["\donde ^representa el carácter 27, dando una puntuación de 13. Versión xxd:

0000000: 6c3a 7e3a 4c2c 4562 322a 6521 346d 2a5f  l:~:L,Eb2*e!4m*_
0000010: 3a7a 267b 5f4d 2a4c 3124 2e65 7c2e 3d31  :z&{_M*L1$.e|.=1
0000020: 2d21 2a5f 262c 343d 7d2c 7e7b 221b 5b22  -!*_&,4=},~{".["
0000030: 5c5f 342a 3237 2b27 6d40 7d66 254e 2a    \_4*27+'m@}f%N* 

Solución directa sin bonificación: 42 caracteres

l:~:L,Eb2*e!4m*_:z&{_M*L1$.e|.=1-!*_&,4=},

Demostración en línea


Con bonificación de cuadrícula: 59 caracteres - 25 = 34

l:~:L,Eb2*e!4m*_:z&{_M*L1$.e|.=1-!*_&,4=},~'|f*2N*'-4*'+***

Demostración en línea


Con salida de imagen, 83 caracteres - 50 = 33. La salida está en formato netpbm.

'P3NKSKS255Nl:~:L,Eb2*e!4m*_:z&{_M*L1$.e|.=1-!*_&,4=},~4f*M*:("§<ºùJ2":i3/f=4f*M*S*

Demostración en línea

Peter Taylor
fuente
¿No debería ser el puntaje 14?
Cyoce
@Cyoce, la versión con solo caracteres imprimibles puntúa 14, pero la versión con un carácter no imprimible puntúa 13.
Peter Taylor
bueno. No vi esa.
Cyoce
6

CJam, 74-50 = 24 bytes (salida de color)

l:~:L;5ZbGm*{_L.-L.*:|!\[4/_z]_:::+e_6-!\__.&=**},s4/{"["\_~4*27+'m@}f%N*

No creo que esto sea muy bueno, ¡pero funciona! Pruébalo aquí. Advertencia: lento .

l:~:L;lee una línea de entrada en L. Entonces, 5Zbes [1 2], y tomamos la 16 ª potencia cartesiana ( Gm*) de esta lista, para obtener todas las soluciones posibles [[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2] ...]. El filtro { },contiene la lógica de Takuzu.

Agregué un bono de salida de color de código ANSI:

salida de color

Esto no funciona en el sitio web, por supuesto. Hay un ESCbyte no imprimible en la cadena "[".

Lynn
fuente
+1 solo para5Zb
Peter Taylor
1

Rubí, 196 bytes

->g{[o=?1,p=?2].repeated_permutation(16).find{|x|a=x.each_slice(4).to_a
t=a.transpose
a.uniq.size==4&&t.uniq.size==4&&(a+t).all?{|y|y.count(o)==2}&&x.zip(g.chars).none?{|y|y==[o,p]||y==[p,o]}}*''}

repeated_permutation, ¿por qué tu nombre debe ser tan largo? -_-

Esto simplemente pasa por todas las soluciones posibles hasta que una de ellas coincida con el patrón de entrada.

Pomo de la puerta
fuente
1

C (función) (con gcc incorporado), 283

Esto parecía un desafío interesante para abordar en C. Estoy bastante seguro de que se puede jugar más, pero aquí hay un comienzo:

#define m(a,b)for(j=0;j<4;j++){l[j]=i&a<<j*b;if(__builtin_popcount(l[j])-2)goto l;for(k=0;k<j;k++)if(l[j]==l[k])goto l;}
i,j,k,l[4];f(char*s){for(i=0;i<65536;i++){m(15,4)m(4369,1)for(j=0;j<16;j++)if((!(i&1<<j)==s[j]-49)&&(s[j]!=48))goto l;for(j=0;j<16;j++)putchar(50-!(i&1<<j));l:;}}

Entrada pasada como cadena para funcionar f(). Salida a STDOUT.

Pruébalo en línea.

Trauma digital
fuente
1

JavaScript (ES6), 263 300

g=>{[...g].map(c=>(t+=t+(c>1),u+=u+(c&1)),u=t=0);for(m=15,n=4369,i=0;i++<6e4;){for(x=y=i,s=new Set;x;x>>=4,y>>=1)[3,5,6,9,10,12,17,257,272,4097,4112,4352].map(v=>(x&m)==v|(y&n)==v&&s.add(v));if(s.size>7&!(i&u)&!(~i&t))return g.replace(/./g,c=>1+(i>>--p&1),p=16)}}

Dadas las limitaciones, el número de posibles soluciones parece sorprendentemente pequeño: 72

Toda la placa se puede ver como un número de 16 bits.
Valores permitidos para filas (enmascarado 1111): 0011, 0101, 0110 y los valores invertidos 1100, 1010, 1001

Lo mismo para las columnas, solo con diferentes enmascaramiento y bits entremezclados (enmascaramiento 1000100010001): 0 ... 0 ... 1 ... 1, 0 ... 1 ... 0 ... 1, 0 ... 1 ... 1 ... 0 y los valores invertidos

Tenga en cuenta que las disposiciones de bits de filas y columnas son diferentes, por lo que para comprobar la falta de distinción, puede agregar filas y columnas a un conjunto y verificar que el tamaño del conjunto sea == 8.

Código para enumerar todas las soluciones posibles en una cuadrícula 4x4

for(m=0xf,n=0x1111,t=i=0;i<0x10000;i++)
{
  // loop condition: row != 0, as valid values have 2 bits set in each row
  for(x=y=i,s=new Set; x; x>>=4, y>>=1) 
    [3,5,6,9,10,12,17,257,272,4097,4112,4352].map(v=>((x&m)==v||(y&n)==v)&&s.add(v))
  if (s.size==8)
    console.log(++t,i.toString(2))
}

Prueba

F=g=>{ // input as a string
  [...g].map(c=>(t+=t+(c>1),u+=u+(c&1)),u=t=0);
  for(m=15,n=4369,i=0;i++<6e4;) // max valid is 51862
  { 
    for(x=y=i,s=new Set;x;x>>=4,y>>=1)
      [3,5,6,9,10,12,17,257,272,4097,4112,4352].map(v=>(x&m)==v|(y&n)==v&&s.add(v));
    if(s.size>7&!(i&u)&!(~i&t))
      return g.replace(/./g,c=>1+(i>>--p&1),p=16) 
  }
}  

// Basic test

console.log=x=>O.textContent+=x+'\n'

;[
['0020010100000100','1221212112122112'],
['0010000200121000','2211112221121221'],
['1000100102000000','1122122122112112']
].forEach(t=>{
  var i = t[0], x=t[1], r=F(i);
  console.log(i+' -> '+r+(r==x?' OK':' Fail (Expected '+x+')'))
})
<pre id=O></pre>

edc65
fuente
0x10000puede ser reemplazado con 65536.
LegionMammal978
Para mí, solo funciona la primera prueba.
user48538
Para mí funciona con Firefox. @ zyabin101
edc65
@ edc65 También tengo Firefox.
user48538
??? No puedo explicar ... @ zyabin101
edc65
1

C, Puntuación 278 257

( 328 307 bytes - 50 bytes para salida en color, o 291 bytes sin bonificación de color)

t,b,c,u,r,p;v(g){for(b=0,u=59799;b<16;b+=4)u&(c=1<<(g>>b&15))?b=u:0,u|=c;return b>16;}main(i,a)char**a;{for(char*A=a[1];*A;p=p*2|*A++>49)r=r*2|*A==49;for(;++i<6e4;t=0){for(b=16;b--;)t|=(i>>b&1)<<b%4*4+b/4;if(!(p&i^p|r&~i^r|v(i)|v(t))){for(b=16;b--;)printf("\x1b[3%s%s",i&1<<b?"5m2":"1m1",b&3?"":"\n");break;}}}

Este es un método de fuerza bruta que imprime la primera cuadrícula coincidente. Realmente funciona en una cuadrícula girada de 180 grados para simplificar algunos bucles, y utiliza una tabla de búsqueda (59799) para determinar qué filas son válidas. Internamente, todas las cuadrículas son solo números de 16 bits. Toma una sola entrada de cadena de sus argumentos.

Debido a los códigos de escape utilizados para colorear, es posible que desee restablecer el estilo de su terminal después de ejecutar esto (ejecutar printf "\x1b[0m")

Descompostura:

// Globals initialise to 0
t, // Transpose of current guess
b, // Bit counter for loops
c, // Current row value when validating
u, // Invalid row mask when validating
r, // Red squares mask (1s in input)
p; // Purple squares mask (2s in input)

// Validation function for rows (returns 0 if valid, shell-style)
v(g){
    for(b=0,u=59799;b<16;b+=4) // "magic" value 59799 is a map of invalid rows
        // For each row:
        u&(c=1<<(g>>b&15))?b=u:0,  // Check if row is valid
        u|=c;                      // Add row to mask (rows cannot be duplicates)
    return b>16; // b = <some massive number> + 4 if a check failed
}

main(i,a)char**a;{ // K&R style function declaration to save 2 bytes
    // Read input (in reverse to save some bytes when reading & printing)
    for(char*A=a[1];*A;
        p=p*2|*A++>49) // Find 2s (input is strictly 012) and go to next
        r=r*2|*A==49;  // Find 1s
    for(;++i<6e4;t=0){ // Brute-force grids (<3 and >=60000 are invalid anyway)
        for(b=16;b--;)t|=(i>>b&1)<<b%4*4+b/4; // Calculate transpose
        if(!(                           // Check...
            p&i^p|                      //  Matches input purples
            r&~i^r|                     //  Matches input reds
            v(i)|                       //  Rows are valid
            v(t)                        //  Columns are valid
        )){
            // Display grid (use ANSI escape codes for colour)
            for(;b--;) // b starts at 16 from last v() call
//              printf(b&3?"%c":"%c\n",(i>>b&1)+49); // no colour variant
                printf("\x1b[3%s%s",i&1<<b?"5m2":"1m1",b&3?"":"\n");
            break; // Stop search
        }
    }
}

Entonces, ¿qué es 59799?

Solo hay 16 estados posibles para cada fila / columna (es un número binario de 4 bits). De esas, las opciones válidas son:

0011 =  3 (decimal)
0101 =  5
0110 =  6
1001 =  9
1010 = 10
1100 = 12

Tomando esos valores como índices de bits, podemos crear una máscara:

0001011001101000 = 5736 (dec)

Pero aquí queremos saber las filas no válidas :

1110100110010111 = 59799 (dec)
Dave
fuente