Car Talk puzzler

[Isaac]

This morning I listened to the car talk puzzler and thought it would make a fun Python challenge:

\"You're given a hundred dollars and told to spend it all purchasing exactly a hundred animals at the pet store. Dogs cost $15. Cats cost a buck, and mice are 25 cents each.\"

Code: Select all

for dogs in [dogs*15 for dogs in range(100)]:
     for cats in [cats*1 for cats in range(100)]:
             for mice in [mice*0.25 for mice in range(100)]:
                     if mice+dogs+cats==100 and (mice/0.25)+(cats/1)+(dogs/15)==100 and mice>0 and cats>0 and dogs>0:
                             print \"%s Dogs =$%s\"% (dogs/15,dogs)
                             print \"%s Cats =$%s\"% (cats/1,cats)
                             print \"%s Mice =$%s\"% (mice/0.25,mice)

 

My answer:
3 Dogs =$45
41 Cats =$41
56.0 Mice =$14.0

[Alter-Fox]

That's a lot of pets .
I think I did something like this with Java in my high school computer science class (but not as complex).

[Heretic]

Why not just buy 400 mice?

[Isaac]

Why not just buy 400 mice?

I believe Tom and Ray said you must have at least one of each animal and you also have to have exactly 100 animals purchased.

[Jeff250]

Without the constraint that we need 100 pets, if we wanted to minimize the number of pets bought, and because the cost of dogs, cats, and mice divide evenly into each other, we can use an efficient greedy algorithm to exactly solve this problem:

Code: Select all

remaining = 10000
dogs, remaining = remaining // 1500, remaining % 1500
cats, remaining = remaining // 100, remaining % 100
mice, remaining = remaining // 25, remaining % 25
print '%d dogs, %d cats, %d mice' % (dogs, cats, mice)

Otherwise, my preference is to just write it as one big list comprehension:

Code: Select all

solutions = [(x, y, 100 - x - y)
             for x in range(100)
             for y in range(100 - x)
             if 1500 * x + 100 * y + 25 * (100 - x - y) == 10000]
print '%d dogs, %d cats, %d mice' % solutions[0]

Also, I strictly used integers, since using equality comparison with floating point numbers is bad. For example:

Code: Select all

>>> sum([0.2] * 5) == 1.0
True
>>> sum([0.1] * 10) == 1.0
False

Essentially, you can't guarantee that they will always round exactly the way you want them to, so they could be off by an extremely small fraction and thus not be equal.

[Isaac]

OH yes! I like.

[Jeff250]

Looking over this again, there is still room for improvement. My answer is unnecessarily inefficient, since it will try to find multiple solutions even though we are only interested in the first solution. Below I've replaced the list comprehension with a generator expression/comprehension. This means that the solutions will be generated lazily:

Code: Select all

solutions = ((x, y, 100 - x - y)
             for x in xrange(100)
             for y in xrange(100 - x)
             if 1500 * x + 100 * y + 25 * (100 - x - y) == 10000)
print '%d dogs, %d cats, %d mice' % solutions.next()