Delirious Ramblings

We've come a long way, baby

Way back in the '80s I took a couple of high school computer programming classes. They were taught using old Apple II computers and BASIC. Even though I was a total n00b and had no prior exposure to other computing platforms or environments, I intuitively knew that the whole process of writing software on those machines was really complicated and awful. Just to print out some text, write branching constructs, and do simple loops meant jumping through all kinds of syntactic loops.

To enter a BASIC program in Apple's DOS you'd have to literally type the program at the DOS prompt, entering each line of code into the computer's memory, complete with line numbers. If you needed to change the program you could LIST it out to the screen and retype the code lines but there was really no editing in the modern sense:

In the above Virtual ][ screenshot I entered a two line Applesoft BASIC program that simply prints the string "HELLO, WORLD." To make sure my program was actually there I LIST'ed my two lines of source code to the screen. I then decided to change the "HELLO, WORLD" string to "HELLO, APPLE II HERE" by retyping that line. Finally, I LISTed the modified program and ran it. As expected, the string "HELLO, APPLE II HERE" appeared on the console.

Archaic, huh? But in a nostalgic sort of way it's kinda cool nonetheless.

For simple programs it was okay but it got unwieldy for really big BASIC programs. And god help you if you needed to insert more lines of code than you had numbers for, i.e. you needed to insert six new lines of code between lines 5 and 10 of your program. There were programs you could use to redo the line numbers in your program but it still sucked.

The editing environment was bad but the BASIC language at that time was simply awful. Whereas in modern Visual Basic.NET you can do something like this

        For counter As Integer = 1 To 10
            If counter Mod 2 = 0 Then
                Console.WriteLine(counter & " EVEN")
            Else
                Console.WriteLine(counter & " ODD")
            End If
        Next

in Applesoft BASIC you had to do this:

        10 FOR C = 1 TO 10 STEP 1
        20 LET R = C = INT (C / 2) * 2
        30 IF R = 0 THEN PRINT C,"EVEN": GOTO 50
        40 IF R = 1 THEN PRINT C,"ODD": GOTO 50
        50 NEXT C
        60 END

Yuck.

They do the same thing (print if an integer between 1 and 10 is odd or even) and in about the same number of source lines but one is a whole lot more readable. Note the lack of a Modulus operator in the Applesoft version!

It gets worse. If you wanted to interface with the operating system - what little there was of it - then you had to resort to PEEK'ing and POKE'ing values into and out of arcane memory locations. Any non-trivial program's source code would be littered with hardcoded memory locations, making them all but impossible to understand. So, in one sense you were working in a high level language (BASIC) but if you needed to do anything with the machine then you immediately found yourself working very close to the "metal" as they say.

Fortunately, back in the later half of the '80s our programming teacher must've realized that learning the guts of a decade old personal computer was a pointless waste of time and I never learned what all those PEEK and POKE addresses were for. I suspect that the only reason we were still using Apple IIs and not IBM PCs was budgetary problems. The school probably got a big technology grant a few years before and someone filled the classroom full of good old Apple IIs.

Okay, so that's your trip down memory lane for this Sunday morning.

Making change in Lisp

In case you were waiting with bated breath for a Common Lisp version of the greedy recursive change-maker program, here it is:

;; Recursive greedy change-maker
(defun make-change (amount coins)
  (if (null coins)
      (format t "~%") ; hit bottom
      (let ((times (floor (/ amount (car coins)))))
        (if (eql 0 times)
            (make-change amount (cdr coins))
            (progn
              (format t "~A (~A) " times (car coins))
              (make-change (- amount (* times (car coins))) (cdr coins)))))))

If you load it into your Common Lisp (I use AquaMacs, SBCL, and SLIME) and run it you should get something like this:

CL-USER> (make-change 123 '(25 10 5 1))
4 (25) 2 (10) 3 (1) 
NIL

This means that is takes 4 quarters, 2 dimes, and 3 pennies to make change for $1.23 (the 123 in the parameter list for make-change).

You can make up your own coin denominations in this version simply by fooling around with the list of coins you pass in. For example, if you're from a country with 79, 18, 11, 7, and 1-cent denominated coins you can run:

CL-USER> (make-change 123 '(79 18 11 7 1))
1 (79) 2 (18) 1 (7) 1 (1) 
NIL

and get some odd-looking but correct counts back.

What's your hobby language?

So what's your "hobby" language? Do you have one? Or are you a "one computer language" sort of programmer?

For me that language is Perl. When I'm poking around with programming ideas or building one-off scripts for use on my Macs I always seem to turn to Perl. I know the language well enough to get most things done without too much hair-pulling and there's an active community to turn to for help if I get in over my head. And it runs on all the platforms I have access to.

Unfortunately, I don't get to write much Perl code at work anymore as most of what we're doing is Windows-only and PowerShell is the scripting language du joir at the moment. Personally, I have a love-hate relationship with PowerShell: I love having access to the .NET framework from a scripting language but I (really) hate its lame error handling and plethora of bugs and nonsense that's par for the course in a version 1.0 product. At least in its current state it's no Perl.

But I digress.

So what makes a good hobby language for those fun little projects we do in our spare time? I think the following might be a good place to start when selecting a hobby language:

• Should be powerful and expressive enough to actually accomplish what we want.
• Language-specific concepts and syntax should be easy to learn and easy to remember. Most hobby projects are done during spare time so fighting the language is a waste.
• There must be a reasonably active Internet community to turn to for support.
• Ideally will be open-source or at least available in a "free" version.
• You should have some interest in it.

If you're a programmer by trade you'll probably be tempted to just use whatever language and/or environment you're using at work. I think this is a mistake for a couple of reasons. First, who the hell wants to spend their free time essentially working in the same environment as they do for 8+ hours a day during the workweek? And secondly - and most importantly - your chances for learning something new are reduced.

So I'll go out on a limb here and state bluntly that your hobby language:

• Must be significantly different from what you use at your day job.

If you're a Visual C++ programmer then you probably shouldn't be tinkering and playing in any of the Microsoft languages. Select something like Perl, Ruby, or JavaScript. Anything that breaks you out of the .NET environment. And if you're a Linux/Unix guy at work then by all means, bring up a Windows machine at home and get cracking with Visual Studio and any of the CLR-based languages it offers. The idea here is to learn something new, work in something different, and above all, have fun!

Greedy recursive change-maker

After a little more thought I cooked up another version of the recursive change-making program. This one uses a greedy algorithm to always try to use the largest possible denomination of coins while making change. The end result is very similar to how humans make change.

Here's the Perl code:

#!/usr/bin/perl
use strict;
use POSIX;

# Coin denominations

my @allcoins = (100, 50, 25, 10, 5, 1);

sub makechange {
 my $remainder = shift @_;
 my @coins = @{ shift @_ };

 # If we've exhausted the list of coins then bail
 if ( $#coins == -1 ) {
 print "\n";
 return;
 }

 # How many of the next element of the coins array

 # will fit?


 my $coin = shift @coins;
 my $times = floor($remainder / $coin);

 if ( $times == 0 ) {
 # This coin won't fit.
 # Try next lower denomination
 &makechange($remainder, \@coins);
 }
 else {
 # The coin fits at least once.
 printf( "%d (%.2f) ", $times, $coin / 100 );

 # Recurse down to the next lower denomination
 &makechange($remainder - $times * $coin, \@coins);
 }
}

#####
# Make change for some amount entered on the command
# line.

my $change = $ARGV[0] * 100.00;
&makechange($change, \@allcoins);

Save the code out to a file and run it like this:

% perl r_greedy.pl 45.20
45 (1.00) 2 (0.10)

The output means it would use 45 silver dollars and 2 dimes to make change for $45.20. If you don't like the idea of it using silver dollars and fifty-cent pieces then shorten the @allcoins array to (25, 10, 5, 1) and it will only use quarters, dimes, nickels, and pennies.

% perl r_greedy.pl 18.39
73 (0.25) 1 (0.10) 4 (0.01)

To make change for $18.39 it would use 73 quarters, 1 dime, and 4 pennies. That's quite a pocket full of change!

[Edit: finally figured out how to post source code through TypePad.]

Recursive change-making

In my previous post I said I'd produce a recursive version of the change-making program. After spending a couple of lunch-hours experimenting with it I came up with this bit of Perl code:

#!/usr/bin/perl
use strict;

# Coin denominations
my @coins = (100, 50, 25, 10, 5, 1);

sub a_total {
  my $total = 0;
  foreach my $coin (@_) { $total += $coin; }
  return $total;
}

sub makechange {
  my $change = shift @_;
  my @solution =  @{ shift @_ };
  my $total = &a_total(@solution);

  # If we've found a solution then print it
  if ( $total == $change ) {
    print join(',', @solution) ."\n";
    return;
  }
 
  # Try each coin to see if it'll fit
  foreach my $coin (@coins) {
    # Don't use coins that push our total
    # over the amount we're making change
    # for.
    if ( ($coin + $total) <= $change ) {
      # Make a copy of the solution so far and
      # recurse down.
      my @tsolution = @solution;
      push @tsolution, $coin;
      &makechange( $change, \@tsolution);
    }
  }
}

# Make change for $1
&makechange(100, []);

The recursive version of the program uses two functions, one called a_total() that adds up the coin values of a potential solution and returns the total and the recursive change-maker function, makechange(). The program works by iterating through each type of coin (silver dollar through penny), subtracting that coin from the running total, and recursively calling itself against the remainder until it reaches zero (i.e. no remainder left), after which it's found a solution. If it can find no more coins that'll fit then the recursion stops and it bounces back up one level.

The code is somewhat easier to read than the iterative version but the solution space it builds is incorrect. Here is a sample of the first few lines of output:

100
50,50
50,25,25
50,25,10,10,5
50,25,10,10,1,1,1,1,1
50,25,10,5,10
50,25,10,5,5,5
50,25,10,5,5,1,1,1,1,1
50,25,10,5,1,5,1,1,1,1

Can you see the problem?

The program starts out by finding several very good solutions (single silver dollar (100¢), couple of half-dollar pieces, etc) but then begins spitting out permutations of essentially the same solutions. For example, it gives us 50,25,10,10,5 and 50,25,10,5,10 which are pretty much the same save for the ordering of the coins. This is technically correct but not useful for our purposes.

The reason the recursive version doesn't work the way we expect is because each successively deeper function call has no idea what went on in other branches so it can't prune the solution tree. The iterative for-loop-based version doesn't have to worry about that as there is no recursion.

We could fix this version using a global array to check possible solutions against but we'd still need to generate all those permutations, and that turns out to be an excessively expensive operation. We'll stick with iterative version, thank you very much!

Brother, can you spare some change?

The other day when I was at the local grocery store I paid for some stuff with cash and one of those change-making machines clicked out a couple of quarters and a few pennies as change. I've done this many times over the course of my life and never thought much about it. But this time was different. For some reason it struck me that that change-maker was actually a pretty intelligent device. Not only do these machine need to make change quickly and accurately but they need to do it in such a way that store customers don't leave with their pockets bulging with pennies when a couple of quarters would work just as well. In other words, they're not just blindly spitting out the first solution they find but are actually looking for an optimal solution to a difficult real-world problem.

A search on the google quickly confirmed my suspicion that making change intelligently and optimally is no easy task. See the side bar on the Wikipedia article on Greedy Algorithms article. To find the best possible solution requires dynamic programming and an exhaustive search of the entire solution space. By solution space I mean all possible combinations of coins that add up to our desired total. So, for example, if you're making change for $1 then that solution space contains 293 combinations, assuming you are using the six currently circulating U.S. coins (silver dollars, half dollars, quarters, dimes, nickels, and pennies). The solution space will be smaller if you're looking to make change for values less than a dollar (i.e. 54¢) or if you don't allow certain coins like the silver dollar or half dollar.

Like a lot of computer science problems, generating all the possible combinations of U.S. coins that add up to some value can be done in two ways: iteratively and recursively. For this post I'll go with the iterative method because it's slightly easier to understand. In a later post I'll switch to a recursive version for readability and code succinctness.

Here's some Perl code you can use to iteratively print out the complete $1 change-making solution space:

#!/usr/bin/perl
use strict;

my $change = 100; # 1$ = 100 pennies

for (my $sd=0; ($sd*100) <= $change; $sd++) { 
  for (my $hd=0; ($hd*50) <= ($change - $sd * 100); $hd++) {
    for (my $q=0; ($q*25) <= ($change - $sd * 100 - $hd * 50); $q++) {
      for (my $d=0; ($d*10) <= ($change - $sd * 100 - $hd * 50 - $q * 25); $d++) {
        for (my $n=0; ($n*5) <= ($change - $sd * 100 - $hd * 50 - $q * 25 - $d * 10 ); $n++) {
          printf("%d Silver Dollars, %d Half Dollars, %d Quarters, %d Dimes, %d Nickels, %d Pennies\n",
                 $sd, $hd, $q, $d, $n, ($change - $sd * 100 - $hd * 50 - $q * 25 - $d * 10  - $n * 5) );
        }
      }
    }
  }
}

[TypePad clipped the longest lines off but if you select the code with your mouse and paste it into a text editor it's not actually gone; it just looks that way. ]

As you can see, the code is nothing but five nested for-loop statements, each one corresponding to successively smaller coin denominations. Each nested for-loop simply computes the combinations of coins needed to add up to the remainder of the previous loop's running total. By the way, that last sentence should clue you in to the recursive solution to this problem.

If you paste the code into a source code file and run it through Perl you'll get 293 lines similar to this:

0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 0 Nickels, 100 Pennies
0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 1 Nickels, 95 Pennies
0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 2 Nickels, 90 Pennies
0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 3 Nickels, 85 Pennies
0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 4 Nickels, 80 Pennies
...
1 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 0 Nickels, 0 Pennies

On my 2.4GHz iMac this code takes about 10 milliseconds to run. That's really fast.

If you want to compute the solution space for values other than $1 then simply modify the value of $change in the third line from 100 (100 pennies) to something else, like say 54 (i.e. 54¢). Doing that yields a much smaller solution space of 50 combinations. Conversely, boosting it up to a larger value like 1,000 ($10), gives us a significantly larger solution space of 2.1 million combinations. Taking it up to $20 (2,000 pennies) bloats the solution space to over 53 million possible combinations. $30 has about 380 million combinations and $50 has 4.5 billion combinations. That last $50 run kept my iMac busy for almost 35 minutes while it crunched through all those coins.

My point here is to show how quickly the solution space for something seemingly simple like making change can grow. Exhaustively searching through all those combinations for a good solution is not going to cut it when you start adding domain-specific constraints like differing numbers of available coins, scarcity of available coins with which to dispense change, random change-making values, unknown daily transaction volumes, etc.

In my next post we'll switch to a recursive change-making program, add some constraints, and get "greedy" to help cut down on the search space.