¿Es justa la pizza?

27

Esta pregunta está inspirada y es la inversa de esta .

Dennis ( E), Doorknob ( D), Martin ( M) y Chris ( C) han pedido una pizza. La pizza rectangular se divide en piezas cuadradas, cada una de ellas marcada con el comedor deseado.

Escriba un programa o función que, dada una pizza rectangular que consta de 0 o más de cada letra, determine si:

  1. Cada segmento para cada persona está conectado a la ruta . Esto significa que todas las letras que son iguales deben estar directamente adyacentes entre sí (sin conexiones diagonales).

  2. El número de rebanadas por persona es el mismo para todos.

Debe generar un valor verdadero / falso con una nueva línea final opcional que indique si la pizza dada es o no justa.

Casos de prueba válidos:

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

Casos de prueba inválidos:

EDM
EDMCCMDE
DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEMDMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC
DDMMEECC
DMMEECCC

El código más corto en bytes gana.

orlp
fuente
1. ¿Qué formas de entrada son aceptables para una función? cadena con líneas nuevas? matriz con una cadena para cada línea? Matriz 2D de personajes? Todas las anteriores? 2. Entiendo que el resultado es verdadero para justo, falso para injusto, ¿o pueden revertirse?
Level River St
52
Casos de prueba válidos: DDDDDDDDDDDDD<- una pizza justa
Pomo de la puerta
@steveverrill Para este desafío, solo se acepta una cadena con líneas nuevas. Debes devolver la verdad por lo justo y la falsedad por lo injusto.
orlp
Además de las nuevas líneas, ¿solo CDEM en la entrada?
edc65
@ edc65 Correcto.
orlp

Respuestas:

5

Pyth, 53 bytes

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

Demostración

Esto es esencialmente un relleno de inundación para cada letra, seguido de una verificación de que todos los conjuntos resultantes son del tamaño apropiado.

Para el relleno de inundación, comienza con la ocurrencia superior izquierda de cada letra, luego genera todos los vecinos de las ubicaciones encontradas hasta ahora, filtra las ubicaciones con la letra correcta y se repite hasta que el conjunto deja de cambiar.

isaacg
fuente
6

Caracoles , 129

Imprime 1 para una pizza justa y 0 para una pizza injusta.

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

Versión ampliada:

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

&significa que el patrón debe coincidir en todas las ubicaciones de la cuadrícula. La primera línea verifica un número igual de cada uno de E, D, M, C. utiliza la instrucción de teletransporte t, que es una excelente manera de hacer programas con complejidad factorial. Si una entrada tiene segmentos de tamaño desigual con varias unidades para cada uno de los 4 mods, el programa se bloqueará más o menos para siempre. Después de eso, hay una comprobación de una ruta contigua a la instancia superior izquierda de cualquier letra en la que comenzó el patrón.

Feersum
fuente
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*=

Pruébalo en línea

Esto es ridículamente largo porque CJam (todavía) no tiene relleno de inundación incorporado o búsqueda de unión. Implementé union-find en el programa.

Explicación:

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
fuente
4

JavaScript (ES6), 153166

Usando cadenas de plantilla, hay una nueva línea que es significativa y contada

Prueba a ejecutar el fragmento en 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
fuente
2

Javascript ES6, 360

Comprueba el mismo número de C, D, E, M, luego inunda los rellenos y comprueba cualquier letra huérfana. No es un ganador, pero tuve que intentarlo.

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

Violín

DankMemes
fuente
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))

Explicación:

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
fuente
1
Código interesante (¡venció al mío!) Sugerencia: use las funciones de flecha es6 (como en mi respuesta) para guardar algunos bytes. Afaik no necesita asignarlo a una variable, usando una declaración de función simple, por ejemplo l=>{...}está bien.
DankMemes
2
También quite los paréntesis k=(o)=>para guardar 2 bytes más. Las funciones de flecha de un solo parámetro no necesitan paréntesis.
DankMemes