Author Topic: Project Euler  (Read 141808 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: Project Euler
« Reply #30 on: 二月 07, 2008, 10:48:34 am »
Quote
Would you just please check it for me.

Why 1064 isn't correct?

It is very hard to check other people's code, one has to get into the same kind of thinking first. I haven't looked at your code carefully. One thing I noticed is that you are going top down, which may be a mistake. A max path at the top level may end up to be not the max for the whole. e.g. if the bottom right corner has a huge number (bigger than the sum of everything else), if you work from top to bottom, any time you take a left, you will never reach that number. You should work bottom up, and it is very straight forward this way.

BTW, 1064 is not anywhere near the maximum. The answer is almost 7 times your answer.
« Last Edit: 二月 07, 2008, 10:50:54 am by 万精油 »

shortstop

  • Newbie
  • *
  • Posts: 4
    • Email
Re: Project Euler
« Reply #31 on: 二月 07, 2008, 11:06:30 am »
Quote
Would you just please check it for me.

Why 1064 isn't correct?

It is very hard to check other people's code, one has to get into the same kind of thinking first. I haven't looked at your code carefully. One thing I noticed is that you are going top down, which may be a mistake. A max path at the top level may end up to be not the max for the whole. e.g. if the bottom right corner has a huge number (bigger than the sum of everything else), if you work from top to bottom, any time you take a left, you will never reach that number. You should work bottom up, and it is very straight forward this way.

BTW, 1064 is not anywhere near the maximum. The answer is almost 7 times your answer.

I got you. You are the best!
Thanks a lot!

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: Project Euler
« Reply #32 on: 二月 11, 2008, 08:46:12 am »
Got another 10 problems this weekend, now I have solved 94. One problem a day this week, I will break 100 by the end of this week.

I like this project more and more. As Siyue pointed out to me, once you solve a problem, the discussion board of that problem opens to you and you can see other people's idea and code. Very interesting. I don't have much time to read them, but for the problems that I spent quite some time, I would read other people's solution and find out the differece between their code and my code.

One bad thing (or interesting thing, depends on your point of view) that I just found out yesterday is that there is a programming language website posted all the solutions for problem from 1 to 40 (their reason is to prove that their language is powerful). Many people are mad about this, because they have spent a lot of time for problem 1 to 40 and now it is freely available to everyone.
« Last Edit: 二月 11, 2008, 01:47:20 pm by 万精油 »

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
100 Problems, I am taking a break
« Reply #33 on: 二月 13, 2008, 03:08:18 pm »
It's been almost a month since I found out this Euler Project (Jan. 14). I have now solved 100 problems in there. It's been interesting but I need a break (at least for a week). I will still participate discussion if other people are interested. There are 6 problems under 100 that I haven't solved yet, they will be the target when I come back. :)
 

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: Project Euler
« Reply #34 on: 二月 15, 2008, 12:14:52 pm »
I said I was going to take a break, but back in my mind I am still thinking about the unsolved problems. One of them is problem 83. My original approach (simple code, brute force, because I was lazy) took more than one day to converge and the answer was wrong. I had a new idea last night before falling sleep, and tried it out this morning, it took 22 minutes, and the answer is correct. I was quite happy until I saw other people's approach (once you solve a problem, the discussion for that problem is open to you). Some other people have some code (which I don't understand since it is in different language) that get the answer in 0.6 second. When I have time, I really need to investigate that code. :) Furthermore, one guy solved the problem in 12 minutes (i.e. 12 minutes after the problem was posted) using Excel !!!. Amazing, and the approach is very easy and smart, but you need to know some features of Excel (obviously I didn't). I have learnt something from this problem.

Now, I have 102 problems under my belt.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: Project Euler
« Reply #35 on: 二月 15, 2008, 03:18:54 pm »
I took some time to look through posts of the problem 83, and saw many of them use something called Dijkstra Algorithm. I have never heard of Dijkstra Algorithm, so I went to Wikipedia and checked it out. To my surprise (and delight) that the so called Dijkstra Algorithm is almost exactly equivalent to the idea I have for this problem. May be it should change its name (if oly we had a time machine :) ).


万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: Project Euler
« Reply #36 on: 二月 15, 2008, 05:45:01 pm »
The more I read this problem, the more I learn. One of the method mentioned there is rediculously simple.  I implemented it in MATLAB with about 15 lines (mostly protocals, essentially just one line), and get the result in 0.1 second.


Dr Kevin Wang

  • Full Member
  • ***
  • Posts: 129
    • Math Zoom - Transform Gifited Youth into Successful Leaders
    • Email
Re: Project Euler
« Reply #37 on: 二月 16, 2008, 09:19:56 pm »
I took some time to look through posts of the problem 83, and saw many of them use something called Dijkstra Algorithm. I have never heard of Dijkstra Algorithm, so I went to Wikipedia and checked it out. To my surprise (and delight) that the so called Dijkstra Algorithm is almost exactly equivalent to the idea I have for this problem. May be it should change its name (if oly we had a time machine :) ).

Indenpendently discover the Dijkstra Algorithm ... that removes any doubt that you are a genius  :-D

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: Project Euler
« Reply #38 on: 二月 18, 2008, 02:18:25 am »
Quote
Indenpendently discover the Dijkstra Algorithm ... that removes any doubt that you are a genius 


