Friday, February 15, 2008

Scheme For Enlightenment Part Seventeen - C Change

So the next idea is to see what this looks like in C. I've said before that the Scheme version is fast enough. So this exercise is pointless, meaning that it is an exercise.

It's really handy to pass part of the list and use recursion. Can this be done in C without using a linked list library and making copies of lists? Yes. One might use an array, pass a pointer or an index potentially part way into the array, use a handy delimiter so we know when to stop. No need to make copies. The sub lists end at the same place as the full list. Arrays are dumb lists, but are good enough for this sort of thing.

But the recursive structure is still handy, so we'll continue using it.

#include <stdio.h>
#include <stdlib.h>

/* -1 for end of list of coins */
int coins[] = { 50, 20, 10, 5, 2, 1, -1 };

int cc(int am, int c[]) {
if (am == 0) {
return 1;
} else {
if (am < 0 || c[0] == -1) {
return 0;
} else {
return cc(am - c[0], &c[0]) + cc(am, &c[1]);
}
}
}

int main(int argc, char *argv[]) {
printf("%d\n", cc(atoi(argv[1]), coins));
return 0;
}

This version works. But i wondered out loud what it might look like using a more Scheme-like syntax. I'm pretty sure no one (sane) would write it this way. The question mark operator isn't very commonly used. Most C programmers think nested comma operators are hard to read. They are. And yet, formulated this way you can still see what is returned fairly quickly. It's whatever is right after a '?', or the last colon.

/* -1 for end of list of coins */
int coins[] = { 50, 20, 10, 5, 2, 1, -1 };

int cc(int am, int c[]) {
return (am == 0) ? 1 :
(am < 0 || c[0] == -1) ? 0 :
cc(am - c[0], &c[0]) +
cc(am, &c[1]);
}

Again, the original LispMe version for comparison. I'm still trying to wrap my head around how to spot the Scheme return values. As near as i can tell, there's no way around matching the parenthesis for the if operators. The first one is easy. The second one has triple nested parenthesis. And the else clause of the second if starts with addition. The result of the addition is also possibly returned. I was hoping that the Emacs indention would give visual clues. It does. It says that the second if is nested as a clause of the first. It says that the addition operator is a clause of the second if, and the two cc calls are part of the addition. Look sharp for the two constants that are the first clauses of the if's. They seem to just hang there doing nothing. These can be returned.

; count change
(define coins '(50 20 10 5 2 1))

(define (cc am c)
(if (eq? am 0) 1
(if (or (< am 0) (null? c)) 0
(+ (cc (- am (car c)) c)
(cc am (cdr c))))))

1 comment:

Stephen said...

Scott Aaronson has posted a draft of his article from this month's Scientific American on the limitations of quantum computers (PDF). With a nice graph, he outlines classes of problems - P, BQP, NP, NP-Complete, and PSPACE. These are in order of difficulty. Map coloring is listed as NP-Complete, along with Traveling Salesman and Theorem-Proving. But i used map coloring as an example of an easy problem. I'd no idea it is considered NP-Complete. And, my C version colors the continental US in 20 milliseconds on a desktop - too small to be a really reliable timing. If this problem is m^n, where n is the number of states, then m appears to be about 1.277. If that's the case, then 100 states should require more than an hour. That would be an interesting experiment, because intuition suggests that 100 states would also be more or less instant.

The wiki article talks about the related problem of finding the Chromatic number as NP-Hard, a class not mentioned by Aaronson. I've always thought that NP-Hard is like NP-Complete, only more so. Does it fit in between NP-Complete and PSPACE? Or is NP-Hard a synonym for PSPACE?

The quantum limitations submission is very interesting for itself. Very well presented. One of the better articles from the Library of Babel.