[Blog] Raindrops puzzle on Exercism
One of the puzzles on Exercism is the Raindrops Puzzle. In this puzzle you find the numbers that divide into the original number (aka: factors). An example of this is the number 28 where 28 can be divided by the following numbers: 1, 2, 4, 7, 14, 28. (Remember that 1 divides into all numbers, and all numbers are divisible by themselves).
The challenge is to output one of the following:
- If 3 is one of the numbers that are divisible by the original number then display "Pling"
- If 5 is one of the numbers that are divisible by the original number then display "Plang"
- If 7 is one of the numbers that are divisible by the original number then display "Plong"
- If the number is not divisible by any of the above display the original number.
So in the case of 4 we factor that (1, 2, 4) and see that 3, 5, or 7 are not in those factors and display 4. For a number like 5 we note that (1, 5) are its factors and since 5 is in that set of factors we display "Plang". In the 28 example above we note that 7 is one of the numbers, and display "Plong".
Where it gets interesting is a number like 15. 15's factors are (1, 3, 5, 15). In this case we first check if the number 3 is one of the factors. 3 is present in the factors so we display "Pling". But note too that 5 is also one of the factors, so we also need to display "Plang". The correct output is "PlingPlang", and we display "PlingPlang" instead of the number 15.
With that in mind I started to attack the problem. This problem was part of the Scheme track so I started thinking how I'd approach this.
The first part was getting the factors out. That suggested "recursion" but my recursion is rusty. I knew that I could easily blow the stack with larger numbers so it would need to be tail-recursive. And that's about where my brain said "do you know how to write a tail-recursive routine because I sure don't?". So I checked Google and found a few examples (one of which lead me down figuring out how to use
let to create a loop, so that was interesting).
Just for grins I wrote an iterative version in Python:
def factor(n): factors =  for i in range(1, n+1): if (n % i == 0): factors.append(i) return factors def main(): print(factor(28)) print(factor(34)) if __name__ == "__main__": main()
Hmm, maybe I don't need recursion after all. This seems to be quick and does the trick. But is that Scheme? Scheme tends to favor recursion over looping (in my experience) so I needed a different approach, and with code that I could ultimately understand.
I found a Prime Decomposition in Scheme on Rosetta Code:
(define (factor number) (define (*factor divisor number) (if (> divisor number) (list number) (if (= (modulo number divisor) 0) (cons divisor (*factor divisor (/ number divisor))) (*factor (+ divisor 1) number)))) (*factor 2 number)) (display (factor 28)) (newline)
Ah, that sort of does what I want. I played with it a bit and came up with my own factorization algorithm / program:
(define (factor number) (define (*factor divisor number) (if (>= divisor number) (list number) (if (= (remainder number divisor) 0) (cons divisor (*factor (+ 1 divisor) number )) (*factor (+ divisor 1) number)))) (*factor 1 number)) (display (factor 28)) (newline)
They may look similar but the key difference is in the
(cons divisor (*factor (+ 1 divisor) number )) line (and the
(*factor 1 number) instead of 2 line). The original algorithm cut the space for searching in half (which is great if you're looking for primes). But in the case of 28 I wanted 2 * 14 = 28. I wanted 4 * 7 = 28 (7 being one of the factors that causes "Plong" to occur). Instead I got
'(2 2 7 1) which sort-of-works, but isn't what I wanted. With the re-worked algorithm I got what I wanted:
'(1 2 4 7 14 28).
Next came learning how to append strings in Scheme. That wasn't nearly as difficult as I thought it would be (
(set! outstring (string-append outstring "Foo")), but what was slightly non-obvious to me was determining if an element is in the list.
Scheme has a function called
memq which will find an element and return the rest of the list. So if I have a list
'(1 2 3 4 5) and I want to see if 4 is in that list I can use
(memq 4 '(1 2 3 4 5)) and get
'(4 5) as the result. If I do the same for 6 (
(memq 6 '(1 2 3 4 5))) I get back
#f. In Scheme the presence of a list can be tested using
if, so checking if we have a list or don't becomes
(if (memq 3 factors) ...).
Appending a string in
Here's the completed code (and a link to comment on Exercism):
(define-module (raindrops) #:export (convert)) (define (factor number) (define (*factor divisor number) (if (>= divisor number) (list number) (if (= (remainder number divisor) 0) (cons divisor (*factor (+ 1 divisor) number )) (*factor (+ divisor 1) number)))) (*factor 1 number)) (define (convert number) (let ((outstring "") (factors (factor number))) (if (memq 3 factors) (set! outstring (string-append outstring "Pling"))) (if (memq 5 factors) (set! outstring (string-append outstring "Plang"))) (if (memq 7 factors) (set! outstring (string-append outstring "Plong"))) (if (string=? outstring "") (number->string number) outstring ) ) )