- See all Programming Challenges.
This month's challenge is an exercise in optimization. You live in Flatland and are in charge of a cannon that can elevate at angles between 10 and 80 degrees. (Anything near 90 degrees is kind of dangerous under the "What goes up must come down" principle.
In short, your cannon fires at targets in a two dimensional plane. There are 50 targets worth varying amounts scattered at different distances to the right of your cannon. It only has 10 rounds of ammunition and takes one second to change its angle for every 10 degrees.
The targets are on a flat piece of land at the same altitude as you so this simplifies the equations. The 50 targets each have a value between 1 and 100 and are scattered randomly in range of your cannon.
Your job is to write a program that changes the angle of your cannon to get the most points in the shortest total time.
The simple physics of projectiles
When you fire a shell at an angle there are several forces involved. First is gravity. This is 10 metres/second2 in Flatland (compared to an average of approximately 9.8 on Earth).
If you point the cannon horizontally then the shell will have no vertical velocity and after one second will be falling at 10 m/second. For every second of travel the vertical velocity increases by 10 m/s. After three seconds it's falling at 30 m/s.
Another force that normally applies is air resistance. Lets keep things simple and ignore it. So the main force that applies is the initial firing of the cannon and this gives the shell a velocity. It has two components, a vertical velocity and a horizontal velocity.
As the shell travels through the air the effect of gravity is to reduce the vertical velocity up (it may have started going up, but it will come down) while in our zero air resistance model the horizontal velocity remains unchanged.
This means the range of the shell is purely determined by the initial angle.
The force of the propellant gives the shell an initial velocity of 100 m/s at the angle alpha (in degrees) that the cannon is set to.
The vertical velocity vv = 100 * sin(alpha) and the horizontal velocity vh is 100 * cos(alpha). The range is 2 * vh * vv / 10. (10 being the acceleration due to gravity = 10 m/s).
An angle of 45 degrees gives the maximum range = 2 * 70.71 * 70.71/10 = 1000 m. The lowest angle is 10 degrees so the minimum range is 2 * 17.36 * 98.48/10= 341 m. All the targets are located between 350 and 975 meters away.
Your mission is to amass the maximum number of points by having your cannon fire ten shots in as short as period of time and score the maximum number of points. Note the following:
- The changes changes angle at the speed of 10 degrees per second. Change it by 5 degrees, it takes 0.5 seconds, by 25 degrees it's 2.5 seconds.
- All cannons face right, start at an angle of 22.5 degrees and the first shell is loaded, ready to fire.
- It takes one second to reload each shell. This can happen while the angle is changing. So It will take a minimum of one second between firing to change the angle between one degree and ten degrees because of the reload time.
- The minimum total time will thus be 9 seconds from 1st to last if the first shot is fired without changing the 22.5 degree starting angle otherwise it's ten seconds.
- The blast radius is 5 meters from the point of impact, ie if two targets are ten meters or less apart and your shot lands exactly half way between them, you hit both.
- Your program should take no more than 10 seconds (in elapsed time) to run for all ten shots.
- There's no wind in Flatland- ever!
Your program is supplied with a text file called input.txt in the same directory as your program containing 50 sets of three comma separated values. The first value is the target number (1-50), the 2nd is the distance (between 350 and 975 meters) and the third is the score for that target between 1 and 100.
Example 1,370,5 is target 1 at 370 meters and worth 5 points.
Use this input.txt for testing. A different one will be used for marking.
Write ten or more lines into output.txt in the same location as your exe, one line per target hit. Each line has five comma separated values: your cannon shot number (1-10), angle (in degrees to 4 decimal points), target hit index (1-50), score, time since last shot. (to two decimal points)
If a shot hits one target output one line. If it hits two then output two lines etc. Example
Here shot 1 at 23.5 degrees hit targets 47 and 48 scoring 9 points and taking 1 second. Only show a non zero time for the first shot that hits a target as the second target was hit at the same time. So no matter how many targets are hit there will only be nine or ten non-zero times.
Below this into output.txt write one additional line showing the total number of points and the total time like this:
Total Points = 86 Total Time = 17.54 seconds.
The highest number of points wins. In the event of a tie breaker the lowest total time (the sum of the nine/ten non-zero times) wins.
Thanks to Ken Weinert, Zeljko Peric, Stephen Burris and Ron Spark for entering. Congratulations to first time entrant Stephen Burriss has won and apologies to Zeljko Peric whose entry I received days ago and managed to lose. He came 2nd.
- Stephen Burris(C#) Result=1689, Time = 7.8 (USA)
- Zeljko Peric(C#) Result=1659, Time = 9.2276
- Ken Wienert(C) Result=1379, Time = 10 (USA,58)
- Ron Spain(C++) Result=1379, Time = 10.02 (USA,34)
General Tips on Entering
This is a single page article with tips on things to do and not do when entering challenges. Please read it!
These tips contain code for C,C++ and C# (Not Go, yet) that can do very high precision timing.
RulesThis is for glory only. About.com does not permit prizes to be given.
Please submit your source code and the output file to the email@example.com?subject=Programming Contest 70 email address with the subject line Programming Contest 70.
It must compile with Open Watcom, Microsoft Visual C++ 2010/2012 Express Edition/Microsoft Visual Studio 2010/2012, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition, GCC/G++ and any Google Go compiler. If it doesn't compile, it can't be run so is automatically disqualified.
- Fancy learning C#? Read all About C#
Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is June 2, 2013 (First Sunday after May 31).
The top ten entries in each challenge will be listed, judged on highest score and in the case of a draw, the fastest time. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.
- An index of Every Past Programming Contest on this site