Um desafio 4x4

6

Existe um jogo cerebral chamado Enumerate (que eu criei , baseado em Takuzu ). Seu desafio é jogar este jogo.


Tarefa

Resolver um jogo de 4x4 Enumerate / Takuzu.

  • Receba uma grade inicial via STDIN ou linha de comando.
  • Saída da grade resolvida via STDOUT ou gravando no arquivo.

Regras

Um jogo é caracterizado por um tabuleiro 4x4, composto de células vermelhas e roxas.

  • Deve haver o mesmo número de células vermelhas e roxas em cada linha e coluna (2 vermelhas e 2 roxas em cada).

  • Não deve haver linhas ou colunas idênticas.


Entrada

A grelha de partida será dada como uma cadeia de caracteres 16 / byte que consiste de apenas 0, 1, e 2. Aqui está um exemplo:

0001100002001200

1representa uma célula vermelha e 2representa uma célula roxa. Todas as placas de entrada serão solucionáveis.


Nota: Se o seu idioma não suportar entrada literal de cadeia , você poderá receber entrada como uma matriz de números inteiros. Por favor, indique na sua resposta que este é o caso. Portanto, não há confusão, é assim que a matriz deve se parecer:

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

Nenhuma matriz aninhada é permitida.


Resultado

A placa resolvida deve ser impressa no mesmo formato acima; uma cadeia de 16 caracteres / bytes, composta apenas por 1e 2. Aqui está a solução para a entrada acima:

2121112222111212

Mais 1uma vez, representa uma célula vermelha e 2representa uma célula roxa.


Bônus

Um bônus de -25 bytes é oferecido para qualquer resposta que produza a placa resolvida como uma grade ASCII. Aqui está um exemplo do quadro mencionado anteriormente.

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

Um bônus de -50 bytes é oferecido para qualquer resposta que produza a placa resolvida em cores. Isso pode ser produzido como uma imagem ou texto colorido.

Se o texto colorido for escolhido, a saída deve ser assim:

2121
1122
2211
1212

No entanto, se uma imagem for o método de saída escolhido, o arquivo resultante deverá ter 20x20 pixels, onde cada célula é um bloco colorido de 5x5 pixels. Aqui está um exemplo:

Aqui estão os códigos de cores:

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

Amostras

In:  0020010100000100
Out: 1221212112122112

In:  0010000200121000
Out: 2211112221121221

In:  1000100102000000
Out: 1122122122112112
Zach Gates
fonte
1
Este quebra-cabeça é conhecido como Takuzu , aliás.
Maçaneta
Obrigado! Eu não sabia que havia um nome formal para isso. Adicionado isso à introdução :) @Doorknob
Zach Gates
Podemos tomar a entrada como uma matriz de 0, 1e 2? Que tal uma matriz bidimensional?
lirtosiast
Somente se o seu idioma não suportar entrada literal de string (se houver). Vou acrescentar isso à pergunta. @ThomasKwa
Zach Gates
1
Você pode assumir que haverá células suficientes fornecidas em cada entrada para produzir uma única solução. @ edc65
Zach Gates

Respostas:

9

CJam (pontuação 13)

Com bônus de texto colorido, apenas caracteres imprimíveis: 64 caracteres - 50 = 14

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

Isso pode ser aprimorado por um caractere usando um caractere não imprimível: 27c'[@torna - se "^["\onde ^representa o caractere 27, dando uma pontuação de 13. xxd version:

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* 

Solução direta sem bônus: 42 caracteres

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

Demonstração online


Com bônus na grade: 59 caracteres - 25 = 34

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

Demonstração online


Com saída de imagem, 83 caracteres - 50 = 33. A saída está no formato netpbm.

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

Demonstração online

Peter Taylor
fonte
Não deveria ser 14 pontos?
Cyoce
@Cyoce, a versão com apenas imprimíveis personagens pontuação 14, mas a versão com um não imprimíveis contagens de caracteres 13.
Peter Taylor
OK. Eu não vi esse.
21416 Cyoce
6

CJam, 74-50 = 24 bytes (saída colorida)

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

Eu não acho que isso seja muito bom, mas funciona! Experimente aqui. Aviso: lento .

l:~:L;lê uma linha de entrada em L. Então, 5Zbé [1 2], e nós tomamos o 16 th poder cartesiano ( Gm*) desta lista, para obter todas as soluções possíveis [[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] ...]. O filtro { },contém a lógica Takuzu.

Adicionei um bônus de saída de cores de código ANSI:

saída colorida

Isso não funciona no site, é claro. Há um ESCbyte não imprimível na sequência "[".

Lynn
fonte
1 apenas para5Zb
Peter Taylor
1

Ruby, 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 que seu nome deve ser tão longo? -_-

Isso simplesmente percorre todas as soluções possíveis até que uma delas corresponda ao padrão de entrada.

Maçaneta da porta
fonte
1

C (função) (com built-in gcc), 283

Este parecia um desafio interessante a ser enfrentado no C. Certamente ele pode jogar mais, mas aqui está o começo:

#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 passada como string para funcionar f() . Saída para STDOUT.

Experimente online.

Trauma Digital
fonte
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 as restrições, o número de soluções possíveis parece surpreendentemente pequeno: 72

A placa inteira pode ser vista como um número de 16 bits.
Valores permitidos para linhas (mascaramento 1111): 0011, 0101, 0110 e os valores invertidos 1100, 1010, 1001

O mesmo para colunas, apenas com diferentes mascaramentos e bits misturados (mascaramento 1000100010001): 0 ... 0 ... 1 ... 1, 0 ... 1 ... 0 ... 1, 0 ... 1 ... 1 ... 0 e os valores invertidos

Observe que os arranjos de bits de linhas e colunas são diferentes; portanto, para verificar a presença de uinidade, você pode adicionar linhas e colunas a um conjunto e verificar se o tamanho do conjunto é == 8.

Código para enumerar todas as soluções possíveis em uma grade 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))
}

Teste

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
fonte
0x10000pode ser substituído por 65536.
LegionMammal978
Para mim, apenas o primeiro teste funciona.
precisa saber é o seguinte
Para mim, funciona com o Firefox. @ zyabin101
edc65
@ edc65 Eu também tenho o Firefox.
precisa saber é o seguinte
??? Não é possível explicar ... @ zyabin101
edc65
1

C, pontuação 278 257

( 328 307 bytes - 50 bytes para saída colorida ou 291 bytes sem bônus de cor)

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 é um método de força bruta que imprime a primeira grade correspondente. Na verdade, ele trabalha em uma grade rotativa de 180 graus para simplificar alguns loops e usa uma tabela de pesquisa (59799) para descobrir quais linhas são válidas. Internamente, todas as grades são apenas números de 16 bits. É preciso uma única entrada de string de seus argumentos.

Devido aos códigos de escape usados ​​para colorir, você pode redefinir o estilo do terminal depois de executar este procedimento (executar printf "\x1b[0m")

Demolir:

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

Então, o que é 59799?

Existem apenas 16 estados possíveis para cada linha / coluna (é um número binário de 4 bits). Dessas, as opções válidas são:

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

Tomando esses valores como índices de bits, podemos criar uma máscara:

0001011001101000 = 5736 (dec)

Mas aqui queremos saber as linhas inválidas :

1110100110010111 = 59799 (dec)
Dave
fonte