# Raindrops puzzle on Exercism

Tue 15 August 2017

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