Careful with that infinite list, Eugene...

Warning: this will give away one way to solve a certain low-numbered Project Euler problem.

Any Haskell book, blog, or tutorials you come across has a good chance of including the très élégant Haskell one-liner for an infinite list containing the Fibonacci sequence:

fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))

Thanks to laziness, it will only evaluate out to the last term we actually request... that was, long ago, my downfall. I wanted the terms no bigger than four million, so

filter (<= 4000000) fibs

right? Wrong. You and I know that the Fibonacci sequence is monotonically increasing, but filter doesn't, and it doesn't even notice the particular function we're filtering with to realize it could terminate thanks to monotonicity. So instead,

takeWhile (<= 4000000) fibs

is the way to go.

The particular problem has an additional constraint, because it only wants the even terms of the sequence no bigger than four million. Easy enough to do, just feed it through

filter even

and you're good. It did, though, occur to me: does the order of filtering matter? I mean, just plain

filter even fibs

is still an infinite list... but as long as we only actually evaluate finitely many values, we're safe.

filter even $ takeWhile (<= 4000000) fibs

and

takeWhile (<= 4000000) $ filter even fibs

both terminate and, as you'd expect, give the same result--but while the order doesn't matter to the result, it may matter for speed. Given that the first Fibonacci number is even and the next odd, the whole sequence is thus even, odd, odd, even, odd, odd, ... so

takeWhile (<= 4000000) $ filter even fibs

will only check a third as many values for being no more than four million.

TMTOWTDI, Haskell Style

I assure you there will be no further allusions to Korean earworms. That said, on to the subject at hand...

Remember the exercise in the online Haskell course that had several tests to filter out weak passwords, all of which had to pass for the fictitious system to allow a String value to be used as a password? I wanted to make it easy to change, so I wanted to take a [String -> Bool] and get a [Bool] I could apply and to for the final thumbs up/thumbs down decision.

The first step: roll my own, which has a pleasing symmetry with map if you write it as a list comprehension:

wonkyMap fs x = [f x | f <- fs]

Then I stumbled across Derek Wyatt's blog post about using sequence for the purpose. Life was good... and then I got Haskell Programming from first principles, and life got better, because its authors do a very good job of explaining the Applicative type class. Applicative defines two functions, pure and (<*>):

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

Here f is a unary type constructor like Maybe or [] (both of which happen to be in Applicative). Being a Functor is a prerequisite for being an Applicative, as you can see from that first line. pure, given a value of type a, gives you back one of type f a. (<*>) is intended to act like function application, letting you take plain old a -> b values and apply some number of them (possibly zero--an empty list is a list, and Nothing is a Maybe (a -> b)) to some number of a values in an f a and get back an f b.

For our purposes, f is [], and if you think about it there's not much choice for what pure and (<*>) can be:

 instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]

That's almost exactly what we want--the only thing we have to do is put our candidate password in a list (purify it?), like so:

s `satisfies` cs = and $ cs <*> [s]

So, for this exercise, Haskell is kind of Perl-like: TMTOWDI (there's more than one way to do it). Some would say this shows Haskell is Perl-like in a worse way, namely having weird unintelligible operators. I won't take a position, save to say that ghci makes it a lot easier than Perl (or APL, the original "WTF does this do?" language). :t is your friend!

Prelude> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

Now, are all three ways we've come up with equally good? Rolling your own function is a way to start, but why reinvent the wheel? sequence works, but

Prelude> :t sequence

sequence :: (Monad m, Traversable t) => t (m a) -> m (t a)

is far more general than (<*>), so that it takes more thought to realize it can be used this way. (<*>) more directly and specifically says it has to do with what we want, so I would argue that it is clearer.

One more thing: type classes don't just have functions; they have rules that those functions must follow. I urge you to track down the rules for Applicative and persuade yourself that [] satisfies them.

Haskell Tool Stack for Ubuntu 16.04

I've upgraded to Ubuntu 16.04 beta 2, and so far, as I've read elsewhere, it's working very nicely.

(One warning: if you have apcupsd installed, turn it off before upgrading! During the upgrade, something happens that causes the UPS battery to look fully discharged, and apcupsd will obligingly shut your system down... in mid-upgrade. Others have seen this when upgrading to 15.10.)

Now I'm reinstalling the various packages I had previously installed, but for FP Complete's Haskell Tool Stack, trying the Ubuntu instructions FP Complete gives (mutatis mutandis for the version) doesn't work, at least as I write. It looks like it's made its way into the Ubuntu repositories, so that sudo apt-get install haskell-stack will do the trick. I'm also quite pleased to see that 16.04 is actually up to date with respect to GHC. ghc --version shows it has 7.10.3. (Now to look to see whether it's up to snuff on the libghc* packages in the repositories...)

