The Decanting Problem
Haskell, 35 bytes
l%n=n`mod`foldr1 gcd l<1&&any(>=n)l
This paper proves a result that vastly simplifies the problem. Prop 1 says that
You can achieve a goal exactly when it's both:
- A multiple of the greatest common divisor (gcd) of the capacities,
- At most the maximum capacity
It's clear why both of these are necessary: all amounts remain multiples of the gcd, and the goal must fit in a container. The key of the result is an algorithm to produce any goal amount that fits these conditions.
Call the operator %
like [3,6,12]%9
.
A 37-byte alternative:
l%n=elem n[0,foldr1 gcd l..maximum l]
05AB1E, 9 8 9 bytes
Uses the CP-1252 encoding
ZU¿%²X>‹‹
Explanation
# 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
Try it online!
Saved 1 byte utilizing the less than trick from Luis Mendo's MATL answer
MATL, 10 bytes
&Zd\&G<~a<
Try it online!
This uses @xnor's approach.
&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