Tag Archives: fizzbuzz

Racket: FizzBuzz, Thunks And Streams

It’s all very well talking about what I’ve learned, but keeping up with it and providing proof is another issue entirely.

So, I’m going to provide variations on what I’ve done with FizzBuzz, a simple programming test to see if you understand the basics of a language – to see if you can be taught the rest from there, really.

The Rules Of FizzBuzz:
1. You start counting.
2. If a number is a multiple of 3, it must be replaced by the word "Fizz".
3. If a number is a multiple of 5, it must be replaced by the word "Buzz".
4. If a number is a multiple of both, it must be replaced by the word "FizzBuzz".

Like I said, simple.

I’m hoping to write up quick but unique implementations in Racket, Ruby, and SML that highlight a little of what I’ve learned from each language.

I’m starting with Racket, a programming language developed from Scheme, which in turn developed from Lisp. All together you’ve got a bit of a mafia movie going.

Racket was by far my favourite language studied on the course, which is probably why I’m starting with it. It’s often seen as a teaching language, but you can definitely do some pretty practical stuff with some easily-available libraries – I’ve been playing around with its JSON abilities during my lunch breaks at work, and it seems very natural (especially as I’ve not done any work with web APIs before).

The basic syntax is:

(define a-symbol a-thing)

This develops pretty quickly and naturally into recursive functions:

(define (multiply-recurse-silly x y)
  (letrec ([f (lambda (y acc)
            (if (<= y 0)
             acc
            (f (- y 1) (+ x acc))))])
    (f y 0)))

This is a silly and impractical use for recursion, using repeated addition to multiply two numbers together. To explain what’s going on here, if you don’t speak Racket:

The main function is defined as “multiply-recurse-silly” and given two arguments “x” and “y”.

We need a recursive function, so we “let” a new symbol, “f” be a new, local function. This function won’t need to change “x”, but it will need to count the number of times it’s added “x” to itself (the multiplication), and we’ll give it an accumulator called “acc” to help it keep track of what “x” is so far.

Once “y” has hit 0 (or below, through some error or inappropriate input), the function returns what the accumulator has saved up.

Otherwise, the function calls itself with the value of “y” – 1 (so “y” is like a countdown timer going towards zero) and “x” added to itself.

Finally, none of this will work unless we call our new “f” function in the first place, so we call it with the last line and then close all the brackets up.

Not too complicated. There’s some things I don’t like about this function looking back on it though:

1.
It’s bad that it isn’t an error for y to be less than 0. This is clearly a function to multiply only positive numbers together, so returning “0” when we try to multiply by a negative number is a big mistake.

What I should have done is either (a) added a new conditional branch so that if y is less than 0 the multiplication works (and works properly) for negative numbers or (b) added a new conditional branch so that if y is less than 0 we raise an error.

2.
For this function we don’t really need a local recursive function. I wanted practice using local functions because I haven’t been using them while designing my game in Java, but this was completely unnecessary. The entire function could have fit on one line, if I’d simply written it to call itself.

Moving quickly on from that:

