Counting rectangles
Since an analytical formula is available for total the number of rectangles, the rest is simply sweeping all possible length and width. It takes less than 1ms to find the answer.
Sunday, March 31, 2013
project euler problem 081, 082, 083
Path sum: two ways, three ways, four ways
project euler problem 081, two ways
Very simple dynamic programming problem. Warm up for the next two problem.
project euler problem 082, three ways
A little bit more complicated. Still simple dynamic programming problem. warm up problem.
project euler problem 083 four ways
This is a real problem. Not that simple. I used the C++ STL priority_queue to solve this problem, fast and simple. 16ms with my debug version.
project euler problem 081, two ways
Very simple dynamic programming problem. Warm up for the next two problem.
project euler problem 082, three ways
A little bit more complicated. Still simple dynamic programming problem. warm up problem.
project euler problem 083 four ways
This is a real problem. Not that simple. I used the C++ STL priority_queue to solve this problem, fast and simple. 16ms with my debug version.
Saturday, March 30, 2013
project euler problem 080
Square root digital expansion
This is an interesting problem. I checked my old code, I used my bigInteger class, and used Newton's method iteratively to get the accurate result. It takes 0.7 second to find the number.
This time I used continued fraction method, and I can figure out as many digits of p/q as required. The code is fast although my bigInteger class is slow. It only takes 1.6ms to find the answer.
I also verified the result for the first 1000 digits of sqrt(2) to sqrt(99) as it is given in the discussion thread. It takes 0.77 second.
Update: 09/26/2017
Python is a great helper. With Decimal, this problem is no-brainer.
This is an interesting problem. I checked my old code, I used my bigInteger class, and used Newton's method iteratively to get the accurate result. It takes 0.7 second to find the number.
This time I used continued fraction method, and I can figure out as many digits of p/q as required. The code is fast although my bigInteger class is slow. It only takes 1.6ms to find the answer.
I also verified the result for the first 1000 digits of sqrt(2) to sqrt(99) as it is given in the discussion thread. It takes 0.77 second.
Update: 09/26/2017
Python is a great helper. With Decimal, this problem is no-brainer.
project euler problem 078
Coin partitions
This problem is similar to problem 076, but need some math knowledge, otherwise, it becomes terrifically difficult. I was forced to find some useful formula, and finally succeed. I need to check how to prove this useful formula.
This problem is similar to problem 076, but need some math knowledge, otherwise, it becomes terrifically difficult. I was forced to find some useful formula, and finally succeed. I need to check how to prove this useful formula.
project euler problem 077
Prime summations
Similar to problem 76.
This is not a difficult problem. But there is a lot math to be learned in the discussion thread. Euler is really a genius!
Update 09/25/2017:
The recursive method used in my previous code is too slow. I did not notice that until I tried to find the number of ways to express 1000 in primes. It is too slow! I used the dynamic programming approach to solve this knapsack problem and it takes less than 1ms to get the result!
Similar to problem 76.
This is not a difficult problem. But there is a lot math to be learned in the discussion thread. Euler is really a genius!
Update 09/25/2017:
The recursive method used in my previous code is too slow. I did not notice that until I tried to find the number of ways to express 1000 in primes. It is too slow! I used the dynamic programming approach to solve this knapsack problem and it takes less than 1ms to get the result!
Friday, March 29, 2013
project euler problem 076
Counting summations
Project Euler problems become interesting from 60--70. The first 50 problems are mainly warm-up problems. Now, we can see some interesting math problems such as Pell equations and partition.
This problem is interesting but still simple. It is very similar to problem 31 and can be solved recursively or with generating function.
update: 09/25/2017: The simplest way of solving this problem is using dynamic programming, this is a knapsack problem.
The answer for N = 10000 can be found in 0.74 second.
Project Euler problems become interesting from 60--70. The first 50 problems are mainly warm-up problems. Now, we can see some interesting math problems such as Pell equations and partition.
This problem is interesting but still simple. It is very similar to problem 31 and can be solved recursively or with generating function.
update: 09/25/2017: The simplest way of solving this problem is using dynamic programming, this is a knapsack problem.
The answer for N = 10000 can be found in 0.74 second.
project euler problem 075
Singular integer right triangles
A simple problem, very easy if one knew the algorithm. I am just wondering if there is any simpler algorithm without the help of a counter array?
A simple problem, very easy if one knew the algorithm. I am just wondering if there is any simpler algorithm without the help of a counter array?
project euler problem 074
Digit factorial chains
This problem is interesting. It is not difficult to brute force. But finding a very efficient algorithm is not that easy. My code runs 0.7second without too much memory cost. The key is to avoid duplicate computation.
PE problem makers like factorial quite a bit. There are quite a few more difficult problems that are related with factorials.
update 09/25/2017:
the old code is still hard to read. I rewrote the recursive function to find the different numbers in the list. The logic is easier to understand now.
This problem is interesting. It is not difficult to brute force. But finding a very efficient algorithm is not that easy. My code runs 0.7second without too much memory cost. The key is to avoid duplicate computation.
PE problem makers like factorial quite a bit. There are quite a few more difficult problems that are related with factorials.
update 09/25/2017:
the old code is still hard to read. I rewrote the recursive function to find the different numbers in the list. The logic is easier to understand now.
Thursday, March 28, 2013
project euler problem 073
Counting fractions in a range
It is one of the best problems in the first one hundred project Euler problems, I learned a lot of stuff from this problem.
This is the third problem about Farey sequence. I learned how to solve this problem from wikipedia. It is very simple when one learned the algorithm. It takes 0.3s to find the answer.
Update: I did not review this problem carefully. Daniel wrote a very good and detailed tutorial for this problem. It has 14 pages! I found a lot of gems in it. I hope everyone who like this problem spending some time to read it.
The result mentioned is not good enough. For limit 12000, the time needed is less than 100 ms. For limit=100000, it only need 2 seconds.
09/24/2017
I tried to solve the problem with mobius inversion formula and find it is very efficient. I learned how to compute the mobius inversion function quickly with sieve after some search from the Internet. For limit = 100000, it only takes 8ms to get the answer! and limit=10000000, the answer can be found in 1.8 second. I have not tried the sublinear(in the review of this problem) algorithm yet, which is much faster!
It is one of the best problems in the first one hundred project Euler problems, I learned a lot of stuff from this problem.
This is the third problem about Farey sequence. I learned how to solve this problem from wikipedia. It is very simple when one learned the algorithm. It takes 0.3s to find the answer.
Update: I did not review this problem carefully. Daniel wrote a very good and detailed tutorial for this problem. It has 14 pages! I found a lot of gems in it. I hope everyone who like this problem spending some time to read it.
The result mentioned is not good enough. For limit 12000, the time needed is less than 100 ms. For limit=100000, it only need 2 seconds.
09/24/2017
I tried to solve the problem with mobius inversion formula and find it is very efficient. I learned how to compute the mobius inversion function quickly with sieve after some search from the Internet. For limit = 100000, it only takes 8ms to get the answer! and limit=10000000, the answer can be found in 1.8 second. I have not tried the sublinear(in the review of this problem) algorithm yet, which is much faster!
project euler problem 072
Counting fractions
I checked my old code. I was trying to factor each number n, then find the number of relative prime numbers to n. This time I directly calculate the totient function for each number, using sieve.
It takes 3.6s to finish for the old code, while 0.076s for the new code.
I checked my old code. I was trying to factor each number n, then find the number of relative prime numbers to n. This time I directly calculate the totient function for each number, using sieve.
It takes 3.6s to finish for the old code, while 0.076s for the new code.
project euler problem 071
Ordered fractions
This problem may be bruteforced. But if the number N is huge(1E15), bruteforce is impossible. The math concept under this problem is called the farey sequence. Once the basic property between neighbors is understood, the problem is easy to figure out. even if N is huge like those in projectEuler+.
This problem may be bruteforced. But if the number N is huge(1E15), bruteforce is impossible. The math concept under this problem is called the farey sequence. Once the basic property between neighbors is understood, the problem is easy to figure out. even if N is huge like those in projectEuler+.
Wednesday, March 27, 2013
project euler problem 070
Totient permutation
This problem is also about totient function, but it is not so straight forward to find an efficient solution.
I do not have my old code, so I first factored all number and calculate phi(n). It is obvious that this is not a good choice. It takes 8 second to get the answer(debug version). I am not satisfied with this solution. So I used a sieve method to compute all number's totient function. This is better, it takes 5 second in debug version and 1 second in optimized version to get the answer.
This problem is also about totient function, but it is not so straight forward to find an efficient solution.
I do not have my old code, so I first factored all number and calculate phi(n). It is obvious that this is not a good choice. It takes 8 second to get the answer(debug version). I am not satisfied with this solution. So I used a sieve method to compute all number's totient function. This is better, it takes 5 second in debug version and 1 second in optimized version to get the answer.
project euler problem 069
Totient maximum
This is the first problem about Euler's famous totient function or phi function. A lot of PE problems need to use totient function. This one is very straight forward if one understand the basic properties of totient function. It can be solved with the help of a calculator actually.
This is the first problem about Euler's famous totient function or phi function. A lot of PE problems need to use totient function. This one is very straight forward if one understand the basic properties of totient function. It can be solved with the help of a calculator actually.
project euler problem 068
Magic 5-gon ring
This is a simple problem. My old code is pure brute force and can only be used for 5-gon. I rewrote the code, it can be used of n-gon ring. It takes 4ms to get the correct answer.
update 09/21/2017
a bug is found in my old code, an obvious one, which still successfully found the maximum value required in the problem but cannot generate all qualified sequences.
This is a simple problem. My old code is pure brute force and can only be used for 5-gon. I rewrote the code, it can be used of n-gon ring. It takes 4ms to get the correct answer.
update 09/21/2017
a bug is found in my old code, an obvious one, which still successfully found the maximum value required in the problem but cannot generate all qualified sequences.
Tuesday, March 26, 2013
project euler problem 066
Diophantine equation
I feel this is the most difficult problem in the first 100 PE problems(at least, the top five). This diophantine equation is called Pell Equation, which can be seen in every elementary number theory books. I should admit that I cheated on this problem. I did not solve this problem, but google helped me to find out the answer. This time, I solved it with the help of wikipedia and wolfram mathworld.
It is a very interesting problem! x^2-61y^2=1 with solution x=1766319049, y=226153980 is a notorious diophantine equation in the math history.
I tried to change D upto 100000, I found that the value of x and y are
9138623307350640837938507246130056541284450249628186652711211526290141593088447074959889691586109808446586788487329855457947449359122812196406183471094085243300140113776722320673519989258197664615506581635543258793642137960637895993371068043922291726707457424732865511811603416709407607285667077345150397643032877987726841522351750655900253781916899660152174806370963781778224969807395941841736594668461346490187409918540644500596164105739747237839541686461147582701486262272823400803243678345216257264359841059899047944315969645240323636858831783554703663860186919961543958325467259751629633944639211198469786177829884186709831569216425531620090438319686256712276877552760998820897069126292769743115626179169131031894821449
29995606985908278391394125599135320972040960690735594014932999302562021607917845625308781046774668965028391500344676078764117785968987025596642346687378667667268554217805689486419938846247966636235622466824853671443727025761340681500617596724921086840802447598463611192953164168684707145263201173090354218890224078617132621981270144387271894050379162839910605924620561997843353743092508084766465038567232036892276652930541497664634108271302723027950641070447197899109815123567584348859003464872979489356061130456764804964145771699318883015346111831572404557647659469760522059443590269944115798752448599110602793086535348170280145151753392282563680433826089979371590683960862942643266548255841329663100421901070962552821740
when D = 92821
It is amazing to find these two more than 700 digits numbers in less than 20 seconds with my x220 notebook.
09/21/2017: did the same thing with python with much easier implementation
I feel this is the most difficult problem in the first 100 PE problems(at least, the top five). This diophantine equation is called Pell Equation, which can be seen in every elementary number theory books. I should admit that I cheated on this problem. I did not solve this problem, but google helped me to find out the answer. This time, I solved it with the help of wikipedia and wolfram mathworld.
It is a very interesting problem! x^2-61y^2=1 with solution x=1766319049, y=226153980 is a notorious diophantine equation in the math history.
I tried to change D upto 100000, I found that the value of x and y are
9138623307350640837938507246130056541284450249628186652711211526290141593088447074959889691586109808446586788487329855457947449359122812196406183471094085243300140113776722320673519989258197664615506581635543258793642137960637895993371068043922291726707457424732865511811603416709407607285667077345150397643032877987726841522351750655900253781916899660152174806370963781778224969807395941841736594668461346490187409918540644500596164105739747237839541686461147582701486262272823400803243678345216257264359841059899047944315969645240323636858831783554703663860186919961543958325467259751629633944639211198469786177829884186709831569216425531620090438319686256712276877552760998820897069126292769743115626179169131031894821449
29995606985908278391394125599135320972040960690735594014932999302562021607917845625308781046774668965028391500344676078764117785968987025596642346687378667667268554217805689486419938846247966636235622466824853671443727025761340681500617596724921086840802447598463611192953164168684707145263201173090354218890224078617132621981270144387271894050379162839910605924620561997843353743092508084766465038567232036892276652930541497664634108271302723027950641070447197899109815123567584348859003464872979489356061130456764804964145771699318883015346111831572404557647659469760522059443590269944115798752448599110602793086535348170280145151753392282563680433826089979371590683960862942643266548255841329663100421901070962552821740
when D = 92821
It is amazing to find these two more than 700 digits numbers in less than 20 seconds with my x220 notebook.
09/21/2017: did the same thing with python with much easier implementation
Monday, March 25, 2013
project euler problem 065
Convergents of e
This is another problem about continued fractions. It is similar to problem 064. I used my bigInteger class to get the numerator of the 100th convergents. Not difficult at all.
09/19/2017
I tried python this time, no worry about long integers anymore!
This is another problem about continued fractions. It is similar to problem 064. I used my bigInteger class to get the numerator of the 100th convergents. Not difficult at all.
09/19/2017
I tried python this time, no worry about long integers anymore!
project euler problem 063
Powerful digit counts
Simple problem. Too few numbers satisfy the specified condition. Littleto be learned in this problem.
Simple problem. Too few numbers satisfy the specified condition. Littleto be learned in this problem.
project euler problem 062
Cubic permutations
I first used brute force method, and it took 3.5s to get the result. Then I revised my code from O(n^2) to O(n). The run time reduce to 0.1s.
The key of hashtable is important. I found two ways for the key. The first way is to convert the number to string and then sort the string characters in order. A second approach is found from INTERNET, using a long integer, each 6 bit is used as count for a digit (0-9). The maximum count is 2^6 = 64 which is much larger than the number of digits for n^3. Smart!
I first used brute force method, and it took 3.5s to get the result. Then I revised my code from O(n^2) to O(n). The run time reduce to 0.1s.
The key of hashtable is important. I found two ways for the key. The first way is to convert the number to string and then sort the string characters in order. A second approach is found from INTERNET, using a long integer, each 6 bit is used as count for a digit (0-9). The maximum count is 2^6 = 64 which is much larger than the number of digits for n^3. Smart!
Sunday, March 24, 2013
project euler problem 061
Cyclical figurate numbers
This problem is a simple problem. One just needs to find all the pairs of number and order(3, 4, 5, 6, 7, 8), then find the cycle recursively. It is very fast, less than 1ms on my notebook.
I found my old code, it was messy, I used multimap in the code. The code has 200 lines; the new one has only 70 lines.
This problem is a simple problem. One just needs to find all the pairs of number and order(3, 4, 5, 6, 7, 8), then find the cycle recursively. It is very fast, less than 1ms on my notebook.
I found my old code, it was messy, I used multimap in the code. The code has 200 lines; the new one has only 70 lines.
project euler problem 060
Prime pair sets
This might be a relatively difficult problem so far. I checked my old code. It is ugly. I created prime numbers up to 1e8, which is a huge cost(run time 22s). I used strong pseduoprime test instead of checking from the prime list, the code run time reduced to 1.4s. But the code structure still looks unacceptable.
I rewrote my code, following the clever idea found in the discussion thread. The new code looks simpler, but not too much performance gain.
This might be a relatively difficult problem so far. I checked my old code. It is ugly. I created prime numbers up to 1e8, which is a huge cost(run time 22s). I used strong pseduoprime test instead of checking from the prime list, the code run time reduced to 1.4s. But the code structure still looks unacceptable.
I rewrote my code, following the clever idea found in the discussion thread. The new code looks simpler, but not too much performance gain.
project euler problem 058
Spiral primes
This problem is about the primality of a number. I used two different method to solve this problem. First, use a prime table and second use strong pseudo prime test. The first method takes 0.1 second and the second takes 0.04 second.
update 09/17/2017. This problem is great, but the 10% requirement is too easy for everyone to get a correct answer, if this number is reduced to 8%, the problem is a lot more difficult since overflow is a challenging issue for primality test. I found a different approach from Inamori and francky's post, which is brilliant.
This problem is about the primality of a number. I used two different method to solve this problem. First, use a prime table and second use strong pseudo prime test. The first method takes 0.1 second and the second takes 0.04 second.
update 09/17/2017. This problem is great, but the 10% requirement is too easy for everyone to get a correct answer, if this number is reduced to 8%, the problem is a lot more difficult since overflow is a challenging issue for primality test. I found a different approach from Inamori and francky's post, which is brilliant.
project euler problem 057
Square root convergents
The problem is not that easy, but still more than 16000 people solved it. I do not like the problem too much since when we reached 1000 iterations, both the numerator and denominator are huge. We need to use vectors(arrays) to store these numbers. The recurrence relation is critical for the continued fraction.
Updated 09/16/2017
with python, one does not need to worry about overflow, and it is very easy to find the relation between numerator and denominator of iteration k and those of iteration k+1. Solved in 13 lines.
The problem is not that easy, but still more than 16000 people solved it. I do not like the problem too much since when we reached 1000 iterations, both the numerator and denominator are huge. We need to use vectors(arrays) to store these numbers. The recurrence relation is critical for the continued fraction.
Updated 09/16/2017
with python, one does not need to worry about overflow, and it is very easy to find the relation between numerator and denominator of iteration k and those of iteration k+1. Solved in 13 lines.
project euler problem 056
Powerful digit sum
I wrote something like BigInteger for problems involve number greater than 2^64; This is the first time that I used this class. There is probably quite a few problems in PE problems between 50--100 require BigInteger.
I do not prefer to use it since the performance of my biginteger class is poor. But for this problem, it is OK. I checker all combinations, and the time cost is only 0.1s.
update: 09/16/2017
I wrote a python script to avoid using bigInteger class. It is just several lines to solve this problem.
I wrote something like BigInteger for problems involve number greater than 2^64; This is the first time that I used this class. There is probably quite a few problems in PE problems between 50--100 require BigInteger.
I do not prefer to use it since the performance of my biginteger class is poor. But for this problem, it is OK. I checker all combinations, and the time cost is only 0.1s.
update: 09/16/2017
I wrote a python script to avoid using bigInteger class. It is just several lines to solve this problem.
project euler problem 055
Lychrel numbers
A simple problem. I used two vectors in the calculation in each iteration. one for current number and the other for the new one. There is not much to be learned from this problem.
A simple problem. I used two vectors in the calculation in each iteration. one for current number and the other for the new one. There is not much to be learned from this problem.
project euler problem 053
Combinatoric selections
This is a simple problem. I do not remember what I did in my old code. But most probably I used the definition of nchoosek, which is quite costly in computation.
This time I used pascal's triangle, which is much more efficient than my previous code.With my notebook, it takes less than 1ms.
But when I tried the challenge with projectEuler+ at hackerrank, it did not work since the value K can be 1e18, which has overflow issue with 64bit integer. I finally use double to get it accepted!
Good simple problem.
This is a simple problem. I do not remember what I did in my old code. But most probably I used the definition of nchoosek, which is quite costly in computation.
This time I used pascal's triangle, which is much more efficient than my previous code.With my notebook, it takes less than 1ms.
But when I tried the challenge with projectEuler+ at hackerrank, it did not work since the value K can be 1e18, which has overflow issue with 64bit integer. I finally use double to get it accepted!
Good simple problem.
Friday, March 22, 2013
project euler problem 052
permuted multiples
After I read the problem, I immediately give the answer. I knew this number pretty well. Otherwise, one needs to bruteforce it. Not a very interesting problem.
After I read the problem, I immediately give the answer. I knew this number pretty well. Otherwise, one needs to bruteforce it. Not a very interesting problem.
project euler problem 051
Prime digit replacements
I like this problem. I looked at my old code, it is ugly and difficult to understand. But after I got the correct answer, I left for the next problem without a better solution. This time, I read the discussion thread, then I found that I missed a very important fact about "8". Now I have a better understanding of this problem.
Good problem!
I like this problem. I looked at my old code, it is ugly and difficult to understand. But after I got the correct answer, I left for the next problem without a better solution. This time, I read the discussion thread, then I found that I missed a very important fact about "8". Now I have a better understanding of this problem.
Good problem!
project euler problem 050
Consecutive prime sum
This problem is simple. Some of the people even assumes that 2 is the first number, still get the correct answer.
This problem is simple. Some of the people even assumes that 2 is the first number, still get the correct answer.
Thursday, March 21, 2013
project euler problem 049
Prime permutations
This problem is simple, but my old code is ugly. But it only take 1.6ms. So I kindly forgave myself. Not too much can be learned from this problem.
Update(06/28/2017):
Actually, my old code was inefficient since I used the stl function next_permutation to generate all arithmetic progression sequence. I can combine all the prime numbers that are made from the same group of digits into a vector and check if any arithmetic progression sequence can be created from them, which is more efficient.
This problem is simple, but my old code is ugly. But it only take 1.6ms. So I kindly forgave myself. Not too much can be learned from this problem.
Update(06/28/2017):
Actually, my old code was inefficient since I used the stl function next_permutation to generate all arithmetic progression sequence. I can combine all the prime numbers that are made from the same group of digits into a vector and check if any arithmetic progression sequence can be created from them, which is more efficient.
project euler problem 048
Self powers
This is a homework problem. It took 4ms in my notebook to get the answer.
The algorithm I used is in CLRS, chapter 31(3rd ed). Everyone should have this classical book, "Introduction to algorithms". I have a copy of the third edition. The only thing I want to complain is that it is too heavy. But it helped me to solve quite a few PE problems. I like to read this book, but did not have time to work on the problems in the book.
This is a homework problem. It took 4ms in my notebook to get the answer.
The algorithm I used is in CLRS, chapter 31(3rd ed). Everyone should have this classical book, "Introduction to algorithms". I have a copy of the third edition. The only thing I want to complain is that it is too heavy. But it helped me to solve quite a few PE problems. I like to read this book, but did not have time to work on the problems in the book.
project euler problem 047
Distinct primes factors
I revisited this problem tonight, I found it was the first problem involving factors. In many PE problems, factor plays a significant role.
I am pretty sure that when I started working on PE problems, I had no idea that sieve method can help to find factor or number of distinct factors. I thought that sieve method was only used to create prime table.
I learned sieve method for factor when I tried to solve a problem numbered around 200 simply because my method was too slow.
Please review the discussion thread if your method is not elegant.
I revisited this problem tonight, I found it was the first problem involving factors. In many PE problems, factor plays a significant role.
I am pretty sure that when I started working on PE problems, I had no idea that sieve method can help to find factor or number of distinct factors. I thought that sieve method was only used to create prime table.
I learned sieve method for factor when I tried to solve a problem numbered around 200 simply because my method was too slow.
Please review the discussion thread if your method is not elegant.
project euler problem 046
Goldbach's other conjecture
This problem is rather simple, I read the discussion thread, but did not find too much useful information.
This problem is rather simple, I read the discussion thread, but did not find too much useful information.
project euler problem 045
Triangular, pentagonal, and hexagonal
This problem is very similar to problem 044. But from this problem, the results
begin to be very large numbers. Long long int are required by many problems.
Overflow is also sometimes become a headache.
Update: this problem is actually best solved by using Pell Equation, but it is not an easy job to solve a generalized pell equation.
This problem is very similar to problem 044. But from this problem, the results
begin to be very large numbers. Long long int are required by many problems.
Overflow is also sometimes become a headache.
Update: this problem is actually best solved by using Pell Equation, but it is not an easy job to solve a generalized pell equation.
project euler problem 044
Pentagon numbers
This problem is simple, but relatively more interesting than other problems. Several approaches pops up in the discussion thread. I lost my old code, but it looks like I used two different approaches.
This problem is simple, but relatively more interesting than other problems. Several approaches pops up in the discussion thread. I lost my old code, but it looks like I used two different approaches.
Wednesday, March 20, 2013
project euler problem 043
Sub-string divisibility
This problem is not bad. It takes me half an hour to figure out the bugs in my code. I used backtracking in my code, but made a couple a stupid mistakes. This problem is good!
I read the discussion thread, this problem may be solved by hand.
This problem is not bad. It takes me half an hour to figure out the bugs in my code. I used backtracking in my code, but made a couple a stupid mistakes. This problem is good!
I read the discussion thread, this problem may be solved by hand.
project euler problem 042
Coded triangle numbers
A simple and boring problem. I have no interest to visit this problem again. Maybe this is one of the top 3 most boring PE problems.
A simple and boring problem. I have no interest to visit this problem again. Maybe this is one of the top 3 most boring PE problems.
project euler problem 041
pandigital prime
This problem is simple and boring, one just need to figure out what is the maximum possible value for a pandigital prime and do not waste the cpu time on useless computation. It is easy to figure out after doing some test on small numbers.
This problem is simple and boring, one just need to figure out what is the maximum possible value for a pandigital prime and do not waste the cpu time on useless computation. It is easy to figure out after doing some test on small numbers.
Tuesday, March 19, 2013
project euler problem 040
Champernowne's constant
This number appeared at least 3 times in all 400 problems. This is the easiest one. Problem 305 is much more difficult than 40. I used binary search on this problem. Simple and fast. I remember that the first time I saw this problem, I solved it by hand. It is not difficult since the number of digits involved is so small.
Update: Binary search is still an overkill if we use a function to count the numbers of digits up to n. With some simple math, the problem can be further simplified. since the numbers with one digit is 9 and with two digits is 90, etc.
This number appeared at least 3 times in all 400 problems. This is the easiest one. Problem 305 is much more difficult than 40. I used binary search on this problem. Simple and fast. I remember that the first time I saw this problem, I solved it by hand. It is not difficult since the number of digits involved is so small.
Update: Binary search is still an overkill if we use a function to count the numbers of digits up to n. With some simple math, the problem can be further simplified. since the numbers with one digit is 9 and with two digits is 90, etc.
Monday, March 18, 2013
vim launch time profiling
Recently, I found that it need quite some time to launch vim. I googled a little bit and found that the following webpage is very useful.
http://usevim.com/2012/04/18/startuptime/
Basically, just two command,
http://usevim.com/2012/04/18/startuptime/
Basically, just two command,
$ vim --startuptime vim.log (optional: file_you_want_to_open)$ cat vim.log | sort -k 2
I found that c.vim cost quite some time. Since I am programming in c++,I still want to stay with it.
project euler problem 300
protein folding
I hesitate to work on this problem for a long time. The only reason is that I have no good algorithm for this problem. Finally, I used some kind of brute force method to solve it. It is solved in three and a half minutes. I am not that happy since it is bruteforcable. Probably that is why so many people solved it.
There is still a lot to be learned in the discussion thread.
I hesitate to work on this problem for a long time. The only reason is that I have no good algorithm for this problem. Finally, I used some kind of brute force method to solve it. It is solved in three and a half minutes. I am not that happy since it is bruteforcable. Probably that is why so many people solved it.
There is still a lot to be learned in the discussion thread.
Thursday, March 14, 2013
project euler problem 039
integer right triangle
I was ashamed to review my old code, it is ugly. I brute-forced this problem, and used some unnecessary structure!
Pythagorean triples is the key to solve this problem.
Update: 06/18/2017
I read the discussion of this problem again and find square1001 proposed an optimization to solve this problem, which is two times faster than my solution at 1e8, good to know!
I was ashamed to review my old code, it is ugly. I brute-forced this problem, and used some unnecessary structure!
Pythagorean triples is the key to solve this problem.
Update: 06/18/2017
I read the discussion of this problem again and find square1001 proposed an optimization to solve this problem, which is two times faster than my solution at 1e8, good to know!
project euler problem 038
pandigital multiple
I feels I cannot learn anything since this problem is simple. But I was wrong,
I read the discussion thread, I found that this problem can be solved with pencil and paper. I felt that I was so inclined to ask computer for help. The problem has given too much hint!
I feels I cannot learn anything since this problem is simple. But I was wrong,
I read the discussion thread, I found that this problem can be solved with pencil and paper. I felt that I was so inclined to ask computer for help. The problem has given too much hint!
project euler problem 037
Truncatable primes
I am a little bit upset I used emacs to figure out how to "continuously remove digits from left to right". Maybe I was watching TV while coding. It is an easy
problem, but I was wondering how to prove that there is only 11 such numbers.
Discussion thread!!!
Zef enlightened me why there are only 11 such numbers, and I learned another way of expressing decimal numbers. It is really interesting! Please read it if you have no idea what I am talking about.
To help others to focus on the discussion thread is one of my goals to write the blog.
I am a little bit upset I used emacs to figure out how to "continuously remove digits from left to right". Maybe I was watching TV while coding. It is an easy
problem, but I was wondering how to prove that there is only 11 such numbers.
Discussion thread!!!
Zef enlightened me why there are only 11 such numbers, and I learned another way of expressing decimal numbers. It is really interesting! Please read it if you have no idea what I am talking about.
To help others to focus on the discussion thread is one of my goals to write the blog.
Wednesday, March 13, 2013
日本推理小说观后感， 评价， 推荐
最近看了不少部日系推理小说， 感觉中国推理小说界真可谓一片空白。 这个可能也跟我们的国家体制有点关系， 很多东西没办法写， 如果全是歌颂型的， 真就是乏味至极了。可是写点日系类的推理小说, 可能又过不了审查一关, 哎....
确切的比较不同作者的作品的优劣， 其实没有意义， 毕竟年代不同， 历史背景也不同， 不同时代的人显然从经历， 价值观等方方面面都不一样,不具有可比性.在一些较早的作家的作品中,我们看不到dna,几乎血液鉴定,指纹都很少,现代作品则对此依赖更多一些.这可能是时代的发展的产物吧.
下面总结一下看过的小说， 剧透基本没有， 我会一段段的更新，看了上百部的作品，十几位作家, 复习都复习不过来。
东野圭吾，
这是我最喜欢的推理小说作家了， 他被搬上荧幕的作品举不胜举。 现在回想起来， 最开始看到的是神探伽利略这个电视剧， 但是看完后， 感觉很无聊， 因为毕竟自己也是学理科的， 利用物理学原理来破案， 实在没有什么说服力。 其后又看了东野圭吾电视剧短篇我2012夏季档，感觉好的故事几乎没有， 所以再次错过这位大牛， 直到最近看了实体小说后才真正的改变了我的看法， 真正征服我的是白夜行和X的献身以及绑架游戏等几部作品。 白夜行跌宕起伏， 我看了百分之二十后， 就再也停不下来， 绑架游戏惊险刺激， 视角新鲜， 而x嫌疑犯的献身构思真是太令人拜服了， 最令我遗憾的是主人公竟然又是伽利略， 美中不足, 伽利略高瞻远瞩, 可谓日本当代诸葛亮, 太过哗众取宠了; 如果没有破案, 或者换一个角度把这个案子破了, 可能会更好.
白夜行， 推荐度（10）， 请不要看电影， 就看书吧， 书比电影好太多了， 电影局限性在看完书后就都出来了， 我是一口气看完的， 实在停不下来， 剧情不难猜测， 但是即便如此， 我仍然想知道主人公的命运结局； 作者不停改换视角， 作品新颖而不令人审美疲劳；
嫌疑犯x的献身，推荐度（10）， 这个会看着有点古怪， 当看到结果时， 我不禁感叹， 原来如此！作者不知道从哪里搞来的四色定理， 黎曼猜想， 懂得还真不少, 尤其黎曼那一段, 还说质数分布有问题, 真是下了一点点功夫；
绑架游戏（9）， 个人比较喜欢这部作品， 很紧张， 很刺激， 结果写的也很好； 具体就不多讲了；推荐大家看;
使命与心的极限， 推荐度（9）， 讲医生的故事， 故事扣人心弦程度不如上面提到的几部，推理性也不是很强, 但是也是一部赚人眼泪的大作；
流星之绊， （8.5） 这个既有推理， 也有独到之处， 个人还是比较欣赏这部作品， 推荐；
家信（8），这部作品是探讨亲情和人性的，推理成分也很少， 个人感觉比其他同类型的作品要成功， 但是我不是很喜欢其过程及结果，太残酷了，这就是杀人不见血的刀吧；
秘密 (8), 这部其实不是推理啦, 一点点都没有, 但是东野叙事的能力太强了, 叹服. 另外一点就是大家看了之后,可能都会有不同的角度来看待结果, 我不太喜欢结局, 具体原因大家看了就知道了;
放学后（8）， 东野的出山之作吧， 名气很大， 推理也够， 但是我还是感觉东野后期作品更值得一读，但是这篇也很值得一读， 做个比较；
恶意 （8）， 有人非常喜欢这部作品， 我觉得相对而言， 不是特别出色的一部作品， 我还是觉得有点牵强， 是我太善良还是这个社会恶人太多？ 哈哈...
预知梦（8）， 这部是伽利略中的一部， 我个人不喜欢汤川学，但是我觉得这部还算不错了，其中的科学部分还有一些可信的成分；
平行世界的爱情故事（7.5）， 我喜欢故事的开端， 但是结果却难以满意， 东野突出了自己理科出身的特色， 但是推理性具有东野风格， 但是不令人十分满意；
圣女的救济（7.5）， 个人不是很喜欢汤川学， 而且这部小说中的作案手法实在过分， 个人感觉这是一部剑走偏锋的作品；
湖边凶杀案，（7.5）， 东野时不时会来一部反映社会问题的作品， 结果都是让人看了觉得很沉重， 很压抑，我不知道这样的作品适合什么时候阅读， 作品当然很不错啦！
红手指， 推荐度（7.5）， 这篇有点沉重了， 看完会觉得有点累， 代沟， 老人 等一系列社会问题才是作者想要探索的吧；
毕业前杀人游戏， （7.5）， 这个有点过了， 高中里也要杀人， 小日本民族发展的有些太过了；东野作品里还是比较喜欢反映学校生活的；
宿命（7）， 这一部是探讨医学方面的作品， 推理性不是太强， 结论不是很令人信服；但是还可以看一下；
雪地杀机， （7）， 东野名作太多， 这个就显得比较一般， 我不是很喜欢这样的作品， 把大家都当傻子玩；
十一文字杀人（6.5）， 我也不是很喜欢这部， 情节曲折但是没意思；
疯狂的电击（6.5）， 短篇算是不错了， 但是对作案手法有些疑问， 所以感觉一般；
伊豆旅馆的神秘案(6.5)， 短篇能够体现东野功力的确实不多， 这个也一般， 略有展开， 但是案情还是牵强；
单恋(6) , 这个个人感觉也是属于东野较为一般的作品，反映了一定的社会现实，但是推理趣味性不浓，而且对于性别的认识问题有点过了，也有偏激成分， 属于可以略过的长篇；
玫瑰与匕首(6)， 我看了一下我的推荐度评分， 感觉我对东野要求是很高的， 比如这篇， 在短篇推理小说中也算过得去了， 但是我还是觉得东野不能在小说中体现他对人性的探索， 就不能称之为一部成功的东野作品， 所以我还是给了个低分；
再生魔术之女， （5）， 我比较不喜欢的作品， 没意思， 不过被改编为电视剧了；
少女委托人, (5), 这个也是属于消遣类的作品， 随便看看就可以了， 现实中， 人不可能那么脆弱；
回亭廊杀人事件(4), 这个属于不怎么样的作品，极为不现实， 而且结局更加是胡扯， 完全略过也不可惜；
变身， 分身（4），我不是很喜欢这两部作品， 内容都是关于医学对人类影响的， 但是其中推理成分很少， 更多的是这种影响会带来什么样的后果；
疯狂的电击（4）， 我不同意东野的观点， 不是什么人都可以和你共同作案的， 很牵强；
横沟正史
如果说现代作家中我最喜爱的作家是东野圭吾的话， 那么除了东野， 我最喜爱的作家就是横沟正史了，个人感觉横沟是非常厉害的。
大多数读者和我一样是有不小代沟的， 横沟出生于1902年， 1981年去世。即便如此， 其作品还让人读来兴趣盎然， 实属不易。 横沟作品中很少依靠DNA， 指纹之类来推断凶手的， 电话 手机都很少，和我们现在这个社会感觉格格不入， 但是我却不觉得有过时的感觉， 可见横沟功力之一斑。
横沟作品分为两类， 一类是金田一作为主角， 大多数都是精品， 都值得一读， 另外一类是侦探小子一类的作品，不推荐， 恶人都功力强劲， 有魔的特点， 不具有人的特点， 和现代推理小说有一定距离；
八墓村（9）， 横沟小说里面很少提及爱情， 这部是比较少见的， 而且横沟的特点是在读了很大一部分后仍然很难推断出凶手， 这部是非常出色的一部作品；
夏树静子，
女性推理作家， 不多见，描写女性的推理小说较多。
蒸发， 推荐度（9）， 个人比较喜欢这一篇小说， 其中的原因是因为推理小说写出了爱情的味道， 很特别， 感觉很少见； 查了一下， 这篇获得了第二十六届日本推理作家协会赏；
跑道灯，推荐度（8） 不知道为什么叫这个名字， 起码现在不记得了， 但是又扫了一遍， 短篇里面算不错了；
W的悲剧 推荐度（7） 这个拍成了电视剧，公认是夏树的代表作之一， 我倒不是特别感冒， 但是要知道小说是82年的；
变性者的隐私， 推荐度（7）， 这里有点感情分在里面， 这个小说被tvb改编到了刑事侦缉档案里， 好像是陶大宇 郭可盈演的， 哪一部记不清楚了， 感觉还算不错了；
来自死亡谷的女人，推荐度（7）属于奇特经历型的推理小说，感觉还行， 算不上佳作；
处心积虑的意外事件， 推荐度（6）， 短篇里感觉还算好的；
云间赐来死亡， 推荐度（5）， 一般， 没有什么特色， 可能我自己看多了吧， 有些麻木， 感觉也就是几起凶杀案；
同班同学， 推荐度（5）， 短篇， 睡前读物， 可以说没有感觉；
伊吹山庄凶案， 推荐度（5）， 短篇， 展开不够， 适合睡前看一下， 看完就睡；
稚子证言， 推荐度（4）， 短篇，没有感觉；
试刀伤的背后， 推荐度（4）， 不怎么喜欢， 感觉一般， 还是个短篇；
托运来的女尸，推荐度（3）， 不喜欢， 属于奇思异想型的小说；
赤川次郎，
做个大概评价吧， 我不怎么喜欢他的作品， 他的华丽侦探系列， 我看了要发疯， 基本上是见到一篇删除一篇， 他的三色猫我也不怎么感冒， 什么什么嘛， 但是零零散散还有几篇可以看。他的特点就是作品多，但是精品不多；
偶像明星杀人事件， 推荐度（7）， 有种似曾相识的感觉，但是又想不起来是什么和它相似，是tvb么， 记不得了， 主人公和配角都还是蛮可爱的；
东西南北杀人事件 推荐度（6） 属于大贯警部系列中的一部， 这个基本上就是糊涂侦探， 很搞笑， 就推荐这个看看吧， 如果喜欢可以去百度百科搜索其他相关的作品来看， 链接就在本段的标题。
罗列莱口哨杀人曲，推荐度（6），感觉有些虎头蛇尾， 结局不明不白，说服力较差, 但是还是推荐看一下， 如果实在没什么可看的话；
昂贵的失恋，推荐度（6）， 感觉还是虎头蛇尾， 真实感不强， 有点勉强的感觉；
确切的比较不同作者的作品的优劣， 其实没有意义， 毕竟年代不同， 历史背景也不同， 不同时代的人显然从经历， 价值观等方方面面都不一样,不具有可比性.在一些较早的作家的作品中,我们看不到dna,几乎血液鉴定,指纹都很少,现代作品则对此依赖更多一些.这可能是时代的发展的产物吧.
下面总结一下看过的小说， 剧透基本没有， 我会一段段的更新，看了上百部的作品，十几位作家, 复习都复习不过来。
东野圭吾，
这是我最喜欢的推理小说作家了， 他被搬上荧幕的作品举不胜举。 现在回想起来， 最开始看到的是神探伽利略这个电视剧， 但是看完后， 感觉很无聊， 因为毕竟自己也是学理科的， 利用物理学原理来破案， 实在没有什么说服力。 其后又看了东野圭吾电视剧短篇我2012夏季档，感觉好的故事几乎没有， 所以再次错过这位大牛， 直到最近看了实体小说后才真正的改变了我的看法， 真正征服我的是白夜行和X的献身以及绑架游戏等几部作品。 白夜行跌宕起伏， 我看了百分之二十后， 就再也停不下来， 绑架游戏惊险刺激， 视角新鲜， 而x嫌疑犯的献身构思真是太令人拜服了， 最令我遗憾的是主人公竟然又是伽利略， 美中不足, 伽利略高瞻远瞩, 可谓日本当代诸葛亮, 太过哗众取宠了; 如果没有破案, 或者换一个角度把这个案子破了, 可能会更好.
白夜行， 推荐度（10）， 请不要看电影， 就看书吧， 书比电影好太多了， 电影局限性在看完书后就都出来了， 我是一口气看完的， 实在停不下来， 剧情不难猜测， 但是即便如此， 我仍然想知道主人公的命运结局； 作者不停改换视角， 作品新颖而不令人审美疲劳；
嫌疑犯x的献身，推荐度（10）， 这个会看着有点古怪， 当看到结果时， 我不禁感叹， 原来如此！作者不知道从哪里搞来的四色定理， 黎曼猜想， 懂得还真不少, 尤其黎曼那一段, 还说质数分布有问题, 真是下了一点点功夫；
绑架游戏（9）， 个人比较喜欢这部作品， 很紧张， 很刺激， 结果写的也很好； 具体就不多讲了；推荐大家看;
使命与心的极限， 推荐度（9）， 讲医生的故事， 故事扣人心弦程度不如上面提到的几部，推理性也不是很强, 但是也是一部赚人眼泪的大作；
流星之绊， （8.5） 这个既有推理， 也有独到之处， 个人还是比较欣赏这部作品， 推荐；
家信（8），这部作品是探讨亲情和人性的，推理成分也很少， 个人感觉比其他同类型的作品要成功， 但是我不是很喜欢其过程及结果，太残酷了，这就是杀人不见血的刀吧；
秘密 (8), 这部其实不是推理啦, 一点点都没有, 但是东野叙事的能力太强了, 叹服. 另外一点就是大家看了之后,可能都会有不同的角度来看待结果, 我不太喜欢结局, 具体原因大家看了就知道了;
放学后（8）， 东野的出山之作吧， 名气很大， 推理也够， 但是我还是感觉东野后期作品更值得一读，但是这篇也很值得一读， 做个比较；
恶意 （8）， 有人非常喜欢这部作品， 我觉得相对而言， 不是特别出色的一部作品， 我还是觉得有点牵强， 是我太善良还是这个社会恶人太多？ 哈哈...
预知梦（8）， 这部是伽利略中的一部， 我个人不喜欢汤川学，但是我觉得这部还算不错了，其中的科学部分还有一些可信的成分；
平行世界的爱情故事（7.5）， 我喜欢故事的开端， 但是结果却难以满意， 东野突出了自己理科出身的特色， 但是推理性具有东野风格， 但是不令人十分满意；
圣女的救济（7.5）， 个人不是很喜欢汤川学， 而且这部小说中的作案手法实在过分， 个人感觉这是一部剑走偏锋的作品；
湖边凶杀案，（7.5）， 东野时不时会来一部反映社会问题的作品， 结果都是让人看了觉得很沉重， 很压抑，我不知道这样的作品适合什么时候阅读， 作品当然很不错啦！
红手指， 推荐度（7.5）， 这篇有点沉重了， 看完会觉得有点累， 代沟， 老人 等一系列社会问题才是作者想要探索的吧；
毕业前杀人游戏， （7.5）， 这个有点过了， 高中里也要杀人， 小日本民族发展的有些太过了；东野作品里还是比较喜欢反映学校生活的；
宿命（7）， 这一部是探讨医学方面的作品， 推理性不是太强， 结论不是很令人信服；但是还可以看一下；
雪地杀机， （7）， 东野名作太多， 这个就显得比较一般， 我不是很喜欢这样的作品， 把大家都当傻子玩；
十一文字杀人（6.5）， 我也不是很喜欢这部， 情节曲折但是没意思；
疯狂的电击（6.5）， 短篇算是不错了， 但是对作案手法有些疑问， 所以感觉一般；
伊豆旅馆的神秘案(6.5)， 短篇能够体现东野功力的确实不多， 这个也一般， 略有展开， 但是案情还是牵强；
单恋(6) , 这个个人感觉也是属于东野较为一般的作品，反映了一定的社会现实，但是推理趣味性不浓，而且对于性别的认识问题有点过了，也有偏激成分， 属于可以略过的长篇；
玫瑰与匕首(6)， 我看了一下我的推荐度评分， 感觉我对东野要求是很高的， 比如这篇， 在短篇推理小说中也算过得去了， 但是我还是觉得东野不能在小说中体现他对人性的探索， 就不能称之为一部成功的东野作品， 所以我还是给了个低分；
再生魔术之女， （5）， 我比较不喜欢的作品， 没意思， 不过被改编为电视剧了；
少女委托人, (5), 这个也是属于消遣类的作品， 随便看看就可以了， 现实中， 人不可能那么脆弱；
回亭廊杀人事件(4), 这个属于不怎么样的作品，极为不现实， 而且结局更加是胡扯， 完全略过也不可惜；
变身， 分身（4），我不是很喜欢这两部作品， 内容都是关于医学对人类影响的， 但是其中推理成分很少， 更多的是这种影响会带来什么样的后果；
疯狂的电击（4）， 我不同意东野的观点， 不是什么人都可以和你共同作案的， 很牵强；
横沟正史
如果说现代作家中我最喜爱的作家是东野圭吾的话， 那么除了东野， 我最喜爱的作家就是横沟正史了，个人感觉横沟是非常厉害的。
大多数读者和我一样是有不小代沟的， 横沟出生于1902年， 1981年去世。即便如此， 其作品还让人读来兴趣盎然， 实属不易。 横沟作品中很少依靠DNA， 指纹之类来推断凶手的， 电话 手机都很少，和我们现在这个社会感觉格格不入， 但是我却不觉得有过时的感觉， 可见横沟功力之一斑。
横沟作品分为两类， 一类是金田一作为主角， 大多数都是精品， 都值得一读， 另外一类是侦探小子一类的作品，不推荐， 恶人都功力强劲， 有魔的特点， 不具有人的特点， 和现代推理小说有一定距离；
八墓村（9）， 横沟小说里面很少提及爱情， 这部是比较少见的， 而且横沟的特点是在读了很大一部分后仍然很难推断出凶手， 这部是非常出色的一部作品；
夏树静子，
女性推理作家， 不多见，描写女性的推理小说较多。
蒸发， 推荐度（9）， 个人比较喜欢这一篇小说， 其中的原因是因为推理小说写出了爱情的味道， 很特别， 感觉很少见； 查了一下， 这篇获得了第二十六届日本推理作家协会赏；
跑道灯，推荐度（8） 不知道为什么叫这个名字， 起码现在不记得了， 但是又扫了一遍， 短篇里面算不错了；
W的悲剧 推荐度（7） 这个拍成了电视剧，公认是夏树的代表作之一， 我倒不是特别感冒， 但是要知道小说是82年的；
变性者的隐私， 推荐度（7）， 这里有点感情分在里面， 这个小说被tvb改编到了刑事侦缉档案里， 好像是陶大宇 郭可盈演的， 哪一部记不清楚了， 感觉还算不错了；
来自死亡谷的女人，推荐度（7）属于奇特经历型的推理小说，感觉还行， 算不上佳作；
处心积虑的意外事件， 推荐度（6）， 短篇里感觉还算好的；
云间赐来死亡， 推荐度（5）， 一般， 没有什么特色， 可能我自己看多了吧， 有些麻木， 感觉也就是几起凶杀案；
同班同学， 推荐度（5）， 短篇， 睡前读物， 可以说没有感觉；
伊吹山庄凶案， 推荐度（5）， 短篇， 展开不够， 适合睡前看一下， 看完就睡；
稚子证言， 推荐度（4）， 短篇，没有感觉；
试刀伤的背后， 推荐度（4）， 不怎么喜欢， 感觉一般， 还是个短篇；
托运来的女尸，推荐度（3）， 不喜欢， 属于奇思异想型的小说；
赤川次郎，
做个大概评价吧， 我不怎么喜欢他的作品， 他的华丽侦探系列， 我看了要发疯， 基本上是见到一篇删除一篇， 他的三色猫我也不怎么感冒， 什么什么嘛， 但是零零散散还有几篇可以看。他的特点就是作品多，但是精品不多；
偶像明星杀人事件， 推荐度（7）， 有种似曾相识的感觉，但是又想不起来是什么和它相似，是tvb么， 记不得了， 主人公和配角都还是蛮可爱的；
东西南北杀人事件 推荐度（6） 属于大贯警部系列中的一部， 这个基本上就是糊涂侦探， 很搞笑， 就推荐这个看看吧， 如果喜欢可以去百度百科搜索其他相关的作品来看， 链接就在本段的标题。
罗列莱口哨杀人曲，推荐度（6），感觉有些虎头蛇尾， 结局不明不白，说服力较差, 但是还是推荐看一下， 如果实在没什么可看的话；
昂贵的失恋，推荐度（6）， 感觉还是虎头蛇尾， 真实感不强， 有点勉强的感觉；
Tuesday, March 12, 2013
project euler problem 036
Double-base palindromes
I do not have my original code, but I kept my isPalindromic() function. When I
review this problem again, I found that my original method is too cumbersome.
I used vector to store all digits and then reverse the vector, finally compare all
digits. This time I found a better method without the help of vector. It looks much better. This method also appeared in the discussion thread.
I also realized that not all numbers need to be checked, only a small portion of
the numbers need to be checked. It takes 4ms to find the answer.
Update:
I rewrote the code again to create all decimal palindromic number in a different way which is a little bit easier to read than the old code, which handles odd number of digits and even number of digits a little bit differently.
I do not have my original code, but I kept my isPalindromic() function. When I
review this problem again, I found that my original method is too cumbersome.
I used vector to store all digits and then reverse the vector, finally compare all
digits. This time I found a better method without the help of vector. It looks much better. This method also appeared in the discussion thread.
I also realized that not all numbers need to be checked, only a small portion of
the numbers need to be checked. It takes 4ms to find the answer.
Update:
I rewrote the code again to create all decimal palindromic number in a different way which is a little bit easier to read than the old code, which handles odd number of digits and even number of digits a little bit differently.
Monday, March 11, 2013
project euler problem 035
circular primes
This is a simple problem, it takes 0.014 second to find the answer. Not too bad.
My first version was lost. I did not remember how I solved it. I am happy that I did not split the number into digits in my second version. I see the same strategy on page 2 in the discussion thread.
This is a simple problem, it takes 0.014 second to find the answer. Not too bad.
My first version was lost. I did not remember how I solved it. I am happy that I did not split the number into digits in my second version. I see the same strategy on page 2 in the discussion thread.
Saturday, March 9, 2013
project euler problem 353
risky moon
This problem is not so hard to solve. We need to find all the stations and then find the shortest path. Both are well defined problems and have been visited in previous problems. But I cannot find an efficient method on the second part. It took 50s to pop up the answer. I took a look at the discussion thread, it is normal.
But one guy provided a method to solve it in less than 0.5 second. I need to learn from his code!
By the way, I feel problem 352 is more difficult than problem 353. Let us take a look at
how many people solved these two problems.
Problem 352, solved by 320
Problem 353 solved by 264
But I still need to work hard on problem 352! No clue for 352!
This problem is not so hard to solve. We need to find all the stations and then find the shortest path. Both are well defined problems and have been visited in previous problems. But I cannot find an efficient method on the second part. It took 50s to pop up the answer. I took a look at the discussion thread, it is normal.
But one guy provided a method to solve it in less than 0.5 second. I need to learn from his code!
By the way, I feel problem 352 is more difficult than problem 353. Let us take a look at
how many people solved these two problems.
Problem 352, solved by 320
Problem 353 solved by 264
But I still need to work hard on problem 352! No clue for 352!
project euler problem 034
Digit factorials
A little bit thought about the upper bound is required. Then the problem can be
solved in 0.1s. Although this problem is easy, later on, the PE problems about factorial are not so easy to solve.
A little bit thought about the upper bound is required. Then the problem can be
solved in 0.1s. Although this problem is easy, later on, the PE problems about factorial are not so easy to solve.
project euler problem 033
Digit canceling fractions
There is not much to say about this problem. Too simple, you can do it in ways you like since there are very few numbers to be checked.
There is not much to say about this problem. Too simple, you can do it in ways you like since there are very few numbers to be checked.
project euler problem 032
Pandigital products
A very simple problem. I checked my old code, I was using next_permutation to solve this problem, which is really a waste of time. I rewrote the code, it
took only 0.03s in debug version. My previous version took 0.1s.
A very simple problem. I checked my old code, I was using next_permutation to solve this problem, which is really a waste of time. I rewrote the code, it
took only 0.03s in debug version. My previous version took 0.1s.
Friday, March 8, 2013
project euler problem 031
Coin sums
I like this problem. Although it is simple, I still learned a lot from this problem.
There are several ways to solve this problem: Generating function; dynamic programming, recursion. Recursion is the most natural way to solve this problem.
Update (06/17/2017):
The problem may look simple, actually the dynamic programming way is the only simple choice for large N. The recursive way only works for small N. For large N, it is extremely slow. The code in the overview of this problem worth the time to read, especially the one by wizeman.
I like this problem. Although it is simple, I still learned a lot from this problem.
There are several ways to solve this problem: Generating function; dynamic programming, recursion. Recursion is the most natural way to solve this problem.
Update (06/17/2017):
The problem may look simple, actually the dynamic programming way is the only simple choice for large N. The recursive way only works for small N. For large N, it is extremely slow. The code in the overview of this problem worth the time to read, especially the one by wizeman.
project euler problem 030
Digit fifth powers
Another simple problem. One may need a moment's thought to give a reasonable upper bound for this problem.
Although the problem can be bruteforced out easily, from a programmer's point of view, an efficient algorithm is preferred. An efficient approach exists for this problem, the numbers checked in the efficient approach is very limited. For example, check only less than 4000 numbers for power = 5 and less than 10000 numbers for power = 6.
The trick is that we can always try large digit first.
Another simple problem. One may need a moment's thought to give a reasonable upper bound for this problem.
Although the problem can be bruteforced out easily, from a programmer's point of view, an efficient algorithm is preferred. An efficient approach exists for this problem, the numbers checked in the efficient approach is very limited. For example, check only less than 4000 numbers for power = 5 and less than 10000 numbers for power = 6.
The trick is that we can always try large digit first.
project euler problem 029, very interesting problem!
Distinct powers
This is a boring problem. It is not a hard problem. One may even solve it by hand.
Update.
I am wrong on this problem, and when I was reviewing this problem several years ago, I am still not very careful about learning from others. This was changed only a few days ago when I was considering the number 100 to be changed to 100000 or larger.
I found my method ate a lot of memory and slow. Then I read the discussion thread again. Wow, the idea by jorgbrown and WP really helps a lot for me to understand the sieve method better! Please try to change the number 100 to 1000000 and see you code can give you the answer in one second or not.
The discussion really changed my view on sieve method, interesting!
This is a boring problem. It is not a hard problem. One may even solve it by hand.
Update.
I am wrong on this problem, and when I was reviewing this problem several years ago, I am still not very careful about learning from others. This was changed only a few days ago when I was considering the number 100 to be changed to 100000 or larger.
I found my method ate a lot of memory and slow. Then I read the discussion thread again. Wow, the idea by jorgbrown and WP really helps a lot for me to understand the sieve method better! Please try to change the number 100 to 1000000 and see you code can give you the answer in one second or not.
The discussion really changed my view on sieve method, interesting!
project euler problem 028
Number spiral diagonals
The 5x5 graph reveals some important fact. Actually this is a O(1) mathematical problem. No more to say about this problem.
The 5x5 graph reveals some important fact. Actually this is a O(1) mathematical problem. No more to say about this problem.
project euler problem 027
Quadratic primes
A simple problem. The only thing I noticed is the formula given by Euler in 1722. With the help of computers, we can do much better than this great mathematician!
But when I read the discussion thread, I was ashamed by such kind of feeling. Euler's formula gave 40 distinct primes. The formula we found gave 71 primes, but only 40 of them are distinct! Our formula is worse in this respect!
The post by hk is also very interesting! He solved the problem without computer! Really amazing!
A simple problem. The only thing I noticed is the formula given by Euler in 1722. With the help of computers, we can do much better than this great mathematician!
But when I read the discussion thread, I was ashamed by such kind of feeling. Euler's formula gave 40 distinct primes. The formula we found gave 71 primes, but only 40 of them are distinct! Our formula is worse in this respect!
The post by hk is also very interesting! He solved the problem without computer! Really amazing!
Wednesday, March 6, 2013
project euler problem 026
reciprocal cycles
An easy problem. Just need to figure out a way to find that the period of recurring cycle. It is really simple. Well, similar idea appears in more difficult
problems such as continued fraction, which is a little bit more difficult to solve.
There is still something that I learned in the discussion thread.
An easy problem. Just need to figure out a way to find that the period of recurring cycle. It is really simple. Well, similar idea appears in more difficult
problems such as continued fraction, which is a little bit more difficult to solve.
There is still something that I learned in the discussion thread.
project euler problem 298
Selective Amnesia
This is not an easy problem. I gave up on this problem for a couple of times. Finally, I made all my effort to simplify this problem, it is solved!
The first part is to transform the pairs of numbers into states, which is quite complicated. I spent half a day or even longer on this part. After this part is done, the task left is just to solve a very easy probability problem. Quite a few problems in Project Euler require such sort of abstraction. For example, problem 324, building a tower.
It takes my code 0.17s to find the answer. It looks like there is still some potential to speed up.
After this problem is solved. I entered level 14. Still another 25 problems left to enter level 15.
This is not an easy problem. I gave up on this problem for a couple of times. Finally, I made all my effort to simplify this problem, it is solved!
The first part is to transform the pairs of numbers into states, which is quite complicated. I spent half a day or even longer on this part. After this part is done, the task left is just to solve a very easy probability problem. Quite a few problems in Project Euler require such sort of abstraction. For example, problem 324, building a tower.
It takes my code 0.17s to find the answer. It looks like there is still some potential to speed up.
After this problem is solved. I entered level 14. Still another 25 problems left to enter level 15.
Subscribe to:
Posts (Atom)