Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Loop/Array Logic

Rick Rodriguez
Ranch Hand
Posts: 44
I am currently having trouble reasoning through some mathematical logic. I have been tasked to write a program that can take 50 coins and note the different combinations that could be used to generate \$1.00.
Only and all 50 coins must be utilized. I have poured over the for/while looping logic, as well as array functionality.
Can anyone give me any "hints" or straight forward logic guidance on this progject? Incidently, since this is a homework project, hinting would be preferred.
Thank you.
[This message has been edited by Rick Rodriguez (edited June 02, 2001).]

Val Dra
Ranch Hand
Posts: 439
Did they tell you what amount of each coins there are ?
[This message has been edited by Val Dra (edited June 02, 2001).]

Junilu Lacar
Bartender
Posts: 7466
50
Originally posted by Rick Rodriguez:
Can anyone give me any "hints" or straight forward logic guidance on this progject? Incidently, since this is a homework project, hinting would be preferred.

It's very commendable of you to say that. I'd give you an A+ for integrity.
I suspect the modulus operator (%) would play a part in the logic and a while loop as well. You have to make some assumputions too, like what the different coin denominations are. Some countries have a 20-cent coin but no 25-cent coin.
Junilu

Rick Rodriguez
Ranch Hand
Posts: 44
The denominations are:
Penny: .01
Nickel: .05
Dime: .10
Quarter: .25
[This message has been edited by Rick Rodriguez (edited June 02, 2001).]

Rick Rodriguez
Ranch Hand
Posts: 44
Thank you for the integrity statement. I know that we can share code, for the most part, but I want to try to understand this logic on my own. Not being able to do this on my own, however, I need to turn to someone for some hints.
I appreciate the feedback. Have you been able to create such a program, with the parameters I have outlined?
Thanks again.

Originally posted by JUNILU LACAR:
It's very commendable of you to say that. I'd give you an A+ for integrity.
I suspect the modulus operator (%) would play a part in the logic and a while loop as well. You have to make some assumputions too, like what the different coin denominations are. Some countries have a 20-cent coin but no 25-cent coin.
Junilu

Bill Norton
Greenhorn
Posts: 27
You only wanted hints so hear goes:
You probably need 4 nested loops, one for each coin. In the innerest(real word?) loop you would need two test conditions:
1. adding up all four loop values to see if they equal 50
2. adding up all four loop values plus mulipling by the value(.1, .5, .10., .25) to see if equals a \$1.00
Note: on the second step you would be much better off using 1,5,10,25 and seeing if it adds up 100
Also Note: If my algebra is correct, there is only one solution, if you have to use all the coins.
Sorry if this was too much or not enough.
But I hope this helps,
Bill

Mike Curwen
Ranch Hand
Posts: 3695
There is a point of confusion for me:

You said "only and all 50 coins must be used." If true, this is very simple. Add all coins up in sequence received, and if they don't make 1.00, then no other combination will do that either. If they do add up, then that must mean that ... it's on the tip of my brain...

i'll make it simpler for myself. Imagine 4 coins passed in a 4-entry array. Imagine further that they are all quarters.
The combinations are:
1,2,3,4
2,3,4,1
3,4,1,2
4,1,2,3
umm...
2,1,4,3
etc....
isn't it 4 to the 4th combinations? But maybe this logic only works because my example has been reduced to a too-simple base case.

