Pouring beer

Pouring beer

(file name: pour.pl)

Ethan just ordered a jug of beer, to be split evenly among a group of friends. At the table is a collection of (sufficiently) clean glassware in a range of sizes, but - perhaps due to having had a pint or three - he cannot partially fill glasses with any precision.

Assume Ethan may only pour beer from one container into another until either (a) the source is empty or (b) the destination is full. Given the glassware available, can Ethan divide the beer fairly amongst his friends? That is, can the beer be split between vessels, and the vessels (including the jug) allocated to friends, such that each friend receives an equal share of beer?

Input format

An input file for LP systems contains the following facts:

  • One fact of the form vessels(N) denoting the number of vessels.
  • One fact source(V) denoting the (full) vessel which is to be shared.
  • One fact of the form people(M) specifying the number of people sharing the beer.
  • A relation capacity(V, K) specifying the capacity K of each vessel V.
  • An additional fact horizon(L) gives an upper bound on the number of actions to be taken.

An input file for Minizinc specifies the number of vessels and people (vessels and people respectively), the source vessel (source), and the capacity of each vessel (capacity).

Output format

The output should contain exactly one fact: split(yes) if the jug may be fairly split among the available glasses, and split(no) otherwise.

Examples

LP input Minizinc intput Output
vessels(4).
source(1).
people(3).
capacity(1, 12).
capacity(2, 4).
capacity(3, 3).
capacity(4, 1).
horizon(10). 
vessels = 4;
source = 1;
people = 3;
capacity = [12, 5, 3, 1];
split(yes).
vessels(4).
source(1).
people(3).
capacity(1, 12).
capacity(2, 3).
capacity(3, 3).
capacity(4, 2).
horizon(10). 
vessels = 4;
source = 1;
people = 3;
capacity = [12, 3, 3, 2];
horizon = 10;
split(no).
vessels(5).
source(1).
people(3).
capacity(1, 12).
capacity(2, 3).
capacity(3, 3).
capacity(4, 3).
capacity(5, 2).
horizon(10). 
vessels = 5;
source = 1;
people = 3;
capacity = [12, 3, 3, 3, 2];
horizon = 10;
split(yes).
ċ
Graeme Gange,
Aug 30, 2017, 2:28 AM
Comments