# (Scheme) Computer science @ school..



## Kantastic (Feb 21, 2010)

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 (Feb 21, 2010)

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 (Feb 21, 2010)

unibrow1990 said:


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



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


----------



## unibrow1990 (Feb 22, 2010)

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 (Feb 22, 2010)

unibrow1990 said:


> 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 (Feb 22, 2010)

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 (Feb 22, 2010)

```
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 (Feb 22, 2010)

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 (Feb 22, 2010)

unibrow1990 said:


> 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 (Feb 22, 2010)

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 (Feb 22, 2010)

unibrow1990 said:


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



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 (Feb 22, 2010)

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 (Feb 22, 2010)

unibrow1990 said:


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



unibrow1990 said:


> ]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 (Feb 22, 2010)

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 (Feb 22, 2010)

unibrow1990 said:


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



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 (Feb 22, 2010)

Scheme has an "and" statement 
	
	



```
(and form1 form2)
```

It also has or and not:
	
	



```
(or form1 form2)
(not form)
```


----------



## Kantastic (Feb 22, 2010)

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


----------

