W ramach naszej witryny stosujemy pliki cookies zgodnie z Polityką Cookie. Zasady przechowywania lub dostępu plików cookie możesz zmienić w swojej przeglądarce.
X

mywebcases
.com



Blog

Geekowy blog o łamigłówkach, JavaScript i wszystkim, co ciekawe.

Cheat Champ: Zadanie 6 - Labirynt ZEN

Cheat Champ - Cheat Champ -
napisał Jakub Caban

Szóste zadanie z Cheat Champ, czyli labirynt ZEN. Przyjemne i proste, gdyby nie wredne miny... Jak dojść bez błędów do końca? Na to pytanie rychło odpowiadam.

Jeśli chcesz wypróbować podawane rozwiązania bądź zmierzyć się z zadaniami - zapraszam do aplikacji treningowej.

Nie ukrywam. Teraz zrobi się na prawdę trudno. Tak na prawdę pierwsze 5 zadań to w założeniach miała być rozgrzewka. A te ostatnie trzy miały wyłonić prawdziwego kozaka i zwycięzcę Cheat Champ. Niejako się to zgadza, patrząc na dane z zadania 6. Z 21 osób, które dotarły do tego etapu zaledwie 9 przeszło dalej.

Tradycyjnie już zliczałem rozpoczęcia gry (ręcznie bądź automatycznie). I tu się robi na prawdę ciekawie. Najwięcej bowiem próbowaliście przejść labirynt aż... 3387 razy! Totalne szaleństwo! Minimum to zaledwie 3 razy, a średnia wynosi 317.52. Zgodnie z przewidywaniami zupełnie się to zmienia, kiedy spojrzymy tylko na tych, którym udało sie przejść dalej. Ilości prób znajdują się u nich w przedziale od 27 do 227, ze średnią w punkcie 85.89.

Przy czasach rozwiązania jak zwykle ucinam z góry przez 12 godzin (czas dłuższe zawierają na pewno w sobie sen, więc są nie miarodajne). Tak więc najszybsza osoba zrobiła to zadanie w godzinę 49 minut i 5 sekund. Najdłużej natomaist to zadanie zatrzymało kogoś na 5 godzin 22 minuty i 34 sekundy. Średnio patrzyliście na ten etap przez 3 godziny 32 minuty i 55 sekund.

6. Labirynt ZEN

Na czym polegało samo zadanie? Znów przytoczę po prostu opis zadania z aplikacji konkursowej:

Wszystkie memy schroniły się w landzie ZEN! Podążaj ich śladami przez labirynt, na którym czyhają różne niebezpieczeństwa. Najwytrwalsi podróżnicy będą musieli jeszcze odpowiedzieć na pytanie strażnika ZEN. Po tej inicjacji będą mogli zaznać spokoju w krainie ZEN ze wszystkimi memami!

Zasady gry: Po kliknięciu "rozpocznij" na ekranie pojawi się labirynt. Poruszaj się po nim strzałkami. Miny zmieniają działanie niektórych strzałek. Wejście do labiryntu znajduje się w górnym lewym rogu. Cel znajduje się w dolnym prawym rogu. Po przejściu labiryntu należy poprawnie odpowiedzieć na pytanie dotyczące oferty zenbox.pl.

Zasady zaliczenia: Przejdź cały labirynt w czasie poniżej sekundy używając najmniejszą możliwą liczbę naciśnięć klawiszy. Tolerancja sieciowa: 2s

6

Także tego... Jak się za to w ogóle zabrać? W tym wypadku warto spróbować przejść ręcznie, aby zobaczyć, o co tak na prawdę chodzi. I o tyle, o ile znalezienie optymalnej drogi jest łatwe przy tak generowanych labiryntach, o tyle kompletna zmiana sterowania po wejściu na minę bardzo skutecznie uniemożliwia wykonanie tego przy minimalnej wymaganej liczbie naciśnięć klawiszy. Już nie mówiąc o czasie poniżej sekundy!

Plan jest więc klarowny - pobrać dane o labiryncie, napisać skrypt, który przejdzie ten labirynt i na koniec przepisać tą trasę na język klawiszy z uwzględnieniem min. Nie brzmi to wcale przyjemnie, ale chociaż już wiemy, do czego dążymy...

Ze skryptu ze strony potrzebujemy więc wyciągnąć informacje na temat tego, gdzie są ściany oraz miny i jak te drugie zmieniają mapowanie klawiszy. Dla referencji cały kod gry dostępny w aplikacji prezentuje się następująco:

