Misja Gynvaela 008

krzaq 1 Comment 
MISJA 008            goo.gl/gg4QcA                  DIFFICULTY: █████████░ [9/10]
┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅

Otrzymaliśmy dość nietypową prośbę o pomoc od lokalnego Instytutu Archeologii.
Okazało się, iż podczas prac remontowych studni w pobliskim zamku odkryto
niewielki tunel. Poproszono nas abyśmy skorzystali z naszego autonomicznego
drona wyposażonego w LIDAR (laserowy skaner odległości zamontowany na obracającej
się platformie) do stworzenia mapy tunelu.

Przed chwilą dotarliśmy na miejsce i opuściliśmy drona do studni. Interfejs I/O
drona znajduje się pod poniższym adresem:

  http://gynvael.coldwind.pl/misja008_drone_output/

Powodzenia!

--

Korzystając z powyższych danych stwórz mapę tunelu (i, jak zwykle, znajdź tajne
hasło). Wszelkie dołączone do odpowiedzi animacje są bardzo mile widziane.

Odzyskaną wiadomość (oraz mapę) umieśc w komentarzu pod tym video :)
Linki do kodu/wpisów na blogu/etc z opisem rozwiązania są również mile widziane!

HINT 1: Serwer może wolno odpowiadać a grota jest dość duża. Zachęcam więc do
cache'owania danych na dysku (adresy skanów są stałe dla danej pozycji i nigdy
nie ulegają zmianie).

HINT 2: Hasło będzie można odczytać z mapy po odnalezieniu i zeskanowaniu
centralnej komnaty.

P.S. Rozwiązanie zadania przedstawie na początku kolejnego livestreama.

Nowa misja, o ile faktycznie trudniejsza, nie zasługuje w mojej opinii na tak wysoką ocenę. Od strony programistycznej nie było w niej nic trudnego (poza błędnym – chyba! – oznaczeniem południa i północy na mapie); całość sprowadzała się do wykorzystania dostarczonego API. Gynvael zachęcał do interaktywnego skorzystania z API (niżej) – czyli stworzenia klienta, który pozwalałby człowiekowi “sterować” dronem.

API

SCAN DRONE v0.17.3
CLASSIFIED DATA. FOR YOUR EYES ONLY.

-- Podręcznik Operatora
 1. Dron posiada zamontowany obrotowy LIDAR.
 2. Dron automatycznie wykonuje skan LIDARem w każdym nowym miejscu.
 3. Skan odbywa się co 10 stopni i zwraca odległość w metrach.
 4. Zerowy stopien oznacza kierunek północny.
 5. Odległość może być niedokładna, szczególnie w okolicy ciasnych przejść.
 6. Zasięg LIDARu to 50m. Powyżej tej odległości zwracany jest "inf".
 7. Skan zawsze odbywa sie na wysokosci 1m nad powierzchnia.
 8. Dron zawsze porusza się o dokładnie jeden metr.
 9. Dron podaje swoją pozycję w metrach na osi zachód-wschód oraz
    północ-południe od ustawionego przez operatora (na stałe) nadajnika.
10. Dron może się poruszać jedynie w kierunkach wschód/zachód/północ/południe.

-- Format Danych
SCAN DRONE v0.17.3
POZYCJA_DRONA_X POZYCJA_DRONA_Y
ODLEGLOSC_NA_KĄCIE_0
ODLEGLOSC_NA_KĄCIE_10
ODLEGLOSC_NA_KĄCIE_20
...
ODLEGLOSC_NA_KĄCIE_350
MOVE_EAST: ADRES_PRZESUWAJĄCY_NA_WSCHÓD_LUB_"not possible"
MOVE_WEST: ADRES_PRZESUWAJĄCY_NA_ZACHÓD_LUB_"not possible"
MOVE_SOUTH: ADRES_PRZESUWAJĄCY_NA_POŁUDNIE_LUB_"not possible"
MOVE_NORTH: ADRES_PRZESUWAJĄCY_NA_PÓŁNOC_LUB_"not possible"

-- Dane
START

Dump

Ja jednak poszedłem w drugą stronę i zdecydowałem się zdumpować całą bazę ruchów. Do tego naskrobałem krótki skrypt w Ruby:

require 'httpclient'
require 'set'
require 'thread'
 
def get_data(n)
    fn = 'g8/%s' % n
    if File.exist? fn
        File.read fn
    else
        link = 'http://gynvael.coldwind.pl/misja008_drone_io/scans/%s' % n
        begin
            b = Time.now
            Thread.current[:c] = HTTPClient.new unless Thread.current[:c]
            body = Thread.current[:c].get_content link
            a = Time.now
            if a - b > 0.1
                puts 'Downloading %s took %.03fs' % [link, a-b]
            end
        rescue => e
            puts 'Download failed: %s' % e
            retry
        end
        File.write fn, body
        body
    end
end
 
def parse_data(data)
    lines = data.each_line.to_a[1..-1]
    pos = lines.first.scan(/\d+/).map(&:to_i)
 
    measured = (0...36).map{ |n|
        m = /(\d\.?\d+)/.match lines[n+1]
        d = m == nil ? nil : m[1].to_f
        [n * 10, d]
    }.to_h
    links = lines[-4..-1].map{|l| l.scan(/[\d\w]+\.txt$/).first }.select{ |n| n }
 
    {
        pos: pos,
        measured: measured,
        links: links,
    }
