snack buying

I got this text message from my father-in-law:

Ok. Soda 1.50 Chocolate bar 1.00 Gum 0.10 Jelly Bean .05

Have to buy exactly 14 items and spend $10

At least one of each.

There are 4 diff combos. (Order: soda, chocolate, gum and jelly bean)

Got 5-2-3-4 3-5-4-2

Can’t get others. Any ideas? :)

I whipped up this solution to check in python:

#!/usr/bin/python3
# created_at: 2017-11-13 13:53:19 -0800

def main():
    solutions = 0
    for si in range(1,7):
        for ci in range(1,11):
            for gi in range(1,101):
                for ji in range(1,201):
                    total = si*150 + ci*100 + gi*10 + ji*5
                    items = si + ci + gi + ji
                    if total == 1000 and items == 14:
                        print(si,ci,gi,ji, total, items)
                        solutions += 1
    print(solutions)

if __name__ == "__main__":
    main()

The core of this solution is the check

total = si*150 + ci*100 + gi*10 + ji*5
items = si + ci + gi + ji
if total == 1000 and items == 14:
    print(si,ci,gi,ji, total, items)
    solutions += 1

in the innermost for-loop. It checks that we spent exactly $10 (1,000 cents) and got exactly 14 items.

I used 7, 11, 101, 201 as the upper bounds here to limit the search, because if we bought purely that item, we’d be limited to 6, 10, 100, 200 as the upper bounds for each product, respectively. This implies that we search $$6 * 10 * 100 * 200 = 1,200,000$$ possible solutions! This was based on an initial mis-reading of the question – I didn’t notice the “14 items” constraint. If we restrict the upper bound to 14 for the gum & jelly bean count, we only have to examine $$6 * 10 * 14 * 14 = 11,760$$ solutions!

In any case, the above code outputs:

3 5 4 2 1000 14
5 2 3 4 1000 14
2

so his original two solutions are the only two!

I was thinking about trying to make a less brute-force solution with octave’s linear programming routines, like:

A = [
  150, 100, 10, 5;
    1,   1,  1, 1;
]
b = [
  1000;
  14;
]
lb = [1,1,1,1]; ub = [inf, inf, inf, inf];

glpk([1,0,0,0], A, b, lb, ub, 'SS', 'IIII')
glpk([-1,0,0,0], A, b, lb, ub, 'SS', 'IIII')

which returns

octave:55> glpk([1,0,0,0], A, b, lb, ub, 'SS', 'IIII')'
ans =
   3   5   4   2
octave:56> glpk([-1,0,0,0], A, b, lb, ub, 'SS', 'IIII')'
ans =
   5   2   3   4

This is a bit unsatisfying because we had to tweak the objective function to get the two different solutions, so there’s no proof that we can’t get more solutions, which is what the original problem was asking. But it’s still a nice way to get some initial solutions.

We can also modify the problem definition to check if there are any solutions with 4 sodas:

A = [
  150, 100, 10, 5;
    1,   1,  1, 1;
    1,   0,  0, 0;
]
b = [1000;14;4];
glpk([0,0,0,0], A, b, lb, ub, 'SSS', 'IIII')'

which returns

octave:51> glpk([0,0,0,0], A, b, lb, ub, 'SSS', 'IIII')'
ans =
    NA    NA    NA    NA

so we can conclude that there aren’t any. We can establish the same for 1 and 2 sodas.

We could do better with custom tree search algorithm, but I’ll save that for another post :-)