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