A rather long blast from the past about recursion elimination and a bit of complexity theory

While going through old papers, I found something I wrote as a follow-up to an article by Aaron Banerjee in the February 1999 issue of the world of 68’ micros (you can find a somewhat mangled version online here). Both concern recursion elimination, with the well-known “eight queens” problem (place eight queens on a chess board so that none attacks any other) as an example.

I don’t remember whether I submitted it, or whether it was printed. I’m also embarrassed by the barely legible layout—large Helvetica with nearly no leading. To let me toss the printout and keep the text, and to make it easier to read (if only by me), here it is again, with formatting help from LibreOffice and editing for clarity and concision, not to mention fixing bugs I caused by not directly copying and pasting source code. I will come back and fix indentation on the BASIC09 code, after a little experimentation.

Recursion Elimination and the Eight Queens Problem

In the February 1999 the world of 68’ micros, Aaron Banerjee discussed recursive algorithms and how to implement them in languages that don’t support recursion. The Fibonacci sequence has a closed form, and can be turned into an iterative form, but in general, recursion elimination requires an explicit stack that takes the place of the stack typically used to implement function calls. The stack holds state information about parts of the problem to be done later, and actually corresponds to the local variables in a recursive call. Like Mr. Banerjee, we will use the eight queens problem as an example, and in addition to recursion elimination, we’ll try to speed up the check for valid arrangements.

BASIC09, unlike Color BASIC, directly supports recursion and procedures with local variables—you have to go outside the language itself, e.g. with a data module, to get the effect of global variables. Instead of doing that, we’ll have a top-level function declare variables for things like the chess board to pass to the procedure that does the real work.

procedure main

dim row, col, nsols: integer; board(8, 8): boolean

for row := 1 to 8

for col := 1 to 8

board(row, col) := false

next col

next row

nsols := 0

run queen8(1, board, nsols)

print nsols; “ solutions”

end

The board array is boolean because we’re just putting queens on the board; each square either has one (true) or it doesn’t (false). The parameters of queen8 are

1. The column we’re about to try to put a queen in.
2. The board itself, which is updated as queens are placed on it or removed.
3. A count of the number of solutions we’ve seen so far; we added it to give a simple test. (A change from one run to another means we either broke something or fixed something.)

Our queen8 is turned around a bit from Mr. Banerjee’s. Rather than testing whether we have a full solution at entry (i.e. looking for col = 9), we check after placing a queen—it reduces the number of calls at the deepest level (and it means the test is for col = 8 rather than 9).

procedure queen8

param col: integer; board(8, 8): boolean; nsols: integer

dim row: integer; ok: boolean

for row := 1 to 8

run check(board, row, col, ok)

if ok then

board(row, col) := true

if col = 8 then

nsols := nsols + 1

run show(board)

else

run queen8(col + 1, board, nsols)

endif

board(row, col) := false

endif

next row

end

[Note from 2016: even if BASIC09 were in the optimization business, the call by reference would keep it from hoisting the evaluation of col = 8 out of the loop. We happen to know check won’t fiddle with col, so we could do it ourselves—but in a large program subject to change, that’s dangerous, and it can be easy to forget to write “run check(board, row + 0, col + 0, ok)” to force the issue. Given its constraints, call by reference was the way to go for BASIC09, but it’s not perfect.]

Now for the check procedure. Rather than iterating over each position to the “left” of the current column, we just look at the positions that can attack the tentatively-placed queen, which has the following advantages:

• It looks at at most three positions per column rather than eight.
• It can be done with one loop instead of two.
• If we only look at attacking positions, we need only check the board for true, rather than checking whether the position is attacking.

Alas, BASIC09 evaluates both operands of boolean operations, so it’s a bit clumsy.

[Note from 2016: unlike the first version of this article, I will stick with the BASIC09-imposed layout. My experience with the Go programming language and the layout that gofmt imposes, thereby avoiding the endless bikeshedding and arguing over layout that afflicts some other languages, makes me appreciate BASIC09’s having established a standard in that regard almost three decades earlier.]

procedure check

param board(8, 8): boolean; row, col: integer; result: boolean

dim delta: integer

result := true

for delta := 1 to col – 1

exitif board(row, col – delta) then

result := false

endexit

if delta < row then

exitif board(row – delta, col – delta) then

result := false

endexit

endif

if row + delta <= 8 then

exitif board(row + delta, col – delta) then

result := false

endexit

endif

next delta

end

