La pizza est-elle juste?

27

Cette question est inspirée et inverse de celle-ci .

Dennis ( E), Doorknob ( D), Martin ( M) et Chris ( C) ont commandé une pizza. La pizza rectangulaire est divisée en morceaux carrés, chacun marqué de son mangeur prévu.

Écrivez un programme ou une fonction qui, étant donné une pizza rectangulaire composée de 0 ou plus de chaque lettre, détermine si:

  1. Chaque tranche pour chaque personne est connectée au chemin . Cela signifie que toutes les lettres identiques doivent être directement adjacentes les unes aux autres (pas de connexions diagonales).

  2. Le nombre de tranches par personne est le même pour tous.

Vous devez générer une valeur de vérité / fausse avec un retour à la ligne facultatif qui indique si la pizza donnée est juste ou non.

Valises de test valides:

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

Cas de test non valides:

EDM
EDMCCMDE
DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEMDMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC
DDMMEECC
DMMEECCC

Le code le plus court en octets gagne.

orlp
la source
1. Quelles formes d'entrée sont acceptables pour une fonction? chaîne avec des sauts de ligne? tableau avec une chaîne pour chaque ligne? Tableau 2D de caractères? Tout ce qui précède? 2. Je comprends que la sortie est véridique pour juste, fausse pour injuste ou peut-elle être inversée?
Level River St
52
Cas de test valides: DDDDDDDDDDDDD<- une pizza juste
Poignée de porte
@steveverrill Pour ce défi, seule une chaîne avec des sauts de ligne est une entrée acceptable. Vous devez renvoyer la vérité pour juste et la fausse pour injuste.
orlp
A côté des nouvelles lignes, seul CDEM en entrée?
edc65
@ edc65 Correct.
orlp

Réponses:

5

Pyth, 53 octets

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

Manifestation

Il s'agit essentiellement d'un remplissage pour chaque lettre, suivi d'une vérification que tous les ensembles résultants sont de la taille appropriée.

Pour remplir, il commence par l'occurrence la plus à gauche de chaque lettre, puis génère tous les voisins des emplacements trouvés jusqu'à présent, filtre les emplacements avec la bonne lettre et se répète jusqu'à ce que l'ensemble cesse de changer.

isaacg
la source
6

Escargots , 129

Imprime 1 pour une pizza juste et 0 pour une pizza injuste.

&
={(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,~},~

Version étendue:

&
={ (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,~)}, ~

&signifie que le motif doit correspondre à tous les emplacements de la grille. La première ligne vérifie un nombre égal de chacun de E, D, M, C. elle utilise l'instruction de téléportation t, qui est un excellent moyen de créer des programmes avec une complexité factorielle. Si une entrée a des tranches de taille inégale avec plusieurs unités pour chacun des 4 mods, le programme se bloquera plus ou moins pour toujours. Après cela, il y a une vérification pour un chemin contigu vers l'instance en haut à gauche de la lettre sur laquelle le modèle a commencé.

feersum
la source
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*=

Essayez-le en ligne

C'est ridiculement long parce que CJam n'a pas (encore) de remplissage intégré ou de recherche d'union. J'ai implémenté union-find dans le programme.

Explication:

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
la source
4

JavaScript (ES6), 153 166

En utilisant des chaînes de modèle, il y a une nouvelle ligne qui est significative et comptée

Testez l'exécution de l'extrait dans 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
la source
2

Javascript ES6, 360

Vérifie un nombre égal de C, D, E, M, puis remplit et vérifie toutes les lettres orphelines. Pas un gagnant, mais j'ai dû essayer.

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]/))

Violon

DankMemes
la source
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))

Explication:

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
la source
1
Code intéressant (vous avez battu le mien!) Suggestion: utilisez les fonctions fléchées es6 (comme dans ma réponse) pour économiser quelques octets. Afaik vous n'avez pas besoin de l'affecter à une variable, en utilisant une déclaration de fonction simple, par exemple, l=>{...}c'est bien.
DankMemes
2
Supprimez également les parenthèses k=(o)=>pour enregistrer 2 octets supplémentaires. Les fonctions de flèche à paramètre unique n'ont pas besoin de parenthèses.
DankMemes