login

Home - Other Content - Programming Competition 2013

Durham University Computing Society Programming Competition 2013

The problem is given below. You can solve it using any programming language you like, and you can enter as individuals or in teams of any size. Don't worry if you're not too good at programming; most of this problem will be problem solving, not implementation.

This competition is open to everyone - members, non-members, students, staff, alumni, members of the public, random people who come across it - HOWEVER the prizes are only eligible to current Durham students or current Compsoc members. (You can still win if this doesn't cover you, and you'll get listed on the website, but you won't get a prize for it)

Mailing List

Any announcements about the competition will be given to the mailing list - it is strongly recommended that you sign up to this (don't worry - you'll have no emails other than ones related to the competition). We'll also update this page.

Code Jam

We're organising a Code Jam event during this week - a chance for anyone who wants to to get together, chat, socialise, and work on the problem. More information on this nearer the time.

For anyone interested in meeting up to work on the programming competition, DUMake will be running a casual codejam on Wednesday afternoon (from 1:00pm), in E278 - the electronic labs in the blue building behind engineering. We’ll be running our regular DUMake session alongside, so we should be working on quadrotors as well!

The Problem:

An object has fallen to Earth, and you need to find it quickly - before anyone else does. You know roughly where it landed (within a 100x100m area), but that doesn't help - it's small enough that you won't see it unless you're a metre away. Luckily, you know that it's most likely to have landed on high ground and less likely to have landed on low ground - so you can make a map showing the probability of each part of the area. You're dropped into the area to make your search.

Given this map of probabilities, and given your known starting point, what route do you take to find the object as quickly as possible?

The winner will be the program that will take a map and position input and which consistently outputs a route that finds the object in the minimum number of moves. The object will have been placed randomly (based on the probability map), and the test run several times to get an average time to find the object.

Program input:

Program output:

The ten map images are below. The start position will be in cell 0,0 (north-west corner) - as you only search a cell by entering it, however, you must leave and re-enter cell 0,0 if you wish to search it.

You must submit one list of directions for each of the map inputs to president@compsoc.dur.ac.uk by 4am on Monday 11th November, along with the source code for your program and a short description of how it works. PLEASE SET THE SUBJECT OF YOUR EMAIL AS 'ProgComp2013 - TeamName'

If you'd like to test your program in advance to see how well it works, you can use our testing script (below)

Extensions

There are a few extensions to the programming competition problem, to stretch anyone who has finished it already.

NOTE - No one will be penalised for not including any extensions.

When you submit your results, please say which extensions you've included.

Extension 1:

You are dropped into the area to find the object, but you can't guarantee to always land at the NW corner. You need to produce two routes for each map - one from position (0,0), and one from another position (as given below):

Map 1: (0,0) and (20,35)
Map 2: (0,0) and (99,5)
Map 3: (0,0) and (55,55)
Map 4: (0,0) and (30,60)
Map 5: (0,0) and (70,15)
Map 6: (0,0) and (85,5)
Map 7: (0,0) and (1,70)
Map 8: (0,0) and (15,51)
Map 9: (0,0) and (18,12)
Map 10: (0,0) and (20,13)

Extension 2:

It turns out that the object is harder to find than you'd expected. The ground is covered in undergrowth, and there's a chance that you might not see it even if you're a metre away.

The probability that you'll see the object given that you're in the same cell as it is 80%.

The probability is constant no matter how often you visit that cell, so if you visit the cell containing the object multiple times then you'll overall be more likely to find it.

Extension 3:

It is vital that the object is found quickly. You've been assigned a team of searchers to help. All of you will start from the same point, but you can all have different routes from that starting point. The object is found when the first searcher finds it.

You have up to five searchers. You must give all routes together, in the form '[Searcher 1 route],[Searcher 2 route],[Searcher 3 route],' etc (eg. 'NSEW,NESW,NWSE,NSNS,EWEW')

Files

You can test your programs here.

Alternatively, download the testing script (runs in Python. If you don't know how to use this, follow the instructions here) to run on your own machine.

Prizes

There will be prizes for categories such as:

Plus other prizes we think sensible. The exact prizes will be decided by the judges based on the entries received.

The prizes will include:

Prizegiving - and a talk about the problem and the judges' favourite solutions - will take place on Tuesday 12th November at 8pm in CG60 (signposted from the Red Greenhouse)

Last edit: Sat 9th Nov, 02:13 p.m.

Google

External Links

Compsoc Wiki
Compsoc Library
DSU

Upcoming Events

There are no upcoming events planned. Check the CompSoc Wiki in case of emergency

RSS | iCal

Sponsors

ARM
DNUK
O'Reilly
No Starch Press
Durham Students Union

Random Poll

Which is the best name for the DUKAT exec?


View results
Submit a new poll
All polls

This section exists to trap prefetching clients. Please just ignore it if you have css disabled and thus can see this. Do not click this link unless you want us to think you are a bot