The show procedure is straightforward. To assist the eye in judging the queens’ positions, we print guide lines.

procedure show

param board(8, 8): boolean

dim row, col: integer

for row := 1 to 8

for col := 1 to 8

if board(row, col) then

print “Q”;

else

print “ ”;

endif

if col < 8 then

print “|”;

endif

next col

print

if row < 8 then

print “-+-+-+-+-+-+-+-”

next row

print

end

Now that we’ve shown the canonical recursive version, let’s eliminate the recursion from queen8, replacing it with a stack. (Happily, we know how big to make the stack; the recursion happens once per column, and there are eight of them on a chess board.) At any stage, there is only one thing to remember, namely the row we’re on. If you think about it, you’ll realize that the stack pointer is always the same as the column we’re on, so there’s no need to save it on the stack as Mr. Banerjee’s code does. (We lucked out on this one; in general, you will have to save the information associated with a pending piece of the problem.) We keep the same interface for now—admittedly from the start we’ve been exposing details we shouldn’t, and we should have put a layer around the board initialization and outer call to queen8. For now, though, we’re concentrating on recursion elimination.

procedure queen8

param col: integer; board(8, 8): boolean; nsols: integer

dim row, rowstack(8): integer; ok: boolean

row := 0

loop

while row < 8 do

row := row + 1

run check(board, row, col, ok)

if ok then

board(row, col) := true

if col = 8 then

nsols := nsols + 1

run show(board)

board(row, col) := false

else

rowstack(col) := row

row := 0

col := col + 1

endif

endif

endwhile

exitif col = 1 then endexit

col := col – 1

row := rowstack(col)

board(row, col) := false

endloop

end

This is less clear than the recursive version, so explanation is in order. The while loop looks for the first row we haven’t tried yet for which we can safely place a queen in that row on the current column. If there is one, we put a queen there, remember the row, and either we’re completely done (on column eight) or we move on to the next column. If there isn’t one, we leave the loop because we’re done with the current column. If that’s the first column, we’re completely done (see the exitif); otherwise, we back up a column, remember the row we were on there, and remove the queen we had on that row and column, so we can try the next possibility for that column.

I’ve yet to run the program on a CoCo. On the MM/1a, the recursive and non-recursive versions both take about two minutes to run. Curiously, over half the time is taken by show! If the body of show is edited out, the result runs in fifty seconds. On the MM/1b (aka AT306), the program runs in 1:15—five eighths of the time—so the screen I/O on the MM/1 and MM/1a has significant overhead.

One can do other things to speed the program up, but the point here is to show recursion and recursion elimination in a language with decent control structures that clarify what’s happening… oh, what the heck. I did it anyway, so why not write it up?

The revised check still takes time proportional to the column number, and the column number ranges over 1 to n, where n = 8, in the fashion of bubble sort, so overall we’re talking O(n²). We haven’t changed its complexity, we just cut it down by a constant factor. To really speed it up we have to make check run in constant time, doing the same amount of stuff no matter what row or column we’re looking at. How much stuff? Well, there are three paths down which an attack can come, so there ought to be a way to just do three tests: one for the row, and one for each diagonal. (We never put more than one queen in a column, so nothing can get us from that direction.) The board is small enough that we could keep a row as an integer with one bit per column, making the board one-dimensional and a check for a row attack is just checking for a non-zero value for that row. OK, what about the diagonals?

They need an array each, one for those going up and one for those going down (from the POV of increasing column number). Each array has fifteen elements, because there are fifteen diagonals of each kind, one per endpoint with the minimum column number (don’t count the middle corner twice, like I almost did). We could keep a count of how many there are… but we don’t have to! This is the eight queens problem. We cut off the search at the first conflict, so the elements can be boolean. For that matter, we needn’t play bit games with the board. There can be at most one piece in each row. We could get away with boolean there, too, if we didn’t want to display the solutions, but we do, so we’ll keep the column number of the queen in that row, or zero if we haven’t put a queen in that row… but that makes “board” a less-than-suggestive name. Let’s call it “column” instead.

With those changes, here are the new main, queen8, and show. We’ll add a little timing info to main. check is simple, and doesn’t need guards—we’ll never fall off the end of an array—so we’ll “inline” it by hand, and not write it separately from queen8. [Note from 2016: the code here isn’t best practice. We’re concentrating on the algorithm and data. Best practice would be to define an abstraction of the chess board that lets you get a new empty board, lets you attempt to place a queen on a square and reports success (if the square isn’t under attack) or failure (if it is), and lets you remove a queen from a square. That would let us make this kind of change without disturbing main or queen8. Sadly, BASIC09’s type statement reveals the innards of the type it defines, making “information hiding” a bit of a sham.]

