Page 1 of 1
Car Talk puzzler
Posted: Sat Jan 08, 2011 11:03 am
by 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
Posted: Sat Jan 08, 2011 11:51 am
by 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).
Posted: Sat Jan 08, 2011 3:07 pm
by Heretic
Why not just buy 400 mice?
Re:
Posted: Sat Jan 08, 2011 8:37 pm
by Isaac
Heretic wrote: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.
Posted: Sun Jan 09, 2011 7:58 pm
by 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.
Posted: Tue Jan 11, 2011 9:36 am
by Isaac
OH yes! I like.
Posted: Sat Jan 22, 2011 8:51 pm
by 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()