Project Euler 1 to 100

Posted: 24 January 2016

I decided to create this post because I thought it would be extremely inconvenient to create a new post whenever I finish a few problems. I think I will just lump everything into a gigantic post for 1 to 100, since they are relatively trivial problems. The headers are arranged in numerical order.

Problem 12

Solved on 24th January 2016. Nothing too fanciful. 7.3 seconds run time. Extremely sub optimal but I just wanted to get the answer. The trick to this question is basically to not brute force. That would take you more than a minute for sure.

Problem 18

Solved on 24th January 2016. As the question suggests, you can’t brute force it. Or rather, you can, but Problem 67 will not allow you to. An approach to consider would be: How can I reduce the problem? For example, try the case of a triangle with 4 rows. Using the answer from 4 rows, how can I get the answer for 5 rows?

Problem 19

Solved on 25th January 2016. I don’t know if you call this cheating, but I used a Python library. Use Python whenever possible, and C for super speed!

Problem 20

Solved on 24th January 2016. A simple Python script.

Problem 21

Solved on 25th January 2016. Wasn’t that hard. A simple python script. But I tried to write everything in a single line. I could for some parts, but I decided to use a Try Except clause, and that can’t be golfed. Other than that, it would have made a single line.

Problem 22

Solved on 25th January 2016. I thought the part on trying to find a mapping from 1=a, 2=b, etc was interesting. I mean you could write code to generate a dictionary, but I found out from stackoverflow that you can use ord() to do something smart!

Problem 23

Solved on 25th January 2016. I wrote a Python script that ran in 38 seconds. Still under the minute requirement! I think C would be instantaneous though. This problem was quite confusing initially. It took me some time to understand what it was asking.

Problem 24

Solved on 24th January 2016. Pen and paper will do the trick! Counting from 0th number might be a good idea ;)

Problem 25

Solved on 24th January 2016. A simple Python script.

Problem 26

Solved on 25th January 2016. Haha this was funny. I saw something similar before. In fact, it is Problem 358! Took me a few seconds to solve it.

Problem 27

Solved on 21st March 2016. This got me stumped for awhile. Seems complicated at first but brute force does the trick. I think brute force is the only method though.

Problem 28

Solved on 21st March 2016. You can do it by hand with a simple calculator! Well okay it’s tedious with a calculator so just write some simple Python code.

Problem 29

Solved on 10th March 2016. An elegant solution to this is tedious. A simple brute force does it in under 0.5 seconds.

Problem 30

Solved on 22nd March 2016. Find the upper bound of your search and you’re done! After all, there’s a divergence after a certain number.

Problem 31

Solved on 23rd March 2016. Did a depth first search initially, but found out from forums that dynamic programming is a better solution. I ended up implementing a dynamic programming version. I should learn how to decompose problems and identify potential DP problems.

Problem 32

Solved on 24th March 2016. I need to get into the habit of having the entire program in my head before going out to code. I should try and get the answer in 1 attempt. It’s not very good if I hack out something and then submit the answer on Project Euler, only to find out it is wrong. I then have to go back to thinking about what went wrong. For this example, I missed out an additional condition, which caused the answer to be wrong. Such training is extremely applicable for real world situations as more often than not, we don’t have the “answer”. Nonetheless, this is a pretty simple problem!

Problem 33

Solved on 25th March 2016. Nothing too difficult.

Problem 34

Solved on 25th March 2016. I started timing myself. I took 21 minutes 0 seconds to solve this. I really need to work on speed! The critical path was finding the upper bound. I made a mistake in my factorial function too. So that wasted some time as well.

Problem 35

Solved on 25th March 2016. 8 minutes 42 seconds. I wrote some helper functions before, so this was relatively simple. It was just a matter of hacking some logic together. It’s not exactly efficient algorithmically, as I don’t remove primes after finding a set of circular primes. I don’t exactly save a lot if I do this either.

Let’s think about it. If there’s a 100-digit prime that is circular, the worst case is that I check this 99 extra times, and in each check, it’s essentially an O(1) look up done 100 times. For this prime, I will then check 10000 times in my implementation. If I do some optimization, I will only have to check 100 times. It’s not worth the effort as the critical path here is really generating the primes. Look ups are almost free. Therefore, why optimize unnecessarily? Let’s save it for the tougher problems ;)

Problem 36

Solved on 25th March 2016. 3 minutes 51 seconds. A simple check_palindrome function was written. I shall add it to my repository of functions that are useful. I should perhaps write a README for all the functions.

Problem 37

Solved on 25th March 2016. Trivial. I didn’t really time it cause I didn’t think I would take more than 5 minutes. Made some careless mistakes initially, but I spotted them quickly.

Problem 38

Solved on 25th March 2016. Trivial. I didn’t understand the question properly. Ended up submitting the wrong value for this. It should have been the “pandigital number”, rather than the number that results in the pandigital number. I submitted the latter initially.

Problem 39

Solved on 25th March 2016. Ah. Slightly challenging problem. I didn’t time this because I thought it was simple math. Turns out it was indeed simple math with lots of catch cases. I guess I learnt how to properly write a function with lots of IF statements. I thought I would do it under 5 minutes but I think I ended up taking 20 minutes for this.

Problem 40

