Horror Movie Search Party

Question

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.

The Rules

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:

1. Each person simultaneously makes a king move (either standing still, or moving to one of the 8 neighboring cells).
2. All of the cells in the sight radius around each person are counted as searched.
3. 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.
4. If all of the open space on the map has been searched, the search is over.

Notes

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:

....      ....
.@#. ---> ..#.
.#..      .#@.
....      ....

Input

The input will be in the format

N M p q
[N cols x M rows grid with characters ".", "#", and "S"]

Sample inputs:

6 5 0 0
......
......
..S...
......
......

and

9 9 1 1
S.......#
.......##
......##.
..#####..
...##....
...##....
...#.....
....#..#.
.........

p and q are the numbers of costars and extras, respectively.

Output

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.

Scoring

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).

Usage:

python controller.py <map file> <your execution line>

I.e.:

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.

Answer 1

Ruby, Safety First + BFS + Randomness, Score ≤ 1458

I'm not sure how you'll be scoring random submissions. If all answers have to be deterministic, let me know and I'll pick a seed or get rid of the randomness altogether.

Some features and shortcomings of this solution:

• No one ever dies. At the start I group all the actors such that everyone is safe. The characters in each of these groups move in unison. That's good for keeping everyone alive but not optimally efficient.
• Each of the groups searches for the nearest unexplored spot on the map via breadth-first search and takes the first move of that branch of the search. If there is tie between multiple optimal moves a random one is picked. This is to ensure that not all groups always head in the same direction.
• This program doesn't know about field-of-view. It actually tries to move to every unexplored cell. Taking this into account might considerably increase the performance, since then you could also quantify the quality of each move by how many cells it will uncover.
• The program doesn't keep track of information between turns (except the actor groups). That makes it quite slow on the larger test cases. map5.txt takes between 1 and 13 minutes to complete.

Some results

Map     Min turns    Max turns
map1        46           86
map2        49          104
map3       332          417
map4       485          693
map5       546          887

Now here is the code:

start = Time.now

map_file = ARGV.shift
w=h=p=q=0
File::open(map_file, 'r') do |file|
    w,h,p,q = file.gets.split.map(&:to_i)
end

costars = p > 0 ? (1..p).map {|i| (i+64).chr} : []
extras = q > 0 ? (1..q).map {|i| (i+96).chr} : []
groups = []

costars.zip(extras).each do |costar, extra|
    break unless extra
    groups << (costar + extra)
    costars.delete(costar)
    extras.delete(extra)
end

costars.each_slice(2) {|c1, c2| groups << (c1 + (c2 || '@'))} unless costars.empty?
extras.each_slice(3) {|c1, c2, c3| groups << (c1 + (c2 || '') + (c3 || '@'))} unless extras.empty?
groups << '@' unless groups.join['@']

#$stderr.puts groups.inspect


directions = {
    1 => [-1, 1],
    2 => [ 0, 1],
    3 => [ 1, 1],
    4 => [-1, 0],
    5 => [ 0, 0],
    6 => [ 1, 0],
    7 => [-1,-1],
    8 => [ 0,-1],
    9 => [ 1,-1]
}

loop do
    break unless gets # slurp turn number
    coords = {}
    input = gets
    input.chop.chop.split.each{|s| actor, c = s.split(':'); coords[actor] = c.split(',').map(&:to_i)}
    #$stderr.puts input
    #$stderr.puts coords.inspect
    map = []
    h.times { map << gets.chomp }

    gets # slurp separator
    moves = groups.map do |group|
        x, y = coords[group[0]]
        distances = {[x,y] => 0}
        first_moves = {[x,y] => nil}
        nearest_goal = Float::INFINITY
        best_move = []
        active = [[x,y]]
        while !active.empty?
            coord = active.shift
            dist = distances[coord]
            first_move = first_moves[coord]
            next if dist >= nearest_goal
            [1,2,3,4,6,7,8,9].each do |move|
                dx, dy = directions[move]
                x, y = coord
                x += dx
                y += dy
                next if x < 0 || x >= w || y < 0 || y >= h || map[y][x] == '#'
                new_coord = [x,y]
                if !distances[new_coord]
                    distances[new_coord] = dist + 1
                    first_moves[new_coord] = first_move || move
                    active << new_coord if map[y][x] == 'o'
                end

                if dist < distances[new_coord]
                    distances[new_coord] = dist + 1
                    first_moves[new_coord] = first_move || move
                end

                if map[y][x] == '.'
                    if dist + 1 < nearest_goal
                        nearest_goal = dist + 1
                        best_move = [first_moves[new_coord]]
                    elsif dist + 1 == nearest_goal
                        best_move << first_moves[new_coord]
                    end
                end
            end
        end

        #if group['@']
        #    distances.each{|k,v|x,y=k;map[y][x]=(v%36).to_s(36)}
        #    $stderr.puts map
        #end

        dir = best_move.sample
        group.chars.map {|actor| actor + dir.to_s}
    end * ' '
    #$stderr.puts moves
    puts moves
    $stdout.flush
end

#$stderr.puts(Time.now - start)

There are a few commented out debug outputs in there. Especially the if group['@'] block is quite interesting because it prints out a visualisation of the BFS data.

Edit: Significant speed improvement, by stopping the BFS if a better move has already been found (which was kinda the point of using BFS in the first place).