Car Talk puzzler

For all coding issues - MODers and programmers, HTML and more.

Moderators: Jeff250, fliptw

Post Reply
User avatar
Isaac
DBB Artist
DBB Artist
Posts: 7127
Joined: Mon Aug 01, 2005 8:47 am
Location: Ơ̸̦͇̲̬̭̱̰͎̞͈̣͎͚̳ͬ͋̃̀̇͊͂͋͐ͦ̽ͣ̂ͥ͊̅̀̚͠ B̶͖̯͉̜̰̲̓̔͋̈́ͅ È̯ Y̪̤̼͉̠̙͝

Car Talk puzzler

Post by Isaac » Sat Jan 08, 2011 11:03 am

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
User avatar
Alter-Fox
The Feline Menace
Posts: 2659
Joined: Thu May 24, 2007 12:49 pm
Location: the realms of theory
Contact:

Post by Alter-Fox » Sat Jan 08, 2011 11:51 am

That's a lot of pets :P.
I think I did something like this with Java in my high school computer science class (but not as complex).
Heretic
DBB Admiral
DBB Admiral
Posts: 1449
Joined: Wed Apr 14, 2010 6:54 pm
Location: Why no Krom I didn't know you can have 100 characters in this box.

Post by Heretic » Sat Jan 08, 2011 3:07 pm

Why not just buy 400 mice? :lol:
User avatar
Isaac
DBB Artist
DBB Artist
Posts: 7127
Joined: Mon Aug 01, 2005 8:47 am
Location: Ơ̸̦͇̲̬̭̱̰͎̞͈̣͎͚̳ͬ͋̃̀̇͊͂͋͐ͦ̽ͣ̂ͥ͊̅̀̚͠ B̶͖̯͉̜̰̲̓̔͋̈́ͅ È̯ Y̪̤̼͉̠̙͝

Re:

Post by Isaac » Sat Jan 08, 2011 8:37 pm

Heretic wrote:Why not just buy 400 mice? :lol:
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.
User avatar
Jeff250
DBB Master
DBB Master
Posts: 6387
Joined: Sun Sep 05, 1999 2:01 am
Location: ☃☃☃

Post by Jeff250 » Sun Jan 09, 2011 7:58 pm

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.
User avatar
Isaac
DBB Artist
DBB Artist
Posts: 7127
Joined: Mon Aug 01, 2005 8:47 am
Location: Ơ̸̦͇̲̬̭̱̰͎̞͈̣͎͚̳ͬ͋̃̀̇͊͂͋͐ͦ̽ͣ̂ͥ͊̅̀̚͠ B̶͖̯͉̜̰̲̓̔͋̈́ͅ È̯ Y̪̤̼͉̠̙͝

Post by Isaac » Tue Jan 11, 2011 9:36 am

OH yes! I like.
User avatar
Jeff250
DBB Master
DBB Master
Posts: 6387
Joined: Sun Sep 05, 1999 2:01 am
Location: ☃☃☃

Post by Jeff250 » Sat Jan 22, 2011 8:51 pm

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()
Last edited by Jeff250 on Tue Mar 08, 2011 5:05 am, edited 1 time in total.
Reason: testing edit
Post Reply