procedure main

dim diag, row, nsols, column(8): integer

dim udiag(15), ddiag(15): boolean

dim t0, t1: string[32]

for row := 1 to 8

column(row) := 0

next row

for diag := 1 to 15

udiag(diag) := false

ddiag(diag) := false

next diag

t0 := date$

nsols := 0

run queen8(1, column, udiag, ddiag, nsols)

t1 := date$

print nsols; “solutions”

print “start at “; t0; “, end at “; t1

end

procedure queen8

param col, column(8): integer; udiag(15), ddiag(15): boolean; nsols: integer

dim row: integer

for row := 1 to 8

if column(row) = 0 and udiag(row + col – 1) and ddiag(8 + row – col) then

column(row) := col

udiag(row + col – 1) := false

ddiag(8 + row – col) := false

if col = 8 then

nsols := nsols + 1

run show(column)

else

run queen8(col + 1, column, udiag, ddiag, nsols)

endif

column(row) := 0

udiag(row + col – 1) := true

ddiag(8 + row – col) := true

endif

next row

end

procedure show

param column(8): integer

dim row, qpos: integer; rowstring: string[16]

rowstring := “ | | | | | | | ”

for row := 1 to 8

qpos := 2 * column(row) – 1

print left$(rowstring, qpos – 1); “Q”; right$(rowstring, 15 – qpos)

if row < 8 then

print “-+-+-+-+-+-+-+-”

endif

next row

print

end

This version runs on the MM/1b in twenty-four seconds, about three times faster. Allen Huffman kindly ran it under a CoCo 3 emulator (using TuneUp, which would give it an advantage over stock OS-9). With sync lock turned on to make it run at CoCo speed, it ran in about two and a half minutes; without sync lock, it ran in twenty-eight seconds. Eliminating recursion only saved about three seconds on the MM/1b. I instrumented queen8, and it proved to only be called 1,965 times, less than I would’ve thought. Moral of this part of the story: choose your data structures carefully; it can make a big difference. (Note that it lets us easily print each row with a single statement rather than a character at a time. I suspect that makes a big difference in BASIC09.)

Having gone this far, we might as well write it in Color BASIC. This is a recursive version—it has recursive GOSUBs, which is as close as you can get in Color BASIC. It lacks the comments that Mr. Banerjee’s code has, and which production code should have (though they eat valuable memory in Color BASIC, so the temptation to eliminate them there is strong). On the other hand, it follows the BASIC09 version closely, so one could argue that the BASIC09 is documentation for the Color BASIC. To conserve writer and reader sanity,

• this is not crammed together the way Color BASIC code tends to be
• the text is in lower case

The first solution, running on an actual CoCo, takes about thirty-five seconds to appear, and a complete run takes, as nearly as I can tell, ten minutes and forty-five seconds. I would recommend running the progam in WIDTH 80 mode.

100 dim cl(8), rs(8), ud(15), dd(15),

110 r$=” ! ! ! ! ! ! ! “

120 for i=1 to 8:cl(i)=0:next

130 for I=1 to 15:ud(i)=1:dd(i)=1:next

140 ns=0

150 co=1

160 gosub 200

170 sound 50,3

180 print ns;”solutions”

190 end

200 for ro=1 to 8

210 if cl(ro)<>0 or ud(ro+co-1)=0 or dd(8+ro-co)=0 then 250

220 cl(ro)=co:ud(ro+co-1)=0:dd(8+ro-co)=0

230 if co=8 then ns=ns+1:gosub 300:else rs(co)=ro:co=co+1:gosub 200:co=co-1:ro=rs(co)

240 cl(ro)=0:ud(ro+co-1)=1:dd(8+ro-co)=1

250 next

260 return

300 cls

310 for rn=1 to 8

320 qp=2*cl(rn)-1

330 print left$(r$,qp-1);”Q”;right$(r$,15-qp)

340 if rn<8 then print “-+-+-+-+-+-+-+-”

350 next

360 return

Recursion is an important concept with many applications, not all of which have closed-form solutions. For example, consider plotting a function f on an interval [a,b] if all you can do on the display is draw line segments. Pick a point c in (a, b) and check whether (c, f(c)) is “close enough” to being on the line segment joining (a, f(a)) and (b, f(b)). If it is, draw that segment. Otherwise, recur on [a, c] and then on [c, b]. (Numerical methods students will recognize this as “adaptive trapezoidal integration”.) By all means, learn to use recursion, and learn how to avoid it or implement it via an explicit stack as Mr. Banerjee describes. [Note from 2016: It can come in handy for any language—for example, it is very common for embedded systems to flatly forbid recursion, whatever the language, for fear of stack overflow.]

