Tantangan 4x4

6

Ada permainan otak yang disebut Enumerate (yang saya buat, berdasarkan Takuzu ). Tantangan Anda adalah memainkan game ini.


Tugas

Pecahkan game 4x4 Enumerate / Takuzu.

  • Terima kisi start melalui STDIN atau baris perintah.
  • Keluarkan grid yang dipecahkan melalui STDOUT atau menulis ke file.

Aturan

Gim ditandai dengan papan 4x4, terdiri dari sel merah dan ungu.

  • Harus ada jumlah sel merah dan ungu yang sama di setiap baris dan kolom (masing-masing 2 merah dan 2 ungu).

  • Tidak boleh ada baris atau kolom yang identik.


Memasukkan

Grid mulai akan diberikan sebagai string 16 karakter / byte yang terdiri dari hanya 0, 1dan 2. Berikut ini sebuah contoh:

0001100002001200

1mewakili sel merah dan 2mewakili sel ungu. Semua papan input akan dapat dipecahkan.


Catatan: Jika bahasa Anda tidak mendukung input string literal , Anda dapat mengambil input sebagai array bilangan bulat. Harap sebutkan dalam jawaban Anda bahwa inilah masalahnya. Jadi tidak ada kebingungan, beginilah kata array seharusnya:

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

Array bersarang tidak diizinkan.


Keluaran

Papan yang dipecahkan harus berupa output dalam format yang sama seperti di atas; string 16 karakter / byte, hanya terdiri dari 1dan 2. Berikut ini solusi untuk input di atas:

2121112222111212

Sekali lagi, 1mewakili sel merah dan 2mewakili sel ungu.


Bonus

Sebuah bonus -25 byte ditawarkan untuk setiap jawaban yang output papan dipecahkan sebagai jaringan ASCII. Berikut adalah contoh papan yang disebutkan sebelumnya.

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

Sebuah -50 byte bonus yang ditawarkan untuk setiap jawaban yang output papan diselesaikan dalam warna. Ini bisa menjadi output sebagai gambar atau teks berwarna.

Jika teks berwarna dipilih, hasilnya akan terlihat seperti ini:

2121
1122
2211
1212

Namun, jika gambar adalah metode output yang dipilih, file yang dihasilkan harus 20x20 piksel, di mana setiap sel adalah blok piksel 5x5 berwarna. Berikut ini sebuah contoh:

Berikut adalah kode warna:

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

Sampel

In:  0020010100000100
Out: 1221212112122112

In:  0010000200121000
Out: 2211112221121221

In:  1000100102000000
Out: 1122122122112112
Zach Gates
sumber
1
Teka-teki ini dikenal sebagai Takuzu , kebetulan.
Gagang Pintu
Terima kasih! Saya tidak tahu ada nama resmi untuk itu. Menambahkan itu ke intro :) @Doorknob
Zach Gates
Bisakah kita mengambil input sebagai array 0, 1dan 2? Bagaimana dengan array dua dimensi?
lirtosiast
Hanya jika bahasa Anda tidak mendukung input string literal (jika ada). Saya akan menambahkan itu ke pertanyaan. @ThomasKwa
Zach Gates
1
Anda dapat mengasumsikan bahwa akan ada cukup sel yang disediakan di setiap input untuk menghasilkan solusi tunggal. @ edc65
Zach Gates

Jawaban:

9

CJam (skor 13)

Dengan bonus teks berwarna, hanya karakter yang dapat dicetak: 64 karakter - 50 = 14

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

Ini dapat ditingkatkan dengan satu char menggunakan karakter non-printable: 27c'[@menjadi "^["\mana ^mewakili karakter 27, memberikan skor 13. versi 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* 

Solusi langsung tanpa bonus: 42 karakter

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

Demo online


Dengan bonus grid: 59 karakter - 25 = 34

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

Demo online


Dengan output gambar, 83 karakter - 50 = 33. Output dalam format netpbm.

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

Demo online

