1. Computing
About.com
C / C++ / C#

Discuss in my forum

Programming Challenge 30 - Zapping the Planet's Surface

Deadline December 31 2009

By , About.com Guide

Captain Church has asked you as the new replacement science officer to assist the new colonists on Epsilon-Beta IV by using phaser fire to destroy hostile flora that is slowly growing and threatening the newly created settlements. This will mean zapping a large part of the planet's surface using phasers from the orbiting ship. This will use lots of energy so use the minimum needed.

There are two problems with just simply targeting the area.

  1. All colonists settlements within the target zone must not be hit. Wiping out colonists is not only illegal but can also damage your career prospects.
  2. The targeting system is off-line so you have to program the phaser targeting sequence.

The phaser target zone has been calibrated to the target area which is 0,0.. 99,99 i.e. it is 100 x 100 in size. Only locations in this zone can be targeted. A file of settlement coordinates that you can get here: Settlers.txt, located within this zone will be available for download. All other locations within the target window are valid and must be targeted.

You must provide an output file of phaser target center locations and aperture size. Phaser aperture sizes are 1,3,7,11 and 15. Each target is rectangular in area corresponding to the size: 1x1, 3x3, 7x7, 11x11 and 15x15 but all aperture sizes except 1 suffer from the Kerensky Attenuation Effect which means that the four corner squares are not targeted.

So 3 x 3 targeted on x (across),y (down) only affects the (9-4= 5) + locations in this area:

   +
+ + +
   +
That is (x,y-1), (x-1,y), (x,y), (x+1,y), (x, y+1). 7 x 7 affects this area of (49-4=45) locations.
   + + + + +
+ + + + + + +
+ + + + + + +
+ + + + + + +
+ + + + + + +
+ + + + + + +
   + + + + +
and 11 x 11 (121-4 = 117 Locations) and 15 x 15 (225-4 = 221 Locations) are equally affected. Use any combination of apertures and coordinates but no location containing settlers or outside of the target box must be targeted.

The Challenge

Write a program that generates a set of targets, targeting all locations except those specified in the supplied settlers.txt file. The settlement coordinates are on its own line with two comma separated values. (x,y) E.g.

23,34
11,9
Note: a different settlers.txt file will be used for the challenge and will be located in the same location as your exe. Your program must output a file targets.txt in the same location as your exe. It must consist of single rows each with three comma separated values x, y, s where x and y are the center of the target coordinates and s is the aperture size 1,3,7, 11 and 15. E.g. e.g.
23,34,11
0,0,1
24,80,15
Your program should total the energy cost of operation, lower is better. The costs for each target vary with aperture size and are listed below so an aperture of 7 hits 45 locations (7x7-4) and costs 40. Phasers are more energy efficient when targeting larger areas. (Hint!)
1. 2
3. 6
7. 40
11. 90
15. 150

The Output

You should also output a map.txt file that contains a map of the 100 x 100 locations using the character space for empty locations (there should be none so use it to initialize!), '0' for settlements, '1' for aperture 1s, and sequences of the characters '2'-'9', 'a'..'z' and 'A'..'Z' for the remaining apertures. Eg if the first target is 2,3,15 then the 221 characters in that target all are '2' then the next target will use '3' and so on. Repeat from '2' if you use all the rest up. The idea of these is to make visual inspection easier by distinguishing between the different targets and you are free to improve on it.

Finally please output the total energy used for all targets and the average time taken to calculate all the targets once. If your targets calculation is really fast please loop it so the running time is between 1 and 10 seconds. The winning criteria is lowest energy cost with fastest time in the case of two or more equal energy costs. Please note, no Klingons were hurt during this terraforming...

Timing Code

Final Results

In a stunning change of tactic, Pedro's code's processing ability took a lot longer but managed to find a much lower cost solution. Thanks to both entrants.
  1. Pedro Graca (Portugal) - C 8250 Time(secs) = 173.812
  2. Gaurav Sarode (USA, 26) - C++ 8844 Time(secs) = 0.00387

More Programming Challenges

©2013 About.com. All rights reserved.