So for the something of it I am going to see how far I can get in the Euler Project Problems (Not sure if I should have capitalized “problems”). Basically finding solutions to questions no one has ever asked. If nothing else, this is a way to further my Lisp knowledge… so yes, this is in Lisp. Hide the children.
First problem is simply to add up all the numbers that are multiples of 3 and 5. It’s like a more boring version of FizzBuzz. Apparently that is possible.
So it’s not exactly a difficult problem. Essentially I just went with tail recursion. Don’t know what that is? Well it’s magic. This is typical recursion:
def someMethod(current, end)
if current == end
return end
else
return current + someMethod(current+1, end)
Basically the method calls will look like this:
(0 + (1 + (2 + (3 + (4..... end)...)
Because the preceding method depends on the current’s answer, that method call has to sit in memory. If end = 10000000… Stack overflow. Oh yeah.
Now some languages have something called “tail call optimization” which basically means all useful information is passed into the next method. IE the preceding method isn’t waiting for a return, because it supplied the next method with everything.
def someMethod(current, end, final)
if current == end
return final
else
return someMethod(current+1, end, final + current)
The big difference here is that every iteration sends all information forward… as in there is no return “x + someMethod(…)” call that leaves the previous iteration on the hook for the current function’s return. Yay. Why does that matter? ‘cuz. Fine. Some languages are smart enough to forget about the previous call, because it no longer has a use. Kind of like garbage collection.
So to attack the original problem at hand, I used a simple tail recursion strategy. Every iteration with push the next number to check, and the updated total to the next.
def euler-one(currentNumber, total)
if currentNumber == 1000
//At the end, so just return the final tally
return total
else
if(currentNumber % 3 == 0 || currentNumber % 5 == 0)
//The currentNumber is divisible by 3 or 5 // so add it to the total, and increase the currentNumber
return euler-one(currentNumber + 1, total + currentNumber)
else
//The currentNumber is not divisible by 3 or 5 // so just increase the currentNumber, and leave the total alone
return euler-one(currentNumber + 1, total)
Or in a real language:
(defun euler-one (currentNumber total)
(if (= currentNumber 1000)
total
(euler-one (+ currentNumber 1)
(if (or (= 0 (mod currentNumber 3)) (= 0 (mod currentNumber 5)))
(+ total currentNumber)
total))))
Of course this wouldn’t be a post by me if I didn’t over complicate it… MACRO TIME!
You might have read my macros primer thing (Most likely not), so this shouldn’t be to hard to understand… right??
What I was shooting for is a macro that would not only do the above, but would allow for as many numbers to check as the divisorable thing… So instead of:
(euler-one 1 0)
Where “1” is the starting number, and “0” is the starting amount. Instead I want to do this:
(euler-go 3 5 7)
Where “3”, “5”, and “7” are the numbers to check if the current number is divisible by. Pretty sure that made sense… Ok, so!
(defmacro euler-go (&rest args)
`(progn
(defun euler-one-a (currentNumber total)
(if (= currentNumber 1000)
total
(euler-one-a (+ currentNumber 1)
(if (or ,@(mapcar (lambda (x) `(= 0 (mod currentNumber ,x))) args))
(+ total currentNumber)
total))))
(eval (euler-one-a 1 0))))
And here’s what it looks like expanded.
(PROGN
(DEFUN EULER-ONE-A (CURRENTNUMBER TOTAL)
(IF (= CURRENTNUMBER 1000)
TOTAL
(EULER-ONE-A (+ CURRENTNUMBER 1)
(IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5)))
(+ TOTAL CURRENTNUMBER)
TOTAL))))
(EVAL (EULER-ONE-A 1 0)))
Looks pretty much the same right? ‘Cept for the PROGN thing. PROGN basically just runs everything in order, and returns the result of the last section. So this macro actually creates the euler-one-a method, and then calls it with the “(EVAL (EULER-ONE-A 1 0))”. The important part is the section that creates the divisor check:
(IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5)))
Which looks an awful lot like:
(if (or (= 0 (mod currentNumber 3)) (= 0 (mod currentNumber 5)))
From the original method. HOWEVER, the one thing the macro can do is make as many or checks as I want. Say I want to use 3,5,7,9:
(euler-go 3 5 7 9)
The expansion is:
(PROGN
(DEFUN EULER-ONE-A (CURRENTNUMBER TOTAL)
(IF (= CURRENTNUMBER 1000)
TOTAL
(EULER-ONE-A (+ CURRENTNUMBER 1)
(IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5))
(= 0 (MOD CURRENTNUMBER 7)) (= 0 (MOD CURRENTNUMBER 9)))
(+ TOTAL CURRENTNUMBER)
TOTAL))))
(EVAL (EULER-ONE-A 1 0)))
And the macro creates all four. How is that possible? One line in the macro:
(if (or ,@(mapcar (lambda (x) `(= 0 (mod currentNumber ,x))) args))
Remember, with macros there’s a step where you can create more code BEFORE the final expansion. What that line says is to take all the values in args (3,5,7,9), and create a “(= 0 (MOD CURRENTNUMBER X)” where X is 3,5,7,9. For people more familiar with c#, pretend you are creating a string.
"(if (or (" + args.Select(x => "(= 0 (mod currentNumber " + x + ")) ".Aggregate(new StringBuilder(), (builder, current) => builder.append(current)).ToString() + ")";
Or something like that. The difference is lisp is creating actual code, not strings. Anyways, that’s it. Yeah. This is awkward.