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)
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.
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!
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.
- Map image (100x100 array of values from 0 to 100)
- List of movements, with compass bearings (eg. 'NNWWSESSS'). Note - We may, if deemed appropriate, set a threshold for number of moves before the search is called off.
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 firstname.lastname@example.org 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)
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.
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)
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.
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')
- Map 1 (image)
- Map 2 (image)
- Map 3 (image)
- Map 4 (image)
- Map 5 (image)
- Map 6 (image)
- Map 7 (image)
- Map 8 (image)
- Map 9 (image)
- Map 10 (image)
You can test your programs here.
There will be prizes for categories such as:
- Fastest program
- Most elegant program
- Best fresher entrants
- Shortest code
- Most entertaining explanation
The prizes will include:
- Raspberry Pi starter kit (provisional)
- Vouchers for ThinkGeek
- Vouchers for SparkFun
- Vouchers for Red Molotov
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.