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