Searching a triangular array for a sub-triangle having minimum-sum
This is a simple problem. My old code is kind of brute force, but we are lucky since that we do not need to search too many points to find the minimum. This time, I make my code have a little bit "memory". This "a little bit memory" dramatically speeds up me code. It only takes 0.4 second to find the answer.
Sunday, April 28, 2013
project euler problem 149
Searching for a maximum-sum subsequence
I do not like this problem. Probably because that it is too random and cannot create enough tricks to avoid some sort of lazy programming. I followed the algorithm in CLRS and got it in 0.8 second.
I do not like this problem. Probably because that it is too random and cannot create enough tricks to avoid some sort of lazy programming. I followed the algorithm in CLRS and got it in 0.8 second.
project euler problem 148
Exploring Pascal's triangle
This is an interesting problem. I like this problem.
I do not know how I solved this problem the first time because I cannot find my old code. I really want to know what I thought at that time. I guess it should be similar to what lzw75 did in the discussion thread.
This time, I read Knuth's book(TAOCP, vol 1). I got a better understanding of this problem. I also read hyperdex's explanation of the problem. It is really interesting!
This is an interesting problem. I like this problem.
I do not know how I solved this problem the first time because I cannot find my old code. I really want to know what I thought at that time. I guess it should be similar to what lzw75 did in the discussion thread.
This time, I read Knuth's book(TAOCP, vol 1). I got a better understanding of this problem. I also read hyperdex's explanation of the problem. It is really interesting!
Saturday, April 27, 2013
project euler problem 147
Rectangles in cross-hatched grids
I cannot believe that there is a closed form for this problem. I need to spent some time to see how this is derived. I just noticed a few things to count the the rectangles in different orientations. It only takes 40 ms, not too bad.
I cannot believe that there is a closed form for this problem. I need to spent some time to see how this is derived. I just noticed a few things to count the the rectangles in different orientations. It only takes 40 ms, not too bad.
project euler problem 146
Investigating a Prime Pattern
This problem is quite difficult. I do not understand why this one is solved by more than 2000 people but problem 143 is solved only by 1100 people.
I do not have a very straight forward way to solve it. I combined two method into the code. It does not run very fast. 18 seconds.
This problem is quite difficult. I do not understand why this one is solved by more than 2000 people but problem 143 is solved only by 1100 people.
I do not have a very straight forward way to solve it. I combined two method into the code. It does not run very fast. 18 seconds.
project euler problem 145
How many reversible numbers are there below one-billion?
This is a simple problem. It can be solved with pencil and papers. There is no need to code. Brute force with small number is helpful to draw a conclusion.
This is a simple problem. It can be solved with pencil and papers. There is no need to code. Brute force with small number is helpful to draw a conclusion.
projectt euler problem 144
Investigating multiple reflections of a laser beam
This is a simple problem. Actually this is a math problem, not a coding problem. One need pencil and papers to do some math before coding.
The code runs in less than 1ms.
There will be a relatively more difficult laser beam problem in PE.
This is a simple problem. Actually this is a math problem, not a coding problem. One need pencil and papers to do some math before coding.
The code runs in less than 1ms.
There will be a relatively more difficult laser beam problem in PE.
project euler problem 143
Investigating the Torricelli point of a triangle
This is undoubtedly the most difficult problem in the first 150 problems. After it was posted for more than 6 years, only less than 1200 people solved the problem. This problem is created by hk. If you often goes to the PE forum, you can not miss his posts. He is very smart and pretty tough :).
Probably the most difficult part is to parameterize the triangles. Wikipedia is our good friend. After that part is done, it is a pure computer science problem. I do not have very good solution. My old code used multimap. It needs 4 second I rewrite the code and used unordered_map (hashmap). Now I only need 0.6 second to get the answer.
Update: in the discussion thread, lzw75 asks the answer for p+q+r <=1e7, I found that my notebook can not run. It costs too much memory. I then checked my code and found that I am too careless about my data structure. I changed the code a little bit. Now I can run it. It takes 71 seconds. For p+q+r<=120000, it only takes 0.2 second now.
This is undoubtedly the most difficult problem in the first 150 problems. After it was posted for more than 6 years, only less than 1200 people solved the problem. This problem is created by hk. If you often goes to the PE forum, you can not miss his posts. He is very smart and pretty tough :).
Probably the most difficult part is to parameterize the triangles. Wikipedia is our good friend. After that part is done, it is a pure computer science problem. I do not have very good solution. My old code used multimap. It needs 4 second I rewrite the code and used unordered_map (hashmap). Now I only need 0.6 second to get the answer.
Update: in the discussion thread, lzw75 asks the answer for p+q+r <=1e7, I found that my notebook can not run. It costs too much memory. I then checked my code and found that I am too careless about my data structure. I changed the code a little bit. Now I can run it. It takes 71 seconds. For p+q+r<=120000, it only takes 0.2 second now.
project euler problem 142
Perfect Square Collection
First time I saw this problem, I got lost. I did not think thoroughly on this problem, but use google to find the answer since this problem is so famous. (Is Euler the first one who gave the minimum solution?) Actually, analyzing the problem is not difficult at all.
My old code is actually from the discussion thread. But it was still not well written. I optimized the code a little bit. It runs 40ms or so.
First time I saw this problem, I got lost. I did not think thoroughly on this problem, but use google to find the answer since this problem is so famous. (Is Euler the first one who gave the minimum solution?) Actually, analyzing the problem is not difficult at all.
My old code is actually from the discussion thread. But it was still not well written. I optimized the code a little bit. It runs 40ms or so.
Thursday, April 25, 2013
project euler problem 141
Investigating progressive numbers, n, which are also square
This problem looks challenging. I do not remember how I solved it two years ago. This time, after analyzing the problem just a little bit, it becomes extremely easy. My code runs only 0.2s.
This problem looks challenging. I do not remember how I solved it two years ago. This time, after analyzing the problem just a little bit, it becomes extremely easy. My code runs only 0.2s.
project euler problem 139
Pythagorean tiles
I checked my code. It runs for 13 seconds. I feel it unacceptable.
I read the code just for one minute, then I found how to optimize it. The code run time reduced to 0.6 second. I should have done the optimization immediately after I solved the problem!
I read the discussion and found that there was a better algorithm! Read it if your code runs more than 0.5 second.
I checked my code. It runs for 13 seconds. I feel it unacceptable.
I read the code just for one minute, then I found how to optimize it. The code run time reduced to 0.6 second. I should have done the optimization immediately after I solved the problem!
I read the discussion and found that there was a better algorithm! Read it if your code runs more than 0.5 second.
Wednesday, April 24, 2013
project euler problem 138
Special isosceles triangles
This problem looks quite different with problem 137, but actually they are quite similar. It is even simpler than problem 137. If you can solve problem 66, I am sure you can reuse your code.
This problem looks quite different with problem 137, but actually they are quite similar. It is even simpler than problem 137. If you can solve problem 66, I am sure you can reuse your code.
project euler problem 137 140
Fibonacci golden nuggets
These two problems are quite difficult. I solved them, but I still do not have a good algorithm for generalized pell equation. I read some papers, but the algorithm is not easy to implement. So I used some of the properties of pell equation and find the solution. I did not find too much info in the discussion thread about solving the generalized pell equation.
These two problems are quite difficult. I solved them, but I still do not have a good algorithm for generalized pell equation. I read some papers, but the algorithm is not easy to implement. So I used some of the properties of pell equation and find the solution. I did not find too much info in the discussion thread about solving the generalized pell equation.
Monday, April 22, 2013
project problem 135 136
same difference, Singleton difference
I did this problem poorly, especially on 136. I used brute force method, and it only takes 2 second.
I read the discussion thread, I found that I just need to do a little bit more investigation on this problem to find a more efficient method.
I did this problem poorly, especially on 136. I used brute force method, and it only takes 2 second.
I read the discussion thread, I found that I just need to do a little bit more investigation on this problem to find a more efficient method.
project euler problem 134
Prime pair connection
This is a simple problem. The algorithm is given in CLRS.
This is a simple problem. The algorithm is given in CLRS.
project euler problem 131
Prime cube partnership
A relatively simple number theory problem. Once you understood what you are looking for, coding is very straight forward.
A relatively simple number theory problem. Once you understood what you are looking for, coding is very straight forward.
Sunday, April 21, 2013
project euler problem 129 130 132 133
Repunit
Problem 129 is easy to brute force. Some observation is required to make this problem simple and easy. This problem is very closely related to problem 26.
Problem 130 is also very simple. If we do not care to use brute force, the result can be found in 20ms or so. But smq and hk extended the problem to the limit of 2500. The problem becomes extremely time costly. I tried the limit = 1000, needs 10 seconds. limit 2500 needs 79 second. I do not want to waste time to 2500 since it takes more than half an hour.
Problem 132 is quite simple if one reviewed the discussion thread of problem 129 and 130. I generated all primes up to 500K, and it just take 50ms to find the first forty prime factors. In the discussion thread, daniel.is.fischer asks the sum of prime factors below 1e9. I tried it, it is quite difficult, my code runs for near 6 minutes to get the answer. I did not figure out how they made it to 1 minute.
Problem 133 looks like quite different, but still the same thing. Solved it under 20 ms.
Problem 129 is easy to brute force. Some observation is required to make this problem simple and easy. This problem is very closely related to problem 26.
Problem 130 is also very simple. If we do not care to use brute force, the result can be found in 20ms or so. But smq and hk extended the problem to the limit of 2500. The problem becomes extremely time costly. I tried the limit = 1000, needs 10 seconds. limit 2500 needs 79 second. I do not want to waste time to 2500 since it takes more than half an hour.
Problem 132 is quite simple if one reviewed the discussion thread of problem 129 and 130. I generated all primes up to 500K, and it just take 50ms to find the first forty prime factors. In the discussion thread, daniel.is.fischer asks the sum of prime factors below 1e9. I tried it, it is quite difficult, my code runs for near 6 minutes to get the answer. I did not figure out how they made it to 1 minute.
Problem 133 looks like quite different, but still the same thing. Solved it under 20 ms.
project euler problem 128
Hexagonal tile differences
This is not a so interesting problem. One just need to figure out which cell could have 3 prime-difference neighbors. Then the rest of the problem is simple and easy.
This is not a so interesting problem. One just need to figure out which cell could have 3 prime-difference neighbors. Then the rest of the problem is simple and easy.
project euler problem 127
abc-hits
This is an interesting and quite difficult problem in the early problems. I checked my old code. It runs for a long time. I killed it since it seems I still need to wait for a long time after 4 minutes run. I rewrote the code, after I learned something useful from problem 124. Well, it still takes 3 minutes to finish.
I checked my code carefully, and reordered some of the code. Then the time needed reduced to 3 second! I just realize that the order of the code is so important.
Finally, hk challenged everyone to try the c < 4000001. I rerun my code, got stuck again! My code need 2 to 3 minutes while hk's solution only needs 12 second. I read the discussion again. This time, I fully enjoyed the problem and reduced my code's run time to 12 second or so.
I learned a lot of things in this problem. I highly recommend everyone to try this problem on his or her own.
This is an interesting and quite difficult problem in the early problems. I checked my old code. It runs for a long time. I killed it since it seems I still need to wait for a long time after 4 minutes run. I rewrote the code, after I learned something useful from problem 124. Well, it still takes 3 minutes to finish.
I checked my code carefully, and reordered some of the code. Then the time needed reduced to 3 second! I just realize that the order of the code is so important.
Finally, hk challenged everyone to try the c < 4000001. I rerun my code, got stuck again! My code need 2 to 3 minutes while hk's solution only needs 12 second. I read the discussion again. This time, I fully enjoyed the problem and reduced my code's run time to 12 second or so.
I learned a lot of things in this problem. I highly recommend everyone to try this problem on his or her own.
project euler problem 126
Cuboid layers
This is the most difficult problem so far? Based on the number of solve, it is. Solved only by less than 2000 after seven years. You cannot name it a simple problem.
I hate this problem. I had a very hard time when I was trying to solve this problem the first time. I spent quite some time to figure out how many blocks needed for each layer. Then my life was much easier.
I read the discussion. I was surprised so many people do not want to take a little bit time to optimize their code. If your code runs more than a second, something is wrong! Mine only need less than 50 ms.
This is the most difficult problem so far? Based on the number of solve, it is. Solved only by less than 2000 after seven years. You cannot name it a simple problem.
I hate this problem. I had a very hard time when I was trying to solve this problem the first time. I spent quite some time to figure out how many blocks needed for each layer. Then my life was much easier.
I read the discussion. I was surprised so many people do not want to take a little bit time to optimize their code. If your code runs more than a second, something is wrong! Mine only need less than 50 ms.
project euler problem 125
Palindromic sums
This is a simple problem. Almost everyone is using brute force method. Although some of the brute force are clever, and some need more cpu time. Other than that, there is not much to learn. But if you read carefully, you still can see something interesting. One guy provided a better way to detect palindrome number, it is on page 2 by ped.
I tested this algorithm, with my implementation, my code runs for 40ms. With the new isPalindromic function, it reduces to 32ms. Really nice job!
There is a much more difficult problem which is related to this problem, problem 261.
This is a simple problem. Almost everyone is using brute force method. Although some of the brute force are clever, and some need more cpu time. Other than that, there is not much to learn. But if you read carefully, you still can see something interesting. One guy provided a better way to detect palindrome number, it is on page 2 by ped.
I tested this algorithm, with my implementation, my code runs for 40ms. With the new isPalindromic function, it reduces to 32ms. Really nice job!
There is a much more difficult problem which is related to this problem, problem 261.
Saturday, April 20, 2013
project euler problem 124
Ordered radicals
This is a simple problem. One can compare the numbers of solves on 124 and 122. Almost doubled! Sieve shows its power in this problem again!
This is a simple problem. One can compare the numbers of solves on 124 and 122. Almost doubled! Sieve shows its power in this problem again!
project euler problem 123
Prime square remainders
This is related to problem 120, even simpler. One just need to have a prime table to figure out the number.
This is related to problem 120, even simpler. One just need to have a prime table to figure out the number.
time and memory usage of a process in Linux
It is easy to google out that there is a utility called time(/usr/bin/time) which can be used to measure how long it takes to run your program. But there is no good tools for peak memory usages. Today, I found that people has already written some script for us. The link is here. I found it in stackoverflow.
project euler problem 122
Efficient exponentiation
I like this problem. It is a very good problem.
I tried it with different approaches. First, I found that Knuth has given a very fast algorithm to find out the most efficient way of doing exponentiation. I followed his idea, and find an answer, but Project Euler rejected it. Then I used a brute force tree method to solve it. It is solved, but very slow, and cost a lot of memory.
I learned from the discussion thread. I found this is a very difficult math problem and there is no algorithm ready for use. So the optimal solution is still kind of brute force. But it is critical to reduce the search space. I learned how to do it in C++. But I am not satisfied with what I learned. It is slower than hk's solution(now admin of PE). For example, if I changed the number 200 to 6000, it takes my code 80s to find the answer. hk's solution only needs 17s(several years ago). Since I am not familiar with Delphi, I gave up. If you understood what he was doing, please leave me a comment.
I like this problem. It is a very good problem.
I tried it with different approaches. First, I found that Knuth has given a very fast algorithm to find out the most efficient way of doing exponentiation. I followed his idea, and find an answer, but Project Euler rejected it. Then I used a brute force tree method to solve it. It is solved, but very slow, and cost a lot of memory.
I learned from the discussion thread. I found this is a very difficult math problem and there is no algorithm ready for use. So the optimal solution is still kind of brute force. But it is critical to reduce the search space. I learned how to do it in C++. But I am not satisfied with what I learned. It is slower than hk's solution(now admin of PE). For example, if I changed the number 200 to 6000, it takes my code 80s to find the answer. hk's solution only needs 17s(several years ago). Since I am not familiar with Delphi, I gave up. If you understood what he was doing, please leave me a comment.
Thursday, April 18, 2013
project euler problem 121
Disc game prize fund
This is a very simple probability problem. I have nothing to say about this problem.
This is a very simple probability problem. I have nothing to say about this problem.
project euler problem 120
Square remainders
This is an interesting problem. I am surprised to realize that this problem can be solved analytically. It is not difficult to find out. Ah, I just found the first part of the problem and did not think too much about the problem.
This is an interesting problem. I am surprised to realize that this problem can be solved analytically. It is not difficult to find out. Ah, I just found the first part of the problem and did not think too much about the problem.
project euler problem 119
Digit power sum
This is a simple problem. I rewrote my code, and it runs in less than 1ms. One just need control the maximum value of the base. Other than that, there is nothing to say about this problem.
This is a simple problem. I rewrote my code, and it runs in less than 1ms. One just need control the maximum value of the base. Other than that, there is nothing to say about this problem.
project euler problem 118
Pandigital prime sets
This problem seem not so easy to find an algorithm under 0.1 second. I checked the discussion thread, found that most solutions are at least a couple of seconds (that was posted several years ago) or use a prebuilt prime table.
It takes 0.6 second for my code to get the answer.
This problem seem not so easy to find an algorithm under 0.1 second. I checked the discussion thread, found that most solutions are at least a couple of seconds (that was posted several years ago) or use a prebuilt prime table.
It takes 0.6 second for my code to get the answer.
Wednesday, April 17, 2013
project euler problem 116, 117
Red, green or blue tiles
This problem is too simple. Coding takes less than 5 minutes. I used a function that was used in problem 113, 114, then I got the answer.
Problem 117 is just a little bit more difficult than problem 116, but it is still easier than 113 and 114. My code runs less than 1ms.
These two problem should have been solved by more than 10000 people.
This problem is too simple. Coding takes less than 5 minutes. I used a function that was used in problem 113, 114, then I got the answer.
Problem 117 is just a little bit more difficult than problem 116, but it is still easier than 113 and 114. My code runs less than 1ms.
These two problem should have been solved by more than 10000 people.
Tuesday, April 16, 2013
project euler problem 114, 115
Counting block combinations I, II
The problem is quite simple. I used binomial coefficient to compute the total number of ways with all red block size>=3.
After I read the discussion thread, I am surprised to find that there are a lot of ways to solve this problem. I felt that I am just lucky, if the size of the problem increased to 5000, my method is useless, but some other method is still very efficient.
Problem 115 is similar to problem 114, my code can still be used on this problem. I got the result in no time.
The problem is quite simple. I used binomial coefficient to compute the total number of ways with all red block size>=3.
After I read the discussion thread, I am surprised to find that there are a lot of ways to solve this problem. I felt that I am just lucky, if the size of the problem increased to 5000, my method is useless, but some other method is still very efficient.
Problem 115 is similar to problem 114, my code can still be used on this problem. I got the result in no time.
project euler problem 113
Non-bouncy numbers
I did not think about the problem and directly go to computer for help. The problem is simple, which can be solved by dynamic programming. But after I read the discussion, I suddenly realize that this problem can be solved analytically.
Think more about this problem before coding!
I did not think about the problem and directly go to computer for help. The problem is simple, which can be solved by dynamic programming. But after I read the discussion, I suddenly realize that this problem can be solved analytically.
Think more about this problem before coding!
project euler problem 112
Bouncy numbers
This problem is too easy! It should not appear after problem 100. I do not enjoy solving such kind of problem. My code only runs 56ms.
This problem is too easy! It should not appear after problem 100. I do not enjoy solving such kind of problem. My code only runs 56ms.
Monday, April 15, 2013
project euler problem 111
Primes with runs
From problem 110, the answer became large, so nobody can guess. And this also force us to think about some clever ways to solve the problem.
I checked my old code, it is not too bad, so I decided not to rewrite it. To solve problem like this one, I learned how to find the next combination number, something like next_permutation in STL. If one does not want to do it this way, the easiest way is probably recursion.
It takes 24ms to get the answer, not bad.
From problem 110, the answer became large, so nobody can guess. And this also force us to think about some clever ways to solve the problem.
I checked my old code, it is not too bad, so I decided not to rewrite it. To solve problem like this one, I learned how to find the next combination number, something like next_permutation in STL. If one does not want to do it this way, the easiest way is probably recursion.
It takes 24ms to get the answer, not bad.
project euler problem 110
Diophantine reciprocals II
This problem is not so easy. But since we have already solved problem 108, this problem becomes much easier. I have a very loose bound on the power of each prime, still only takes 8ms to get the answer.
This problem is not so easy. But since we have already solved problem 108, this problem becomes much easier. I have a very loose bound on the power of each prime, still only takes 8ms to get the answer.
Sunday, April 14, 2013
project euler problem 108
Diophantine reciprocals I
My old code is too ugly and complicated. I do not want to read it.
This time I rewrote my code, it is easy to read and runs pretty fast, only 0.3 second. But after I read the discussion, I felt that I should think more about how to solve this diophantine equation before writing the code. This could be a serious issue when the problem becomes more difficult.
If you did not give too much analytical analysis on this problem, please learn from the discussion.
My old code is too ugly and complicated. I do not want to read it.
This time I rewrote my code, it is easy to read and runs pretty fast, only 0.3 second. But after I read the discussion, I felt that I should think more about how to solve this diophantine equation before writing the code. This could be a serious issue when the problem becomes more difficult.
If you did not give too much analytical analysis on this problem, please learn from the discussion.
firefox right click menu not working solution in ubuntu
Go to advanced javascript settings in ubuntu at Edit->Preferences->Content->Advanced (next to "Enable javascript")-> uncheck the "Disable or replace context menus".
But sometimes the right button menu does not show up. Really disappointed! I will update when I find a better solution.
Looks like google Chrome does not have this problem.
But sometimes the right button menu does not show up. Really disappointed! I will update when I find a better solution.
Looks like google Chrome does not have this problem.
project euler problem 107
Minimal network
This is a simple minimum spanning tree problem. The algorithm is readily found in CLRS. I checked my old code, it runs pretty fast, but I wrote my own version of minheap. This time, I used STL's maxheap. It helps to reduce 40% of the code. But I found my old code runs faster.
This is a simple minimum spanning tree problem. The algorithm is readily found in CLRS. I checked my old code, it runs pretty fast, but I wrote my own version of minheap. This time, I used STL's maxheap. It helps to reduce 40% of the code. But I found my old code runs faster.
Saturday, April 13, 2013
project euler problem 364
Comfortable distance
This problem is not a very difficult one. But in my opinion, it is not easy.
When I first tried to solve this problem, the first and the last seat are quite troublesome. I also felt that occupancy of one seat would affect its neighbors, so it was difficult to use dynamic programming method.
I thought it over and finally found that this was just an relatively complicated combination problem. Several different situations needs to be handled. In each situation, it is relatively easy to find the number of ways to make all people seated following the rule.
My code's efficiency is not too bad. It takes less than 0.6 second to get the correct answer.
This problem is not a very difficult one. But in my opinion, it is not easy.
When I first tried to solve this problem, the first and the last seat are quite troublesome. I also felt that occupancy of one seat would affect its neighbors, so it was difficult to use dynamic programming method.
I thought it over and finally found that this was just an relatively complicated combination problem. Several different situations needs to be handled. In each situation, it is relatively easy to find the number of ways to make all people seated following the rule.
My code's efficiency is not too bad. It takes less than 0.6 second to get the correct answer.
Friday, April 12, 2013
project euler problem 334
Spilling the beans
An interesting problem!
I spent several hours on this problem, but failed to find any clue. I wrote a brute force solution for it, checked the number of moves required when the number of beans are small in each bowl(two bowls for example). I found some analytical formula for any number of beans in only two bowls, but all futile. Since the problem ask for 1500 bowls, the total number of beans is about 1.5 million! The largest headache I found is to determine the position of the empty bowl.
I played the game again and again on papers, those empty bowls are killing me! Finally I found a solution to make number of empty bowls at minimum. But my program is too slow. After some time, I found how to make it efficient. The trick is simple, we need to do as much analytical work as we can, leave the task for the computer easy and simple.
It only takes my notebook 0.03 second to get the answer! Isn't that kidding?! I spent a couple of days working for the computer and leave it only 30 millisecond's work.
I really enjoyed in solving the problem. This is the glamour of project euler!
An interesting problem!
I spent several hours on this problem, but failed to find any clue. I wrote a brute force solution for it, checked the number of moves required when the number of beans are small in each bowl(two bowls for example). I found some analytical formula for any number of beans in only two bowls, but all futile. Since the problem ask for 1500 bowls, the total number of beans is about 1.5 million! The largest headache I found is to determine the position of the empty bowl.
I played the game again and again on papers, those empty bowls are killing me! Finally I found a solution to make number of empty bowls at minimum. But my program is too slow. After some time, I found how to make it efficient. The trick is simple, we need to do as much analytical work as we can, leave the task for the computer easy and simple.
It only takes my notebook 0.03 second to get the answer! Isn't that kidding?! I spent a couple of days working for the computer and leave it only 30 millisecond's work.
I really enjoyed in solving the problem. This is the glamour of project euler!
Wednesday, April 10, 2013
project euler problem 104
Pandigital Fibonacci ends
I reviewed my old code today, it is ugly. I kept all digits in a vector, which finally contains a n X 10,000 of digits, where most of them are useless. This time, I only kept the last 9 digits.
I compared my old code with my new code.
Old code: 20 seconds;
New code: 0.144 second;
The difference is huge!
There is another problem which is quite similar to this problem but much more difficult to solve. Problem 399
I reviewed my old code today, it is ugly. I kept all digits in a vector, which finally contains a n X 10,000 of digits, where most of them are useless. This time, I only kept the last 9 digits.
I compared my old code with my new code.
Old code: 20 seconds;
New code: 0.144 second;
The difference is huge!
There is another problem which is quite similar to this problem but much more difficult to solve. Problem 399
project euler problem 103
Special subset sums: optimum
I do not like this problem too much. It seems that everyone is using brute force method. The problem cannot be easily generalized to n = 10 or larger numbers.
I do not like this problem too much. It seems that everyone is using brute force method. The problem cannot be easily generalized to n = 10 or larger numbers.
project euler problem 102
Triangle containment
This problem is great! I used very complicated logic in my code. I got the correct answer after I fixed one tricky bug in my code. Then I checked the discussion thread. I found two interesting algorithms. First, how to calculate the area of the triangle given the coordinates of vertices. Second, how to solve this problem efficiently. I feel awful that I missed these algorithms for more than a year!
This problem is great! I used very complicated logic in my code. I got the correct answer after I fixed one tricky bug in my code. Then I checked the discussion thread. I found two interesting algorithms. First, how to calculate the area of the triangle given the coordinates of vertices. Second, how to solve this problem efficiently. I feel awful that I missed these algorithms for more than a year!
Tuesday, April 9, 2013
project euler problem 101
Optimum polynomial
This problem is not difficult. I used matrix solve to find the optimal polynomial. After I read the discussion thread, I found there was a better solution for this problem, which can make everything simpler. I never heard of the algorithm before. Please take a look at the thread to learn it.
This problem is not difficult. I used matrix solve to find the optimal polynomial. After I read the discussion thread, I found there was a better solution for this problem, which can make everything simpler. I never heard of the algorithm before. Please take a look at the thread to learn it.
Monday, April 8, 2013
project euler problem 100
Arranged probability
This problem is simple if problem 66 has been solved. These two problems are closely related. Actually this problem is easier than problem 66. Brute force is not an option. It takes less than 1ms to get the answer.
This problem is simple if problem 66 has been solved. These two problems are closely related. Actually this problem is easier than problem 66. Brute force is not an option. It takes less than 1ms to get the answer.
project euler problem 099
Largest exponential
This is a very simple problem. It can not be simpler. Everyone can solve it. At least for those who like math.
This is a very simple problem. It can not be simpler. Everyone can solve it. At least for those who like math.
project euler problem 097
Large non-Mersenne prime
This problem is easy if one has an efficient algorithm to calculate power. Another headache is to find value mod 10^10 correctly. If either is not an issue, the problem is extremely simple. It takes less than 1ms.
This problem is easy if one has an efficient algorithm to calculate power. Another headache is to find value mod 10^10 correctly. If either is not an issue, the problem is extremely simple. It takes less than 1ms.
project euler problem 095
Amicable chains
I checked my old code. It was cumbersome. I used set and my algorithm to find all divisors was too slow. It takes 6.5 second to find the answer.
This time, I changed the divisor sum algorithm by using some sieve method. But it is still not very fast since I used hashset to check if the number appeared in the sequence. It is kind of overkill. But this reduced the run time to 0.764 second.
I read the discussion thread and find a better algorithm to stop the sequence. I reimplemented the code, it reduced to 0.196 second with my debug version. Sweet!
I checked my old code. It was cumbersome. I used set and my algorithm to find all divisors was too slow. It takes 6.5 second to find the answer.
This time, I changed the divisor sum algorithm by using some sieve method. But it is still not very fast since I used hashset to check if the number appeared in the sequence. It is kind of overkill. But this reduced the run time to 0.764 second.
I read the discussion thread and find a better algorithm to stop the sequence. I reimplemented the code, it reduced to 0.196 second with my debug version. Sweet!
Sunday, April 7, 2013
project euler problem 094
Almost equilateral triangles
This problem is a little bit challenging. I take a look at my old code, it runs very fast. But I can not figure what I was doing since I did not write any comment. Then I spent an hour to analyze this problem and figured out why I wrote those magic code. It takes 4ms to get the answer.
Pythagorean triplet is critical for an efficient algorithm.
update 10/15/2017
The old code still not works very efficient especially when perimeter goes to 1e18. Actually, after the restriction equation on the sides is determined, it is easy to see that this problem is a Pell Equation problem. Pell equation has very rare solutions and it takes zero ms to figure out all triangles.
This problem is a little bit challenging. I take a look at my old code, it runs very fast. But I can not figure what I was doing since I did not write any comment. Then I spent an hour to analyze this problem and figured out why I wrote those magic code. It takes 4ms to get the answer.
Pythagorean triplet is critical for an efficient algorithm.
update 10/15/2017
The old code still not works very efficient especially when perimeter goes to 1e18. Actually, after the restriction equation on the sides is determined, it is easy to see that this problem is a Pell Equation problem. Pell equation has very rare solutions and it takes zero ms to figure out all triangles.
project euler problem 093
Arithmetic expressions
My old code is too complicated, so I rewrote the code. The new code is much simpler and easier to read. It took 1.7 second for my old code to finish while the new one only needs 0.048 second.
But I do not have a good solution if we change the number of distinct numbers to 10 or even larger number. There is another similar problem in project Euler which is more difficult. Problem 259. Some of the strategy used in this problem may also apply to that problem.
Update 10/13/2017
One version of my code missed the role of parenthesis but the result of the original ProjectEuler problem is still correct. Thanks for projectEuler+ to help me fix the bug.
My old code is too complicated, so I rewrote the code. The new code is much simpler and easier to read. It took 1.7 second for my old code to finish while the new one only needs 0.048 second.
But I do not have a good solution if we change the number of distinct numbers to 10 or even larger number. There is another similar problem in project Euler which is more difficult. Problem 259. Some of the strategy used in this problem may also apply to that problem.
Update 10/13/2017
One version of my code missed the role of parenthesis but the result of the original ProjectEuler problem is still correct. Thanks for projectEuler+ to help me fix the bug.
Saturday, April 6, 2013
project euler problem 092
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.
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.
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)