Partia poszukiwań horrorów

Fabuła : Jimmy zaginął; musimy go znaleźć. Powinniśmy się rozdzielić.

Fabuła : Jimmy już nie żyje.

Ale nasza obsada tego nie wie, więc i tak muszą przeszukać cały obszar. Istnieje N kolumn x M wierszy (1 <= M, N <= 256) siatki komórek, albo oznaczonych jako „S” dla punktu początkowego, „.” dla otwartej przestrzeni lub „#” dla przeszkody. To jest mapa .

Istnieje 0 <= p <= 26 kostiumów , 0 <= q <= 26 statystów i 1 gwiazdka . Wszyscy są początkowo w komórce oznaczonej S.

Zasady

Każda osoba ma promień widzenia pokazany poniżej:

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

Gwiazda jest oznaczona przez „@”, a koszty przez duże litery, zaczynające się od „A”, a dodatki przez małe litery, zaczynające się od „a”. Początkowo promień wzroku otaczający punkt początkowy jest już oznaczony jako przeszukany. Jeśli stanowi to całą otwartą przestrzeń mapy, gra się kończy. Każda tura w następującej kolejności :

1. Każda osoba jednocześnie wykonuje ruch króla (stojąc nieruchomo lub poruszając się do jednej z 8 sąsiednich komórek).
2. Wszystkie komórki w promieniu wzroku wokół każdej osoby są liczone jako przeszukane.
3. Jeśli costar nie widzi nikogo innego, umiera. Jeśli dodatkowy nie widzi ani costara, gwiazdy ani przynajmniej 2 innych statystów, umiera. Dzieje się to jednocześnie - to znaczy, że w jednej turze nie może wystąpić reakcja łańcuchowa śmierci; powyższe warunki są sprawdzane i każdy, kto umrze, umiera od razu.
4. Jeśli przeszukano całą otwartą przestrzeń na mapie, wyszukiwanie jest zakończone.

Notatki

Wiele osób może znajdować się na tym samym placu w dowolnym momencie, a one mogą się widzieć.

Przeszkody nigdy nie utrudniają widzenia, tylko ruch; ludzie widzą się po drugiej ... lawie?

Otwarte przestrzenie na mapie są gwarantowane przez ruchy króla.

Początkowe „S” jest również uważane za otwartą przestrzeń, a nie przeszkodę.

Każdy ruch króla, który wyląduje na otwartej przestrzeni, jest ważny. Na przykład następujący ruch jest legalny:

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

Wkład

Dane wejściowe będą miały format

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

Przykładowe dane wejściowe:

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

i

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

p i q są odpowiednio liczbami kosztów i dodatków.

Wydajność

Wyjściem powinno być, dla każdej tury, wykonane ruchy, z kierunkami wskazanymi przez

789
456
123

Kolejność ruchów nie ma znaczenia, ponieważ wszystkie są wykonywane jednocześnie. Brak wyszczególnienia ruchu dla osoby jest w porządku i jest równoważny z przesunięciem go w kierunku 5. Ruchy powinny być wymienione w następującym formacie:

@9 A2 a2 B7.

„.” oznacza koniec twoich ruchów na turę.

Po przeszukaniu mapy końcowa linia wyników powinna zawierać trzy liczby całkowite, oddzielone spacjami: liczbę zwojów, które zajęło ci ukończenie przeszukiwania planszy, liczbę żywych costarów i liczbę żywych dodatków. Dla pierwszego przykładu wpisz

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

prawidłowe dane wyjściowe:

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

Ostatnia uwaga: gwiazda nie może umrzeć, a otwarta przestrzeń na mapie gwarantuje połączenie, więc wyszukiwanie zawsze się powiedzie.

Punktacja

Twój wynik to łączna liczba zwojów wykonanych w zestawie testów porównawczych; zapraszamy do przesłania własnego przypadku testowego wraz z odpowiedzią. Suma liczby kosztów utrzymania w porównaniu z zestawem wzorcowym zostanie wykorzystana jako remis, aw przypadku remisu zostanie użyta suma liczby dodatków na życie.

Zestaw testowy i kontroler

Obecnie 5 map jest dostępnych online pod adresem https://github.com/Tudwell/HorrorMovieSearchParty/ . Każdy, kto udzieli odpowiedzi, może również przesłać test, który zastrzegam sobie prawo do odrzucenia z dowolnego powodu (jeśli z jakiegoś powodu odrzucę twoją mapę, możesz przesłać inny). Zostaną one dodane do zestawu testowego według własnego uznania.

