Ist die Pizza fair?

27

Diese Frage ist inspiriert von und ist das Gegenteil von dieser Frage .

Dennis ( E), Doorknob ( D), Martin ( M) und Chris ( C) haben eine Pizza bestellt. Die rechteckige Pizza ist in quadratische Stücke unterteilt, die jeweils mit ihrem vorgesehenen Esser gekennzeichnet sind.

Schreiben Sie ein Programm oder eine Funktion, die bei einer rechteckigen Pizza, die aus 0 oder mehr Buchstaben besteht, bestimmt, ob:

  1. Jedes Slice für jede Person ist mit dem Pfad verbunden . Dies bedeutet, dass alle Buchstaben, die gleich sind, direkt nebeneinander liegen sollten (keine diagonalen Verbindungen).

  2. Die Anzahl der Scheiben pro Person ist für alle gleich.

Sie müssen einen Wahrheits- / Falschwert mit einem optionalen nachgestellten Zeilenumbruch ausgeben, der angibt, ob die angegebene Pizza fair ist oder nicht.

Gültige Testfälle:

DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEDMMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC
DEMC
DD
EE
MC
MC
EEDDMMMCCC
EEEDDDMMCC

Ungültige Testfälle:

EDM
EDMCCMDE
DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEMDMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC
DDMMEECC
DMMEECCC

Kürzester Code in Bytes gewinnt.

orlp
quelle
1. Welche Eingabeformen sind für eine Funktion zulässig? Zeichenfolge mit Zeilenumbrüchen? Array mit einer Zeichenfolge für jede Zeile? 2D-Array von Zeichen? Alles das oben Genannte? 2. Ich verstehe, dass die Ausgabe für fair, für unfair falsch ist, oder können sie rückgängig gemacht werden?
Level River St
52
Gültige Testfälle: DDDDDDDDDDDDD<- eine faire Pizza
Türklinke
@steveverrill Für diese Herausforderung ist nur eine Zeichenfolge mit Zeilenumbrüchen als Eingabe zulässig. Sie müssen ehrlich für fair und falsch für unfair zurückkehren.
Orlp
Neben Newlines nur CDEM in der Eingabe?
edc65
@ edc65 Richtig.
Orlp

Antworten:

5

Pyth, 53 Bytes

!f-lJs.z*4lu&G{smfqT@JY@UJ+Ld[Z1_1Klh.z_K)G]xJT)"CDEM

Demonstration

Dies ist im Wesentlichen eine Überflutung für jeden Buchstaben, gefolgt von einer Überprüfung, ob alle resultierenden Mengen die richtige Größe haben.

Zum Füllen wird mit dem Vorkommen jedes Buchstabens oben links begonnen, dann werden alle Nachbarn der bisher gefundenen Orte generiert, nach Orten mit dem richtigen Buchstaben gefiltert und wiederholt, bis sich der Satz nicht mehr ändert.

isaacg
quelle
6

Schnecken , 129

Gibt 1 für eine faire Pizza und 0 für eine unfaire Pizza aus.