Or for the question being asked, is this actually only one combination, and 'order' is not being considered. The problem becomes much easier if that is the case. (ie: once you find a combination of coins, you don't need to list off all possible combinations of THAT combination).

"Using any number of the 50, but only from those 50..." is probably what is meant?

Rick Rodriguez
Ranch Hand
Posts: 44
I appreciate your response Bill. Have you been able to recreate the solution to my project and are now feeding me hints? I just want to verify that it has worked for you, before moving forward.
You mentioned "if your algebra is correct" below. What theorem/formula did you use?
Thanks again Bill and anyone else who may be able to create this piece of code, feeding me hints afterwards.
Thanks again.
Originally posted by Bill Norton:
You only wanted hints so hear goes:
You probably need 4 nested loops, one for each coin. In the innerest(real word?) loop you would need two test conditions:
1. adding up all four loop values to see if they equal 50
2. adding up all four loop values plus mulipling by the value(.1, .5, .10., .25) to see if equals a \$1.00
Note: on the second step you would be much better off using 1,5,10,25 and seeing if it adds up 100
Also Note: If my algebra is correct, there is only one solution, if you have to use all the coins.
Sorry if this was too much or not enough.
But I hope this helps,
Bill

Rick Rodriguez
Ranch Hand
Posts: 44
I appreciate you replying to my posting Mike. To answer your question, I need to utilize all 50 coins. Apparently, there are several combinations, less than 10, of 50 U.S. coins that can add up to \$1.00.
Have you been able to create this code? Thanks again Mike.
Originally posted by Mike Curwen:
There is a point of confusion for me:

You said "only and all 50 coins must be used." If true, this is very simple. Add all coins up in sequence received, and if they don't make 1.00, then no other combination will do that either. If they do add up, then that must mean that ... it's on the tip of my brain...

i'll make it simpler for myself. Imagine 4 coins passed in a 4-entry array. Imagine further that they are all quarters.
The combinations are:
1,2,3,4
2,3,4,1
3,4,1,2
4,1,2,3
umm...
2,1,4,3
etc....
isn't it 4 to the 4th combinations? But maybe this logic only works because my example has been reduced to a too-simple base case.

Or for the question being asked, is this actually only one combination, and 'order' is not being considered. The problem becomes much easier if that is the case. (ie: once you find a combination of coins, you don't need to list off all possible combinations of THAT combination).

"Using any number of the 50, but only from those 50..." is probably what is meant?

Mike Curwen
Ranch Hand
Posts: 3695
When Bill said "if my algebra is correct", he was thinking along the same lines I was.

There is no real 'formula', but just think hard for a second. If you are given a single array of 50 coins, and you must use ALL of them to see if they add up to 1.00, then this is a TRUE/FALSE situation. Do they add up, or don't they? If they don't, then adding them up in a different order will not produce a different result. But what I get from your next comment, is that you want a list of all arrays that successfully add up to \$1.00...

Your last sentence "Apparently, there are several combinations, less than 10, of 50 U.S. coins that can add up to \$1.00" really helped clarify the program requirement.

The brute force method is an easy approach. You have 50 positions to fill (one for each of the 50 coins). There are four possible values in each position (1,5,10,25). That means there are 4 to the 50 combinations you must check. When you add up a certain combination, and it equals \$1.00, then remember that combination. The list of combinations that adds up to \$1.00 will be your answer.

This is different than what I thought you were supposed to do. I thought it was "I've given you 50 random coins. How many ways can you make \$1.00? (you can use as little as 4 coins, and as many as 50)".

I am a geek with nothing better to do today.. sigh...

I think I'll work on this a bit.

Mike Curwen
Ranch Hand
Posts: 3695
I have a program that finds two combinations. Anyone else?

p.s. My earlier musings might lead you to produce a program with 50 nested for loops. Sorry about that. Loops represent coins.. think of it that way. Bill's hints were much better.

Bill Norton
Greenhorn
Posts: 27
Rick you mentioned that there was more than one combination that would work. Do you have to use each type of coin? If you do than I believe there is only one possiblility here is why
p = # of pennies
n = # of nickels
d = # of dimes
q = # of quarters
You have two equations that can now be derived
p+n+d+q = 50
1p + 5n + 10d + 25q = 100 //I multiplied by 100 to make things pretty here
If you solve for p in the second equation you get
p = 100 - 5n - 10d - 25q
Now substituion p into the first equation
100-5n-10d-25q+n+d+q= 50
Simplify
-4n-9d-24q = -50
4n + 9d + 24q = 50
Now since q is the amount of quarters there are only a few possiblities. q= 1,2,3
3 would not work
So for 2-> 4n + 9d + 24(2) = 50
4n + 9d = 2
Can't work!
Therefore the only possible value left is q=1
This leaves us with a new equation
4n + 9d + 24 =50
4n + 9d = 26
Now d would have to equal 2 to make the equation
4n + 9(2) = 26
4n = 8

n=2
Any other values for 9d or 4n will not add up to 26.

Now if you don't have to use all types of coins then you could just have q=0, and get the equation
4n + 9d =50
Ther are some more possibilities there.
Well need to go lawn needs moving and it looks like rain!
Bill
ps I didn't proof read sorry for mistakes

Mike Curwen
Ranch Hand
Posts: 3695
The original question didn't state that you had to use at least one of each type, only that you had to use 50 coins that add up to 100.

q d n p
0 2 8 40 = 100 count = 50
1 2 2 45 = 100 count = 50

Rick, when you are done (or close), post your code and let us see how you did it.

Junilu Lacar
Bartender
Posts: 7466
50
Originally posted by Mike Curwen:
> I have a program that finds two combinations. Anyone else?
I got the same results.
Rick, using brute force, you can find the good combinations using three "for" loops.
Junilu

Bob Graffagnino
Ranch Hand
Posts: 81
I too got the same results using 4 "for" loops. Each "for" loop has the local variables totalCoins and totalCoinAmount. These variables are initalized to the values of the corresponding outer loop variables. For instance:

[This message has been edited by Bob Graffagnino (edited June 04, 2001).]

Junilu Lacar
Bartender
Posts: 7466
50
Originally posted by Bob Graffagnino:
>>I too got the same results using 4 "for" loops
You could probably simplify your solution. 3 nested "for" loops are sufficient really because another loop for pennies would be superfluous. Also, I didn't use any variables other than the three for-loop index variables. I did have a separate 3-line method that determined whether a combination of coins met the criteria.
Junilu

Mike Curwen
Ranch Hand
Posts: 3695
Like most programs I write, I usually start with the longest or most 'brute force' way of doing it.. especially with math or logic problems.

And then come the optimizations.

I've gone through two 'cycles' of this optimization effort, and I admit to thinking there must be a way to kill off the outer loop (the quarters loop). But now thanks to Junilu, I see now why the pennies loop was worse than useless (it's a big timewaster!). So I've got it down to three loops as well.

Hopefully Rick will tell us when the due date is, so I can see if my code is the best it could be.

Roger Graff
Ranch Hand
Posts: 112
Doh! You're right, the pennies loop is not needed. Anyone come up with a recursive solution?
-Sorry moderators. I accidently posted this message as graff48 instead of my corrected user account Bob Graffagnino.
[This message has been edited by graff48 (edited June 05, 2001).]

Mike Curwen
Ranch Hand
Posts: 3695
I try to back away slowly from anything recursive

But I admit to thinking 'there is probably a way to do this with recursion'.

Joel Cochran
Ranch Hand
Posts: 301
In all logic problems some assumptions have to be made. As I understand it, our assumptions here are:
1: We have w pennies, x nickels, y dimes, and z quarters.
2: w + x + y + z MUST equal 50 and there cumulative value MUST equal 100.
This allows us to conclude that only x penny values evenly divisable by 5 could complete our needs, so we can set the penny array like so... { 5, 10, 15, 20, 25, 30, 35, 40, 45 }. 0 and 50 are automatically excluded since they do not meet the minumum requirements.
Now we can write a function to whittle this down a little: we'll use 45 for the 1st example.
1: 45 pennies provides a difference of 5 coins.(50 - 45 = 5).
2: The 5 coins must total 55 (100 - 45 = 55).
*2A: Add a vlidity check here: multiply the # of coins (5) x our denominator (5) = 25. Is this less than the amount needed (55)? Yes, so you can continue. {If NOT then this number of pennies is not valid and you can stop here.}
3: Can 5 coins containing at least one nickel, one dime, and one quarter = 55? To find out we add 5 + 10 + 25 and get 40. (this could actually become a program constant)
4: 55 - 40 = 15.
5: Divide 15 by our denominator (5) = result (3).
6: A Static array of arrays could determine what the corresponding values would be (*hint: a result of 3 would point us to a positional Array[3] which would have subsequent Array[3][0]=5 and Array[3][1]=10. Array[0] and Array[1] would both be null) Deciphering the Array values will tell you which coins you need to add to your assumed coins ( 45 pennies, 1 nickel, 1 dime, 1 quarter ) to achieve a value of 100.
7: So our solution for 45 is "45 pennies, 2 nickels, 2 dimes, and 1 quarter"
Confused? Me too... let's test it with penny array 20...
1: 20 pennies provides a difference of 30 coins.(50 - 20 = 30) .
2: The 30 coins must total 80 (100 - 20 = 80).
*2A: Validity check: multiply the # of coins (30) x our denominator (5) = 150. Is this less than the amount needed (80)?
No, it is not, so this number of pennies cannot represent a valid solution.
Now that you've built the function, loop through the array and call it 9 times, printing out the good results and you should come up with a correct solution. I hope this helps in some way... it may not be complete but should give you plenty to think about!
------------------
I'm a soldier in the NetScape Wars...
Joel
[This message has been edited by Joel Cochran (edited June 05, 2001).]

Joel Cochran
Ranch Hand
Posts: 301
Sorry for the second post, but I wanted to point out that there are a couple of things I intentionally left out of my solution to give Rick a chance to work with some of the ideas since he said this was for a homework assignment.
------------------
I'm a soldier in the NetScape Wars...
Joel

Marcellus Tryk
Ranch Hand
Posts: 64
Bob -
Here's a recursive solution. It prints a solution as a sequence of coins in descending order. If anyone would like to try it out you can compile it and run it at the command line to solve any problem of this form. It could easily be modified to accept coins of arbitrary denomination.
To solve the stated problem: java Coins 100 50
By the way I believe this problem is np-complete. Does anyone have any opinions on this?
Here's the basic idea of this algorithm:
The trivial case is one coin. There's a solution if the amount is equal to a valid denomination and no solution if it isn't.
Otherwise -
Remove a quarter and see if there's a solution for what you have left (amount - 25, coins - 1). Do the same with a dime, nickel, and penny.
-----------------------------------------------------------------

[This message has been edited by Tod Tryk (edited June 07, 2001).]
[This message has been edited by Tod Tryk (edited June 07, 2001).]

Rick Rodriguez
Ranch Hand
Posts: 44
Todd,
I appreciate your help, but we (our class) haven't learned the "Switch" statement yet. We're still on loops.
To let everyone know, tonight our teacher could not understand, after class, why I could not understand this simple concept. When he discovered that the "nested" for loop concept was not explained, either in the book or by himself last week, he reminded me to teach the rest of the class next week.
At any rate, after he explained the logic of how nested for loops work, "Eyes Are Open!"
This project is due next week for me. I will, however post my code within the next two days. Please wait to post your own until such time, as it may be deemed as "cheating" on my part, if it is inferred that I got my code from this message board.
Thank you again everyone, and come back to see my code this Saturday.

Marcellus Tryk
Ranch Hand
Posts: 64
Rick -
I know you didn't want a solution, but I figured since your implementation is supposed to use nested loops you wouldn't mind if I posted the recursive algorithm as a curiosity.
Best of luck on finishing your assignment - I'm looking forward to seeing it!
Tod

Mike Curwen
Ranch Hand
Posts: 3695
Just that I'd raise my hand and say "Holy cow I feel dumb." LOL.

That coding example is why I back away slowly from recursion. And I haven't heard "np-complete" since I dropped out of University.

But thanks for the code, because God help me, I'm going to try and understand it.

Marcellus Tryk
Ranch Hand
Posts: 64
Mike -
I don't even know if it makes sense to ask if this problem is np-complete. I was wondering if there might be a way to discover all the solutions to the coin problem without exhaustive search - and then I thought - naah this problem is probably np-complete. Being very non-expert in this area I was hoping someone could shed some light on it. Anyway I think I'm getting off-topic so let me just say in conclusion - I encourage the use of logic when constructing loops that process arrays.

Rick Rodriguez
Ranch Hand
Posts: 44
Ok Guys! I have finally coded this program. If it were only explained to me, either in my text book or by my teacher, the "logic/flow" of nested 'for' loops, I would have never needed to post questions on this matter in the first place.
I started coding this program at approximately 1:00pm and finished at approximately 2:00pm, ET. Most of that time was spent in my IDE's debug session, looking at how the 'for' loops rotate to find the parameters defined.
At any rate, here is my homework code:

Incidently, the text that my "Intro to Java" course utilizes is 'JAVA: Programming From the Beginnnig', by K.N. King. I think that this is a fantastic book for beginners, and I can only speak from that perspective, since I am a beginner.
Thanks again guys for all of your input, and let me know if I can "fine tune" my code any further.
(edited by Cindy to format code)
[This message has been edited by Cindy Glass (edited June 09, 2001).]

Junilu Lacar
Bartender
Posts: 7466
50
The solution below is pure brute force. I don't know if having "if" statements in each of the for-loop actually makes a whole lot of difference. Finding bottlenecks should really be done with a profiler though. I go by the XP philosophy of going for simple and clear code first, then refactor to optimize for performance using the results of using a profiler.
<pre>
{
public static void main(String[] args)
{
// We don't need a loop for pennies because
// we can derive the penny count from the
// count of other coins we have so far
for (int q = 0; q < 4; q++)
for (int d = 0; d < 10; d++)
for (int n = 0; n < 20; n++)
if ( isGoodCombo(q, d, n) )
System.out.println(
" 25c = " + q +
" 10c = " + d +
" 5c = " + n +
" 1c = " + (50-q-d-n));
}

// chose to move evaluation to a separate method
// to keep the main loop code clear and concise
static boolean isGoodCombo(int q, int d, int n)
{
int p = 50 - q - d - n;
return ((p + q + d + n) == 50) &&
((q*25 + d*10 + n*5 + p) == 100);
}
}
</pre>
[This message has been edited by JUNILU LACAR (edited June 10, 2001).]

Mike Curwen
Ranch Hand
Posts: 3695
Hi Rick,

I'm assuming the empty if() statements between your for loops were used during development for debugging? Otherwise, I can't see what they'd be used for, except perhaps a 'continue' statment? As it is, they are doing nothing...

I would also suggest there is a small (negligable) optimization that can be made to the quarters loop. You can bring the exit condition down to < 3. Also, regard how others have dropped the pennies loop... pennies are worth '1' each, and we can determine how many of them there are by how many of the other coins there are.

The last thing is also a very slight optimization, but if we are talking about efficiency, then lets squeeze everything we can out of math...Your innermost if() statement is coded thus Because Java performs short-circuited ANDs, we can realize (I know, I know) a very small boost, if you place the second test first. That way, it only does 4 additions, instead of 3 multiplications and then 4 additions. Because we need both of them to be true, we should always check the 'cheapest' side first. Once it proves to be false, Java ignores the other side of the AND (short-circuited AND). Congratulations on figuring it out.

fred cook
Greenhorn
Posts: 8
In general, when you are trying to code always look for an algebraic way to make the code work faster. Brute force is a lowsy way to do stuff. Try to stay away from using it. The responses you've been getting could be very useful in the future.
--Freddy
------------------
I have a cute bird