Project Euler : Problem 15 Solved
The first problem for June was quite tricky (at first 
)
I would like to ask for anyone to give me a Brute force solution Problem 15 for Project Euler
If you know your Combination equations : n! / r!(n-r)! then this question is a joke.
So, I challenge you coders to come up with something a little bit more brute force
The Problem is as follows :
How many routes are there through a 2020 grid?
Tips :
- Combinations without repeats = n! / r! * (n-r )!
Project Euler Stats :
Total Research Time : 0 Days
Total Coding Time : 20mins
Total Code Execution Time : 0ms
Project Euler : Problem 12 Solved
Because of my work on my OpenGL glut assignment, I've had to put my Project Euler stuff on hold. But, now that is all over I finally got to jump back into Problem 12 and really spent some time on it.
1) You need to find out how to generated total amount of divisors very quickly
2) You need a more advanced formula for calculating Triangle Numbers
3) You need to recode your primefactoring
After doing the research for number 1 and 2, I tried using my current prime factoring functions for the 3rd part but it was hitting 4mins execution time without solving it.
I decided to start from scratch and do it again.. Bingo.. 0ms. Problem solved! Some times it is just easier to redo things..
The Problem is as follows :
What is the value of the first triangle number to have over five hundred divisors?
Tips :
- Triangle Number = n * (n + 1) /2
- You don't need BigInteger.. If you starting using BigInteger in your code, something is going wrong.
Project Euler Stats :
Total Research Time : 3 Days
Total Coding Time : 40mins
Total Code Execution Time : 0ms
Project Euler : Problem 11 Solved
Problem 11 of Project Euler is a strange cat.
The Problem is as follows :
Problem 11
When I first attempted to solve this, I thought to myself :
Gah.. Brute force?? Who would be so fail to brute force this such a wonderful example of AI?
Answer : ME
See at first I thought brute forcing this would be rather disrespecting to the challenge, but then it dawned on me that "brute-forcing" was the most sufficient way of solving this one.
But you must be smart in the way you check your products..
Tips :
- Don't count what has already been counted *cough*up,left*cough*
- Don't forget that a diagonal goes 45° and 135°
- Math.max() FTW!
Project Euler Stats :
Total Research Time : 0 Days
Total Coding Time : 20mins
Total Code Execution Time : 0ms
Project Euler : Problem 13 Solved
Problem 13 of Project Euler is quite interesting.
The Problem is as follows :
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
(numbers omitted)
Tips :
- Look @ Problem 8
- BigInteger
- It is 100 SEPARATE 50 digit numbers they want you to add.
- Don't miss copy the number and miss the last line "53503534226472524250874054075591789781264330331690" and spam Project Euler with a solution you are 100% works
Project Euler Stats :
Total Research Time : 0 Days
Total Coding Time : 10mins
Total Code Execution Time : 0ms
Project Euler : Problem 14 Solved ( Collatz Problem )
Problem 14 of Project Euler is quite interesting.
The reason I say this is because you think it will be simple (and in fact it really is simple).
But doing it in Java has a certain snag to it.
Notice the hint they give you :
NOTE: Once the chain starts the terms are allowed to go above one million.
Then remember that wonderful BigInteger class in java that is so retardedly un-user friendly..
That is all I have to say.. It seems other languages have the edge on Java on this one. Users are reporting 0.81 secs execution time where as I'm only managing to get it done in 10secs (not my finest moment). Will attempt to get this number down, but I doubt it.
The Problem is as follows :
The following iterative sequence is defined for the set of positive integers:
n n/2 (n is even)
n 3n + 1 (n is odd)Using the rule above and starting with 13, we generate the following sequence:
13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.Which starting number, under one million, produces the longest chain?
Tips :
- Read the tip
- BigInteger
Project Euler Stats :
Total Research Time : 0 Days
Total Coding Time : 20mins
Total Code Execution Time : 9922ms
Project Euler : Problem 20 Solved
If you did Problem 16 of Project Euler just before this, then Problem 20 is quite the joke.
I did decide to change the way I get the sum of digits a little bit though. ( as per suggestion by Tim )
I changed the following code from Problem 16
String smallerNumber = removeChar(bigNumber, '0');
char[] chars = smallerNumber.toCharArray();
for (char aChar : chars)
{
answer+= Character.digit( aChar,10 );
}
to the following in Problem 20
BigInteger total = new BigInteger("0");
BigInteger ten = new BigInteger( "10" );
while (!number.equals( new BigInteger("0")))
{
BigInteger mod = number.mod( ten );
total = total.add( mod );
number = number.divide( ten );
}
No string conversion ftw! (FYI : The reason I use BigInteger is because I doubt I'll ever need to add up digits of a long or an Integer )
The Problem is as follows :
"Find the sum of the digits in the number 100!"
Tips :
Project Euler Stats :
Total Research Time : 0 Days
Total Coding Time : 15mins
Total Code Execution Time : 0ms
Project Euler : Problem 16 Solved
Okay, this is just getting too easy..
Next to nothing research, Re-use of old code.
I hope the next challenge is a bit more difficult. Maybe it is just because Java supports big ass numbers with a class I'm starting to use quite often in Project Euler, namely : BigInteger
But.. Really now..
Problem 16's solution goes as follows :
(yes, I know I said I wouldn't put up any solutions, but really now.. I'm not spoiling anyone's day here)
BigInteger bigInt = new BigInteger( "2" );
String bigNumber = bigInt.pow( 1000 ).toString();
Then loop through each character and add it using :
Integer.parseInt( Character.toString( aChar ) );
*Editors Note
Interesting development
Using Integer.parseInt( Character.toString( aChar ) ), Execution Time : 36ms
Using Character.digit( aChar,10 ), Execution Time : 0ms
Intelligence has officially been insulted!
The Problem is as follows :
"What is the sum of the digits of the number 2^1000?"
Tips :
- Read up!
Project Euler Stats :
Total Research Time : 0 Days
Total Coding Time : 5mins
Total Code Execution Time : 0ms
Project Euler : Problem 10 Solved
With Problem 10 of Project Euler things started hotting up.
My final version executed in 2846ms.. This is the first time I had ever had a problem go over the 1000ms mark after tweaks and fixes. At first I was a bit irritated by this and decided to go back to the drawing board. But after reading through the forums, most guys were hitting the 5min mark.. Suddenly 2secs didn't seem so bad Again, I used Sieve's algorithm from Problem 3 and Problem 7
The Problem is as follows :
"Find the sum of all the primes below two million."
Tips :
Project Euler Stats :
Total Research Time : 0 Days
Total Coding Time : 10mins
Total Code Execution Time : 2846ms
Project Euler : Problem 9 Solved
With Problem 9 of Project Euler I got a bit lazy 
I'll be the first to admit that instead of researching this one properly I just did a mean old brute force attack.
My first attempt took over 4secs to calculate the answer.
I then cleaned up the loops and made it more efficient and got it down to 1297ms.
Then after looking at examples of how other people did it I first bashed my head on the keyboard at the simplicity of it all, and then recoded my final version...
0ms!
The Problem is as follows :
"There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc."
Tips :
- Don't try brute force this.. Remember how Pythagorean triplets work
Project Euler Stats :
Total Research Time : 0 Days
Total Coding Time : 15mins
Total Code Execution Time : 1297ms (after complete redo : 0ms)
Project Euler : Problem 8 Solved
Problem 8 of Project Euler solvable purely with pen and paper.. But if you decide to do it via Java (like me) I'd like to just mention one tip...
Character.toString()
The Problem is as follows :
"Find the greatest product of five consecutive digits in the 1000-digit number (below).
'731671765313306249192251196744265747423553491949349698352031277
450632623957831801698480186947885184385861560789112949495459501
737958331952853208805511125406987471585238630507156932909632952
274430435576689664895044524452316173185640309871112172238311362
229893423380308135336276614282806444486645238749303589072962904
915604407723907138105158593079608667017242712188399879790879227
492190169972088809377665727333001053367881220235421809751254540
594752243525849077116705560136048395864467063244157221553975369
781797784617406495514929086256932197846862248283972241375657056
057490261407972968652414535100474821663704844031998900088952434
506585412275886668811642717147992444292823086346567481391912316
282458617866458359124566529476545682848912883142607690042242190
226710556263211111093705442175069416589604080719840385096245544
436298123098787992724428490918884580156166097919133875499200524
063689912560717606058861164671094050775410022569831552000559357
2972571636269561882670428252483600823257530420752963450'"
Tips :
- Character.toString()
Project Euler Stats :
Total Research Time : 0 Days
Total Coding Time : 10mins
Total Code Execution Time : 0ms
3D Renders 21km 2010 ADSL AI Awesome Blizzard Cataclysm Coding Diablo Epic Epic Fail ESL Fail Fail Cakes Fifa 2010 FTW Gaming GG Google Grails Java Liverpool Malema MWEB OMW Problem Solving Programming Project Euler RED-i Replays ROFL Running Shaman Starcraft Starcraft 2 Starcraft 2 Replays tips Vuvuzela World Cup World of Warcraft WoW WTF Youtube Zerg
WP Cumulus Flash tag cloud by Roy Tanck requires Flash Player 9 or better.
Calendar
Recent Posts
- Twitter Weekly Updates for 2012-05-18
- Twitter Weekly Updates for 2012-05-11
- Twitter Weekly Updates for 2012-04-27
- Twitter Weekly Updates for 2012-04-20
- Twitter Weekly Updates for 2012-04-13
Archives
- May 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- August 2011
- July 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
Meta
Ultra's Brain Dump
- Seether? RT @Terencementor: Need some angry music this morning. Maybe some System of the Down. Any other suggestions?
- Right, 1hr Cycling done, coke in my belly! Act 2 here we come!! @GrantHinds @Hypn
- @GrantHinds was good fun :D Now on to level 20!
- @GrantHinds @Bashiok Alright Diablo! U have won(for now!) I've used up all my potions, but Error37 was too strong! I'll be back! #Diablo3
- @GrantHinds Talking to a friend on TS who is busy killing his first mob on #Diablo3 :(