(Scheme) Computer science @ school..

[Kantastic]

I've been working on this problem for an hour...

Write the function (minCoins cents) that reports the minimum number
of coins required to make the amount cents. Assume cents is a nonnegative
integer and the only coins available are : quarters, dimes, nickels,
and pennies.


    Test Cases:
    (minCoins 5) -> 1             
    (minCoins 26) -> 2
    (minCoins 31) -> 3
    (minCoins 4) -> 4
    (minCoins 118) -> 9

And this is where I'm stuck:

(define (minCoins x)
(+ (quotient x 25)
(quotient (remainder x 25) 10)))

This will give me the proper result if I put in any amount of cents that only require quarters and dimes. I've tried going further with nickels but nothing seems to work.

My latest attempt is:

(define (minCoins x)
(+ (quotient x 25)
(quotient (remainder x 25) 10)
(quotient (remainder (quotient (remainder x 25) 10) 5))
))

Logically it makes sense to me but it doesn't seem to work. I'll be frank, I'm terrible at this coding stuff and this is my second time taking the course because I flunked the first time. I just don't get this stuff at all!

Help would be nice!

Edit: Just tried

(define (minCoins x)
(+ (quotient x 25)
(quotient (remainder x 25) 10)
(quotient (remainder x 10) 5)))

 

[unibrow1990]

I don't know scheme at all, but here is a solution in common lisp(a similar language that I do know) maybe it can help you find your solution. As a hint, you'll see that i used several variable beyond the initial given value, try doing that first to get your statement working, and then if you really don't want the extra variables slowly take them out.

(defun mincoins (x)
    (let ((q nil)(d nil)(n nil))
        (setf q (truncate (/ x 25)) x (rem x 25)
          d (truncate (/ x 10)) x (rem x 10)
          n (truncate (/ x 5)) x (rem x 5))
        (+ q d n x)))

Hope this helps you out, if not I'll try and pick up a little scheme and see if I can help more.

 

[Kantastic]

I don't know scheme at all, but here is a solution in common lisp(a similar language that I do know) maybe it can help you find your solution. As a hint, you'll see that i used several variable beyond the initial given value, try doing that first to get your statement working, and then if you really don't want the extra variables slowly take them out.

(defun mincoins (x)
    (let ((q nil)(d nil)(n nil))
        (setf q (truncate (/ x 25)) x (rem x 25)
          d (truncate (/ x 10)) x (rem x 10)
          n (truncate (/ x 5)) x (rem x 5))
        (+ q d n x)))

Hope this helps you out, if not I'll try and pick up a little scheme and see if I can help more.

I sort of see what you're doing there but I don't know how to apply it to Scheme.

 

[unibrow1990]

Alright well I wrote a working example in scheme. I don't want to just want to give you the answer so I will tell you that you need the quotient and remainder you were already using as well as the "let*" form, which which creates lexical variables in the order they are given. Try and figure it out yourself and if you still can't figure it out I will post the solution.

 

[Kantastic]

Alright well I wrote a working example in scheme. I don't want to just want to give you the answer so I will tell you that you need the quotient and remainder you were already using as well as the "let*" form, which which creates lexical variables in the order they are given. Try and figure it out yourself and if you still can't figure it out I will post the solution.

I don't mean to question your solution, but is there a way to do it without using let? I think I came very close: (The reason being that let wasn't covered in the class and the teacher said quotient and remainder were all that was needed.)

(define (minCoins x)
(+ (quotient x 25)
(quotient (modulo x 25) 10)
(quotient (modulo x 10) 5)
(modulo x 5)))

Modulo is the same as remainder, I remember it from my first time taking the course... one of the few things I actually understood. If I made it so that the above code would subtract 1 from all of it's outputs then I'd be spot on.

Edit: Here's what I mean:

(define (minCoins x)
(- (+ (quotient x 25)
(quotient (modulo x 25) 10)
(quotient (modulo x 10) 5)
(modulo x 5)) 1))

Wait, that's wrong.

 

[unibrow1990]

I think you are very close, but to be perfectly honest the problem is going to be much cleaner and easier to solve if you use at least 1 more variable, i.e a variable to hold the number of coins you used so far and one to hold the amount of change you still need to break down. You can do it the way you are trying two, but it seems like a more complicated answer. There is always more than 1 way to do it.

 

[Disparia]

function minCoins($c) {
	$t = intval($c / 25);
	$r = $c % 25;
	$t+= intval($r / 10);
	$r = $r % 10;
	$t+= intval($r / 5);
	$t+= $r % 5;
	return $t;
}

Don't know how much my PHP solution lends itself to Scheme. I put the output of it from 1 to 1000 cents here if you need a quick list to check your output.

 

[unibrow1990]

I came up with a second solution that doesn't use let*, and is based on what you posted above I will post both as spoilers in case you still want to figure is out for yourself. If you want further explanation of any point just ask.

Spoiler

(define (mincoins x)
    (let* ((y (quotient x 25))(x (remainder x 25))(y (+ y (quotient x 10)))
    (x (remainder x 10))(y (+ y (quotient x 5)))(x (remainder x 5)))
    (+ x y)))

