1
\$\begingroup\$

Because there isn't enough xkcd on PPCG...

Challenge

The challenge is the same as above - given a menu and a total price, you need to find what the customer ordered.

The menu will be supplied as a text file in the format:

Name:Price
Name:Price

The path to the menu file and the total price should be supplied via argv or STDIN. If you wish, the menu may be supplied via STDIN/argv (instead of newlines, separate each item by commas).

The output should be a list of values. If there are multiple answers, output all of them.

Example

Menu:

Burger:12.60
Pepsi:3.50
Lobster Thermidore:33.10
Ice Cream:23.00

Total Price: 68.70

The output is:

Burger
Lobster Thermidore
Ice Cream

Winning

The fastest code given an undisclosed problem wins. The speed will be taken five times and averaged.

\$\endgroup\$
16
  • 1
    \$\begingroup\$ Can the menu be directly input via STDIN/arguments ? \$\endgroup\$
    – Optimizer
    Oct 4, 2014 at 22:53
  • 1
    \$\begingroup\$ Limitation of a file makes a lot of programming languages impossible to use here. \$\endgroup\$
    – Optimizer
    Oct 4, 2014 at 22:53
  • 1
    \$\begingroup\$ What do you mean by fastest code ? Time wise ? Complexity wise ? If its time wise, then its completely unfair \$\endgroup\$
    – Optimizer
    Oct 4, 2014 at 22:54
  • 2
    \$\begingroup\$ Why unfair? I assume OP will run the undisclosed test case on their machine. However, it should be run multiple times for each submission to rule out noise. It also begs the question if there are limitations of the languages that can be used. \$\endgroup\$
    – Ingo Bürk
    Oct 4, 2014 at 23:44
  • \$\begingroup\$ @IngoBürk If there are two answers, 1 in JS and 1 in C, JS one is bound to be slower what so ever. \$\endgroup\$
    – Optimizer
    Oct 5, 2014 at 7:16

1 Answer 1

2
\$\begingroup\$

Python 2 - Naive implementation - 224

Well, let's start with "the most naive algorithm" as some kind of reference solution:

import itertools

path = input()
total = input()

with open(path) as f:
    menu = map(lambda l: l.split(':'), f.read().split('\n'))

names, prices = zip(*menu)
prices = map(float, prices)

for i in range(len(menu)):
    for comb in itertools.combinations(range(len(menu)), i):
        if sum(prices[c] for c in comb) == total:
            for i in comb:
                print names[i] 

Input:

"data.txt"
68.70

Output:

Burger
Lobster Thermidore
Ice Cream

Complexity:

O(2^N * N)

--> exponential in the number of menu items N (of course)


Edit:

To reflect the new winning criterion I golfed it down quite a bit:

from itertools import*
S=str.split
f,t=S(input())
m=[S(l,':')for l in S(open(f).read(),'\n')]
R=range(len(m))
F=float
for i in R:
 for C in combinations(R,i):
  if sum(F(m[c][1])for c in C)==F(t):
   for j in C:print m[j][0]

The input format changed to data.txt 68.70 (both on one line separated with a whitespace).

\$\endgroup\$
3
  • \$\begingroup\$ I'm pretty sure the naive implementation is the only one anyone is going to have the stamina for. \$\endgroup\$
    – COTO
    Oct 5, 2014 at 14:57
  • \$\begingroup\$ @COTO: Agree. And if tested with a menu filled with 100 appetizers (!?) a complexity of O(2^N * N) vs. O(2^(N/2)) doesn't even matter. ;) \$\endgroup\$
    – Falko
    Oct 5, 2014 at 15:05
  • \$\begingroup\$ Sorry for being so indecisive, but to avoid this being marked as a dupe, I've changed it back to fastest code. \$\endgroup\$
    – Beta Decay
    Oct 6, 2014 at 6:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.