var gel = null;
 function gotozen(){
 gel = document.getElementById("game");
 gel.innerHTML = "";
 callMe("zenland.php?b=s", function(o){
 if(!o.html){
 alert('Errorek :(');
 reload();
 return;
 }
 new Preloader(o.html, function(html){
 gel.innerHTML = html;
 zenmove.Init(o.maze, o.mines);
 timer.tInit();
 });
 }, true);
 var zenmove = {
 el: null,
 x: 0,
 y: 0,
 top: 24,
 left: 220,
 maze: null,
 mines: null,
 mutation: 0,
 data: [],

 Init: function(maze, mines){
 this.el = document.getElementById("zenmove");
 this.maze = maze;
 this.mines = mines;
 document.onkeydown = function(e){ zenmove.Key(e); };
 },
 Key: function(e){
 if(!e) e = window.event;
 var unicode = e.keyCode ? e.keyCode : e.charCode;
 switch(unicode){
 case 40:
 case 39:
 case 38:
 case 37:
 this.Prevent(e);
 this.data.push(unicode);
 this.Move(this.Mutate(unicode));
 break;
 }
 },
 Prevent: function(e){
 e.returnValue = false;
 if(e.preventDefault) e.preventDefault();
 },
 Move: function(side){
 var f = this.maze[this.x+1][this.y+1];

 switch(side){
 case "N":
 if((f&1) == 0 && this.y > 0){
 this.y--;
 }
 break;
 case "S":
 if((f&2) == 0 && this.y < 17){ 
 this.y++; 
 }
 break;
 case "W":
 if((f&4) == 0 && this.x > 0){
 this.x--;
 }
 break;
 case "E":
 if((f&8) == 0 && this.x < 17){
 this.x++;
 }
 break;
 }
 this.el.style.left = (this.left+this.x*20)+"px";
 this.el.style.top = (this.top+this.y*20)+"px";
 if(this.mines[this.x+"x"+this.y]){
 this.mutation = this.mines[this.x+"x"+this.y];
 }
 if(this.x == 17 && this.y == 17){
 this.Finish();
 }
 },
 Mutate: function(uni){
 var perm = this.mutation;
 var sides = ["N","E","S","W"];
 if(uni == 38){
 return sides[Math.floor(perm/6)];
 }
 sides.splice(Math.floor(perm/6), 1);
 perm = perm%6;
 if(uni == 39){
 return sides[Math.floor(perm/2)];
 }
 sides.splice(Math.floor(perm/2), 1);
 perm = perm%2;
 if(uni == 40){
 return sides[perm];
 }
 return sides[(perm+1)%2];
 },
 Finish: function(){
 timer.tStop();
 var t = timer.tGet();
 callMePost("zenland.php?b=f&t="+t, "data="+this.data.join("`"), function(o){
 gel.innerHTML = o.html;
 }, true);
 }
 }
 }
 function SendAnswer(){
 var a = 0;
 var as = [8,16,32];
 for(var i=0; i<as.length; i++){
 if(document.getElementById("vcpu"+as[i]).checked){
 a = as[i];
 }
 }
 callMe("zenland.php?b=a&a="+a, function(o){
 gel.innerHTML = o.html;
 }, true);
 }

Nie wygląda ani kusząco, ani przyjemnie. Ale wierzcie mi lub nie - rozwiązanie też nie będzie miało 10 linijek ładnego kodu. No - chyba, że ktoś takie znalazł...?

Zacznijmy więc od podstaw i po kolei analizujmy te elementy, które musimy wykonać. Przede wszystkim dane - jak zwykle w Cheat Champ rozpoczynamy rozwiązywanie przez wysłanie zapytania AJAX do zenland.php?b=s. W odpowiedzi mamy obiekt, który posiada kilka atrybutów. o.html najmniej nas interesuje, ale dla doznań graficznych zawsze możemy go wrzucić do #game. o.maze zawiera w jakiś sposób informacje na temat możliwości poruszania się po labiryncie. Natomiast o.mines zawiera w jakiś sposób informacje o minach. Ta analiza wynika z linii 13 (oraz zdrowego rozsądku co do nazewnictwa bądź podejrzenia linii 30-31 itd.).

Żeby zachować ciągłość w omawianiu trochę nie po kolei opiszę dalsze wnioski, ale za to po kolei będą kroki do rozwiązania. Przede wszystkim - aby rozwiązać labirynt automatycznie musimy wiedzieć, gdzie są ściany. Bądź konkretniej - musimy wiedzieć, z którego pola, na które możemy przejść. Tak więc przyglądamy się metodzie Move obiektu zenmove, w szczególności liniom 56-76. Na potrzeby chwili ustalmy, że znajdujemy się na polu o współrzędnych (x, y) takich, że start jest na pozycji (0,0). Widzimy, że dane na temat tego pola znajdują się w maze[x+1][y+1] (linia 53). Wartość z tego pola (idąc za listingiem) nazwijmy f. I teraz co następuje: jeśli f&1, to nie możemy iść na północ; jeśli f&2, to nie możemy iść na południe; jeśli f&4, to nie możemy iść na zachód; jeśli f&8, to nie możemy iść na wschód. Do tego warunki brzegowe (x lub y równe 0 bądź 17) dają pełną informację na temat kształtu labiryntu.

