Eine 4x4 Herausforderung

6

Es gibt ein Denkspiel namens Enumerate (das ich basierend auf Takuzu gemacht habe ). Ihre Herausforderung besteht darin, dieses Spiel zu spielen.


Aufgabe

Löse ein 4x4 Enumerate / Takuzu-Spiel.

  • Erhalten Sie ein Startraster über STDIN oder Befehlszeile.
  • Das gelöste Raster über STDOUT ausgeben oder in eine Datei schreiben.

Regeln

Ein Spiel zeichnet sich durch ein 4x4-Brett aus roten und violetten Zellen aus.

  • In jeder Zeile und Spalte muss die gleiche Anzahl roter und violetter Zellen vorhanden sein (jeweils 2 rote und 2 violette).

  • Es dürfen keine identischen Zeilen oder Spalten vorhanden sein.


Eingang

Die Startaufstellung wird als 16 Zeichen / Byte - Zeichenfolge gegeben werden , die nur aus 0, 1, und 2. Hier ist ein Beispiel:

0001100002001200

1repräsentiert eine rote Zelle und 2repräsentiert eine lila Zelle. Alle Eingangskarten sind lösbar.


Hinweis: Wenn Ihre Sprache keine Zeichenfolgenliteraleingabe unterstützt , können Sie die Eingabe als Array von Ganzzahlen verwenden. Bitte geben Sie in Ihrer Antwort an, dass dies der Fall ist. Es gibt also keine Verwirrung, so sollte das Array aussehen:

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

Es sind keine verschachtelten Arrays zulässig.


Ausgabe

Die gelöste Karte sollte im gleichen Format wie oben ausgegeben werden. Eine 16-Zeichen- / Byte-Zeichenfolge, die nur aus 1und besteht 2. Hier ist die Lösung für die obige Eingabe:

2121112222111212

Wieder 1stellt eine rote Zelle und 2eine lila Zelle dar.


Boni

A -25 Byte Bonus wird für jede Antwort angeboten, die gelöst Board als ASCII - Raster ausgibt. Hier ist ein Beispiel für die zuvor erwähnte Karte.

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

A -50 Bytes Bonus wird für jede Antwort angeboten, die gelöst Board in Farbe ausgibt. Dies kann als Bild oder farbiger Text ausgegeben werden.

Wenn farbiger Text ausgewählt ist, sollte die Ausgabe folgendermaßen aussehen:

2121
1122
2211
1212

Wenn jedoch ein Bild die gewählte Ausgabemethode ist, sollte die resultierende Datei 20 x 20 Pixel groß sein, wobei jede Zelle ein farbiger 5 x 5 Pixel-Block ist. Hier ist ein Beispiel:

Hier sind die Farbcodes:

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

Proben

In:  0020010100000100
Out: 1221212112122112

In:  0010000200121000
Out: 2211112221121221

In:  1000100102000000
Out: 1122122122112112
Zach Gates
quelle
1
Dieses Puzzle ist übrigens als Takuzu bekannt .
Türknauf
Vielen Dank! Ich wusste nicht, dass es einen offiziellen Namen dafür gibt. Fügte das zum Intro hinzu :) @Doorknob
Zach Gates
Können wir die Eingabe als ein Array von nehmen 0, 1und 2? Was ist mit einem zweidimensionalen Array?
Lirtosiast
Nur wenn Ihre Sprache keine Eingabe von Zeichenfolgenliteralen unterstützt (falls vorhanden). Ich werde das der Frage hinzufügen. @ ThomasKwa
Zach Gates
1
Sie können davon ausgehen, dass in jeder Eingabe genügend Zellen vorhanden sind, um eine einzelne Lösung zu erhalten. @ edc65
Zach Gates

Antworten:

9

CJam (Punktzahl 13)

Mit farbigem Textbonus nur druckbare Zeichen: 64 Zeichen - 50 = 14

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

Dies kann durch ein Zeichen verbessert werden , um eine nicht-druckbare Zeichen verwendet: 27c'[@wird , "^["\wo ^repräsentiert Charakter 27, eine Punktzahl von 13. xxd Version geben:

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* 

Gerade Lösung ohne Bonus: 42 Zeichen

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

Online-Demo


Mit Gitterbonus: 59 Zeichen - 25 = 34

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

Online-Demo


Bei Bildausgabe 83 Zeichen - 50 = 33. Die Ausgabe erfolgt im Netpbm-Format.

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

Online-Demo

