OCUK Xmas Programming Challenge

Tilluss · 8 Dec 2010 at 14:59

Entry submitted. I hope is all works as per the requirements tntcoder.

Rjindael · 8 Dec 2010 at 16:24

Currently at 500ms on a dual core 2.0Ghz

Gonna optimize some more, should have a solution in later or tomorrow. Are we allowed to send in further submissions if we make any improvements after the first as long as it's before the deadline?

Peve · 8 Dec 2010 at 16:47

I am really looking forward to seeing how you guys are getting it done so quick. I thought my 2.7 seconds was decent!

oOYoDaOo · 8 Dec 2010 at 16:59

Just completed my version, takes a few seconds using C# on mac.
I will tidy and optimise it and then send it along!

Garee · 8 Dec 2010 at 17:13

Can someone help me understand the first challenge?

From what I gather I have to loop through 1 - 1,500,000 as a starting n value and find the smallest n that has the longest chain?

Phyre · 8 Dec 2010 at 17:27

Garee said:
Can someone help me understand the first challenge?

From what I gather I have to loop through 1 - 1,500,000 as a starting n value and find the smallest n that has the longest chain?

Pretty much, yes. You need to find the number with the longest chain, but there are multiple numbers with the "longest chain", so you choose the smallest one.

I've improved on my previous 500ms result... It now stands at ~200ms, entirely single-threaded.

tntcoder · 8 Dec 2010 at 17:55

Tilluss said:
Entry submitted. I hope is all works as per the requirements tntcoder.

Yep all received and working correctly thanks

Runs in at 2.198s on my box.

BTW for judging ill take an average over 3 executions with everyones code running on the same hardware.

Rjindael said:
Are we allowed to send in further submissions if we make any improvements after the first as long as it's before the deadline?

Yep that's fine, ill just go with the most recent submission at the end.

Phyre said:
I've improved on my previous 500ms result... It now stands at ~200ms, entirely single-threaded.

Nice, im not sure there's a huge need for multi-threadding tbh as the threads will probably add a fair chunk of overhead themselves, nice addition learning wise though. Shame I didn't use larger and more demanding numbers for the calculations on hindsight (I naively assumed they would take people at least longer than 1s to crunch

).

Garee · 8 Dec 2010 at 19:43

I keep getting 910107 as my answer for challenge 1. Is this one of the values of n that has the longest chain or am I way off?

Rjindael · 8 Dec 2010 at 19:50

Hey Phyre, I'm curious, what specs are you getting those times on?

Fourstar · 8 Dec 2010 at 20:03

Garee said:
I keep getting 910107 as my answer for challenge 1. Is this one of the values of n that has the longest chain or am I way off?

I find two answers with longest chain length. 1126015 for the larger and the correct answer for the smaller.

Peve · 8 Dec 2010 at 21:28

Just sent my entry in!

tntcoder · 8 Dec 2010 at 21:32

Peve said:
Just sent my entry in!

Received and working thanks

- 1.183 seconds from start to finish on a quick test.

Haydz · 8 Dec 2010 at 22:00

Garee said:
I keep getting 910107 as my answer for challenge 1. Is this one of the values of n that has the longest chain or am I way off?

It may be because you're using a signed integer and the calculation is too big, try using an unsigned int or unsigned long.

I think I had a similar problem

Finished mine, just going to do some optimization and maybe convert it to c++, just to see if there's any benefit.

Phyre · 8 Dec 2010 at 23:02

Rjindael said:
Hey Phyre, I'm curious, what specs are you getting those times on?

Tried it on two computers and got the same speed on both. First was an E8500 (clocked at.. 3.3ghz?) and the second an i7 920 at stock.

slylittlefox · 9 Dec 2010 at 13:08

Just to be perfectly clear: the code we produce has to carry out the whole computation every time it runs? That is, we're not allowed to store answers from the previous stage? Because some of the times people are getting are insane.

Pho · 9 Dec 2010 at 13:09

Done \o/. The whole thing takes just over a second though (E2180 @ 3.2Ghz) :/. Stage 1 takes up most of that.

I thought I'd been clever for stage 1 but clearly I have some tweaks left. Mind you, I haven't written the code for all-out performance.

Pho · 9 Dec 2010 at 13:11

slylittlefox said:
Just to be perfectly clear: the code we produce has to carry out the whole computation every time it runs? That is, we're not allowed to store answers from the previous stage? Because some of the times people are getting are insane.

That's how I've read it. Every step must be calculated live and fed into other functions that require that result each time.

NickK · 9 Dec 2010 at 15:08

Change of tact.. Going for the most ludicrous implementation award

excessive parallelism for the win..

So far the prime numbers are generated on the GPU.. At the same time the CPUs are doing other bits...

Thrash · 9 Dec 2010 at 15:15

Mine is finished (in C#) but seems slow compared to some of the other results. Might have to port it to another platform.

Pho · 9 Dec 2010 at 15:40

NickK said:
Change of tact.. Going for the most ludicrous implementation award excessive parallelism for the win..

So far the prime numbers are generated on the GPU.. At the same time the CPUs are doing other bits...

How are you calculating using the GPU, via CUDA or something else? (also wouldn't that be classed as an external lib?

)