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

Tags:

Math

Code Golf