Wednesday, February 27, 2013

project euler problem 064

Odd period square roots

This problem is interesting in the early problems. My method is not elegant and I learned a little bit math in the discussion thread which I have no idea how to prove it. My method ran in 0.1 second and my new version only take 0.02 second.

The old day's project Euler problem are quite friendly. For example, This
problem only asks find the numbers less than 10,000. If this problem is posted in 2013, I guess it might be 1,000,000 or even larger.

I tested my code, if the number changed to 1,000,000. My old version takes 29.6s while new version takes 7s. Not too bad.

Monday, February 25, 2013

project euler problem 223 and 224

Almost right-angled triangles

Let us first take a look how many people solved these two problems.

Problem 223: 732
Problem 224: 626

No doubt, problem 224 are much more difficult than problem 223. But here 
is a pitfall that almost all new project euler users (including me) are get trapped. We cared about how many problems we solved much more
than how these problems are solved. We seldom take part in the brainstorm in
the discussion thread for each problem. There is some very sad truth. We can do much better and learn much more and save a lot of time in the future if we read the post carefully and give these problems a second shot. 

These two problems are very good examples. 

Problem 223 can be solved in some kind of brute force way but 224 cannot.
If one solved problem 223 and read the discussion, one may find that there 
is a very clever way to solve problem 224 just in the first page. But why there is still more than 100 people did not solve problem 224?


project euler problem 316

Numbers in decimal expansions

This is another probability problem. I knew how to solve it from the very beginning, but my code is not very efficient. I also got accuracy issues in this problem. But I was too lazy to rewrite the code and somehow managed to solve it.

If you do not know how to solve such kind of problem, try to read some probability book. You will find how to solve such kind of problems. For example,
Introduction to probability models by Ross Sheldon

project euler problem 280

ants and seeds

I have studied probability theory for some time, and I thought that I should not have too much difficulty to solve probability problems, but actually I still have quite a few probability problems unsolved. 

This is a probability and combinatoric problem. It looks quite difficult at first thought but after I tried, it is actually not difficult at all. I recently began to use Lapack and I tried Lapack in this problem. The code runs quite fast, only 1.4 second, with some potential for further optimization.

After I solved this problem,  I read some posts in discussion thread and luckytoilet's blog since I knew that he has two post about this problem (I resist the temptation to read it before I solved the problem). I am surprised to find that  there is quite a few different approaches to solve it. I believe my method is quite straight forward and efficient. Maybe the combinatoric part scared the people.

Manually solve a 2x2 problem is helpful to solve the 5x5 problem.

Excellent problem! I like it.

Saturday, February 23, 2013

project euler problem 368

A Kempner-like series

This problem does not look like a puzzle but a research project. After some reading from Internet, the problem is solved. The idea behind the problem is very interesting.

If the key word Kempner is not provided in the problem, it may take me a lot more time.

Thursday, February 21, 2013

project euler problem 395

Pythagorean tree

The graph looks nice, but the problem is not so interesting. If you have some 
graph tools, it helps a lot. Otherwise accuracy is always a headache.....

Wednesday, February 20, 2013

project euler problem 269

Polynomials with at least one integer root

This problem is only solved by 400 people. But actually it is not a so difficult problem. I just felt that it was too complicated to consider all situations and never gave it a try. 

Finally I decided to solve it. I am surprised to find that it was not difficult to implement. The algorithm was used again and again in PE problems.  The code ran very fast,  less than 0.1 second.  

The math involved is not that much(All the ideas involved has been used many times).  If you go this far, you definitely can solve it.

Monday, February 18, 2013

project euler problem 255

Rounded Square Roots

The first time I saw this problem, I feels that this is a Monte Carlo problem. But I did not try MC, since that is a no-brainer. No way! There are so many 
14 digits number and the problem asked for 10 decimal places. 

I thought about this problem for months, I always got bored by it in a few minutes.