The dijkstra Algorithm is suitable for general graph, mine is for this problem only. But it has the similar idea. After reading the official Dijkstra algorithm, I changed one way of updating my array and significantly reduced the computing time.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Anyone knows J?
« Reply #39 on: 二月 18, 2008, 12:13:57 pm »
For problem 101, I have a very neat short MATLAB code, and I was very happy with my code. Here's my MATLAB code (c is the answer).

Code: [Select]
c = 1;
for i = 2:10, c = c + round(((((1:i).^11+1)./(2:i+1))/exp((0:(i-1))'*log(1:i)))*((i+1).^(0:i-1))'); end

I thought it can't be simpler than this until I saw someone's code in J language (as I mentioned before, once you solve a problem, the discussion board for that problem opens to you). I don't know J, but I am certainly impressed by this. It is much shorter than my MATLAB code (which I thought can't be shorter). If anyone knows J and can explain in detail about what does what, I will really appreciate it. Here's the J code.

Code: [Select]
ps=: %.@(^/ <:)@:>:@i.@# +/ .*
+/(p. >:@#)@ps\(11$1 _1)p.1+i.10x
« Last Edit: 二月 18, 2008, 12:52:28 pm by 万精油 »

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: Project Euler
« Reply #40 on: 二月 20, 2008, 12:54:28 am »
Wikipedia is really wonderful. It has almost everything. I found a link in there about the J_programming language. Very interesting.

J_Programming Language

I can't help myself, can't really take a break, still solve a problem or two each day. Now, I have 110 problems solved and got into the 3rd page (i.e. below 300). I think it will take me at least another month to get to the 2nd page. I still have one problem under 100 that I haven't solved. :(

I also noticed that id94 is moving up in the rank amazingly fast. With that speed, you will over pass me in notime. After all, two people (assuming FZY is helping you) is stronger than one. :(
« Last Edit: 二月 20, 2008, 10:54:54 am by 万精油 »

jeff_gao

  • Jr. Member
  • **
  • Posts: 35
Re: Project Euler
« Reply #41 on: 二月 20, 2008, 11:10:26 am »
I have been quite busy recently: recovering from Miami ING marathon; 11 month baby got cold, then his mom, and then myself (interestingly, I am always the last one to get cold if at all - which may due to that fact I am stronger :-) ).

In any case, I got 93 solved so far. I don't have time to read the forum yet, but I think I get the fastest factorization algorithm in the world:-) It help me solved both the Euler phi problems in less than 1 second, and continues to help me solve factorization-related problem. My method does require 2 integers of storage per integer although (which is not an issue for the scale of these problems).

I agree with Prof Wan, the project is interesting enough that I can do it as a way to kill spare time and relax :-)
Jeff G

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: Project Euler
« Reply #42 on: 二月 20, 2008, 12:56:51 pm »
We have 77 now, on the 6th page I think. I solved about 2/3 of them. Tomorrow I will go on a 3 week trip to China. As of now I am not sure whether I have more or less spare time, most likely less.  :-(

So far no problem used more than one minute of computer time. If my program runs more than a few minutes, I would just kill it and start over. I do this for one reason: I almost never get the right number in the first try, usually in the fourth or fifth. So I cannot afford long programs.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: Project Euler
« Reply #43 on: 二月 20, 2008, 02:39:30 pm »
Quote
I have been quite busy recently: recovering from Miami ING marathon; 11 month baby got cold, then his mom, and then myself (interestingly, I am always the last one to get cold if at all - which may due to that fact I am stronger  ).

Another marathon runner. Great.

I don't remember the last time that I had a cold. All my sickness is due to sports injuries.

Quote
In any case, I got 93 solved so far.


7 more to get to 100. There are not too many 5-star red flags above 100. We need you up there.

Quote
I don't have time to read the forum yet, but I think I get the fastest factorization algorithm in the world:-)

I doubt it. Factorization has been investigated by so many people, the fastest algorithm for factoring, if there is such a thing, must be discovered by many people already. On the other hand, the problems in this Project all involve small numbers (they are big numbers, but for factoring algorithm, they are small, since most of the advanced factor algorithms deal with numbers with hundreds of digits), factoring small numbers should not take long, even MATLAB can factor a 10 digit number in less than 1 milli-second.

 
Quote
It help me solved both the Euler phi problems in less than 1 second, and continues to help me solve factorization-related problem.


It means you have a good way of computing Phi. Under 1 second is really impressive. Are we talking about problem 72? Problem 69 talks about phi, but it takes less than 1 milli-second.

Quote
I agree with Prof Wan, the project is interesting enough that I can do it as a way to kill spare time and relax


Yes, very entertaining.

Quote
We have 77 now, on the 6th page I think. I solved about 2/3 of them.


I suggest you change the profile of that account to China, so that we can have more 5-star red flags there. :)

Quote
Tomorrow I will go on a 3 week trip to China. As of now I am not sure whether I have more or less spare time, most likely less. 


Let me know if you can access this site. I had trouble accessing this site from China.

Quote
So far no problem used more than one minute of computer time. If my program runs more than a few minutes, I would just kill it and start over. I do this for one reason: I almost never get the right number in the first try, usually in the fourth or fifth. So I cannot afford long programs.

Out of all the problems that I have solved, there are 3 of them takes longer than 1 minute. The website says all problems should be done within one minute.

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: Project Euler
« Reply #44 on: 二月 25, 2008, 12:53:00 am »
Quote
I suggest you change the profile of that account to China, so that we can have more 5-star red flags there. :)


You need to ask Id94 for that. Technically he still owns the account.

Quote
Let me know if you can access this site. I had trouble accessing this site from China.


Yes I can access this site, but basically nothing else.