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
)
)
)

comments