Then finally one day I see something in 5 digits case.  The problem is solved. I love it so much now!  Evil!

I feel problems between 250 and 260 are very difficult to solve.  

252 convex hole
253 caterpillar
254 sum of digit factorial
255 rounded square root
256 tatami
257 angular bisetctor
258 lagged fibonacci sequence
261 pivotal square sum

Some of the problems are still unsolved, some of them took me very long time to figure
out how to solve. 

I am addicted to PE.....


project euler problem 177

Integer angled Quadrilaterals

I solved this problem after I solved more than 300 problems. I was worried about accuracy too much. But actually it is not an issue. Two key words need one's attention, convexity and distinct (non-similar) solutions. I strongly recommend one to solve it independently. After I solved it, I was so happy!  However it is not an easy problem. More than five years passed, only 600+ people solved this problem.  So this is definitely the most difficult problem in the first 200 PE problem.

I am curious how this problem is created. Genius!

project euler problem 237

Tours on a 4 x n playing board

A very interesting problem. There are two ways to solve it , a mathematical way and a CS way, both are very interesting. The method I learned in the discussion thread was used again and again in other problems.

I feel this problem is a difficult one. But more than 800 peoples solved this problem. It is amazing!

project euler problem 253

tidying up

A very difficult probability problem. It takes me quite some time to write the code for a brute force method(well, it is not Monte Carlo). I found it was too slow, and also took too much memory. Then based on this brute force version, I did some optimization to reduce the memory cost since something are actually equivalent. However, after the optimization, It still took 16 seconds.

Please read the discussion thread, there is a very smart way to solve this problem.

project euler problem 356

largest roots of cubic polynomials

Interesting problem! Evil problem! 'Simple' problem!

After I solved it, it looks so simple. Why I can not solve it for months? Well, I did get a somewhat not so useful hint from the PE forum a long time ago. One guy suggested to solve problem 318 first. (It is actually very helpful!)


Finally, something came to my mind and I found how these two problems are related to each other.  There is a little bit math involved in it, but this is very popular, everyone knows about it. I learned the knowledge in high school. Well, in this problem, it is a little bit more complicated than high school math.

There is still another programming component in this problem for you to identify, this part is not difficult since some earlier problems has used it a couple of times.

If you still cannot solve this problem, please stare at the title of this problem for 1 minute. 

Sunday, February 17, 2013

project euler problem 025

1000 digits fibonacci number

a pure mathematical flavor problem. No coding needed if you read fibonacci number on wikipedia. 

project euler problem 024

Lexicographic permutations

Permutation is a routine task for programming. STL is ideal for this problem since it has next_permutation in "algorithm".

Problem 336: Maximix Arrangements is a little bit  more difficult problem. But the idea is similar.

There is a trick to speed up these two problems. Using the same idea, the problem may be solved by hand.  

My code runs for 8ms.

project euler problem 023

non abundant sums

check my comments on  problem 021, same method. Once the algorithm is understood, this problem is simple. 

Probably the most difficult one so far.

project euler problem 021

amicable numbers

There is a neat solution in the discussion thread.  It got 5 kudos, which worth a careful read(in page 1)! This problem is very similar to problem 12.

project euler problem 020

factorial digit sum

simple and fast. 


bigInteger is not necessary.

project euler problem 019

counting sundays

another boring problem. But just a few such kind of problem.

project euler problem 018, 067

maximum path sum

If you can solve problem 15, this one is similar. 

If you say you can brute force it,   can you brute force problem 67?

Project euler become more interesting when one solved more than 150 problems simply because the answer to the problems are huge and cannot be solved by brute force and solving a PE problem is such a fantastic pleasure.

project euler problem 017

number letter count

I do not like this problem. Very boring.

project euler problem 016

power digit sum

problem is simple. but a neat solution is not that easy.

There are many ways to solve this problem. mathematica, python, gmp, etc.