(define (mincoins x)
    (+ (quotient x 25)
        (quotient (remainder x 25) 10)
        (quotient (remainder (remainder x 25) 10) 5)
        (remainder (remainder (remainder x 25) 10) 5)))

 

[Kantastic]

I think you are very close, but to be perfectly honest the problem is going to be much cleaner and easier to solve if you use at least 1 more variable, i.e a variable to hold the number of coins you used so far and one to hold the amount of change you still need to break down. You can do it the way you are trying two, but it seems like a more complicated answer. There is always more than 1 way to do it.

Wait! I think I got it:

(define (minCoins x)
(+ (quotient x 25)
(quotient (modulo x 25) 10)
(quotient (modulo (modulo x 25) 10) 5)
(modulo x 5)))

I believe that's 100% correct. If it's not too much can you please verify if it's correct? And if it is, I'd love to see your code using let so that I can apply that to other problems in the future!

If there's a flaw (there shouldn't because I tried a lot of different coin combinations) then I'll give up and look up how to use let.

 

[unibrow1990]

Thats great, your solution seems to wok perfectly and it's different from the two I came up with, just shows what I mean about there always being many ways to solve the same problem. Both of my solutions are in the post above yours.

 

[Kantastic]

Thats great, your solution seems to wok perfectly and it's different from the two I came up with, just shows what I mean about there always being many ways to solve the same problem. Both of my solutions are in the post above yours.

Awesome! There's a huge smile on my face right now and it looks something like this:

Thanks a lot for helping me through this problem, it was a serious headache. And yes, now I know that there's always a different solution.

PS - You know what I just realized? It took me 4-5 hours to find one solution to a problem that took you minutes to find 2 different solutions for, and you didn't even know the language!

Edit: So that was part 1, I finished part 2 because that was easy (still took me an hour), and now I'm doing part 3. Part 3A looks simple enough but 3B is going to be a pain, I'll be back if I'm stuck.

Here's part 2:

Part II:
=======
For this part, assume n is a positive integer less than 1000 and n not a
multiple of 10.

1. Write the function (onesDigit n) that evaluates to the ones
digit of integer n.

Test Cases:
(onesDigit 3) -> 3
(onesDigit 62) -> 2
(onesDigit 239) -> 9


2. Write the function (tensDigit n) that evaluates to the tens
digit of integer n. Assume n is greater than 10.

Test Cases:
(tensDigit 25) -> 2
(tensDigit 162) -> 6



3. Write the function (hundredsDigit n) that evaluates to the hundreds
digit of integer n. Assume n >= 100.

Test Cases:
(hundredsDigit 315) -> 3
(hundredsDigit 821) -> 8

4. Write the function (reverseDigits n) that reverses the digits in
the integer n. You can use the procedures from above to write
your solution.

Test Cases:
(reverseDigits 3) -> 3
(reverseDigits 62) -> 26
(reverseDigits 921) -> 129

Here are my solutions in proper order:

(define (onesDigit n)
(modulo n 10))

(define (tensDigit n)
(modulo (quotient n 10) 10))

(define (hundredsDigit n)
(modulo (quotient n 100) 100))

(define (reverseDigits n)
(+
(modulo (quotient n 100) 100)
(* 100 (modulo n 10))
(* 10 (modulo (quotient n 10) 10))))

 

[unibrow1990]

Awesome Just a quick question, where do go to school that they teach you to program using scheme? Also as for not knowing the language, in this particular problem there was virtually no difference between scheme and common lisp(which I know fairly well) otherwise I would have been clueless.

Those are some really nice solutions for part II by the way.

 

[Kantastic]

Awesome Just a quick question, where do go to school that they teach you to program using scheme? Also as for not knowing the language, in this particular problem there was virtually no difference between scheme and common lisp(which I know fairly well) otherwise I would have been clueless.

Stuyvesant High School in New York, NY.

It's a mandatory course and I hate it with all my heart.

]Those are some really nice solutions for part II by the way.

Thanks.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Working on part 3 right now, it's a little harder than I thought.

 

[unibrow1990]

As far as I can tell you use "set!" in scheme to assign a new value to a variable that has been declared, so you should be able to use that along with an if statement to solve part III really easily.

You don't even need "set!" just "if" and the literal values for true and false.

If you are still having trouble just remember that lisp's if statement is just an if else so really all you need is

(if (algorithm for finding leap years) true-value false-value)

 

[Kantastic]

As far as I can tell you use "set!" in scheme to assign a new value to a variable that has been declared, so you should be able to use that along with an if statement to solve part III really easily.

You don't even need "set!" just "if" and the literal values for true and false.

If you are still having trouble just remember that lisp's if statement is just an if else so really all you need is

(if (algorithm for finding leap years) true-value false-value)

Is there a way to form sort of an "and" statement in lisp/scheme? I'm having a hard time writing the code so that it defines a leap year as a year thats divisible by 400 but not 100. I've been trying for an hour... jeez I'm really bad at this stuff. I'm gonna hit the shower and see if I take wake myself up.

 

[unibrow1990]

Scheme has an "and" statement

(and form1 form2)

It also has or and not:

(or form1 form2)
(not form)

 

[Kantastic]

:shadedshu

I can't figure this one out. It's midnight, I'm gonna sleep and try again tomorrow unless he goes over it in class.