Square digit chains
This is a simple problem. After I read the discussion thread, I found that my solution is kind of brute force style. It could be solved in a much simpler way.
Updated 10/08/2017:
After I reviewed the projecteuler+ problem, I found that this is a simple dynamic programming problem. It can be simply solved without combinatorial and actually even simpler.
Saturday, April 6, 2013
project euler problem 091
Right triangles with integer coordinates
This problem is too simple. I wrote the code, compile and run, then it is solved. Even if I modify the boundary to 5000, my code only runs 1.5 second to find the correct answer.
There is only one concept in the problem. How to solve the equation ax+by = c, it is easy to find out how to solve such kind of diophantine equation.
This problem is too simple. I wrote the code, compile and run, then it is solved. Even if I modify the boundary to 5000, my code only runs 1.5 second to find the correct answer.
There is only one concept in the problem. How to solve the equation ax+by = c, it is easy to find out how to solve such kind of diophantine equation.
project euler problem 305
Reflexive Position
This is the third time we see this number?
Champernowne’s constant. The first time we see it is in problem 40. If you take a look, you can feel the difference between the problems created in recent years and the problems created 10 years ago.
This problem is really interesting. It is easy to write a brute force code for small numbers, it is no-brainer! But for large numbers, it takes hours or days to get a correct answer.
From a long time ago, I knew how to solve it, but I do not want to write the complicated code to handle all situations. Several days ago, I decided to work on this problem in my spare time. It is really disturbing to find bugs here and there. Finally, I made it work. It takes less than 1 ms to get the answer! But I spent hours to make it correct.
The examples are very helpful if one does not write his own brute force code. 7780 is a very very important number. Even with this number, I still made some mistake in my code. But I watched those 3^n for a couple of minutes, then figured out why my answer is not correct. Another important number is 243, but it is small and easy to debug.
This is the third time we see this number?
Champernowne’s constant. The first time we see it is in problem 40. If you take a look, you can feel the difference between the problems created in recent years and the problems created 10 years ago.
This problem is really interesting. It is easy to write a brute force code for small numbers, it is no-brainer! But for large numbers, it takes hours or days to get a correct answer.
From a long time ago, I knew how to solve it, but I do not want to write the complicated code to handle all situations. Several days ago, I decided to work on this problem in my spare time. It is really disturbing to find bugs here and there. Finally, I made it work. It takes less than 1 ms to get the answer! But I spent hours to make it correct.
The examples are very helpful if one does not write his own brute force code. 7780 is a very very important number. Even with this number, I still made some mistake in my code. But I watched those 3^n for a couple of minutes, then figured out why my answer is not correct. Another important number is 243, but it is small and easy to debug.
project euler problem 090
Cube digit pairs
The problem is easy to solve since there is not too many numbers to be checked. The critical part is to find all combinations efficiently. I checked several pages in the discussion thread, but I did not find any better method.
Update 10/07/2017
Actually there is a an approach in the discussion which used bit to represent 0-9. With bit, it is easier to implement the code.
The problem is easy to solve since there is not too many numbers to be checked. The critical part is to find all combinations efficiently. I checked several pages in the discussion thread, but I did not find any better method.
Update 10/07/2017
Actually there is a an approach in the discussion which used bit to represent 0-9. With bit, it is easier to implement the code.
Monday, April 1, 2013
project euler problem 088
Product-sum numbers
First, we can find an upper bound for the minimal product-sum numbers. The rest of the job is just to find the minimal by checking all combinations. Brute force is still quite fast.Update 10/06/2017
Brute force method is usually not a good choice. I checked my old code and find it very inefficient. I used a top down method, which start from a number n and try to figure out all possible combinations that leads to a product of n. The worst thing is that I do not know the limit that I should pick. So in my old code I pick 1e7 and get the correct answer. After some thought, I figured out that a bottom up approach is better which can handle the limit much easier!
I think I learned a little bit from this review.
project euler problem 087
Prime power triples
This problem is simple.We can compare it with problem 86.
problem 86: solved by 5155.
problem 87: solved by 8745.
There is not too much to say about this problem. I compared the efficiency of set with unordered_set. I do not want to create a large vector. With set, it takes 0.62sec. With unordered_set, it takes 0.44sec.
This problem is simple.We can compare it with problem 86.
problem 86: solved by 5155.
problem 87: solved by 8745.
There is not too much to say about this problem. I compared the efficiency of set with unordered_set. I do not want to create a large vector. With set, it takes 0.62sec. With unordered_set, it takes 0.44sec.
project euler problem 086
Cuboid route
Among the first 100 problems, this one is not easy.
Since my old code was lost, I rewrote it. It still took me three hours to get it work in a relatively efficient way. It takes less than 1ms for my optimized version to get the correct answer.
Update 10/05/2017, I found my previous code for this problem is not efficient because I did not choose the number range carefully and I need to set the maximum to be large enough to get a correct answer for n=1e11. It is a little bit tricky to find an appropriate limit for the pythagorean triangle numbers. There is still room to make improvement, but I will live with it since I have already passed the projecteuler+ tests for this problem.
Among the first 100 problems, this one is not easy.
Since my old code was lost, I rewrote it. It still took me three hours to get it work in a relatively efficient way. It takes less than 1ms for my optimized version to get the correct answer.
Update 10/05/2017, I found my previous code for this problem is not efficient because I did not choose the number range carefully and I need to set the maximum to be large enough to get a correct answer for n=1e11. It is a little bit tricky to find an appropriate limit for the pythagorean triangle numbers. There is still room to make improvement, but I will live with it since I have already passed the projecteuler+ tests for this problem.
Subscribe to:
Posts (Atom)