Challenge 26 will be marked on Wednesday evening so there's still time to get your entry in. There's just one so far.
Challenge 27 is a simple but different programming exercise. On a game map (made up of a 2d array of characters representing land, sea, forest and mountains), your application must add as many cities as possible. However these cities must be placed only on land (not in forests or mountains or sea!) and some cities must be near the sea. No cities should be too near each other. That's it, get as many as possible on the map. The deadline for this is the end of September.
- Link to Programming Challenge Twenty Six Process a book
- Link to Programming Challenge Twenty Seven Pack Cities onto a map
“No cities should be too near each other.”
So if I assume that right next to each other is not “too near”, it’s alright? [Or how should I interpret that? How much space should there be? Some euclidean distance? Manhattan?]
How about “No two cities can be within 7 locations (as the crow flies) of each other.” and The “as the crow flies” distance restriction simply means that if city 1 is at point x1,y1 and city 2 at x2,y2 then sqr root((x2-x1)2 + (y2-y1)2) must be > 7. It’s simple Pythagoras theorem.
So if one city was at 10,10 and the other at 11,11 ie they are next to each other but the distance = sqrt(2) ie around 1.4 which is much less than 7 so not allowed.
It’s all in the Programming Challenge 27 page.
David
About C, C++ and C# Guide
If I read the instructions correctly, there is no functional difference between mountains and forest. Am I missing anything?
Can you tell us more about how the entries will be judged? I assume they will be tested against a variety of maps. Will each entry’s “score” just be the average number of cities it places across all maps? Is speed only relevant in the event of an exact tie in the number of cities placed?
Also, when you say “The first 15 cities put on the map must be placed by the sea. I.e. on land, next to a ~”, what do you mean? Does each piece of land have four neighbors (N, S, E, W) or 8 neighbors (N, S, E, W, NW, SW, NE, SE)?
Edgar, good points thanks! I’ll update the challenge document. Yes there is no difference between forest and mountain and if any of the 8 squares around a location have sea then it’s considered sea-side.
seems like a well-specified and interesting challenge..
another question David:
Will you test the entries with the supplied test.txt file, or with another unknown one?
“Just in case there is a tie, please include timing code with loops so it takes 1-10 seconds. If if you code ran once in 20 ms then doing it a hundred times would take 2 seconds.”
I’m just a little confused as to what you mean by this… Do you mean to say we should report timing at each loop or enclose the entire code to keep track of time over multiple passes of the program. Thanks! (apologies if I’m just missing something)
Makis. Congrats on winning Challenge 26, I’ll publish the results shortly!
It shouldn’t matter if I use another file should it? It would be identical- same number of lines and chars per line. Would that cause problems?
Jon, some entries have been so fast I’ve had to run it in a loop hundreds or thousands of times so the overall timing was reasonably measurable.
So put the whole code inside a repeat loop and time the total time. Divide the total time by loop count to give an accurate time for one loop.
David
About C, C++ and C#
I’m having fun!
… 12 random cities
http://i32.tinypic.com/11lklkp.png
49 random cities (the first 15 by the sea) in 0.08 secs.
http://i32.tinypic.com/wvu5nc.gif
Pedro, that 0.08 secs time is suspicious
do you count from start (read file) to finish,
or just the time placing cities?
I “lost” the source file — but I’m sure the timing included everything except the malloc/free calls. My current version (with backups!) is not yet functional.
Are people still working on this? Mine runs a lot longer than Pedro’s but is able to deploy a lot more.