Fiesta de búsqueda de películas de terror

Trama : Jimmy está desaparecido; Tenemos que encontrarlo. Deberíamos separarnos.

Giro de la trama : Jimmy ya está muerto.

Pero nuestro elenco no lo sabe, por lo que deben buscar en toda el área de todos modos. Hay una cuadrícula de celdas N columnas x M filas (1 <= M, N <= 256), marcadas como "S" para el punto de partida "." para espacios abiertos, o "#" para un obstáculo. Este es el mapa .

Hay 0 <= p <= 26 costeros , 0 <= q <= 26 extras y 1 estrella . Todos están inicialmente en la celda marcada con S.

Las normas

Cada persona tiene un radio de visión que se muestra a continuación:

 ...
.....
..@..
.....
 ...

La estrella se denota con "@", los costeros con letras mayúsculas, que comienzan con "A", y los extras con letras minúsculas, que comienzan con "a". Inicialmente, el radio de visión que rodea el punto de partida ya está marcado como buscado. Si esto constituye todo el espacio abierto del mapa, el juego termina. Cada turno, en el siguiente orden :

1. Cada persona simultáneamente hace un movimiento real (ya sea parado o moviéndose a una de las 8 celdas vecinas).
2. Todas las celdas en el radio de visión alrededor de cada persona se cuentan como buscadas.
3. Si un coprotagonista no puede ver a nadie más, ella muere. Si un extra no puede ver a un coprotagonista, la estrella o al menos a otros 2 extras, él muere. Esto sucede simultáneamente , es decir, no puede haber una reacción en cadena de muertes en un solo turno; se verifican las condiciones anteriores, y todos los que van a morir mueren a la vez.
4. Si se ha buscado todo el espacio abierto en el mapa, la búsqueda ha terminado.

Notas

Varias personas pueden estar en el mismo cuadrado en cualquier punto, y estas personas pueden verse entre sí.

Los obstáculos nunca impiden la vista, solo el movimiento; la gente puede verse a través de, er ... ¿lava?

Los espacios abiertos en el mapa están garantizados para estar conectados por movimientos de rey.

La "S" inicial también se considera espacio abierto, en lugar de un obstáculo.

Cualquier movimiento rey que aterrice en un espacio abierto es válido. Por ejemplo, el siguiente movimiento es legal:

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

Entrada

La entrada estará en el formato

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

Entradas de muestra:

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

y

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

p y q son los números de costeros y extras, respectivamente.

Salida

La salida debe ser, para cada turno, los movimientos que se realizan, con direcciones indicadas por

789
456
123

El orden de los movimientos no importa, ya que todos se ejecutan simultáneamente. No enumerar un movimiento para una persona está bien, y es equivalente a moverlo en la dirección 5. Los movimientos deben estar listados en el siguiente formato:

@9 A2 a2 B7.

"." denota el final de tus movimientos por un turno.

Una vez que se ha buscado el mapa, la línea final de salida debe ser tres enteros, separados por espacios: la cantidad de turnos que le llevó a terminar de buscar en el tablero, la cantidad de costas vivas y la cantidad de extras vivos. Para el primer ejemplo de entrada

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

lo siguiente es salida válida:

@4.
@6.
@6.
@6.
4 0 0

Una nota final: la estrella no puede morir y se garantiza que el espacio abierto en el mapa esté conectado, por lo que la búsqueda siempre tendrá éxito.

Tanteo

Su puntaje es el número total de turnos realizados en un conjunto de pruebas de referencia; puede enviar su propio caso de prueba junto con su respuesta. La suma del número de costars vivos sobre el conjunto de referencia se usará como un desempate, y en caso de que aún haya un empate, se usará la suma del número de extras vivos.

Conjunto de prueba y controlador

Actualmente, 5 mapas están en línea en https://github.com/Tudwell/HorrorMovieSearchParty/ . Cualquier persona que envíe una respuesta también puede presentar un caso de prueba, que me reservo el derecho de rechazar por cualquier motivo (si rechazo su mapa por algún motivo, puede enviar otro). Estos se agregarán al conjunto de prueba a mi discreción.