Sterownik Python (testowany w wersji 2.7.5) jest dostępny na github jako controller.py . Drugi kontroler, kontroler_disp.py , jest identyczny, z tym wyjątkiem, że pokazuje wyniki graficzne podczas wyszukiwania (wymaga biblioteki Pygame).

Zastosowanie :

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

To znaczy:

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

Kontroler ma wyjście (na standardowe wyjście programu ) formularza

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

Jest to numer tury (tura 1 jest przed przeprowadzką), zakończona „.” Lista wszystkich aktorów i ich współrzędnych x, y (lewy górny znak to (0,0)), reprezentacja całego tablica i linia z 40 '. Następnie czeka na dane wejściowe (z twojego programu stdout ) formularza

@9 A2 B7.

Jest to format wyjściowy określony powyżej. Sterownik wysyła „o” dla przeszukanej otwartej przestrzeni, „.” dla otwartej przestrzeni, która nie została przeszukana, i „#” dla przeszkód. Zawiera tylko żyjących ludzi na liście osób i ich współrzędnych oraz śledzi wszystkie zasady gry. Kontroler zakończy pracę, jeśli nastąpi próba nielegalnego ruchu. Jeśli ruchy dla danej tury zakończą wyszukiwanie, wynik nie jest taki jak powyżej; zamiast tego ma formę

Finished in 4 turns
4 1 0

„4 1 0” tutaj oznacza 4 całkowite obroty, 1 żywy costar i 0 żywych dodatków. Nie musisz używać kontrolera; możesz go użyć lub zmodyfikować dla własnego wpisu. Jeśli zdecydujesz się go użyć i napotkasz problemy, daj mi znać.

Dzięki @githubphagocyte za pomoc w napisaniu kontrolera.

Edycja: W przypadku losowego wpisu możesz wybrać dowolny przebieg na określonej mapie jako wynik dla tej mapy. Zauważ, że ze względu na wymagania punktacji, zawsze powinieneś wybierać najmniejszą liczbę tur, następnie najmniej martwych koszarów, a następnie najmniej martwych dodatków dla każdej mapy.

Rubin, Bezpieczeństwo przede wszystkim + BFS + losowość, wynik ≤ 1458

Nie jestem pewien, jak będziesz oceniać losowe zgłoszenia. Jeśli wszystkie odpowiedzi muszą być deterministyczne, daj mi znać, a ja wybiorę ziarno lub całkowicie pozbędę się przypadkowości.

Niektóre funkcje i wady tego rozwiązania:

• Nikt nigdy nie umiera. Na początku grupuję wszystkich aktorów, aby wszyscy byli bezpieczni. Postacie w każdej z tych grup poruszają się zgodnie. To dobrze utrzymuje wszystkich przy życiu, ale nie jest optymalnie wydajne.
• Każda z grup wyszukuje najbliższe niezbadane miejsce na mapie za pomocą wyszukiwania o szerokości pierwszego i wykonuje pierwszy ruch tej gałęzi wyszukiwania. Jeśli między wieloma optymalnymi ruchami występuje remis, wybierany jest losowy. Ma to zapewnić, że nie wszystkie grupy zawsze zmierzają w tym samym kierunku.
• Ten program nie wie o polu widzenia. W rzeczywistości próbuje przenieść się do każdej niezbadanej komórki. Biorąc to pod uwagę, możesz znacznie zwiększyć wydajność, ponieważ odtąd możesz również oszacować jakość każdego ruchu według liczby komórek, które wykryje.
• Program nie śledzi informacji między turami (z wyjątkiem grup aktorów). To sprawia, że ​​działa dość wolno w większych przypadkach testowych. map5.txtwykonanie zajmuje od 1 do 13 minut.

Niektóre wyniki

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

Oto kod:

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)

Istnieje kilka skomentowanych wyników debugowania. Szczególnie if group['@']blok jest dość interesujący, ponieważ drukuje wizualizację danych BFS.

Edycja: Znacząca poprawa prędkości poprzez zatrzymanie BFS, jeśli już został znaleziony lepszy ruch (co było w pewnym sensie celem użycia BFS).