grocery Test Program

The name relates to the 7-eleven franchise of convenience stores. The franchise itself derives its name from the extended opening hours 7 a.m. until 11 p.m. One internet source attributes the problem to Doug Brumbaugh from the University of Central Florida. It must have been posted as a problem of the week as early as May 31, 2004. We adapted the problem in that we only ask for three prices instead of four, and in that we ask for a total sum of $6.42.

There is a pure Prolog and a CLP(FD) solution. The CLP(FD) solution is straight forward. The pure Prolog solution does use a special enumeration of solutions to a multiplication constraint by factorizing. Let’s assume that a constant c has the following prime factors:

c = p1^n1 * .. * pm^nm

Solutions to the constraint c = x*y can be generated by assigning shares of the different prime factor exponents to the variables x and y. This is done by the predicate split/4 in the pure Prolog solution. There is still some work to do, when there are large prime factors.

Both solutions produce the same unique prices, sorted by their magnitude:

?- grocery(X).
X = [375, 160, 107] ;
false

?- grocery3(X).
X = [375, 160, 107] ;
false

Comments