My first version also used my bigInteger class. But actually this is overkill. 

One may use two bitset as carry and one vector to solve this problem. I learnt
this in the discussion thread.

project euler problem 015

lattice paths

In math, it is a combination problem. Very simple and straight forward. 
But I would like to treat it as a dynamic programming problem. There are so many dynamic programming problems in PE.

Actually, just set some points to be inadmissible, the problem is much harder, see problem 408. Dynamic programming still helps in solving the problem. Well not very efficient though. There is a brilliant approach to solve 408!

project euler problem 014

It looks like this problem is relatively easy since brute force is not that slow.
My code takes 0.4s.

project euler problem 013

large sum

I do not have my original code for this problem, but probably I used my bigInteger class. After reviewing this problem, I realized that it is not necessary to use such kind of tools, long long is sufficient. 
 "
Well, unless the test case is a corner case with flood of "9s.  This is something that projectEuler did poorly in early problems. Later on, the problem is always a sum of different cases which is harder to pass for buggy code.

project euler problem 012

This is not a difficult problem. You may try a much more difficult one, problem 378.  After I solved 378, I feel my divisor function is too complicated. 

I rewrote the code, now it  has only 30 lines. It took 0.004 second (my debug version).

Saturday, February 16, 2013

project euler problem 011

largest product in a grid

I do not like such kind of problem, Basically, we need to brute force it. However, your code should not exceed 0.5 second. Otherwise, you need to check your code.  

Update:

I read my code a few days ago, I failed to understand what was going on in my code. It was really messy! I found that I used meaningless variable names like i, j, k and use some magic numbers like 17 and 37, etc.  The logic under the code is not lucid at all. 

I started trying to modify the old code, and begin to use meaningful names like row and col.  After a few minutes, I found that some of my code can be reorganized in a simpler way. I did it and then found a better way to handle the main diagonal and off-diagonal.  The code is cleaner now and very easy to understand. 

I should be more serious on all coding problems even if I got the correct answer and the problem is believed to be really simple!

project euler problem 010, very interesting problem

If you can solve problem 7, there is no difficulty to solve this one.  This can be a very simple problem using the sieve method.

But if you are really interested to count the primes or count the sum of primes under N, the sieve method is not efficient at all when N is large. In the discussion of this problem, a dynamic programming approach is suggested and it is a fast method to count prime numbers. Please do not miss the opportunity to learn if you do not know this method! The code is written in python,  and lucy did an excellent job in his post!

project euler problem 009

Special Pythagorean triplet

This problem is easy. There are many different approaches.  If you use brute force on this problem(sqrt, check whether a number is an integer, etc), please learn from the discussion thread. The best approach is used again and again in many project Euler problems.


project euler problem 008

largest product in series

Very basic problem.

project euler problem 007

This is a warm-up problem.  Very basic.  Read the discussion thread if your code took more than 0.2 second.

project euler problem 006

sum square difference

please do it in O(1) time;

project euler problem 005

smallest multiple

calculator problem, every one can solve it.

project euler problem 004

largest palindrome product

This problem is simple. We will see other palindromic numbers related problems later.

project euler problem 003

largest prime factor

I use C or C++ to solve project euler problems. But I rarely use long long in coding. After I solved 
50 to 100 problems, I found long long is necessity. The problem is easy, even one use some kind of  brute force method. One may read the book from CLRS and try some fancy method. 

It is interesting to notice that for most of the project euler problems that require an integer as an answer, number is usually less than 2^64.  

project euler problem 002

even Fibonacci numbers

around problem 400, there are a lot of problems about Fibonacci numbers. Some on quite difficult to solve. This one is the easiest one that is somewhat related to Fibonacci number.

project euler problem 001

Multiples of 3 and 5

I first started working on project euler in Aug 2011, I really enjoyed solving most of the problems. 

 This is an extremely easy problem, everyone can solve it. No comments needed.