Peter Taylor
quelle
Sollte es nicht Punktzahl 14 sein?
Cyoce
@Cyoce, die Version mit nur druckbaren Zeichen erzielt 14 Punkte, aber die Version mit nicht druckbaren Zeichen erzielt 13.
Peter Taylor
okay. Das habe ich nicht gesehen.
Cyoce
6

CJam, 74-50 = 24 Bytes (Farbausgabe)

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

Ich denke nicht, dass dies sehr gut Golf ist, aber es funktioniert! Probieren Sie es hier aus. Warnung: langsam .

l:~:L;liest eine Eingabezeile in L. Dann 5Zbist [1 2], und wir nehmen die 16 th cartesianischen Leistung ( Gm*) diese Liste, alle möglichen Lösungen zu erhalten [[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] ...]. Der Filter { },enthält die Takuzu-Logik.

Ich habe einen ANSI-Code-Farbausgabebonus hinzugefügt:

Farbausgabe

Das funktioniert auf der Website natürlich nicht. ESCDie Zeichenfolge enthält ein nicht druckbares Byte "[".

Lynn
quelle
+1 nur für5Zb
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, warum muss dein Name so lang sein? -_-

Dies geht einfach alle möglichen Lösungen durch, bis eine davon mit dem Eingabemuster übereinstimmt.

Türknauf
quelle
1

C (Funktion) (mit eingebauten gcc), 283

Dies schien eine interessante Herausforderung für C zu sein. Ich bin mir ziemlich sicher, dass man mehr Golf spielen kann, aber hier ist ein Anfang:

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

Eingabe als Zeichenfolge an Funktion übergeben f(). Ausgabe an STDOUT.

Probieren Sie es online aus.

Digitales Trauma
quelle
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)}}

Angesichts der Einschränkungen scheint die Anzahl der möglichen Lösungen überraschend gering zu sein: 72

Die gesamte Karte kann als 16-Bit-Nummer angesehen werden.
Zulässige Werte für Zeilen (Maskierung 1111): 0011, 0101, 0110 und die invertierten Werte 1100, 1010, 1001

Gleiches gilt für Spalten, nur mit unterschiedlichen Maskierungs- und Mischbits (Maskierung 1000100010001): 0 ... 0 ... 1 ... 1, 0 ... 1 ... 0 ... 1, 0 ... 1 ... 1 ... 0 und die invertierten Werte

Beachten Sie, dass die Bitanordnungen für Zeilen und Spalten unterschiedlich sind. Um die Eindeutigkeit zu überprüfen, können Sie einer Menge sowohl Zeilen als auch Spalten hinzufügen und sicherstellen, dass die eingestellte Größe == 8 ist.

Code zum Auflisten aller möglichen Lösungen in einem Raster 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))
}

Prüfung

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
quelle
0x10000kann durch ersetzt werden 65536.
LegionMammal978
Für mich funktioniert nur der erste Test.
user48538
Bei mir funktioniert es mit Firefox. @ zyabin101
edc65
@ edc65 Ich habe auch Firefox.
user48538
??? Kann nicht erklären ... @ zyabin101
edc65
1

C, Punktzahl 278 257

( 328 307 Bytes - 50 Bytes für farbige Ausgabe oder 291 Bytes ohne Farbbonus)

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

Dies ist eine Brute-Force-Methode, bei der das erste übereinstimmende Raster gedruckt wird. Es funktioniert tatsächlich mit einem um 180 Grad gedrehten Raster, um einige Schleifen zu vereinfachen, und verwendet eine Nachschlagetabelle (59799), um herauszufinden, welche Zeilen gültig sind. Intern sind alle Gitter nur 16-Bit-Zahlen. Es wird eine einzelne Zeichenfolge aus seinen Argumenten eingegeben.

Aufgrund der zum Färben verwendeten Escape-Codes möchten Sie möglicherweise Ihr Terminal-Styling zurücksetzen, nachdem Sie dies ausgeführt haben (ausführen printf "\x1b[0m").

Nervenzusammenbruch:

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

Also, was ist 59799?

Es gibt nur 16 mögliche Zustände für jede Zeile / Spalte (es ist eine 4-Bit-Binärzahl). Von diesen sind die gültigen Optionen:

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

Wenn wir diese Werte als Bitindizes verwenden, können wir eine Maske erstellen:

0001011001101000 = 5736 (dec)

Aber hier wollen wir die ungültigen Zeilen wissen :

1110100110010111 = 59799 (dec)
Dave
quelle