end
 
class Explorer
 
    def initialize(threads = 1)
        @traversed = Set.new
        @todo = ['68eb1a7625837e38d55c54dc99257a17.txt']
        @data = {}
        @threads = threads
        @mutex = Mutex.new
    end
 
    def traverse loc
        data = get_data loc
        parsed = parse_data data
        @mutex.synchronize{ @traversed.add loc }
        parsed[:links].each do |l|
            @mutex.synchronize{ @todo.push l unless ((@traversed.include? l) or (l !~ /\.txt$/)) }
        end
    end
 
    def execution_thread
        while @mutex.synchronize{ @todo.size } > 0
            link = @mutex.synchronize{ @todo.pop }
            puts 'doing \'%s\'' % link
            traverse link if link =~ /\.txt$/
        end
        puts 'finishing thread...'
    end
 
    def execute
        ts = (1..@threads).map{ execution_thread }
    end
 
end
 
Thread.abort_on_exception = true
 
Explorer.new(20).execute

Tutaj chciałbym zwrócić uwagę na fantastyczny ficzer Ruby: retry. W przypadku gdy, z dowolnego powodu, nie udało się ściągnąć pliku, wystarczyło małe, proste retry, aby powtórzyć cały blok. Bez samodzielnego opakowywania tego w pętle i dodatkowe zmienne. Lekko zmodyfikowany przykład, ku zwiększeniu czytelności:

begin
    body = httpclient.get_content link
rescue => e
    puts 'Download failed: %s' % e
    retry
end

Dzięki zastosowaniu współbieżnego ściągania (dodane trochę później, widać na wykresie w okolicy 2200. sekundy) udało się całkiem szybko ściągnąć wszystkie1 187812 plików z danymi pozycji:

Liczba ściągniętych plików w czasieLiczba ściągniętych plików w czasie

Obsługa danych

Mając już pewny i szybki dostęp do danych można zabrać się za obliczanie bezwzględnych współrzędnych wykrytych ścian:

def data_to_points(node)
    x, y = node[:pos]
    node[:measured]
        .select{ |_, v| v }
        .map{ |k, v|
            a = k * 2 * Math::PI / 360
            [x + Math.sin(a) * v, y + Math.cos(a) * v]
        }
end

Oraz lekko zmodyfikowana metoda explore:

def execute
    n = 1
    begin
        while @todo.size > 0
            # link = @todo.pop # dfs
            link = @todo.shift # bfs
            puts 'doing %s (%s) (@todo.size: %s)' % [link, n, @todo.size]
            n = n + 1
            traverse link if link 
        end
    rescue => e
        puts 'rescue: %s' % e
    end
    File.write 'data.json', @explored.to_json
    puts 'finishing...'
end

Finalnie, generowanie obrazka w Pythonie. Nie wiem dlaczego też tego nie robiłem w Ruby – chyba tylko dlatego, że miałem część kodu gotowego z jakiegoś innego zadania:

import json
from PIL import Image, ImageDraw
 
with open('data.json') as f:
    arr = json.load(f)
 
Mult = 2
 
img = Image.new('RGB', (Mult*1000,Mult*1000), (255,255,255))
 
id = ImageDraw.Draw(img)
 
for stage in arr:
    for p in stage:
        x, y = p
        id.point([(round(Mult*x),round(Mult*y))], (0,0,0))
 
del id
img.save('g8.png')

Nope

Niestety, okazało się, że coś zrobiłem nie tak. Moje porażki widać na screenach ponizej.

FailFail
FailFail
FailFail

Poprawka

Jak widać, albo miałem przesunięcie w pionie, albo strzały lasera wychodziły daleko poza ściany jaskini. Chociaż całkiem ładnie to wygląda – nie o to tutaj chodziło. Winne okazało się odwrotne pojmowanie przestrzeni – północ to dla robota malejące współrzędne y, a nie rosnące, co założyłem. Jeśli wczytamy się w punkt 9. opisu, to faktycznie można to wywnioskować. Wobec tego, wystarczyło więc poprawić wyliczanie współrzędnych ścian:

def data_to_points(node)
    x, y = node[:pos]
    node[:measured]
        .select{ |_, v| v }
        .map{ |k, v|
            a = k * 2 * Math::PI / 360
            [x + Math.sin(a) * v, y - Math.cos(a) * v]
#                                   ^
        }
end

Efektem była poprawna mapa:

WinWin

Sekretna komnata:

SECRET: DR0N3$C4NSECRET: DR0N3$C4N

Extras

Mając już wszystkie elementy pod ręką postanowiłem zwizualizować przejście przez nie wszystkie za pomocą BFS i DFS. Poniżej porównanie liczby lokacji pozostawionych do przejrzenia na później podczas zwiedzania wszystkich dostępnych lokacji w jaskini:

DFS vs. BFSDFS vs. BFS
BFS: przybliżenieBFS: przybliżenie

Więcej wykresów wrzuciłem na fejsa.

Na koniec animacja porównująca eksplorację jaskini za pomocą w.w. metod:

Polska misja Gynvaela 008 – DFS vs BFS

1Tak naprawdę plików było 187814, ale dwa były kompletnie niedostępne dla graczy

One thought on “Misja Gynvaela 008”

  1. Pingback: Gynvael’s mission PL-008 | derfenriswolf's weblog

Leave a Reply

Your email address will not be published.