Wiemy, które pole z którym ma połączenie (nomenklatura nie przypadkowa!). Każdy, kto kiedyś miał w ręku książkę z "algorytmy" w tytule w tym momencie ma na pewno jedno skojarzenie. Jedno i tylko jedno. I to właśnie jedno jedyne poprawne. Mianowicie - GRAF! Tak, to jest słowo-klucz na tym etapie. Budujemy więc graf, w którym wierzchołkami są pola na labiryncie, a połączeniami są możliwości przejścia w jednym kroku z jednego pola do drugiego. Jak to zrobić? Najlepiej stworzyć dla każdego wierzchołka (pola) obiekt przechowujący w swoim atrybucie referencje do obiektów sąsiadów (czyli wierzchołków, z którymi ma połączenie). Ja dla swojej wygody już na tym etapie buduję drzewo z korzeniem w punkcie startu i przechowuję zawsze referencję do rodzica. Zaraz wszyscy się przekonamy czemu.

Zastanówmy się teraz - czym jest rozwiązanie naszego zadania? Jest drogą od punktu (0,0) do punktu (17, 17). Jest więc najkrótszym łańcuchem o początku w starcie i końcu w mecie. Dodatkowo tu jest łatwo - labirynty generowane w tym zadaniu zawsze miały tylko jedną drogę przejścia bez pętli. A jak szukać optymalnego połączenia wierzchołków w grafie? Wystarczy na przykład przeszukać go wszerz. Albo wiedząc, że dowolne rozwiązanie bez pętli zapewnia rozwiązanie optymalne wystarczy przeszukać go dowolnie (również wgłąb). I tutaj wychodzi moja chytrość z budowaniem drzewa z korzeniem w starcie. Budowa tego drzewa jest już przeszukaniem grafu, więc jak tylko napotkamy wierzchołek z metą, znamy drogę łączącą start z metą, która nie zawiera pętli, więc jest optymalna.

Mając tą drogę jako np. tablica kolejnych wierzchołków (pól) możemy bez problemu rozczytać ją we współrzędnych NSEW opisując po prostu każdy kolejny ruch jako przesunięcie na północ, południe, wschód lub zachód. Gdyby nie miny moglibyśmy to przełożyć na kod klawiatury za pomocą prostego klucza (z keyCode klawiatury). Teraz trzeba rozszyfrować chytry algorytm działania min. Na szczęście jest na to prosta droga. Spójrzmy na linie 86-103, czyli metodę Mutate. Wystarczy ją sobie wziąć i przekopiować, podrzucając za każdym razem zamiast this.mutation aktualna mutację (czyli wartość z tablicy mine) ostatnio napotkanej miny. Następnie chcąc wykonać ruch w kierunku X wykonujemy ją 4 razy dla parametrów 37,38,39,40 i sprawdzamy, który zwrócił pożądany efekt.

Jednak dla ambitniejszych wyjaśnię, w jaki sposób te permutacje tutaj były wykorzystane. Użyłem porządek permutacji, który o ile się nie mylę, nazywa się leksykalnym. Działanie opiszę na przykładzie tu wykorzystywanym - zawsze permutowałem tablicę ["N","E","S","W"] przy początkowej wartości odpowiadającej keyCode, czyli [38,39,40,37] (taki troling z kolejnością). Numer permutacji określmy jako M (to jest ta wartość z mines). I teraz bierzemy tą wartość i dzielimy przez 6 (to jest 3!, bo tyle permutacji jest pozostałych elementów), zaokrąglając w dół. I uznajemy, że pierwsza wartość (w tym wypadku 38) odpowiada elementowi o danym indeksie (czyli Math.floor(M/6)). Usuwamy pierwszą wartość (38) oraz wartość, na którą wskazuje i powtarzamy algorytm dla 3 pozostałych wartości oraz M=M%6. Rozwiązanie wzorcowe zawiera właśnie to podejście do tematu permutacji dla referencji.

