### Thread: Help Solving a Puzzle

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. 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).
3. 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.
4. 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.
5. 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.
6. 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
7. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2012
Posts
187
Rep Power
86
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.
8. No Profile Picture
M20
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.
9. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2012
Posts
187
Rep Power
86
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.
10. No Profile Picture
M20
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.