Advent of Code

I seem to always come in late on these things, but I hope this one will stay around for a while so I can get through it all.

The Advent of Code site features one problem a day from December 1 through December 25. (Actually two, but the problems for any given day are related, the second being a variation or extension of the first.) The problems have cute Santa-related back stories. You can use the language of your choice, so I'm using Haskell.

I have to admit I'm wimping out somewhat, in that so far I haven't written code to parse a file of input data. Instead I've fired up vi and edited it into a list that I can copy, fire up ghci, and say

let input = shift-ctrl-v

and just deal with the guts of the problems. I've not gotten all that far into the problems, but so far, a lot of it has been finding the appropriate library package(s). OTOH, getting to know the libraries is useful; why reinvent the wheel?

Advent of Code is a fun exercise. Check it out.

"I want my xfce...."

Sorry, Mr. Knopfler, it doesn't scan--but it is the truth.

I am now the proud owner of two Raspberry Pi 2s, computers we would have killed for back in the 80s. I have "Raspbian" running on them. (It's a version that apparently will run on the 1 (an ARMv6) and on the 2 (a four-core ARMv7); I definitely want to build it targeting the ARMv7.)

Anyway--it comes up with LXDE for a windowing environment if you use X. Very stripped down, and unfortunately with minimal control over font size, which my wife and I really kind of need. So off we go to install it. It's in the repository, so that's no problem. Then you run

sudo update-alternatives --config x-window-manager

and tell it you want xfce4. Then you get out of X if you're already in it, and then get [back] in...

...and you see LXDE again. (Cheesy descending horn sting here.)

At least that's what happens on my wife's computer. I managed to get mine to come up in xfce4, and I am kicking myself for not having written down exactly what I did, because it's well out of short-term memory now. (I can tell you what it's not; I did NOT uninstall all the LXDE packages, as some people will say you have to do.)

Any ideas? I'd love to hear them.

Flashback, Part Two

Last time we found that our program to count ways to make change, while much better than the engineering class's brute force nested DO loops, isn't up to snuff.

There is a better way, it turns out. If you look at the Rosetta Code entry for this problem, which they call "Count the Coins", you'll find a number of approaches. For Haskell, there are two. The first "naive" program is essentially what we wrote (save that there's no explicit case for a one-element list; it's a little less efficient, but the recalculation may well swamp that difference).

The other Haskell program takes a different approach:

count = foldr addCoin (1:repeat 0)
        where addCoin c oldlist = newlist
              where newlist = (take c oldlist) ++ zipWith (+) newlist (drop c oldlist)

and if you look at the main for the program,

main = do
    print (count [25,10,5,1] !! 100)
    print (count [100,50,25,10,5,1] !! 100000)

you see that count returns a list that one indexes by the amount one wants to know how many ways to make change for (remember that the head of a list has index 0), reminiscent of the elegant Haskell Fibonacci sequence definition

fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))

If you try it, you'll find it runs a lot faster than our program.

Consider the base case, no denominations, and then how to add a denomination. With no denominations, the only amount you can make change for is zero, so if count is correct it should hand back an infinite list whose head is 1 and all the other elements zero. That's exactly the

1 : repeat 0

that is the starting value for the fold.

So, suppose we have the list that corresponds to the first n denominations. How do we use that to generate the list for the first n + 1?

Well... if there are w ways to make change for c cents (just to have a name, we'll call the smallest denomination "cents") using the first n denominations, and the (n+1)st denomination is d cents, then there are w more ways to make change for c + i * d cents, for i in [1..] when you add the new denomination. So the new list is the current list plus the current list shifted right d places plus the current list shifted right 2 * d places plus... etc. That does look like what addCoin does. (Apologies for picking names that clash with addCoin; what they call "c", we're using "d" for.) Looking like, though, isn't proof. Back when I have proof.... and why foldr  rather than foldl?

Flashback

Back in the Cretaceous era I worked at the University of Oklahoma as a student assistant at Remote 1. OU was a [shudder] IBM big iron shop at the time, and beginning students typically got a job class that limited CPU time to thirty seconds, lest a beginner submit a program with an endless loop and chew up serious resources. (And when the computer everyone's sharing is a 370 of mid-1970s vintage, it doesn't take much to be considered serious resources. According to the Hercules FAQ, a Celeron 300 can emulate a 370 at speeds greater than a 3033, which was at least twice as fast as what OU had at the time.)

