If you’re not familiar with project euler yet, I recommend that you have a look: projecteuler.net. As they state on their website:
“Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.”
This makes it a wonderful site to get challenges that can be solved in code, and also a great way of teaching yourself a new language! My plan is to try and solve some of the problems from project euler using Common Lisp, as actually writing code is a great way to learn the language once the bare minimum of basics is learned. If you want to follow along, the easiest way to start writing and interpreting Common LISP is to use Portacle on a computer, or CL REPL on Android. I don’t have much spare time to spend in front of the computer, so I’ll try to use the android app quite a lot.
My idea for this post is for it to become a list of solutions for the problems on project euler implemented in Common LISP. It will be a great tool for myself to see how I implemented things the first time and perhaps how I would refactor it at a later time when I’m starting to grok LISP
P1: Multiples of 3 or 5
Link: https://projecteuler.net/problem=1
(defun foo (x)
(if (or (eq (mod x 3) 0)
(eq (mod x 5) 0)) x 0))
(defun euler1 (n)
(cond ((zerop n) 0)
(t (+ (foo n) (euler1 (- n 1))))))
I first created a function called foo (for no particular reason). I strongly believe in giving better names to functions for readability, but it’ll have to do for now. The function accepts an argument X. Then I check whether a division by 3 or 5 returns 0 using the modulus operation. The modulus operation returns the remainder of a division, so by checking if the result of the mod-operation is 0 we know if the argument is divisible by 3 or 5. If the argument of foo is divisible by 3 or 5 I return the argument, else I return 0.
Next I created the function euler1. It too takes a number n as an argument. It then checks if n is zero using the zerop predicate, and if it is 0 it returns 0. If zerop of n is not 0 then it goes on to the next statement t which is LISP for true. Note that anything other than nil is true, but t is the norm for boolean true. It then adds the result of foo of n to the result of euler1 of n-1. So as you’ve might already understand, euler1 calls itself recursively until it reaches 0 while counting down from whatever argument n was when it was first called. Thus it creates a stack of numbers to be added until it has reached 0, then unwinds the stack and adds all the numbers until we get the solution.
I cleaned up the code a little bit by getting rid of the first function and doing the modulus in the main function.
This seems to be a little bit faster than the previous version.
P20: Sum of digits of factorial of 100
Yes, a bit of a mouthful! The task is to calculate the factorial of 100 (written mathematically as 100!), and then summing up the digits of the answer. So for 5! we get 5x4x3x2x1=120, then we sum the digits of the answer: 1+2+0=3. Easy enough for a small number like 5, but for a 100 it’s nice to use programming to solve the problem.
My plan is to do like I did for 5! but to generalize it so that it does the same steps for any argument n.
The first calculation we need is to get the factorial of n. To do that, we make a function that first checks if n is zero and returns 1. If n is not zero, then multiplies n to the factorial of n – 1. Do you smell recursion? I do!
(defun fact (n)
(cond ((zerop n) 1)
(t (* n (fact (- n 1))))))Let’s give it a test run
Neat! The function does as I described above, and uses the inbuilt zerop predicate to check if n is zero. A predicate is a function that returns t or nil (LISP for true or false). As long as it returns nil, the cond operator goes to the next case, which is always t, and recurses. By applying the inbuilt function trace to our function fact, we can see the recursion tree.
The next part is to get each digit of the result and adding them together. Numbers is a single symbol that evaluates to itself, but if we can convert it to a string we should be able to get each character of the string (that is really a digit) and start summing them up.
The first thing we need is a way to convert a number to a string, and Lisp provides write-to-string which does exactly that. Next, I would like it to be a list of characters, so we need to coerce the string to become a list. I love that it is actually named coerce in Lisp. I wrote the following function:
(defun make-list-of-digits (n)
(coerce (write-to-string n) 'list))And then we need a function that goes through the list and adds all the digits together. It also has to convert the characters to numbers since characters cannot be added together (concatenation would just give us the initial result of the factorial function again). Lisp also presents characters a bit weird; #\o (where python would just use ‘o’), and there is no parse function from character to int, so we need to convert from char to string to int. Here’s what I came up with:
(defun sum-list-of-digits (list-of-digits)
(cond ((null list-of-digits) 0)
(t (+ (parse-integer (string (first list-of-digits)))
(sum-list-of-digits (rest list-of-digits))))))Again I’m using recursion to add the first of the list to the result of the sum-function of the rest of the list. Basically the same idea as with the factorial-function, so I won’t explain it to much in depth here as it would be mostly redundant. The most interesting method here is the parse-integer that gets called with the result of string of the first item in list of digits.
Now all we need to do is put it all together. I opted for a base-function that I could call with the number stated in the assignment and then let it do the rest of the function calls. You can see the functions and the result in the screenshot from my phone below:
P36: Double-base palindromes
This problem states that the number 585 is a palindrome in both base 10 and base 2 as its base 2 representation is 1001001001. It then wants us to find the sum of all the double-base palindromes under one million. My first attempt was to try and solve it recursively (LISP has made me think recursively about everything!). Here is my proposed solution:
(defun db-palins (n)
(cond ((zerop n) 0)
((equal (write-to-string n)(reverse (write-to-string n)))
(if (equal (write-to-string n :base 2)(reverse (write-to-string n :base 2)))
(+ n (db-palins (- n 1)))
(+ 0 (db-palins (- n 1)))))
(t (+ 0 (db-palins (- n 1))))))The code seems to give the right answer, but when attempting to call the function with an argument of 100 000, it throws an unexpected error. My guess is that it reaches its recursion limit. So I had to try another solution using a loop:
(defun db-palins2 (limit)
(reduce '+ (loop for n from 1 to limit when
(and (equal (write-to-string n)(reverse (write-to-string n)))
(equal (write-to-string n :base 2)(reverse (write-to-string n :base 2))))
collect n)))This worked wonderfully! I tried doing a simple performance comparison of the two, but the recursion limit only lets me pass an argument of about 3000 (on my phone at least) so I’m not sure how good of a comparison this really is.
