OCUK Xmas Programming Challenge

7e7en · 12 Dec 2010 at 10:52

Lightnix said:
I've managed to confuse myself. I think stage 8 should be easy, but I've come up with two totally different methods (one mathematical, one brute force) for it which come up with the same wrong answer.

Incidentally, the same right answers when I check them for other (although far smaller) values.

I should probably go to bed.

I'm not sure if you've ever played This game but it might help you out.

ProOrWhat · 12 Dec 2010 at 12:41

This looks interesting, might have a go.

Lightnix · 12 Dec 2010 at 16:12

Yeah I think I stopped being able to program at around 2 last night. It all kind of went down hill from there. First thing I tried this morning worked, how about that?

Edit: Okay mine's finished. It takes about 5.6 seconds... on a VIA C7 at 1.6GHz running ubuntu 9.04. Not going to submit it just yet, I think I can squeeze a bit more out of it.

Tilluss · 12 Dec 2010 at 23:17

7e7en said:
I'll edit this post, as I've fixed it all now. Just trying to optimize stage one. Got it down to <500 sec.

Also here's what I used for stage 1.

Stage 1 Spoiler.

And reading the Collatz Conjecture got me it that fast.

Your code is very similar to my first implementation, but i've since modified it to try and get the process time down, I can now get my first stage to run sub 100ms now.

BTW, posting code before the competition finishes is making it easy for new contestants to complete answer 1

RatHat · 13 Dec 2010 at 07:30

entry submitted. very nice challenge

7e7en · 13 Dec 2010 at 15:00

Tilluss said:
Your code is very similar to my first implementation, but i've since modified it to try and get the process time down, I can now get my first stage to run sub 100ms now.

BTW, posting code before the competition finishes is making it easy for new contestants to complete answer 1

I've been stucking on <500sec. I just don't know what to do the increase the speed. I was thinking some thing that remembers the past numbers and if the current number comers across a past number it can simply add that numbers length to it's own length.

Any hints anyone?

Also, If you want I can take that link from my other post out?

PaulStat · 13 Dec 2010 at 15:10

I'd very much appreciate if some maths guru could explain with examples the wikipedia sections

http://en.wikipedia.org/wiki/Collatz_conjecture#As_a_parity_sequence
http://en.wikipedia.org/wiki/Collatz_conjecture#Optimizations

I'm fairly sure I'd be able to put some code together if I understood the maths. At the moment though without step by step instructions on how those maths formulas actually work it might as well be Greek.

I have step 1 working but in a simple loop 1.5million times type fashion which obviously takes a long time

BunnyKillBot · 13 Dec 2010 at 16:13

PaulStat said:
I'd very much appreciate if some maths guru could explain with examples the wikipedia sections

http://en.wikipedia.org/wiki/Collatz_conjecture#As_a_parity_sequence
http://en.wikipedia.org/wiki/Collatz_conjecture#Optimizations

I'm fairly sure I'd be able to put some code together if I understood the maths. At the moment though without step by step instructions on how those maths formulas actually work it might as well be Greek.

I have step 1 working but in a simple loop 1.5million times type fashion which obviously takes a long time

I haven't actually coded anything yet, but from reading the wiki page the optimization allows you to jump k steps into a chain. For each n rather than computing a full chain, test the result of jumping the largest known chain length.* If the chain is terminated, this number cannot have a larger chain so disregard.

(i have no idea what happens if you jump beyond the chain length that hits 1. I presume that when it hits 1 it cycles 4 2 1 for infinity, so these would be special cases?)

Something i learnt early on in graphics engine programming is you don't have to understand the mathematics as it is written, just the notation. Programme in as written, get result, sorted

RatHat · 13 Dec 2010 at 16:19

BunnyKillBot said:
Something i learnt early on in graphics engine programming is you don't have to understand the mathematics as it is written, just the notation. Programme in as written, get result, sorted

this won't get you very far...

BunnyKillBot · 13 Dec 2010 at 17:02

RatHat said:
this won't get you very far...

It is not always necessary to understand why something works, and programmers are not by requirement mathematicians. The knowledge that something works as a means to an end is sufficient. I am not an Einsteinian mathematician and no matter how hard i try there will always be somebody better than me. I will leave it up to those so skilled to come up with super theories and God formula.

RatHat · 13 Dec 2010 at 17:07

well maybe my approach on things is slightly different than yours, but I usually like to understand the maths I am operating on

EDIT: respectively, operating with

Tilluss · 14 Dec 2010 at 15:41

7e7en said:
I've been stucking on <500sec. I just don't know what to do the increase the speed. I was thinking some thing that remembers the past numbers and if the current number comers across a past number it can simply add that numbers length to it's own length.

Any hints anyone?

Also, If you want I can take that link from my other post out?

Your thoughts will help the speed a lot

Nimble · 15 Dec 2010 at 02:12

Submitted my entry.

PaulStat · 15 Dec 2010 at 09:32

Sent mine (python), managed to get it under 10 seconds in the end. What are the chances of a leader board at the end of this to see the top 10 times say?

RatHat · 15 Dec 2010 at 10:34

maybe top 10 per programming language would be good, since you can get it way faster in C, for example. mine ran in 0.17 to 0.28 sec

tntcoder · 15 Dec 2010 at 17:19

Nimble said:
Submitted my entry.

PaulStat said:
Sent mine (python), managed to get it under 10 seconds in the end. What are the chances of a leader board at the end of this to see the top 10 times say?

RatHat said:
maybe top 10 per programming language would be good, since you can get it way faster in C, for example. mine ran in 0.17 to 0.28 sec

Thanks guys, both entries received & working

I'll definetly sort out some leader boards and general performance stats once everything is in

That's 12 entries in now

jonneymendoza · 16 Dec 2010 at 14:16

lol £5? is that all for what i can see nearly a full days worth of work.

tntcoder · 16 Dec 2010 at 16:42

jonneymendoza said:
lol £5? is that all for what i can see nearly a full days worth of work.

If you see it as work don't do it - it's a programming 'fun' challenge... not really about the money.

Nimble · 16 Dec 2010 at 17:18

tntcoder said:
Thanks guys, both entries received & working

I'll definetly sort out some leader boards and general performance stats once everything is in

That's 12 entries in now

Can you tell me what time it runs in (there's a show time #define at the top you can uncomment)? Just want to know if it's performing as well as it should. Oh, and if you do try it with threading enabled, it has to be linked against libboost_thread.a (or whatever the static thread library is called).

tntcoder · 16 Dec 2010 at 17:32

Nimble said:
Can you tell me what time it runs in (there's a show time #define at the top you can uncomment)? Just want to know if it's performing as well as it should. Oh, and if you do try it with threading enabled, it has to be linked against libboost_thread.a (or whatever the static thread library is called).

Runs in 0.060 seconds without threading and 0.015s when compiled against boost_thread-mt. Crazy fast