Solved on 25th March 2016. Trivial. Once again, I read the question wrongly. I ended up adding instead of multiplying. After realising that error, I changed it to *= and it’s done!

Problem 41

Solved on 26th March 2016. I took approximately 10 minutes. Another pandigital problem. It’s simply just coming up with a function to check if a number is pandigital from 1 to n, and then checking if it’s a prime.

Problem 42

Solved on 26th March 2016. I took approximately 10 minutes. It wasn’t that hard.

Problem 43

Solved on 26th March 2016. I took approximately 10 minutes. And this is my 50th question solved! I didn’t know solving 50 questions puts you into top 6.25% of Project Euler members. I think many people are inactive. The function to check divisibility is simple. I initially iterated all pandigital numbers from 1,000,000,000 to 9,999,999,999. I already had a pandigital number check function, so I simply used it again. It was extremely inefficient.

Why check a number when I can just permute from 0123456789? I did that. It solved in 3.3 seconds. Compared to something along the lines of more than a minute.

Problem 44

Solved on 8th April 2016. I forgot to time this one.

Problem 45

Solved on 6th April 2016. I forgot to time this one.

Problem 46

Solved on 6th April 2016. 11 minutes.

Problem 47

Solved on 6th April 2016. 4:30.

Problem 48

Solved on 6th April 2016. 1:35.

Problem 49

Solved on 6th April 2016. 26:54. I took quite awhile for this, so it’s blog-worthy. I got stuck at this initially because of the incrementer. You first have to find all the permutations that are primes, and then find a valid value for incrementer. I thought it was as simple as finding all permutations but I misunderstood.

Problem 50

Solved on 8th April 2016. I forgot to time this one. WOOHOO. 50 questions SOLVED!

Problem 51

Solved on 15th September 2016. Oh my. What a long hiatus. The last one I solved was in April 2016. I took an hour for this one. And it wasn’t entirely right. But then again, this was a 15% problem and not a simple 5% one. Nonetheless, I should have solved it faster though. Time to brush up my skills. An Euler a day keeps the doctor away!

Problem 52

Solved on 19th September 2016. Added a function called count_unique_digits that returns a collections defaultdict. I’m sure this will be helpful in future questions.

Problem 53

Solved on 19th September 2016. Simply iterating over all combinations. I wrote my own combinations function as it wasn’t that hard. Definitely solved it suboptimally since there are some symmetries in combinations.

Problem 54

Solved on 26th March 2017. A ton of hardcoding. There were so many cases to code up. It was a pretty boring problem. The only hard part was to design a representation that expresses the various combinations you can get and to decide a draw. Took about half an hour.

Problem 55

Solved on 31st March 2017. A simple problem. I should work on reading the question more carefully and solving it the first time. I confused the definition of a Lychrel number initially and thus spent 3-4 times submitting my answer before I got it right. Interesting concept I learnt today, never heard of a Lychrel number before.

Problem 56

Solved on 31st March 2017. Overthinked this problem. It was a simple n-squared complexity where n = 100, just that if one codes this in C++, one has to account for big num. I thought the search space was much bigger initially.

Problem 57

Solved on 4th January 2018. Instead of jumping straight into the problem, I decided to force myself to think about it on pen and paper and searching Google for the math behind it. Perhaps there’s a math trick. I found the wiki page and soon realized that because of the PEMDAS rule, it seems like I can’t do it in the form of a DP or some memoization technique. For example, the 1000th expansion is not based on the 999th. Having established that, I concluded that brute force is the way out and proceeded to code it. The first mistake I made was in using recursion. The default recursion depth exceeded. I changed all recursion to for loops. The second mistake I made was to do a gcd at every expansion. This is the classic speed-memory trade off. Since I was using Python and I don’t have to deal with BigNum, there wasn’t a need to do this and I could simply accumulate all the huge numbers and do a GCD at the end. I’m starting to think that I should actually code this in C to tackle this problem head on.

Problem 67

Solved on 24th January 2016. Identical to problem 18. Only difference is that it has a lot more rows. Therefore, you definitely can’t brute force this.

Problem 81

Solved on 26th March 2017. Wanted to solve a dynamic programming problem so I googled for project euler DPs. Came across this and it was pretty easy. Solved it in about 10 minutes. Was stuck on it for awhile because of a careless mistake in the initialization of the memoization table.

Problem 82

Solved on 27th March 2017. An extension of problem 81. I did it using 2 methods. The first one was using an 80x80x80 array to save all distances between columns from various starting locations. The second one was recursion, which somehow using up the entire Python recursion stack. I had to edit the last part to not make it overflow. The second method was more interesting because I learnt about the space saving trick we can use for this, which helps if your arrays are huge.

Problem 83

Solved on 31st March 2017. An extension of problem 81. It was a relatively simple DP. It’s quite similar to 82, in the sense that the frontier of comparison for 82 was 2 columns, but the frontier for comparison for 83 was a mirrored L. This concept can be expanded to N-dimensional DPs but it’s going to be pretty challenging beyond 3 I think. Would be interesting to try such a problem in future.

Problem 98

Solved on 20th February 2016. Seems intimidating at first, since it’s rated 35% difficulty. It wasn’t that bad after all There are very few anagrams in the first place. Once you find the anagrams, it’s a matter of permuting potential substitutions.

Problem 99

Solved on 14th February 2016. Logarithms are the key!