Kiedy już mamy określoną ścieżkę i za każdym razem wiemy, jaki klawisz odpowiada danemu ruchowi, pozostaje wysłać ją na serwer. Czyli wysyłamy zapytanie do zenland.php?b=f&t=1 (t=1 wmawia serwerowi, że zrobiliśmy to w 1ms - można dopasować, jeśli nie łapiemy się w margines sieciowy), wysyłając w danych POST w kluczu data kody kolejnych klawiszy oddzielone znakiem ` (bo czemu nie).

Jeśli wszystko pójdzie dobrze dostaniemy pytanie, na które odpowiedź łatwo znaleźć w internecie, więc nie będę się na jego temat rozwodził.

Poniżej, jak zwykle, rozwiązanie wzorcowe zawierające wszystkie opisane elementy w ramach obiektu Solver. Należy je skopiować do konsoli (np. Firebug) i uruchomić na ekranie początkowym zadania, pamiętając o dobrym kontekście wywołania (w Firebug cd(frames[0]) wchodzi do niego z poziomu FB).

var gel = document.getElementById("game");
callMe("zenland.php?b=s", function(o){
 if(!o.html){
 alert('Errorek :(');
 reload();
 return;
 }
 gel.innerHTML = o.html;
 Solver.Init(o.maze, o.mines);
}, true);
var Solver = {
 graph: {},
 mutation: {
 "N": 38,
 "E": 39,
 "S": 40,
 "W": 37
 },
 data: [],
 
 Init: function(maze, mines){
 for(var x=0; x<18; x++){
 this.graph[x] = {};
 for(var y=0; y<18; y++){
 this.graph[x][y] = {
 x: x,
 y: y,
 maze: maze[x+1][y+1],
 parent: null,
 children: []
 };
 }
 }
 var stack = [this.graph[0][0]], leaf;
 while(leaf = stack.shift()){
 var add = [];
 if((leaf.maze & 1) == 0 && leaf.y > 0)
 add.push([leaf.x, leaf.y-1]);
 if((leaf.maze & 2) == 0 && leaf.y < 17)
 add.push([leaf.x, leaf.y+1]);
 if((leaf.maze & 4) == 0 && leaf.x > 0)
 add.push([leaf.x-1, leaf.y]);
 if((leaf.maze & 8) == 0 && leaf.x < 17)
 add.push([leaf.x+1, leaf.y]);
 var v;
 for(var i=0; v=add[i]; i++){
 var c = this.graph[v[0]][v[1]];
 if(leaf.parent != c){
 this.graph[v[0]][v[1]].parent = this.graph[leaf.x][leaf.y];
 this.graph[leaf.x][leaf.y].children.push(this.graph[v[0]][v[1]]);
 stack.push(this.graph[v[0]][v[1]]);
 }
 }
 }
 var road = [[17,17]];
 var field = this.graph[17][17];
 while(field.x != 0 || field.y != 0){
 field = field.parent
 road.push([field.x, field.y]);
 }
 road.reverse();
 var move = [];
 for(var i=1; i<road.length; i++){
 var last = road[i-1], now = road[i];
 switch(now[0]-last[0]+2*(now[1]-last[1])){
 case 1:
 move.push("E");
 break;
 case -1:
 move.push("W");
 break;
 case 2:
 move.push("S");
 break;
 case -2:
 move.push("N");
 break;
 }
 }
 var xy;
 for(var i=1; xy=road[i]; i++){
 this.data.push(this.mutation[move[i-1]]);
 if(mines[xy[0]+"x"+xy[1]]){
 this.Mutate(mines[xy[0]+"x"+xy[1]]);
 }
 }
 callMePost("zenland.php?b=f&t=1", "data="+this.data.join("`"), function(o){
 gel.innerHTML = o.html;
 }, true);
 },
 Mutate: function(perm){
 //38,39,40,37
 var sides = ["N","E","S","W"];
 var i = Math.floor(perm/6);
 this.mutation[sides[i]] = 38;
 sides.splice(i, 1);
 perm = perm%6;
 i = Math.floor(perm/2);
 this.mutation[sides[i]] = 39;
 sides.splice(i, 1);
 perm = perm%2;
 this.mutation[sides[perm]] = 40;
 this.mutation[sides[(perm+1)%2]] = 37;
 }
}

 

Co Wy na to?

 

Bezsprzecznie okrzyknęliście to zadanie najtrudniejszym dając mu średnią ocenę trudności 4.50. Było też na pewno dla Was ciekawe - tu również ocena 4.50. Napisaliście tylko dwie opinie do tego zadania. Przytocze więc obie.

Kasjan napisał:

Już sama forma zapisania labiryntu mnie zaciekawiła. Długo starałem przekonać siebie, że nie trzeba tak naprawdę szukać w nim poprawnej ścieżki, ale w końcu wygrałem z lenistwem ;- )

