El problema de decantación

23

Dado N decantadores (0 < N <10) con eso puede contener C 0 ... C N-1 litros (0 < C <50) y un objetivo G litros, determine si es posible alcanzar ese objetivo utilizando solo el siguientes acciones:

  • Llenar una jarra
  • Vaciar una jarra
  • Vierta de un decantador a otro hasta que el que se vierte esté lleno o el que se vierte esté vacío

La cantidad objetivo G debe ser la cantidad de agua en uno de los contenedores al final. No puede tener un 'decantador de salida'.

Ejemplos

N : 2
C 0 : 5
C 1 : 12
G : 1
Resultado: Sí

N : 3
C 0 : 6
C 1 : 9
C 2 : 21
G : 5
Resultado: No

Sugerencia: Para calcular si es posible, verifique si G es divisible por el MCD de las capacidades. Además, asegúrese de que quepa en un recipiente.

Recuerde, este es el , por lo que gana el código con el menor número de bytes.

Tablas de clasificación

Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:

# Perl, 43 + 2 (-p flag) = 45 bytes

También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento de la tabla de clasificación:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Oliver Ni
fuente
Relacionado.
Martin Ender
¿Hay un "decantador de salida"? Aka, si tengo una jarra de tamaño 1, ¿es posible alguna capacidad?
Nathan Merrill
@MartinEnder Ahh. Fijo.
Oliver Ni
@NathanMerrill No hay "decantador de salida". Debe poder obtenerlo en uno de los decantadores dados.
Oliver Ni
99
Este mismo desafío estaba siendo Sandboxed .
xnor

Respuestas:

5

Gelatina , 9 8 7 bytes

-1 byte gracias a @Dennis (use división entera :, en lugar de no menos que, )

Ṁ:a⁸g/ḍ

TryItOnline

¿Cómo?

Ṁ:a⁸g/ḍ - Main link: capacities, goal
Ṁ       - maximum capacity
 :      - integer division with goal (effectively not less than goal since non-0 is True)
  a     - and
   ⁸    - left argument (capacities)
    g/  - gcd reduce over list (gcd of capacities)
      ḍ - divides
Jonathan Allan
fuente
17

Haskell, 35 bytes

l%n=n`mod`foldr1 gcd l<1&&any(>=n)l

Este papel demuestra un resultado que simplifica enormemente el problema. La Proposición 1 dice que

Puede lograr un objetivo exactamente cuando ambos son:

  • Un múltiplo del máximo común divisor (mcd) de las capacidades,
  • A lo sumo la capacidad máxima

Está claro por qué ambos son necesarios: todas las cantidades siguen siendo múltiplos del mcd, y la meta debe caber en un contenedor. La clave del resultado es un algoritmo para producir cualquier cantidad objetivo que se ajuste a estas condiciones.

Llame al operador %como [3,6,12]%9.

Una alternativa de 37 bytes:

l%n=elem n[0,foldr1 gcd l..maximum l]
xnor
fuente
Creo que el objetivo tiene que caber en uno de los decantadores, debe ser menor que el volumen del decantador más grande (según el comentario de @ Oliver "Debe poder colocarlo en uno de los decantadores dados").
m-chrzan
Convenientemente, esa es en realidad la definición utilizada en el documento y lo leí mal, por lo que es una solución fácil.
xnor
6

05AB1E , 9 8 9 bytes

Utiliza la codificación CP-1252

ZU¿%²X>‹‹

Explicación

          # true if
   %      # target size modulo
ZU¿       # gcd of decanter sizes
        ‹ # is smaller than
    ²X>‹  # target size is less than or equal to max decanter size

Pruébalo en línea!

Se guardó 1 byte utilizando el truco de la respuesta MATL de Luis Mendo

Emigna
fuente
1
utilizando el truco menos que ... que aprendí de Dennis :-)
Luis Mendo
La respuesta real sigue siendo 9 bytes ;-)
ETHproductions
@ETHproductions ¡Vaya! Parece que solo actualicé la explicación y el enlace TIO, no el código real. Gracias :)
Emigna
5

MATL , 10 bytes

&Zd\&G<~a<

Pruébalo en línea!

Esto utiliza el enfoque de @ xnor .

&Zd    % Take array C as input. Compute the gcd of its elements
\      % Take number G as input. Compute that number modulo the above. Call this A
&G     % Push the two inputs again: C, then G
<~a    % Gives 1 if some element of C is at least G; 0 otherwise. Call this B
<      % Gives true if A is 0 and B is 1; otherwise gives false
Luis Mendo
fuente
5