One day one of the instructors assigned his charges the following problem: count the number of ways to make change for a dollar assuming you have a generous supply of half dollars, quarters, dimes, nickels, and pennies. (The language is a bit loose; there wasn't any buying going on, just figuring out how to get coinage adding up to a dollar.) They all headed off to punch their FORTRAN programs to run using WATFIV, successor to WATFOR, the University of Waterloo FORTRAN compiler designed to give good error messages rather than worrying about optimization.

The student assistants were getting swamped with students coming in and wanting to know how to get more computer time; their change-making programs were running thirty seconds and getting killed. Every one of them had written something like this, modulo the length of that logical IF; I'm not going to bother to churn out the appropriate "continuation card"):

       IWAYS = 0
       DO 100 ICENTS = 0,100
         DO 200 INICKELS = 0,20
           DO 300 IDIMES = 0,10
             DO 400 IQUARTERS = 0,4
               DO 500 IHALFS = 0,2
                  IF (ICENTS + 5 * INICKELS + 10 * IDIMES + 25 * IQUARTERS + 50 * IHALFS .EQ. 100) IWAYS = IWAYS + 1
 500           CONTINUE
 400         CONTINUE
 300       CONTINUE
 200     CONTINUE
 100   CONTINUE
       WRITE(6,600) IWAYS
 600   FORMAT(I8,' WAYS')
       STOP
       END
       
so that no attention was paid to how much you'd accumulated in outer loops--no matter whether ICENTS was 0 or 99, it would doggedly try counts of other coins sure to push the total far over a dollar.

I wrote a recursive program in Algol W, my then language of choice, with a function that took an arbitrary array of coin denominations and amount and a main program passing the particular values for the problem the instructor set. It ran in 0.01 seconds. A friend and coworker, Raymond Schlecht (alevasholem), wrote a FORTRAN version that took less than 0.01 seconds, so from the output, which only gave run time to two decimal places, it looked like it took no time at all. We handed the listings and output to our boss, who had a chat with the instructor. I like to think the discussion was educational.

Nowadays, of course, just about everyone has computers so much faster than that 370/158 that the above brute force code would run to completion in no time at all. The old fogey in me hopes that the up and coming programmers serve time with low-end hardware, and indeed systems like Arduino mean that does happen at least some of the time. OTOH, another way to do it is to crank the input size so you still can't get away with an inefficient method, vide the small and large inputs for Code Jam problems... and we'll see that shortly as I get my comeuppance.

So, how to do it in Haskell?

waysToMakeChange :: [Int] -> Int -> Int

Obviously there's exactly one way to make change for 0.

waysToMakeChange _ 0  = 1

For a nonzero amount, you need at least one denomination!

waysToMakeChange [] _ = 0

With just one denomination, either you can do or do not, as Yoda would say.

waysToMakeChange [denom] amount
    | amount `mod` denom == 0 = 1
    | otherwise               = 0

With more than one, consider the first one. The number should be the sum of the ways to make change for the amount minus 0, 1, 2, ... of the coins of that denomination using the remaining denominations as long as the difference is non-negative.

waysToMakeChange (denom:denoms) amount
    = sum $ map (waysToMakeChange denoms) [amount, amount - denom .. 0]

That should do the trick... shouldn't it?

*Main> waysToMakeChange [50, 25, 10, 5, 1] 100
292

Do we believe that? Turns out that Rosetta Code has the same problem, only their example doesn't bother with half-dollars. The result they get for that variation is 242, and sure enough, that's what we get as well.

For completeness's sake, the Rosetta Code page shows an example with considerably larger amounts, for us it would be

waysToMakeChange [100, 50, 25, 10, 5, 1] 100000

Let's try it. (Given the output shown on Rosetta Code, we have to switch over to Integer for the result.) Now we're in the same boat as the engineering students! Even compiled, ten minutes isn't enough given the above implementation.

We need a better method. Why? This version of the code is doing a lot of recalculation. For example, if we have a half-dollar and a quarter, or three quarters, or two quarters, two dimes, and a nickel, or... we will keep evaluating, among other things, the number of ways to make change for 25 cents just using pennies. So while we have a nice recursive function that is pretty clearly correct, it's inefficient. We tried one dollar, ten dollars, and one hundred dollars, running time on the compiled program, and looking at the user line of the time output, we see

one dollar:                 0.002 s
ten dollars:                 0.009 s
one hundred dollars:  6.794 s

Definitely the larger problem isn't practical this way... but this is already long enough and has been sitting for months waiting to be published, so let's make this Part One. Stay tuned.

2010 Code Jam problem: "Store Credit"

A fellow on the haskell-beginners mailing list asked for suggestions on how to improve code he'd written to solve a 2010 Code Jam qualifying problem, "Store Credit". Here's the problem statement:

"You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first)."

Then the format of the input is described, and among the things we learn are:

• The prices are all integers.
• "Each test case will have exactly one solution."

But then one of the examples for which a solution is shown has a credit amount of 8 and this list of prices:

2 1 9 4 4 56 90 3

and the solution "4 5". At first one would--well, I did--think that violates the promise of only one solution, since two of item 4 or two of item 5 would also add up to the credit amount of 8. I would say that the problem statement is at least a little misleading, and should have said "...would like to buy two different items that add up to the entire value of the credit." It's arguably implied by the parenthetical "(smaller number first)", and perhaps the intent is to show the need to read specs carefully.

Clearly you want to keep around two items, or for a functional version, you want to generate two items as you trudge down the list of prices:

• an array or vector of integers with C/2 elements
• a mapping that, given a price, returns the position (or positions, given the one example) of the items with that price

The array/vector starts out as all zeroes, and for each item, you increment the element whose index is the minimum of the price and C - the price. (Ignore anything with price > C.) You've found a solution when the result of the increment is 2.

It's pretty clear how to implement this in an imperative language. We'll see what I come up with for a Haskell version.

Look and say sequence

If I don't already have the Haskell subreddit link over on the right, I'll add it ASAP.

This evening a Haskell beginner posted about some trouble he was having writing code to generate a particular sequence. I didn't catch on to the sequence he was going for, but I should have from a comment in his code:

enunBlock :: [Int] -> [Int] -- [2,2,2] -> [3,2] | [3] -> [1,3]  

Someone did catch on, though, and asked "Are you trying to make a look and say sequence?" The poster said yes... and off to Wikipedia I went.

Said sequence starts 1, 11, 21, 1211, 111221, ... and the way you get the next term is to take the current one and sort of run-length encode it. The first term would be "one one", i.e. a run of ones of length one, so the second term is 11. That in turn would be described as "two ones", hence the third term is 21, or "one two, one one", giving 1211, and so on.

If each digit were on its own line, you could get the next term of the sequence by piping it through uniq -c and playing some sed games to pull out some whitespace. (Hey, wait; will we ever have a run length needing two digits? Actually, you can bound it even more tightly than that, unless you pick a starting value that forces the issue. The result, and a reference, is in the Wikipedia article.)

We'll go along with the poster--as you can see from that declaration, he's using a [Int] for a term of the sequence, saving some hassle. If we can just write a function that takes a term and generates the next, then, if you've read much here or done much Haskell at all, then you know where we're headed for the sequence, namely iterate.

lookAndSay :: [Int] -> [[Int]]
lookAndSay xs = iterate nextTerm xs
     where nextTerm xs = ...

So, how to define nextTerm (that's what we're calling what the original poster called enunBlock)? Clearly our base case is

nextTerm [] = []

the more interesting one is

nextTerm (x:xs) = ....

and for it we're going to take advantage of span from Data.List:

nextTerm (x:xs) = length run  + 1 : x : (nextTerm leftovers)
      where (run, leftovers) = span (== x)  xs

put it all together after a pass through hlint, and you have

import Data.List

lookAndSay :: [Int] -> [[Int]]
lookAndSay = iterate nextTerm
    where nextTerm []     = []
          nextTerm (x:xs) = length run + 1 : x : nextTerm leftovers
                            where (run, leftovers) = span (== x) xs

UPDATE: Aha! Should've looked closer at what the poster was trying to do. He or she was looking to use group which takes a list and chops it up into a list of lists made up of the runs of equal elements; for example, if you hand it "balloon", you get back ["b", "a", "ll", "oo", "n"]. That does come closer to what we want, but we need the counts and to get rid of the duplicates where they exist, something like

nextTerm xs = concat [[length ys, head ys] | ys <- group xs]

or, if you're feeling pointless--er, pointfree,

nextTerm = concat . (map (\xs -> [length xs, head xs]) . group

and sure enough, that does the trick.

UPDATE: Darn it! You'd think that after having found and used sequence, I'd remember it. Make that

nextTerm = concat . map (sequence [length, head]) . group

and we'll be that much more concise. Ah, even better is

nextTerm = concatMap (sequence [length, head]) . group

and once you have it boiled down this far, why bother giving it a name? Once the smoke clears, the whole thing is just

import Data.List

lookAndSay :: [Int] -> [[Int]]
lookAndSay = iterate $ concatMap (sequence [length, head]) . group

Clearly I need to spend some time just rummaging through the available functions... and now I'll have Cream's "I Feel Free" stuck in my head until I take a stab at a filk, working title "I'm Pointfree".

Fun with pattern matching

I just noticed that I did something almost without thinking.

I'm still being lazy about dealing with inputs. I haven't gotten around to using one of the many elegant parser packages that Haskell makes possible, and the Code Jam problems I've tried so far haven't required much more than skipping the leading line--kids, ask your grandparents about the card decks they would feed to their FORTRAN programs that started with a card that said how many sets of input values followed!--and handing back a list of values per line of input afterwards.

A particular Cookie Clicker Alpha input has three values, and so I passed cookieTime a list I knew would always have three elements, so that the pattern

cookieTime [farmCost, farmRate, goal] = ...

matches it and also splits out the elements of the list and binds them to names--just the way that introductory Haskell texts always mention that you could make yourself comfortable if you're used to languages that want parameter lists parenthesized by passing tuples, but you shouldn't. I will try to wean myself away from it.

Well, drat... *spoiler alert*

I didn't do well in the qualifying round of Code Jam this year, alas. Part of it I can thank the IRS for, in a way, because we paid our annual last-minute visit to H&R Block today. But really it's my fault; I didn't arrange to have the interval during which one could enter solutions clear to devote to it.

I didn't get my improved version of Cookie Clicker Alpha done in time to count, but it did check out, so I have a moral victory at least. I probably should have devoted the time needed to do the simplest of the qualifying problems, Magic Trick, rather than just sketching out the solution.

A quick summary of the problem: in the problem's version of the game "Cookie Clicker" (inspired by a real game of that name) is parametrized by three values:

• X, a goal number of cookies to accumulate
• C, the cost in cookies of a "cookie farm"
• F, the rate at which one can "harvest" cookies from a cookie farm once bought

OK, actually, there's a fourth value: if you click on a giant cookie, you can gain two cookies/second. (You have to have a way to get started accumulating cookies, or you couldn't buy a cookie farm.)

One thing to note: in real life, cookies are discrete entities; a whole cookie is either there or not. In this problem, though, you should think of cookies as being produced continuously; for example, with no farms, you can lay claim to two thirds of a cookie in a third of a second.

So, the problem as posed: given X, C, and F, figure out the soonest you can accumulate the goal of X cookies. Of course, cookies you spend on farms don't count towards X, though of course it will usually pay off to buy farms. (Not necessarily, though! If X < C, best to just click away.)

As usual for Code Jam, the input is a line with the number of cases of the problem to solve, followed by lines with the data for the cases. For this one, it's one line per case, with C, F, and X (which are "real" numbers) on the line in that order, separated by spaces. The output format? You should know by now:

Case #<number>: <time>

where <time> is the minimum time to get X cookies with the given cost and rate per cookie farm.

Magic Trick is simple enough that you don't have to worry about optimization the way you do for problems like Fair and Square last year... but Cookie Clicker has two inputs to try, and my initial solution was far too slow to handle the larger input within the time limit.

Spoilers behind the break...

Letting the compiler do it for you

A while back I posted about how looking at the type can give you hints or even tell you what a function has to do, giving the simple example of function composition and pointing at a video by Matthew Brecknell showing how you can enlist ghci to help you in that respect.

Here's another example, provoked by a comment on a reddit question, namely map. If you only knew

map :: (a -> b) -> [a] -> [b]

could you write map? The signature says "give me a function that maps as to bs and a list of as, and I'll give you back a list of bs". Well, you could be a wise guy and write

map _ _ = []

and if anyone complained, say "Hey, the empty list is a list of bs", but in your heart you'd know you were cheating. The only way you're given to get a b given an a is to use the function, so the obvious thing to write is

map f xs = [f x | x <- xs]

(Yes, you could be a wise guy at the next level up and write

map f xs = reverse [f x | x <- xs]

but again, your conscience should bother you.)

Well, it turns out that at least sometimes, a compiler can do some of that kind of reasoning for you. Not in Haskell (though there's been a proposal), but in languages that support what are called "dependent types". Dependent types depend on a value; the canonical example is parametrizing lists by their length. That lets the language's type checker catch more errors.

"Hey, wait!" you say, "Does that mean I can't write my cool

fibs = 1 : 2 : (zipWith (+) fibs (tail fibs))

to neatly specify the Fibonacci sequence?" Alas, I suspect it does--after all, it doesn't have a finite length. There may be a way around that in this case, but the parametrization means you have to do calculations when type checking: "is this list empty?" "is this list at least as long as that list?" and in the general case, it can be undecidable.

All that said, it's still pretty darned impressive what can be done, and there's an excellent video from David Raymond Christiansen that shows it being done in the language Idris (which recently had a new version released). Check it out.