Oraz opinia Maćka Stasiełuk (SocialFreaks.pl):

Jestem bardzo ciekaw jak inni to rozwiązali, super zadanie! Najtrudniejsze z całej serii i wymagające najbardziej algorytmicznego podejścia, co uważam za super pomysł. Czekam z niecierpliwością na publikacje jak wyglądała weryfikacja tego server-side.

Odpowiadając - na serwerze również zaimplementowany był algorytm rozwiązywania labiryntu (identyczny do opisanego powyżej, tylko w PHP zamiast JS). Z niego brana była minimalna liczba kroków potrzebnych do rozwiązania już na etapie generowania labiryntu. Następnie, po otrzymaniu danych o drodze gracza, symulowany był jego ruch (z uwzględnieniem min), aby sprawdzić, czy w ogóle doszedł do końca. Jeśli tak, to dodatkowo porównywał długość wysłanych danych z długością optymalną.

Nie wątpliwie - jakakolwiek wiedza algorytmiczna była tu wymaga. Ale nie oszukujmy się - choć przy tworzeniu stron nie spotykamy się zbyt często z problemami algorytmicznymi, to wypadałoby choć podstawy znać. Nie raz różnica między stroną a dobrą stroną może zależeć od szczegółów implementacji front-, czy back-endu. A tu na plus tylko może działać nam dodatkowa wiedza.

Wasze rozwiązania

Dotąd otrzymałem rozwiązania od Arka 'flies' Rzadkowolskiego, Maćka Stasiełuk (SocialFreaks.pl) i Michała Szumigaj. Dzięki!

Bez zbędnego więc komentarza przytaczam je. Najpierw komentarz Arka:

Prawie każde zadanie rozwiązywałem za pomocą trzech narzędzi: Charles Web Debugging Proxy (breakpoint, aby zmodyfikować zwrotny request do przeglądarki), WebServer z php + ulubione IDE.

 

Labirynt (plik labirynt.html): - dodałem algorytm liczenia najkrótszej trasy na grafie (Dijkstra), - reverse enginering na badaniu keykod pozwolił mi zapisać labirynt grafu (pole 1 łączy się z polami 2 i 20 i ma moc = 1, pole 2 łączy się się z polem 1 i polem 3 etc), - wyłączyłem mutację dla keykodów, ale dodałem demutator dla zapisywanych klikniętych pól.

Oraz do pobrania plik labirynt.html (klikajcie prawym i "Zapisz jako...", bo inaczej otworzy jako stronę i wykonanie JS przeniesie Was na inną lokację).

Oraz komentarz do rozwiązania od Maćka:

Ciekawi mnie jak zadanie 6 rozwiązali inni, mnie zmobilizowało do szukania informacji na temat algorytmów rozwiązujących labirynty :) Jako że żaden z powszechnie stosowanych mnie nie zadowalał to napisałem implementacje według własnego pomysłu. Też pewnie nic odkrywczego ale dało mi dużo radości :)

Do pobrania plik z rozwiązaniem - lvl6.js.

Czas na zwycięskie rozwiązanie. Najpierw komentarz od Michała:

Dużo zmian co do oryginału z aplikacji nie ma. Rekurencyjne przeszukiwanie wszerz, gdy dojdzie do końca mamy najkrótszą ścieżkę (każda następna będzie dłuższa).

 

Teraz zajrzałem w mój kod i mam drobne sprostowanie. Przeszukuję rekurencyjnie w głąb. Co prawda nie wiem czemu to działa na pierwszą znalezioną drogę. Zadziałało raz i stwierdziłem, że więcej nie trzeba dopisywać (sprawdzanie czy faktycznie jest najkrótsza). Sprawdziłem przed chwilą w aplikacji treningowej i też zadziałał. Kod oczywiście brzydki, gdyż był pisany na szybko i pod presją czasu. Najważniejsze, że zadziałał.

Do tego oczywiście plik z rozwiązaniem - level6.js.

Jak widać Michał nieświadomie skorzystał z faktu, że labirynt zawsze miał jedno rozwiązanie.

Jeśli chcecie, aby Wasze rozwiązanie równiez się tu znalazło - wysyłajcie je na mój e-mail z informacją o tym, w jaki sposób mogę je opublikować (anonimowo/z nickiem/z imieniem i nazwiskiem).

Cheat Champ
Cheat Champ to zawody w łamaniu internetowych aplikacji konkursowych. Tutaj możesz się dowiedzieć wszystkiego z nimi związanego i przekonać się, że warto wziąć w nich udział!

Podobne artykuły:

Skomentuj: