So there was I, tinkin.

And I thought maybe others would like to think a bit too

It's from projecteuler.net. It's one of the "easier" ones, it's not actually about writing something that works. That's not tough. It's about writing something that works and solves it within a reasonable amount of time (preferably seconds, not days!).



No, the actual problem isn't that hard per say, you can simply brute force it to find the number. But brute force = bad.

So, trying to come up with an elegant method of doing this, so it solves within the shortest time possible. A starter...

Firstly we have to work all the "triangle numbers" or whatever. Just do a never-ending loop...

Sum? That'll just be a simple sum to get the "triangle" number.
i is representing the ith number
so inside something along the lines of

to keep track of our "triangle number", course, we need to increment i. Completing it a bit...



The if statement is merely calling a method "divisors" which will return the number of divisors that the number has. If it's more than 500, print it and exit.
So what are some solutions for it? Elegance over brute force preferred

The code I wrote took 1.79 seconds to find the answer, however someone else has solved it with a different solution in 94ms (mine is 1719ms!)

Give it a go, how long did it take and what was the answer and your code?

Fastest seen on the actual problem is in the solution paper, which is as follows:

Bugger!

69

_________________





Went to a zoo, they only had one animal there, a dog............. It was a shitzu....



I’z leakin… bring amberlamps

That's your age Geoff

_________________

The Pancreas of S.T.F.U. | Never take life too seriously - nobody gets out alive anyway.
Disco_jim: um..... I have no excuse. | Chips: Thank the Beef | Rev Dr: Beef, I think i wee'd a little

Answers on the back of a postcard to the usual address...........








Anyone have a feckin clue wtf he was on about there?

_________________

LINUX : If it was any good, they'd charge for it.
I want to die peacefully in my sleep just like my Grandad, not kicking and screaming like his passengers...

I'm working through, done the first 5....apparently there's some trick with prime factors...I'll have a go when I get there.

_________________
“There are some people in this world who don’t love their fellow man, and I HATE people like that!”

thats a no

_________________

Games: DC, CSS, BF2, Insurgency, Cod2, Cod4, Cod5, BFBC2, Surpreme Commander, Hidden Source, bfbc2/vietnam, Cod black ops, need for speeds (underground 1 and 2, prostreet, hot pursuit, most wanted), juiced 1 and 2, im sure theres more...

What language are you using chips?

in p*thon i can do it in 1.38 seconds (hey, it's an interpreted language) by working out prime factors. .19 seconds is generating a list of primes up to 65500, which is probably a bit exessive.

In p*thon the brute force method that chips is using takes minutes to run, so I'm not sure what our comparison is.

my code is pretty much



prime_factor will return a dictionary of prime factors along with their exponents, ie

12 is made from 2^2 and 3^1, so {2:2, 3:1}

and numfactors will calcualte the number of factors based on the exponents (have a look on wikipedia). plist is my list of primes - I should be able to not pass it I'm sure, which should save time, but I cba to fix it now

[edit] Just seen the solution - might try implementing that too, see how much faster it goes

_________________
“There are some people in this world who don’t love their fellow man, and I HATE people like that!”

changing it actually made it worse - which means that there's something pretty shitty in my code I think the numfactors I can include optimise by just having a running total of exponents in prime_factor

[edit] nope, turns out the dictionary is most efficient!

_________________
“There are some people in this world who don’t love their fellow man, and I HATE people like that!”

im moving atm but ill take a look more at this in a week

_________________

nice

Am using Java Currently completed up to problem 22*

For the Divisors problem my brute force was the following method:


However, remembering some optimisations I made during my summer placement whilst writing code - I replaced the for loops calculation with a reference to the actual calculation value.


Suddenly you are cutting out Math.sqrt(sum) amounts of square root calculations per method call. This, in fact, shaves over 1.2 seconds off the execution time - bringing it down to


Simple optimisation, often overlooked


For the primes calculations problems I basically used a sieve of Eratosthenes (I didn't know at the time, I just happened to write it ) - in my own implementation
Basically, apart from the number 1, a prime was any number not divisable by any other prime. Once a prime is found, it's added to a collection of primes for numbers to be tested against...
So 2 isn't divisible by any prime as there are none at the moment. Add to collection. 3 isn't divisible by 2, so add to collection. 4 is, so ignore, 5 isn't divisible by 2 or 3... so add to collection. Lather rinse and repeat.

I don't think my sieve is 100% correct though as it took 5 mins to find all the primes this way, and then sum them up (for the problem of summing all primes below 2 million)!

* A few confessions:

1) I haven't done number 18 yet. Reason why is simply not knowing my algorithms well enough and (shamefully) the tree's implemented in Java collections

Well, I know the theory of the algorithms, but have never written them - and simple breadth first, or even depth first, is not an "elegant" solution

2) Number 15, finding the paths in a 20x20 grid. I couldn't actually come up with an algorithm to solve this whatsoever (by myself) so I had to look up with regards to algorithms and it basically gave me the answer
So I didn't really solve that one, I cheated

Then again, not doing this for any other reason than I like problems (despite being, as said, crap at maths) and I wanted to practice/learn algorithms and their implementations
Later on I assume I'll be referring to textbooks repeatedly, however, at the moment I can get by with just making them up on the spot (problem 21 took 3 minutes from start to finish, I found it to be fairly trivial... but 23 I'm not even sure I understand yet ).

I think my head exploded :/

_________________

At least the contents of ur head released Mine still swish around in there (after reading that, that is )

_________________

My work blog | My Flickr | Complaints form | Get

wrt to 18, apparently you need to read
http://en.wikipedia.org/wiki/Dynamic_programming
to be able to approach it...

I'm running out of ones that are interesting and doable - the ones like find the number of xs under N are just tedious...problem 102 was fun though

_________________
“There are some people in this world who don’t love their fellow man, and I HATE people like that!”

I feel like I'm in MENZA or something
You know, that feeling.. when you realise...... ur waaaaaaaaaaaaaaaay out of your depth?

_________________

My work blog | My Flickr | Complaints form | Get

That would be MENSA genius

_________________

The Pancreas of S.T.F.U. | Never take life too seriously - nobody gets out alive anyway.
Disco_jim: um..... I have no excuse. | Chips: Thank the Beef | Rev Dr: Beef, I think i wee'd a little