(define (fizz-buzz start finish)
  (letrec ([f (lambda (strt acc)
                (cond [(> strt finish) (reverse acc)]
                      [(and (= (modulo strt 3) 0) (= (modulo strt 5) 0)
                       (f (+ strt 1) (cons "FizzBuzz" acc)))]
                      [(= (modulo strt 3) 0) (f (+ strt 1) (cons "Fizz" acc))]
                      [(= (modulo strt 5) 0) (f (+ strt 1) (cons "Buzz" acc))]
                      [(integer? strt) (f (+ strt 1) (cons strt acc))]
                      [#t (f 1 acc)]))])
    (f start null)))

My first FizzBuzz function in Racket. It seems to work OK.

Just a simple recursive function, only this time I am using cond, which in practice works like a switch statement, instead of if. “cons”, not to be confused (ha) with “cond”, simply means that we are adding something to a list. At the very end, we see a “#t” condition – this means that for any value other than “#f”, if the conditions before it haven’t executed, the condition at the end will execute. This is because Racket interprets any value other than false (#f) as true (#t).

This means that if an incorrect value is passed by the user as the start value we assume they just meant “start from the bottom!” and go from there.

Again, this is probably not something I would include in a program meant to be used seriously.

Because of the way we are joining the list together, we need to reverse it at the end to make sure it comes out the right way round for human eyes.

This function is able to count from a start number to a finish number, and gives back a Racket list depending on those numbers, in accordance with the FizzBuzz rules.

So:

(fizz-buzz 1 15)

Gives:

'(1 2 "Fizz" 4 "Buzz" "Fizz" 7 8 "Fizz" "Buzz" 11 "Fizz" 13 14 "FizzBuzz")

All working as expected.

Of course, if we put the inputs in the wrong way round, it gives us:

'()

A null or empty list.

Going with the bodge-job aesthetic I’ve employed so far, I decided I wanted it to be able to handle both ways. Simple but unsatisfying to implement:

(define (fizz-buzz-up-or-down x y)
  (letrec ([f (lambda (countdown goal acc)
                (cond [((< countdown goal) acc]
                      [(and (= (modulo countdown 3) 0) (= (modulo countdown 5) 0)
                       (f (- countdown 1) goal (cons "FizzBuzz" acc)))]
                      [(= (modulo countdown 3) 0) (f (- countdown 1) goal (cons "Fizz" acc))]
                      [(= (modulo countdown 5) 0) (f (- countdown 1) goal (cons "Buzz" acc))]
                      [(integer? countdown) (f (- countdown 1) goal (cons countdown acc))]
                      [#t (raise "Inappropriate input!")]))])
    (if (> x y)
        (f x y null)
        (f y x null))))

Giving us:

(fizz-buzz 15 1)
'(1 2 "Fizz" 4 "Buzz" "Fizz" 7 8 "Fizz" "Buzz" 11 "Fizz" 13 14 "FizzBuzz")

Just to confuse everything, this time I’ve changed the function so that the accumulator doesn’t need to be reversed, and the new way of doing things means that I have to raise an error if there’s an inappropriate input – I can’t just guess what the countdown would start at.

On the other hand, with the new up-or-down-ness this function will raise an error for an inappropriate input before I even get to that stage, rendering the error-raising and checking to see if the number’s an integer entirely moot, but it’s nice to be prepared (maybe).

The last thing I did in this file was create the ability to input custom fizzes and buzzes into the function:

(define (fizz-buzz-plus pairs x y)
  (letrec ([f (lambda (xs countdown goal acc)
                (cond [(< countdown goal) acc]
                      [(letrec ([g (lambda (ys ac)
                                     (cond [(null? ys)
                                            (if (null? ac)
                                                (f pairs (- countdown 1) goal (cons countdown acc))
                                                (f pairs (- countdown 1) goal (cons (reverse ac) acc)))]
                                           [(= (modulo countdown (cdar ys)) 0) (g (cdr ys) (cons (caar ys) ac))]
                                           [#t (g (cdr ys) ac)]))])
                         (g xs null))]))])
    (if (> x y)
        (f pairs x y null)
        (f pairs y x null))))

We’ve got an inner loop and an outer loop here.

(fizz-buzz-plus (list (cons "Snark" 7) (cons "Flunge" 4) (cons "Grontch" 9)) 1 25)

This time we pass in a list of pairs and get back:

'(1 2 3 ("Flunge") 5 6 ("Snark") ("Flunge") ("Grontch") 10
11 ("Flunge") 13 ("Snark") 15 ("Flunge") 17 ("Grontch") 19 ("Flunge")
("Snark") 22 23 ("Flunge") 25)

More-or-less what we expected.

(fizz-buzz-plus (list (cons "Snark" 3) (cons "Flunge" 6) (cons "Grontch" 9)) 1 25)
'(1  2  ("Snark")
  4  5  ("Snark" "Flunge")
  7  8  ("Snark" "Grontch")
  10  11  ("Snark" "Flunge")
  13  14  ("Snark")
  16  17  ("Snark" "Flunge" "Grontch")
  19  20  ("Snark")  22  23  ("Snark" "Flunge") 25)

I can’t remember why I chose to cons them together rather than string-append them. That’s this line:

[(= (modulo countdown (cdar ys)) 0) (g (cdr ys) (cons (caar ys) ac))]

It worked for my purposes. I suppose it makes it easier to parse the list as well, when we’re looking back over it.

Yeah, that was probably my reasoning. Let’s go with that.

Now to what I really learned: thunks and streams.

A “Thunk” is a function without arguments which we create only so that we can delay it ever being called, hopefully forever. Thunks are therefore prone to existentialist angst, but they are very useful in many ways.

I remember what they do by thinking of them as an onomatopoeia for a program slamming up against one (THUNK) or alternatively as a “then-function” – a function to do later. Then-func – Th-unc – Thunk. It’s a stretch but it helped me remember it.

Probably the most useful place for a Thunk (at least, at my current level of programming knowledge) is a Stream. A Stream is a Thunked pair, of which pair the latter part is a call to the Stream usually but not always with a different argument. This enables us to create infinite patterns, which we can read at a later date. Naturally this is very useful, and naturally I will only use it to mess around (for now at least).

Here is a simple stream I wrote while on the course. It shows alternately dan.jpg then dog.jpg, but only when called:

(define dan-then-dog (lambda () (cons "dan.jpg" (lambda () (cons "dog.jpg" dan-then-dog)))))

And here is how we read any given stream for a certain number of steps (starting from step 1):

(define (stream-for-n-steps s n)
   (if (<= n 0)
       null
       (cons (car (s)) (stream-for-n-steps (cdr (s)) (- n 1)))))

So, this is how we adapt our simple FizzBuzz function from earlier (I changed modulo to remainder, but it’s otherwise a very similar idea):

(define fizz-buzz-stream
  (letrec ([f (lambda(x)
                (cons
                 (if (and (= (remainder x 3) 0) (= (remainder x 5) 0))
                     "FizzBuzz"
                     (if (= (remainder x 3) 0)
                         "Fizz"
                         (if (= (remainder x 5) 0)
                             "Buzz"
                             x)))
                 (lambda () (f (+ x 1)))))])
                (lambda () (f 1))))

Finally, as an extension of the fizz-buzz-plus function defined earlier, here is a stream for prime numbers.

(define prime-numbers-stream
  (letrec ([f (lambda(x xs ys)
                (if (< x 3)
                    (cons x
                          (lambda () (f (+ x 1) ys ys)))
                    (if (null? xs)
                        (cons x
                              (lambda () (f (+ x 1) (cons x ys) (cons x ys))))
                        (if (= (remainder x (car xs)) 0)
                            (f (+ x 1) ys ys)
                            (f x (cdr xs) ys)))))])
    (lambda () (f 1 (list 2) (list 2)))))

This is really what FizzBuzz is all about. Once you’ve assigned enough multipliers to miscellaneous noises, you end up with only the prime numbers left. If you played FizzBuzz in Primary school, like me, you might have just realised it was a sneaky way of teaching you to think about the patterns involved in multiplication.

Someone once said that prime numbers are what’s left when all the patterns are taken away. I prefer to think of them as the seeds of their own patterns. Each prime fulfils its own unique function, creating a pattern that tessellates perfectly with every other prime, stretching out into infinity.

My method of reading this infinite stream is a lot less elegant and looks like this:

(define (read-prime-stream x)
  (begin (if (equal? x "quit")
             (display "Prime Number Generator Exited.")
             (display (stream-for-n-steps prime-numbers-stream x)))
         (display "\r")
         (if (equal? x "quit")
             (display "\r")
             (read-prime-stream (read)))))

(display "Type \"quit\" (including quotes) to exit. \r")
(read-prime-stream (read))

I learned a lot by writing all of this, though, and it’s really helped solidify some of the concepts of the course in my mind.

Did I get anything wrong? Was I inaccurate somewhere? Should I have expanded on something? Let me know in the comments.

Advertisements
Tagged , , ,
%d bloggers like this: