OCUK Xmas Programming Challenge

[tntcoder]

Submitted my entry.

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?

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

 

[tntcoder]

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.

 

[tntcoder]

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

 

[tntcoder]

Hi,

Just submitted my attempt. Looks like I could be entry 13!

Mine is c# .Net 4 and runs in just under one second.

Merry XMAS to all readers

Mark

Thanks, recieved and working. Runs in 0.713 seconds

Nice, I wonder where the bottleneck is though since my laptop with a 2Ghz Core 2 Duo does it in 70ms without threading about 40ms with threading. Is optimisation on?

Hmm not much of a bottleneck? 60ms no threading and 15ms with threading. That is without GCC optimizations though yes.

 

[tntcoder]

What are GCC optimizations?

GCC is the Linux C/C++ Compiler and you can ask it to spend extra time optimizing your code during compiling to make it as fast as possible. There are 3 levels of optimizations avaliable, for example the highest does:

This option turns on more expensive optimizations, such as function inlining, in addition to all the optimizations of the lower levels -O2 and -O1. The -O3 optimization level may increase the speed of the resulting executable, but can also increase its size. Under some circumstances where these optimizations are not favourable, this option might actually make a program slower.

Won't be using it here though as not sure it's very fair towards other bulky languages (.net or python).

 

[tntcoder]

Finally submitted my entry. It runs in around 160ms when compiled for x64 using C#/.NET 4. I'd mainly written it with re-usability in mind rather than for all out performance, I could squeeze a bit more out of it by going from Int64s to ints but that kills the re-usability a bit .

This was my first time using Visual Studio 2010, it's much nicer than 2008.

Thanks, all working I get it at 125ms on x64.

Also, awesome christmas tree

 

[tntcoder]

Arghhhh, nearly finished mine but stage 1 takes far too long. I can't make much sense of the Wikipedia page...

1 week left to crack it

 

[tntcoder]

Entry e-mailed.

Thanks Congrats on getting it done.

 

[tntcoder]

Ok thanks guys - comps all finished and is now over

A grand total of 19 submissions totalling just over 8500 lines of code!

Now I shall try and work out a winner, somehow...

Results + everybody's code will be up sometime tomorrow afternoon, hopefully not too long after 3-4pm.

Edit: afraid it will be about 7pm now as had to go out.

 

[tntcoder]

Ok - The results are in - 19 Submissions A few people who developed solutions in this thread didn't submit e.g Nickk and Rjindael - maybe you could upload your code anyway somewhere when it's done.

So every submission was correct in that it matched the spec perfectly and performed correctly to given inputs. This made picking a winner very tricky...

I don't have access to my 980x at the moment as im away for xmas, but all code was executed on a quad core Q8400 with 2gb ram. Everything except C# code was evaluated on Linux 64bit and C# code under Windows 7 64bit. Even then I did some comparisons between running c# under linux/mono and windows and there was very little in it. All timings were averaged over 3 executions.

Language Summary:
Java - 1
PHP - 1
Python - 2
C - 5
C++ - 3
C# - 7

So as expected C/C++ were the fastest performers with Python and PHP being surprisingly slow, even with good code being used. Several people used threading, be it pthreads, boost or .NET, all were fine.

Here are individual stats and links to everyone's code:


Bloomfield - C++
View Code
Time: 2.172 seconds
Lines of Code: 303

Crowze - PHP
View Code
Time: 9.291 seconds
Lines of Code: 843

Lightnix - C
View Code
Time: 0.227 seconds
Lines of Code: 354

Matja - C
View Code
Time: 0.147 seconds
Lines of Code: 225

Grimbough - C
View Code
Time: 0.099 seconds
Lines of Code: 329

MrMark - C#
View Code
Time: 0.281 seconds
Lines of Code: 273

Nimble - C++ ** Winner **
View Code
Time: 0.049 seconds
Lines of Code: 977

oOYoDaOo - C#
View Code
Time: 0.438 seconds
Lines of Code: 504

PaulStat - Python
View Code
Time: 8.160 seconds
Lines of Code: 184

Peve - Java
View Code
Time: 1.074 seconds
Lines of Code: 338

Pho - C#
View Code
Time: 0.225 seconds
Lines of Code: 736

Phyre - C#
View Code
Time: 0.173 seconds
Lines of Code: 607

Rat Hat - C ** Second **
View Code
Time: 0.110 seconds
Lines of Code: 246

7e7en - Python
View Code
Time: 9.445 seconds
Lines of Code: 181

Seany84 - C#
View Code
Time: 2.1 Seconds
Lines of Code: 306

Swanser - C
View Code
Time: 0.174 seconds
Lines of Code: 416

Thrash - C#
View Code
Time: 1.2 seconds
Lines of Code: 491

Tillus - C++
View Code
Time: 0.800 seconds
Lines of Code: 523

Haircut (Jon) - C# (many files!)
View Code 1
View Code 2
View Code 3
View Code 4
View Code 5
View Code 6
View Code 7
View Code 8
Time: 0.625 seconds
Lines of Code: 537

Winner: Nimble - Very nice overall implementation with threading used very effectively. Although the code is slightly lengthy and verbose and some elements could have been trimmed down, it all works nicely and is easy to read and comprehend - Rat Hat & Grimborough very nearly had the edge here as their code was a bit more 'raw/lower level', but I could only pick one.

Runner Ups: Rat Hat, Grimborough, Lightnix, Phyre, Pho - honestly everyone's was very good with good algorithms and efficient implementations. It's very difficult to say one is better than the other!


Hope everyone enjoyed the competition and learnt some bits and bobs along the way (Now you can tear each others code apart )

Nimble - I'll drop you a mail so you can claim the epic prize fund