* FAQ    * Search  * Register * Login 
Active topics
Unanswered topics

All times are UTC-06:00



Post new topic  Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Car Talk puzzler
PostPosted: Sat Jan 08, 2011 11:03 am 
Offline
DBB Artist
DBB Artist
User avatar

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

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


Top
   
 Post subject:
PostPosted: Sat Jan 08, 2011 11:51 am 
Offline
The Feline Menace
User avatar

Joined: Thu May 24, 2007 12:49 pm
Posts: 2625
Website: http://vertigofox.bandcamp.com
Location: the realms of theory
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).


Top
   
 Post subject:
PostPosted: Sat Jan 08, 2011 3:07 pm 
Offline
DBB Admiral
DBB Admiral

Joined: Wed Apr 14, 2010 6:54 pm
Posts: 1449
Location: Why no Krom I didn't know you can have 100 characters in this box.
Why not just buy 400 mice? :lol:


Top
   
 Post subject: Re:
PostPosted: Sat Jan 08, 2011 8:37 pm 
Offline
DBB Artist
DBB Artist
User avatar

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


Top
   
 Post subject:
PostPosted: Sun Jan 09, 2011 7:58 pm 
Offline
DBB Master
DBB Master
User avatar

Joined: Sun Sep 05, 1999 2:01 am
Posts: 6377
Location: ☃☃☃
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:
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:
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:
>>> 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.


Top
   
 Post subject:
PostPosted: Tue Jan 11, 2011 9:36 am 
Offline
DBB Artist
DBB Artist
User avatar

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


Top
   
 Post subject:
PostPosted: Sat Jan 22, 2011 8:51 pm 
Offline
DBB Master
DBB Master
User avatar

Joined: Sun Sep 05, 1999 2:01 am
Posts: 6377
Location: ☃☃☃
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:
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.
testing edit


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 7 posts ] 

All times are UTC-06:00


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron



Descent'rs have piloted these pages
 
The layout and contents contained within this site are © DescentBB.net 1997-2006.
Descent, Descent II are © Parallax Software Corporation.
Descent III is Outrage Entertainment.
Descent is a Trademark of Interplay Productions.

Miner Wars™ is trademark of Keen Software House s. r. o.
.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group