#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    2
    Rep Power
    0

    Help Solving a Puzzle


    Hello all!

    Today, my professor gave us a puzzle to solve using programming, but it has stumped me.

    Here is the problem:

    "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.

    The only other criterion is that you have to purchase at least one of each animal.

    How many of each animal do you have to purchase to equal a hundred animals purchased at exactly a hundred dollars?"

    Anyone know a C program to write that will search through all possible solutions?

    Help is very much appreciated! :D
  2. #2
  3. Did you steal it?
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    13,996
    Rep Power
    9397
    Here's one way you might do it if you had to answer this manually:
    Code:
    1 dog  + 1 cat   + 98 mice = 40.50
    1 dog  + 2 cats  + 97 mice = 41.25
    1 dog  + 3 cats  + 96 mice = 42.00
    ...
    1 dog  + 80 cats + 19 mice = 99.75
    1 dog  + 81 cats + 18 mice = 100.50
    Too expensive
    
    2 dogs + 1 cat   + 97 mice = 55.25
    2 dogs + 2 cats  + 96 mice = 56.00
    ...
    2 dogs + 60 cats + 38 mice = 99.50
    2 dogs + 61 cats + 37 mice = 100.25
    Too expensive
    
    3 dogs + 1 cat   + 96 mice = 70.00
    3 dogs + 2 cats  + 95 mice = 70.75
    ...
    3 dogs + 40 cats + 57 mice = 99.25
    3 dogs + 41 cats + 56 mice = 100.00
    Stop
    This incorporates a couple optimizations: (1) you always have 100 animals and (2) you stop once you go over $100. Keep in mind that the second one relies on counting the animals from most expensive (dog) to least expensive (mouse).
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    2
    Rep Power
    0
    The thing is, I haven't gotten to complex C coding yet, so I don't have a clue how to solve this.

    We've only done simple while statements.

    Algebraically, I know how to solve it. It's just translating it to C code that I don't understand.
  6. #4
  7. Did you steal it?
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    13,996
    Rep Power
    9397
    How about for loops? They're very simple and better suited to this than a while loop, though you can do it easily with either one so go with whatever you're most comfortable.


    Two loops, one inside the other. The outside loop will count the number of dogs in the "equation", starting at one (because you must have at least one dog).

    What's left is cats and mice, but since you know the total number of animals and you know the total number of dogs then you can just pick a number for one and do some subtraction to get the other. Like with five dogs, if you pick 30 cats then there have to be 100-30-5=65 mice.

    So now you've got two loops, one on the outside counting dogs (most expensive) and one on the inside counting cats (second-most expensive). Inside you do some math for the number of mice and the total cost of all the animals. If that cost is exactly 100 then you can print the current combination. If the cost is more than 100 then you should break out of the inner-most loop: because of how things are arranged, if the inner loop continues the cost will only go up so you can immediately exclude those.


    That there is a fairly technical explanation of the problem. Try translating it into code.
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,841
    Rep Power
    480
    Brutish:
    Build an array, the Cartesian product of the number of each animal. The number of triples is roughly pow(100,2) because given the number of dogs and cats fixes the number of mice. Take the dot product of that matrix with the price/animal by species vector. Compare these results with 100, making a logical mask vector. Copy the matching animal triples to the output. Well, there's only one.

    More efficient:
    If the price exceeds the count, add 4 mice. If the animal count exceeds price add a dog. Repeat, then fill with cats.


    Here's a j solution www.jsoftware.com
    Code:
       animals =: +/
       cost =: 15 1r4&(+/ .*)
       While =: 2 : 'u^:v^:_'
       dogs_n_mice =: (+ (1 0,:0 4) {~ (animals<cost)) While (animals~:cost)
       dogs_n_mice 1 0   NB. start with 1 dog
    3 56
    or you could solve directly
    Solve[15d+m/4 == d+m, m]
    56d == 3m
    if d were 3 then m would be 56, the gcd(3,56) is 1, so we're done.
    Last edited by b49P23TIvg; February 25th, 2013 at 06:57 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  10. #6
  11. No Profile Picture
    Banned
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Location
    New York
    Posts
    28
    Rep Power
    0
    Hey , the puzzle is very complicated.I tried to get the solution but its very much confused.Sorry
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    187
    Rep Power
    82
    Originally Posted by RobertWoges
    Hey , the puzzle is very complicated.I tried to get the solution but its very much confused.Sorry
    b49P23TIvg solved the puzzle mathematically:
    56d == 3m
    He essentially combined two equations into one. Let's assume D= dog, M = mouse and C = cat.

    The first equation would be the total number of animals:
    D + M + C = 100
    and the second equation would be total cost:
    D15 + M.25 + C = 100

    He merged the equations as follows:

    D15 + m.25 + (100- M - D) = 100
    D14 - M.75 + 100 = 100
    D56 - M3 + 400 = 400
    D56 - M3 = 0

    If you solve the equation you will get D=3 , M = 56, and C = 41

    The OP poster has to write a brute force program using for loops to calculate the total cost of the animals and total count of the animals. If total cost = $100 and total count = 100 then that combination of animals is a solution to the puzzle. The for loops would calculate total cost. If total cost = $100 then determine if the animal count = 100. If so, it's a solution.
    Last edited by BobS0327; February 27th, 2013 at 11:09 PM.
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Location
    Arizona, USA
    Posts
    6
    Rep Power
    0
    Here is my quick and dirty yet simple way to implement the loop. This is NOT the best way to write this. I also completely agree with the above comments into finding a mathematical solution. Unless you were asked otherwise.

    Code:
    for (d = 0; d < 100; d++){
            numC = 100;
            for (c = 0; c < 100; c++){
                    numM = 100;
                    sum = (dogPrice * numD) + (catPrice * numC) + (mousePrice * numM);
                    if (sum == 100.0)
                            printf("numD: %d\nnumC: %d\nnumM: %d\n\n", numD, numC, numM);
                    for (m = 0; m < 100; m++){
                            sum = (dogPrice * numD) + (catPrice * numC) + (mousePrice * numM);
                            if (sum == 100.0)
                                    printf("numD: %d\nnumC: %d\nnumM: %d\n\n", numD, numC, numM);
                            numM--;
                    }
                    numC--;
            }
            numD--;
            sum = (dogPrice * numD) + (catPrice * numC) + (mousePrice * numM);
            if (sum == 100.0)
                    printf("numD: %d\nnumC: %d\nnumM: %d\n\n", numD, numC, numM);
    }
    I am not completely confident of my code above and noticed that when there are 100 mice the output is repeated. Any comments would be appreciated.
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    187
    Rep Power
    82
    I am not completely confident of my code above and noticed that when there are 100 mice the output is repeated. Any comments would be appreciated.
    You might want to somewhat alter your code. One possible alternative is to have three loops, a mice loop, a dog loop and a cat loop each going from one to one hundred. We have to start at one since the requirements indicate that at least one of each animal must be purchased. You must calculate the total cost of all three animals in the innermost loop. If this total cost is equal to $100, you must then total up the dog, cat and mouse quantity count. If the quantity count is equal to 100 and the total cost is equal to $100 in the body of the innermost loop then you have a solution to the puzzle.

    Finally, keep in mind that by using b49P23TIvg's equation listed above, there will be only one solution to the puzzle. That solution is 3 dogs, 56 mice and 41 cats.
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Location
    Arizona, USA
    Posts
    6
    Rep Power
    0
    Originally Posted by BobS0327
    Finally, keep in mind that by using b49P23TIvg's equation listed above, there will be only one solution to the puzzle. That solution is 3 dogs, 56 mice and 41 cats.
    I did not realize that the pets must total to 100 pets where my code does not test for that

    Thanks BobS0327. I appreciate the support I fixed the code and sure enough I got 3 dogs, 41 cats, 56 mice.
    I hope that gives QueensNative a pretty good picture here. Again guessing that the purpose of the assignment he was given is to use and implement loops instead of figuring it out mathematically.

IMN logo majestic logo threadwatch logo seochat tools logo