Top Dice
The problem is not a difficult one. My old code runs for near 1 second. I checked it and did some small modification, the the run time is reduced to 0.2 second(debug version) with some room for further optimization. The combination property is essential for this problem.
Wednesday, July 3, 2013
project euler problem 239
Twenty-two Foolish Primes
This problem is really simple. The code is less than 15 lines. The key principle is well-known. I used this principle to solve quite a few PE problems.
This problem is really simple. The code is less than 15 lines. The key principle is well-known. I used this principle to solve quite a few PE problems.
Tuesday, July 2, 2013
project euler problem 236
Luxury Hampers
This problem is quite difficult. My first code runs for a couple of minutes to get the answer. After I read the discussion, I found I missed an important fact from those five integer pairs given in the problem.
I optimized my code using this important and obvious fact, my code's run time is reduced to 16 seconds. Still too slow! Finally, I realized that it really matters how you search the space. By changing the search order, the search space can be greatly reduced. After this important optimization, it only take 0.6 second to get the answer!
This problem is quite difficult. My first code runs for a couple of minutes to get the answer. After I read the discussion, I found I missed an important fact from those five integer pairs given in the problem.
I optimized my code using this important and obvious fact, my code's run time is reduced to 16 seconds. Still too slow! Finally, I realized that it really matters how you search the space. By changing the search order, the search space can be greatly reduced. After this important optimization, it only take 0.6 second to get the answer!
Monday, July 1, 2013
project euler problem 235
An Arithmetic Geometric sequence
This problem needs some numerical analysis work. I checked the discussion. Some of the people used bisection method. But I would recommend Newton-Raphson method. It is way faster.
This problem needs some numerical analysis work. I checked the discussion. Some of the people used bisection method. But I would recommend Newton-Raphson method. It is way faster.
project euler problem 234
Semidivisible numbers
This is a very simple problem. It seems quite difficult since the upper bound is very large. But after you did a little bit math, you will find some magic formula for this problem and the result is straight forward.
This is a very simple problem. It seems quite difficult since the upper bound is very large. But after you did a little bit math, you will find some magic formula for this problem and the result is straight forward.
project euler problem 233
Lattice points on a circle
This is a problem of great importance. Many problems are based on the math theory of this one. It would be nice that one can spend an hour or two on this subject. I learned it from Ivan Niven's book. It takes 40 ms for my code to get the answer. The only advise is that do not miss any possible combinations. Problem 354 is an advanced version of this problem.
This is a problem of great importance. Many problems are based on the math theory of this one. It would be nice that one can spend an hour or two on this subject. I learned it from Ivan Niven's book. It takes 40 ms for my code to get the answer. The only advise is that do not miss any possible combinations. Problem 354 is an advanced version of this problem.
project euler problem 220
Heighway Dragon
This problem is a very interesting problem. When I tried to solve it a year ago, I had no clue about it until I figured out the relation between D_n and D_{n-1}. Then the problem is relatively simple and easy to code.
I took a look at the discussion. I find the dragon curve has very nice math properties. I do not know how to prove those properties. But even if one does not know the math, the problem can still be solved in an elegant approach.
This problem is a very interesting problem. When I tried to solve it a year ago, I had no clue about it until I figured out the relation between D_n and D_{n-1}. Then the problem is relatively simple and easy to code.
I took a look at the discussion. I find the dragon curve has very nice math properties. I do not know how to prove those properties. But even if one does not know the math, the problem can still be solved in an elegant approach.
Subscribe to:
Posts (Atom)