Excel: 43 bytes

=AND(MOD(A10,GCD(A1:A9))=0,A10<=MAX(A1:A9))

Pruébalo en línea !

Cómo usar:
coloque esta fórmula en cualquier lugar, excepto A1-A10.
Luego ingrese sus volúmenes de Decant holding en las celdas A1: A9 (porque el número de decants es fijo) y el objetivo en A10. las celdas sin decantadores deben dejarse en blanco. Donde sea que coloque la fórmula contendrá el resultado. VERDADERO si puedes lograr el objetivo, FALSO si no puedes.


fuente
5

JavaScript (ES6), 58 bytes

(n,a)=>a.some(e=>n<=e)&n%a.reduce(g=(d,e)=>d?g(e%d,d):e)<1

Otro puerto de la respuesta de @ xnor. Sí, puedo volver a usar reduce!

Neil
fuente
3
e=>n<=e
Subfunción
4

Retina , 39 bytes

\d+
$*
^(?>(1+)(,?\1)*;)(\1+)$(?<=\3.+)

La entrada debe ser una lista separada por comas de los decantadores, seguida de un punto y coma, seguido del volumen de destino. P.ej:

6,9,21;5

El resultado es 0(falso) o 1(verdadero).

Pruébalo en línea! (La primera línea habilita un conjunto de pruebas separado por salto de línea).

Explicación

\d+
$*

Esto solo convierte la entrada a unario. Luego simplemente hacemos coincidir las entradas válidas con una única expresión regular:

^(?>(1+)(,?\1)*;)(\1+)$(?<=\3.+)

La parte interior (?>...)encuentra el MCD. Hacemos esto al encontrar la subcadena más grande 1+con la que podamos unir todos los decantadores (permitiendo un opcional ,solo después de una coincidencia completa del GCD). El grupo atómico (el (?>...)) en sí mismo para que el motor regex no retroceda a los divisores del GCD si el volumen objetivo no se puede igualar (de lo contrario, el grupo se 1reducirá en algún momento para que coincida con uno solo 1y todas las entradas serán verdaderas) .

Una vez que hemos encontrado el GCD, tratamos de hacer coincidir el volumen objetivo como un múltiplo con un simple (\1+)$.

Finalmente, verificamos que el volumen objetivo no sea mayor que la capacidad de la jarra más grande, al asegurarnos de que el volumen pueda coincidir dentro de cualquier jarra con (?<=\3.+).

Martin Ender
fuente
3

Ruby, 35 bytes

->n,g{g<=n.max&&1>g%n.reduce(:gcd)}
m-chrzan
fuente
2

PARI / GP , 31 bytes

Bastante sencillo. Verificar el max ( vecmax) es muy costoso, me pregunto si se puede hacer mejor.

f(c,g)=g%gcd(c)<1&&vecmax(c)>=g
Charles
fuente
2

Perl, 47 bytes

Incluye +2 para -ap

Ejecute con los tamaños de jarra en la primera línea de STDIN y el jarra de destino en la segunda línea:

decanter.pl; echo
2 5 12
1
^D

decanter.pl:

#!/usr/bin/perl -p
$_=($_<@G)>$_%$=;$=--while@G[@F]=grep$_%$=,@F

Esta solución es inusual ya que procesa la entrada línea por línea y genera algo para cada una de ellas. El resultado de la primera línea fue cuidadosamente diseñado para estar vacío, mientras que la segunda línea imprime la solución. Dos bytes se pierden en la ()causa <y >están diseñados para ser no asociativo en Perl.

La solución regex también es buena pero 49 bytes:

#!/usr/bin/perl -p
s/\d+/1x$&/eg;$_=/^(?>(1+)( |\1)*:)(\1+)$/&/$3./

(algunas partes robadas de la solución Retina)

Para esto, ingrese STDIN como frascos separados por espacios y destino después de un ::

decanter.pl <<< "2 5 12:1"

Idiomas difíciles de superar con un incorporado gcd(21 bytes) y max(7 bytes) para este ...

Ton Hospel
fuente
0

Scala, 90 53 bytes

def h(g:Int,a:BigInt*)=a.max>g&&a.reduce(_ gcd _)%g<1

Funciona básicamente igual que las otras respuestas, pero scala no tiene una función incorporada de gcd. Scala tiene una función incorporada en gcd, pero solo para BigInt.

corvus_192
fuente