Code Golf: Mezcle las nueces para que ninguna del mismo tipo toque

16

Entrada:

La entrada es una matriz aleatoria de tuercas (en su idioma), siguen las posibles tuercas. Su programa debe tener una forma de representar cada tipo de tuerca, como un código entero. El programa debe ser capaz de manejar cualquier tamaño de matriz de cualquier configuración de tuercas.

Nueces posibles:

Kola nut
Macadamia
Mamoncillo
Maya nut
Mongongo
Oak acorns
Ogbono nut
Paradise nut
Pili nut
Pistachio
Walnut

Salida:

La salida debe ser la matriz ordenada de tal manera que no haya tuercas adyacentes del mismo tipo. Si esto es imposible, la salida debería ser una matriz vacía.

Entrada de ejemplo (simplificada):

["walnut", "walnut", "pistachio"]

Salida de ejemplo:

["walnut", "pistachio", "walnut"]

Las soluciones no pueden simplemente barajar la matriz hasta que se vuelva única por casualidad. El tipo empleado debe ser determinista.

¿Nueces mixtas?  ¡Veo dos almendras tocando!

Thomas Dignan
fuente
44
"Su programa debe tener una forma de representar cada tipo de tuerca, como un código entero" ¿por qué es eso? - "no puede simplemente barajar la matriz hasta que se vuelva única por casualidad. El tipo empleado debe ser determinista", una barajadura aún puede ser determinista. ¿Simplemente quiere imponer un límite en la complejidad del tiempo del programa?
dejó de girar en contra del reloj el
1
Tengo que estar de acuerdo con @leftaroundabout porque prohibir que un algoritmo en particular sea una tontería sin una muy buena razón. Una de las cosas más gratificantes sobre los juegos de código como este es exactamente la variedad de métodos que se emplean.
dmckee
@dmckee, creo que el requisito de que el algoritmo sea determinista es razonable: si el RNG es defectuoso o la entrada es bastante larga, una solución no determinista puede no terminar.
stand
@boothby. Meh Soy un físico de partículas. Monte Carlo es una herramienta importante por derecho propio. Además, si elijo un PRNG fijo y una semilla fija, es determinista.
dmckee
1
Creo que encontré un ejemplo que tiene varias soluciones, pero puede causar que algunas respuestas no encuentren ninguna. ¿Puedo agregarlo? (5,4,4,3,3,2) perl6 -e 'my @a="aaaaabbbbccccdddee".comb;my @b = @a.pick(*) while @b.squish !== @a;say [~] @b' baedcbdacdecbabaca(3,3,2) también pueden hacer que fallen.
Brad Gilbert b2gills

Respuestas:

8

GolfScript, 42 41 37 38 caracteres

~.`{\`{=}+%1-,}+$.,)2//zip[]*.2<..&=*p

El código espera entrada en STDIN e imprime el resultado en STDOUT, por ejemplo:

> ["walnut" "walnut" "walnut" "macadamia" "pistachio"]
["walnut" "macadamia" "walnut" "pistachio" "walnut"]

> ["walnut" "walnut" "walnut" "macadamia" "walnut"]
[]

El guión se hizo más largo de lo esperado, pero supongo que hay margen de mejora.

Editar: el caso de una lista con un solo elemento me cuesta 1 personaje (la mejor comparación que puedo encontrar es la misma que la de Peter).

Howard
fuente
1
Todavía no me había sentado para implementar esto, pero $.,)2//zipes exactamente lo que tenía en mente. Mi interpretación de la especificación fue que podría recibir información en la pila y dejarla en la pila, por lo que tal vez deberíamos presionar para obtener una aclaración.
Peter Taylor
@PeterTaylor, genial. Funciona para mi.
Boothby
Esto se bloquea en la entrada ["walnut"]en la sección de comparar los dos primeros.
Peter Taylor
@PeterTaylor Tienes razón. Tendré que trabajar en ese caso de la esquina.
Howard
6

GolfScript, 32 caracteres

~:x{]x\-,}$.,)2//zip[]*.2<..&=*`

Mismo formato de entrada y salida que la solución de Howard.

Peter Taylor
fuente
Tuve la misma idea en la parte de clasificación, pero aún no la codifiqué :-) ¡Buen trabajo!
Howard
6

Brachylog v2, 10 bytes

p.¬{s₂=}∨Ė

Pruébalo en línea!

Solución de fuerza bruta. (Esta es una función, permitida porque el desafío no dice "programa completo"). También es principalmente una traducción directa de la especificación (la única sutileza real es que logré organizar las cosas para que todas las restricciones implícitas llegaran exactamente lugares correctos, por lo que no necesita caracteres adicionales para desambiguarlos).

Tenga en cuenta que este es un algoritmo genérico para reorganizar cualquier tipo de lista para que no tenga dos elementos en contacto; puede manejar representaciones en cadena de los elementos y también puede manejar códigos enteros. Por lo tanto, realmente no importa cómo "Su programa debe tener una forma de representar cada tipo de tuerca, como un código entero". requisito de la pregunta se interpreta.

Explicación

p.¬{s₂=}∨Ė
p            Find a permutation of {the input}
  ¬{   }     which does not have the following property:
    s₂         it contains a pair of adjacent elements
      =        that are equal
        ∨    {no constraint on what value the equal elements can have}
 .           If you find such a permutation, output it.
        ∨    If no permutation is found, ignore the input and
         Ė     {output} an empty list
ais523
fuente
1

J, 80 caracteres

]`_:@.(0<2&([:+/=/\))({.~-:@#),((],.|.)~>.@-:@#)<"1;(\:#&.>)(</.])[;.1' ',1!:1[1

No realmente en la misma liga que Golfscript en este caso. Sospecho que hay ganancias por hacer, pero los 14 caracteres necesarios solo para obtener la lista en el programa[;.1' ',1!:1[1 es una gran desventaja.

Básicamente, el programa toma la lista, agrupa elementos similares, ordena por número de elementos en cada grupo descendente y alterna la salida entre la primera mitad y la segunda mitad de la lista. El resto si el código se deshace de elementos extraños y decide si la lista es una salida válida (salida infinita_ si no lo es).

Ejemplo:

macadamia walnut walnut pistachio walnut

grupo (</.]):

macadamia walnut walnut walnut pistachio

ordenar (\:#&.>):

walnut walnut walnut macadamia pistachio

ravel ((],.|.)~>.@-:@#):

walnut macadamia walnut pistachio walnut
Gareth
fuente
0

Jalea , 14 bytes

Ġz0UẎḟ0ịµẋ⁻ƝẠ$

Pruébalo en línea!

Los últimos 6 bytes se pueden eliminar si podemos tener un comportamiento indefinido para entradas no válidas.

Erik el Outgolfer
fuente
0

Stax , 10 bytes

│éÿ∞å[zàL⌂

Ejecutar y depurarlo

Aquí está el mismo programa desempaquetado, sin golf y comentado.

|T      get all permutations
{       block to filter by
  :g_=  after dropping repeated elements, it's still equal
f       execute filter
|c      terminate and pop if falsy (no match)
hJ      take the first permutation, and join with spaces

Ejecute este

recursivo
fuente