Plot: Jimmy is missing; we have to find him. We should split up.
Plot twist: Jimmy is already dead.
But, our cast doesn't know that, so they need to search the whole area anyway. There is an N columns x M rows (1<=M,N<=256) grid of cells, either marked as "S" for the starting point, "." for open space, or "#" for an obstacle. This is the map.
There are 0<=p<=26 costars, 0<=q<=26 extras, and 1 star. Everyone is initially in the cell marked S.
Each person has a sight radius shown below:
... ..... ..@.. ..... ...
The star is denoted by "@", the costars by capital letters, starting with "A", and the extras by lowercase letters, starting with "a". Initially, the sight radius surrounding the starting point is already marked as searched. If this constitutes the entire open space of the map, the game ends. Each turn, in the following order:
- Each person simultaneously makes a king move (either standing still, or moving to one of the 8 neighboring cells).
- All of the cells in the sight radius around each person are counted as searched.
- If a costar cannot see anyone else, she dies. If an extra cannot see either a costar, the star, or at least 2 other extras, he dies. These happen simultaneously -- that is, there can be no chain reaction of deaths on a single turn; the above conditions are checked, and everyone who is going to die dies at once.
- If all of the open space on the map has been searched, the search is over.
Multiple people can be on the same square at any point, and these people can see each other.
Obstacles never impede sight, only movement; people can see each other across the, er... lava?
The open spaces on the map are guaranteed to be connected by king moves.
The initial "S" is also considered to be open space, rather than an obstacle.
Any king move that lands on an open space is valid. For instance, the following move is legal:
.... .... .@#. ---> ..#. .#.. .#@. .... ....
The input will be in the format
N M p q [N cols x M rows grid with characters ".", "#", and "S"]
6 5 0 0 ...... ...... ..S... ...... ......
9 9 1 1 S.......# .......## ......##. ..#####.. ...##.... ...##.... ...#..... ....#..#. .........
p and q are the numbers of costars and extras, respectively.
The output should be, for each turn, the moves that are made, with directions indicated by
789 456 123
The order of the moves does not matter, as they are all enacted simultaneously. Not listing a move for a person is fine, and is equivalent to moving him in direction 5. Moves should be listed in the following format:
@9 A2 a2 B7.
"." denotes the end of your moves for a turn.
After the map has been searched, the final line of output should be three integers, separated by spaces: the number of turns that it took you to finish searching the board, the number of living costars, and the number of living extras. For the first example input
6 5 0 0 ...... ...... ..S... ...... ......
the following is valid output:
@4. @6. @6. @6. 4 0 0
A final note: the star cannot die and the open space on the map is guaranteed to be connected, so the search will always succeed eventually.
Your score is the total number of turns taken over a set of benchmark tests; you're welcome to submit your own test case along with your answer. The sum of the number of living costars over the benchmark set will be used as a tie-breaker, and in the event there is still a tie, the sum of the number of living extras will be used.
Test Set and Controller
Currently, 5 maps are online at https://github.com/Tudwell/HorrorMovieSearchParty/. Anyone submitting an answer may also submit a test case, which I reserve the right to reject for any reason (if I reject your map for some reason, you may submit another). These will be added to the test set at my discretion.
A Python (tested in 2.7.5) controller is provided on github as controller.py. A second controller there, controller_disp.py, is identical except that it shows graphical output during the search (requires Pygame library).
python controller.py <map file> <your execution line>
python controller.py map1.txt python solver.py map1.txt
The controller has output (to your program's stdin) of the form
Turn 1 @:2,3 A:2,3 B:2,3. ##...## #ooo..# ooooo.. ooooo.. ooooo.. #ooo... ##..... ###.... ----------------------------------------
This is the turn number (turn 1 is before you have moved), a '.'-terminated list of all the actors and their x,y coordinates (the upper left character is (0,0)), a representation of the entire board, and a line with 40 '-'s. It then waits for input (from your program's stdout) of the form
@9 A2 B7.
This is the output format specified above. The controller outputs a 'o' for open space that has been searched, '.' for open space that has not been searched, and '#' for obstacles. It includes only living people in its list of people and their coordinates, and tracks all rules of the game. The controller will exit if an illegal move is attempted. If the moves for a given turn finish the search, the output is not as above; instead it is of the form
Finished in 4 turns 4 1 0
"4 1 0" here denotes 4 total turns, 1 living costar, and 0 living extras. You do not need to use the controller; feel free to use it or modify it for your own entry. If you decide to use it and encounter problems, let me know.
Thanks to @githubphagocyte for helping me write the controller.
Edit: For a randomized entry, you can choose any run on a particular map as your score for that map. Note that due to the scoring requirements, you should always choose the fewest turns, then the fewest dead costars, then the fewest dead extras for each map.