Se proporciona un controlador Python (probado en 2.7.5) en github como controller.py . Un segundo controlador allí, controller_disp.py , es idéntico, excepto que muestra una salida gráfica durante la búsqueda (requiere la biblioteca Pygame).

Uso :

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

Es decir:

python controller.py map1.txt python solver.py map1.txt

El controlador tiene salida (al stdin de su programa ) del formulario

Turn 1
@:2,3 A:2,3 B:2,3.
##...##
#ooo..#
ooooo..
ooooo..
ooooo..
#ooo...
##.....
###....
----------------------------------------

Este es el número de turno (el turno 1 es antes de que te hayas movido), una lista '.'-terminada de todos los actores y sus coordenadas x, y (el carácter superior izquierdo es (0,0)), una representación de todo tablero, y una línea con 40 '-'s. Luego espera la entrada (del stdout de su programa ) del formulario

@9 A2 B7.

Este es el formato de salida especificado anteriormente. El controlador emite una 'o' para el espacio abierto que se ha buscado, '.' para espacios abiertos que no se han buscado, y '#' para obstáculos. Incluye solo personas vivas en su lista de personas y sus coordenadas, y rastrea todas las reglas del juego. El controlador saldrá si se intenta un movimiento ilegal. Si los movimientos para un turno dado finalizan la búsqueda, la salida no es como la anterior; en cambio es de la forma

Finished in 4 turns
4 1 0

"4 1 0" aquí denota 4 turnos totales, 1 costar vivo y 0 extras vivos. No necesita usar el controlador; siéntase libre de usarlo o modificarlo para su propia entrada. Si decides usarlo y tienes problemas, avísame.

Gracias a @githubphagocyte por ayudarme a escribir el controlador.

Editar: para una entrada aleatoria, puede elegir cualquier ejecución en un mapa en particular como su puntaje para ese mapa. Tenga en cuenta que debido a los requisitos de puntuación, siempre debe elegir la menor cantidad de turnos, luego la menor cantidad de costeros muertos, y la menor cantidad de extras muertos para cada mapa.

Rubí, seguridad primero + BFS + aleatoriedad, puntaje ≤ 1458

No estoy seguro de cómo puntuarás las presentaciones aleatorias. Si todas las respuestas tienen que ser deterministas, avíseme y elegiré una semilla o eliminaré la aleatoriedad por completo.

Algunas características y defectos de esta solución:

• Nadie muere nunca. Al principio, agrupo a todos los actores para que todos estén a salvo. Los personajes de cada uno de estos grupos se mueven al unísono. Eso es bueno para mantener a todos vivos, pero no es óptimamente eficiente.
• Cada uno de los grupos busca el punto inexplorado más cercano en el mapa a través de una búsqueda de amplitud y realiza el primer movimiento de esa rama de la búsqueda. Si hay un empate entre múltiples movimientos óptimos, se elige uno aleatorio. Esto es para asegurar que no todos los grupos se dirijan siempre en la misma dirección.
• Este programa no sabe sobre el campo de visión. Realmente trata de moverse a cada celda inexplorada. Tener esto en cuenta podría aumentar considerablemente el rendimiento, ya que también podría cuantificar la calidad de cada movimiento según la cantidad de celdas que descubrirá.
• El programa no realiza un seguimiento de la información entre turnos (excepto los grupos de actores). Eso lo hace bastante lento en los casos de prueba más grandes. map5.txtTarda entre 1 y 13 minutos en completarse.

Algunos resultados

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

Ahora aquí está el código:

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)

Hay algunas salidas de depuración comentadas allí. Especialmente el if group['@']bloque es bastante interesante porque imprime una visualización de los datos BFS.

Editar: Mejora significativa de la velocidad, al detener el BFS si ya se ha encontrado un mejor movimiento (que fue el punto de usar BFS en primer lugar).