&
={(t\Dt\Et\Ct\M),!(t.}{(o\D)+l^D,=~u{^D=(r^D,~},~|o\E`+l^E,=~u{^E=(r^E,~},~|o\C`+l^C,=~u{^C=(r^C,~},~|o\M`+l^M,=~u{^M=(r^M,~},~

Erweiterte Version:

&
={ (t\Dt\Et\Ct\M), !(t.)}   {
(o\D)+ l^D,=~ u{^D=(r^D,~)}, ~ |
(o\E)+ l^E,=~ u{^E=(r^E,~)}, ~ |
(o\C)+ l^C,=~ u{^C=(r^C,~)}, ~ |
(o\M)+ l^M,=~ u{^M=(r^M,~)}, ~

&bedeutet, dass das Muster an allen Stellen im Raster übereinstimmen muss. Die erste Zeile prüft, ob E, D, M und C gleich viele sind. Dabei wird der Teleport-Befehl verwendet t, mit dem Programme mit faktorieller Komplexität erstellt werden können. Wenn ein Eingang Slices ungleicher Größe mit mehreren Einheiten für jeden der 4 Mods hat, bleibt das Programm mehr oder weniger für immer hängen. Danach wird nach einem zusammenhängenden Pfad zu der linken oberen Instanz des Buchstabens gesucht, mit dem das Muster begonnen hat.

Feersum
quelle
6

CJam, 93

qN/_z,:W;s:A,,:B_{{{_B=_@-}g}%$}:F;{a+_Af=)#{F~B\@t:B}|;}:U;W>{_W-U}/{W%},{_(U}/BFe`0f=_1<4*=

Probieren Sie es online aus

Das ist lächerlich lang, weil CJam (noch) kein integriertes Flood-Fill oder Union-Find hat. Ich habe union-find in das Programm implementiert .

Erläuterung:

qN/_         read input, split into lines and duplicate
z,:W;        transpose, get length (original width) and store in W
s:A          convert to string (without newlines) and store in A
,,           make an array [0..n-1] (n = pizza size)
:B_          store in B (initial structure) and duplicate (will be used in 2 loops)
{…}:F;       define function F ("Find" for multiple indices and sort)
  {…}%       for each value (x)
    {…}g     do…while
      _B=    duplicate x and get B[x]
      _@-    leave a B[x] on the stack and calculate B[x] - x
              if non-zero, repeat the loop with B[x]
  $          sort the results
{…}:U;       define function U ("Union" for 2 indices)
  a+         make an array of the 2 indices
  _Af=       get the corresponding letters from A
  )#         check if the letters are different
  {…}|       if not, execute…
    F~       call F on the array and dump the 2 results on the stack
    B\@t     join the sets - B[bigger index] = smaller index
    :B       store back in B
  ;          pop the last value (either array if indices or B)
W>           remove the first row of indices
{…}/         for each index
  _W-        duplicate and subtract W ("go up")
  U          call U to join sets if they match
{W%},        remove the first column of indices
{…}/         for each index
  _(         duplicate and decrement ("go left")
  U          call U to join sets if they match
BF           call F on B, to get the final sets and sort
e`           RLE encoding
0f=          keep only the repetition counts
_1<4*=       check if it's the first value (if any) repeated 4 times
aditsu
quelle
4

JavaScript (ES6), 153 166

Unter Verwendung von Vorlagenzeichenfolgen gibt es einen Zeilenumbruch, der signifikant und gezählt ist

Testen Sie das Ausführen des Snippets in FireFox.

f=z=>![...'CDEM'].some(c=>((l=p=>z[p]==c&&[-1,1,w,-w].map(o=>l(p+o),z[p]='',++k))(z.indexOf(c),h=k,k=0),~h&&h-k),w=~z.search`
`,z=[...z],k=-1)&z.join``-1

// Ungolfed
U=z=>{
  w = ~z.search`\n`
  z = [...z]
  fill = p=>(
    c = z[p],
    z[p] = '',
    [-1,1,w,-w].forEach(o=>z[o+=p] == c && fill(o)),
    ++k
  )
  h = -1
  r = ['C','D','E','M'].every( c =>(
    k = 0,
    y = z.indexOf(c),
    y >= 0 && fill(y),
    v = h >= 0 ? h == k : true,
    h = k,
    v
  ))
  return r & 1-z.join``
}  

// Test
out=x=>O.innerHTML+=x+'\n';

// Valid test cases
valid=[`DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEDMMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC`,
`DEMC`,
`DD
EE
MC
MC`,
`EEDDMMMCCC
EEEDDDMMCC`];
out('Valid')
valid.forEach(t=>out(t+'\n'+f(t)+'\n'));
invalid=[`EDM`,
`EDMCCMDE`,
`DDDDDDDDDDDDDD`,         
`DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEMDMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC`,
`DDMMEECC
DMMEECCC`
];
out('Invalid')
invalid.forEach(t=>out(t+'\n'+f(t)+'\n'))
<pre id=O></pre>

edc65
quelle
2

Javascript ES6, 360

Prüft auf die gleiche Anzahl von C, D, E, M, füllt sie dann mit Wasser und prüft auf verwaiste Buchstaben. Kein Gewinner, aber ich musste es versuchen.

i=>(I=i.split`
`.map(e=>e.split``),c=(i[m='match'](/C/g)||[])[l='length'],a=(x,y,z)=>{if(I[x][y]!=z)return;I[x][y]=0;x>0&&a(x-1,y,z);x<I[l]-1&&a(x+1,y,z);y>0&&a(x,y-1,z);y<I[0][l]-1&&a(x,y+1,z)},![...'CDEM'].some(k=>{if((i[m](eval(`/${k}/g`))||[])[l]!=c)return 1;I.some((w,x)=>(g=-1<(y=w.indexOf(k)),g&&a(x,y,k),g));})&&!I.map(e=>e.join``).join``[m](/[CDEM]/))

Geige

DankMemes
quelle
2

JavaScript ES6, 328 318 316 269 178

l=>(d=[0,0,0,0],s=[...l.split`
`.join``].map(i=>(d["EDMC".search(i)]++,i)),!l||d.every(i=>i==d[0])&&(s.every((r,i)=>[1,-1,X=l.split`
`[0].length,-X].some(o=>s[o+i]==r))||d[0]<2))

Erläuterung:

l => (
  d = [0,0,0,0],          // array containing each letter count
  s = [...l.split`                    
`.join``]                 // removes newlines from input and converts it into array
  .map(i => (             // loops through the array
    d["EDMC".search(i)]++ // increases letter count
    ,i)),                 // returns unchanged value in order to preserve original array
  !l                      // input is empty
  || d.every(i=>i==d[0])  // each letter count is equal
  && (
    s.every((r, i) =>     // there is no orphaned letters 
      [1,-1,X=l.split`
`[0].length,-X]           // letters on respectively: right, left, bottom, top
      .some               // at least one of them
        (o=>s[o+i]==r))   // equals original letter
    || d[0] < 2           // count of each letter equals 1
  )
)
Michał Perłakowski
quelle
1
Interessanter Code (du hast meinen geschlagen!) Vorschlag: Nutze die Pfeilfunktionen von es6 (wie in meiner Antwort), um ein paar Bytes zu sparen. Afaik Sie müssen es nicht einer Variablen zuweisen, mit einer einfachen Funktionsdeklaration zB l=>{...}ist in Ordnung.
DankMemes
2
Entfernen Sie auch die Klammern k=(o)=>, um 2 weitere Bytes zu sparen. Einzelparameter-Pfeilfunktionen benötigen keine Klammern.
DankMemes