Peter Taylor
sumber
Bukankah seharusnya skor 14?
Cyoce
@Cyoce, versi dengan karakter yang hanya dapat dicetak mencetak skor 14, tetapi versi dengan karakter yang tidak dapat dicetak mencetak skor 13.
Peter Taylor
baik. Saya tidak melihat itu.
Cyoce
6

CJam, 74-50 = 24 byte (keluaran warna)

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

Saya tidak berpikir ini golf yang sangat baik, tetapi berhasil! Coba di sini. Peringatan: lambat .

l:~:L;membaca sebaris input ke L. Kemudian, 5Zbadalah [1 2], dan kami mengambil kekuatan Cartesian ke- 16 ( Gm*) dari daftar ini, untuk mendapatkan semua solusi yang mungkin [[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] ...]. Filter { },berisi logika Takuzu.

Saya menambahkan bonus warna keluaran kode ANSI:

keluaran warna

Ini tidak berfungsi di situs web, tentu saja. Ada ESCbyte yang tidak bisa dicetak dalam string "[".

Lynn
sumber
+1 hanya untuk5Zb
Peter Taylor
1

Ruby, 196 byte

->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, mengapa namamu begitu panjang? -_-

Ini hanya melewati semua solusi yang mungkin sampai salah satu dari mereka cocok dengan pola input.

Gagang pintu
sumber
1

C (fungsi) (dengan built-in gcc), 283

Ini sepertinya tantangan yang menarik untuk ditangani di C. Cukup yakin itu bisa bermain golf lebih banyak, tapi ini awalnya:

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

Input diteruskan sebagai string berfungsi f(). Output ke STDOUT.

Cobalah online.

Trauma Digital
sumber
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)}}

Mengingat kendala, jumlah solusi yang mungkin tampak sangat kecil: 72

Seluruh papan dapat dilihat sebagai angka 16 bit.
Nilai yang diizinkan untuk baris (masking 1111): 0011, 0101, 0110 dan nilai terbalik 1100, 1010, 1001

Sama untuk untuk kolom, hanya dengan bit masking dan intermixed yang berbeda (masking 1000100010001): 0 ... 0 ... 1 ... 1, 0 ... 1 ... 0 ... 1, 0 ... 1 ... 1 ... 0 dan nilai terbalik

Perhatikan bahwa pengaturan bit baris dan kolom berbeda, jadi untuk memeriksa uiniqueness Anda dapat menambahkan baris dan kolom ke set dan memverifikasi bahwa ukuran set adalah == 8.

Kode untuk menyebutkan semua kemungkinan solusi dalam kisi 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))
}

Uji

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
sumber
0x10000dapat diganti dengan 65536.
LegionMammal978
Bagi saya, hanya tes pertama yang berhasil.
user48538
Bagi saya ini berfungsi dengan Firefox. @ zyabin101
edc65
@ edc65 Saya punya Firefox juga.
user48538
??? Tidak bisa menjelaskan ... @ zyabin101
edc65
1

C, Skor 278 257

( 328 307 byte - 50 byte untuk output berwarna, atau 291 byte tanpa bonus warna)

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

Ini adalah metode brute-force yang mencetak grid yang cocok pertama. Ini benar-benar bekerja pada grid diputar 180 derajat untuk menyederhanakan beberapa loop, dan menggunakan tabel pencarian (59799) untuk mencari tahu baris mana yang valid. Secara internal semua kisi hanya angka 16-bit. Dibutuhkan input string tunggal dari argumennya.

Karena kode pelarian yang digunakan untuk pewarnaan, Anda mungkin ingin mengatur ulang gaya terminal Anda setelah menjalankan ini (jalankan printf "\x1b[0m")

Kerusakan:

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

Jadi, apa 59799?

Hanya ada 16 kemungkinan status untuk setiap baris / kolom (ini adalah angka biner 4-bit). Di luar itu, opsi yang valid adalah:

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

Mengambil nilai-nilai itu sebagai indeks bit, kita bisa membuat topeng:

0001011001101000 = 5736 (dec)

Tapi di sini kita ingin tahu baris yang tidak valid :

1110100110010111 = 59799 (dec)
Dave
sumber