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 8 - Memory game

Cheat Champ - Cheat Champ -
napisał Jakub Caban

Ostatnie zadanie z Cheat Champ, czyli memory game. Do odkrycia 60 pól z symbolami, których nie sposób pamiętać. Ale dobry algorytm poradzi sobie ze wszystkim!

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

To zadanie zostało przez Was okrzyknięte najbardziej przypominającym prawdziwe konkursy z wszystkich w ramach Cheat Champ. I to na pewno nie bez przyczyny - w końcu memory game to najpowszechniejszy typ gry konkursowej na Polskim Facebooku. To akurat miało konkretną inspirację w konkursie, który jakoś w grudniu czy styczniu się odbywał. Z tym, że w tamtym serwer zwracał URLe obrazków, z których wystarczyło przez HEAD pobrać rozmiar wynikowy, aby znaleźć pary. I dodatkowo obsługiwał wiele zapytań na raz, przez co podrasowanie przeglądarki dawało na prawdę kosmiczne wyniki dosyć łatwo. Ja poszedłem parę kroków dalej, bo w końcu mamy do czynienia z ostatnim zadaniem!

Rozwiązało je 5 z 7 osób, które do niego dotarły. Pojedynek o pierwsze miejsce był bardzo zacięty i zakończył się różnicą zaledwie 5 minut! Jak zwykle zliczałem ilość podejść do zadania. Najmniej było ich 36, a maksimum osiągnęło 163. To bardzo dużo zważywszy na fakt, że przejście do końca nawet już optymalne trwało parę minut. Średnio tych prób było 64.57.

Wśród piątki, która rozwiązała to zadanie przedział ilości podejść pozostał ten sam, jednak średnia zmienia się na 71.20. Czyli pozostałe dwie osoby może zbyt szybko zaprzestały prób? Rozwiązanie zadania najmniej zajęło 2 godziny 29 minut i 54 sekundy, a najwięcej 6 godzin 9 minut i 4 sekundy. Średnio spędziliście nad nim 3 godziny 49 minut i 11 sekund.

8. Memory game

Jako że z opisu tego zadania (oraz komunikatów przy nim) jestem wyjątkowo dumny, to również z dumą go Wam zaprezentuję:

Wszystkie memy poszły na melanż. Wszystkie oczywiście poza Forever Alone. Ten jak zawsze został pominięty. Aby urozmaicić sobie dzień postanowił pobawić się w swoją ulubioną grę. Aby jeszcze bardziej go pogrążyć Twoim zadaniem jest rozwiązać jego zabawę szybciej od niego. Niech ma!

Zasady gry: Po kliknięciu "rozpocznij" na ekranie pojawi plansza z 60 polami. Klikając w nie odsłonisz obrazki. Na raz możesz odsłonić 2 pola. Jeśli będą one takie same - odpadną z gry. Jeśli będą różne - zakryją się przy następnym kliknięciu. Twoim zadaniem jest sprawić, aby wszystkie klocki odpadły z gry.

Zasady zaliczenia: Rozwiąż grę w czasie poniżej 210 sekund. Wszelkie marginesy sieciowe są wliczone w czas do zaliczenia. Dodatkowo czas między kolejnymi kliknięciami nie może przekroczyć 4s.

8

Ktoś, kto tego zadania nie robił, może teraz zakrzyknąć "210 sekund na zadanie?! To musiał być banał!". Każdego, kto tak uważa zapraszam do aplikacji treningowej - zadanie czeka. Bo tak na prawdę ilość kombinowania na minutę kwadratową jest tutaj wcale nie mała. Tak więc nie przedłużając przyjrzyjmy się listingowi zadania:

var gel, lock = false, toclose = null;
 function memememe(){
 gel = document.getElementById("game");
 gel.innerHTML = "";
 callMe("meee.php?m=s", function(o){
 if(!o.html){
 alert('Errorek :(');
 reload();
 return;
 }
 gel.className = "info meme";
 gel.innerHTML = o.html;
 var cn = gel.children, el;
 for(var i=0; el=cn[i]; i++){
 if(el.tagName == "A"){
 el.myIndex = i;
 el.onclick = iamclicked;
 }
 }
 timer.tInit();
 }, true);
 function iamclicked(e){
 if(lock) return;
 lock = true;
 if(toclose){
 gel.children[toclose[0]].innerHTML = "";
 gel.children[toclose[1]].innerHTML = "";
 toclose = null;
 }
 var el = this;
 callMe("meee.php?m=c&i="+el.myIndex, function(o){
 lock = false;
 if(o.error) return;
 if(o.html){
 timer.tStop();
 gel.className = "info";
 gel.innerHTML = o.html;
 return;
 }
 if(o.image){
 el.innerHTML = '<img src="'+o.image+'" />';
 }
 if(o.done){
 gel.children[o.done[0]].className = "done";
 gel.children[o.done[1]].className = "done";
 }
 if(o.close){
 toclose = o.close;
 }
 }, true);
 return false;
 }
 }

Niepozorny i krótki listing sugeruje, że nie może być tak źle... A może może? Spójrzmy - rozpoczęcie jak zawsze wykonuje się przez wysłanie zapytania do meee.php?m=s, w odpowiedzi mamy html zawierające kod HTML planszy z grą. Generalnie niesamowicie prosty kod, jeśli ktoś mnie zapyta. I tyle - żadnych więcej informacji! Nie wiemy, jakie znaki są pod jakimi polami i w ogóle co, gdzie, jak?

Pojawiają się więc pierwsze wątpliwości i myśli "nie chce mi się". Ale Ci wytrwalsi patrzą dalej. Kliknięcie w dowolne pole (poza kilkoma operacjami odpowiedzialnymi za samo działanie gry) wysyła na serwer informację o kliknięciu meee.php?m=c, przekazując w parametrze GET i indeks klikniętego pola. Więc to serwer kontroluje naszą grę! He wants to play a game! Ale omówmy jeszcze, co możemy wyciągnąć na temat odpowiedzi. Z wynikowego obiektu mamy bowiem trochę informacji. Jeśli istnieje atrybut html, to skończyliśmy grę i warto go wyświetlić. W atrybucie image mamy base64 encoded obrazek do wyświetlenia. Natomiast jeśli istnieje atrybut done oznacza on, że właśnie odkryliśmy parę i należy ją jako taką traktować. I w końcu jeśli mamy atrybut close, to powinniśmy przy następnym ruchu zakryć pola w nim opisane.

Znów więc określmy najpierw cel naszego działania. Przede wszystkim musimy najpierw pobrać informację o wszystkich obrazkach, zwracając przy tym uwagę na wynikowe done, aby na pewno ewentualne znalezione pary później pomijać. Następnie trzeba porównać obrazki znajdując pary i w końcu wysłać na serwer kolejne informacje o klikaniu w nie. Jako, że mamy aż 60 pól, to może to chwilę potrwać.

Zaczynajmy więc!

Na wstępie omawiania mojego rozwiązania wspomnę, że korzystam z napisanej na jego potrzeby funkcji caller, która jest po prostu powłoką wysyłającą zapytanie AJAX na serwer o wybranej metodzie (w tym wypadku będę używał GET i HEAD) i wynik parsuje jako JSON. Po drodze w przypadku nie udanego połączenia próbuje ponownie do skutku.

W rozwiązaniu wzorcowym całą logikę wrzuciłem do obiektu Solver, aby można było łatwo przejrzeć na wylot, co się tam dzieje. Przede wszystkim w ramach inicjalizacji tworzę 60 obiektów field i każę im pobrać swoje obrazki. W ramach metody Load obiektów field nie dzieje się wiele zaskakującego - wysyłam zapytanie na serwer o kliknięciu w dane pole i po otrzymaniu odpowiedzi sprawdzam, czy przypadkiem nie trafiłem na parę. Jeśli tak, to ustawiam atrybuty done odpowiednich elementów field, aby wiedzieć, że są już usunięte. Po pobraniu obrazka (oraz informacji o jego pikslach przez rzutowanie na CANVAS jak przy poprzednim zadaniu) informuję Solver przez metodę Loaded o zakończeniu ładowania. O samej tej metodzie będzie za chwilę.

Teraz mając wszystkie obrazki należałoby je porównać. Niektórzy zawodnicy może będą zaskoczeni, po jak małej linii oporu dało się tu pójść. Bo oczywiście - obrazki mają na sobie nałożony dosyć mocny kolorowy szum, który uniemożliwia bezpośrednie porównanie. Ale jak już w poprzednim zadaniu porównywaliśmy piksle, tak i tutaj można. A że wszystkie mają taką samą obwódkę, to porównujmy tylko ich środek (bez bocznych 5px). Może Wam się to wydawać nie wiele, ale teraz zamiast porównywać 2500 punktów porównuję tylko 1600 - bardzo duży zysk! Próbowałem jeszcze zmniejszyć tą wartość, ale wyniki przestały być poprawne. Spójrzcie więc na metodę Compare w field, która bierze za parametr drugi obiekt typu field. Korzysta z metody GetPixel, która jak poprzednio zwraca po prostu wartości kanałów R, G i B oraz funkcji ColorDiff, która po prostu liczy odległość (znów jako sumę różnic wartości w kolejnych kanałach).

W tak opisany sposób można uzyskać swego rodzaju podobieństwo dwóch obrazków w field jako wartość liczbową (im mniejsza, tym lepiej). Idea więc jest taka, aby parować te obrazki, które są sobie najbliższe. Brzmi prosto. Ale zanim do tego dojdzie dochodzi jeszcze jeden problem. Otóż na moim sprzęcie przeliczenie wszystkich indeksów podobieństwa zajmuje ponad 8 sekund. Jeśli bym brał całe obrazki, zamiast tylko środkowych części, to ten czas wzrasta do 12 sekund. Warunek o klikaniu przynajmniej co 4 sekundy w tym momencie pozwoli Forever Alone uciec.

Tutaj wchodzi do gry metoda Solver.Loaded. Ona bowiem nie tylko oznacza, że obrazek się załadował (bo wtedy byśmy doszli do sytuacji wyżej opisanej). Dodatkowo jak tylko obrazek się pobierze od razu wymusza porównanie go z wszystkimi dotąd pobranymi. Ponieważ zapytania na serwer idą sekwencyjnie (serwer nigdy w tym zadaniu nie będzie przetwarzał dwóch na raz) oraz czas odpowiedzi to minimum 1.5s (przynajmniej tak się u mnie zachowywało w czasie testów), a średnio około dwóch sekund, to czekając na kolejny obrazek mamy aż za dużo czasu na porównanie ostatniego z dotąd załadowanymi. W ten sposób po pobraniu ostatniego obrazka wykonujemy tylko 59 porównań zanim przejdziemy dalej, zamiast 1770 i spokojnie mieścimy się z olbrzymim zapasem w 4 sekundach.

Jeśli już dobrnęliśmy do tego etapu to jest z górki. Idziemy po kolei po obrazkach, szukając pierwszego dotąd nie zakrytego. Jak go znajdziemy, to przeszukujemy jego tablicę porównań szukając najbardziej do niego podobnego i wysyłamy informację o kliknięciu ich. Gdy oba kliknięcia się wykonają szukamy kolejnych. I tak do końca. Metoda field.FindPair szuka najbliższego, a Solver.PairStep obsługuje ich klikanie. Tutaj jeszcze aby znów przyspieszyć działanie wysyłam zapytania typu HEAD (zamiast domyślnego GET), aby nie tracić czasu na pobieranie odpowiedzi (jako, że zawiera ona zawsze cały obrazek, to kawałek waży). Tylko ostatnią parę pobieram przez GET, aby móc wyświetlić sobie komunikat na zakończenie.

Tak więc jak widać starałem się rzucać kłody pod nogi gdzie tylko się dało, a i tak można takie memory rozgryźć. Tak to już w tym życiu jest. Prezentuję więc całe rozwiązanie wzorcowe, w ramach którego dodatkowo wszystkie pobrane obrazki wyświetlam tak o - dla wrażeń estetycznych. Kod należy 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).

function caller(url, method, callback){
 var ajax = new XMLHttpRequest();
 ajax.onreadystatechange = function(){
 if(ajax.readyState == 4){
 if(ajax.status == 200){
 Handle(url.replace('ajax/',''),ajax.responseText,callback);
 }else{
 caller(url, method, callback);
 }
 }
 };
 ajax.open(method, url+"&t="+Number(new Date), true);
 ajax.send(null);
}
function Handle(url,json, callback){
 var obj;
 try{
 if(typeof(JSON) === "object" && typeof(JSON.parse) === "function")
 obj = JSON.parse(json);
 else
 eval("obj = "+json+";");
 }catch(e){
 obj = json;
 }
 if(typeof(callback) === "function"){
 callback(obj);
 }
}

function ColorDiff(c1, c2){
 return Math.abs(c1[0]-c2[0])+Math.abs(c1[1]-c2[1])+Math.abs(c1[2]-c2[2]);
}

var field = function(el, index){
 this.el = el;
 this.index = index;
 this.diff = {};
};
field.prototype = {
 el: null,
 index: null,
 loaded: false,
 data: null,
 diff: null,
 pair: null,
 done: false,
 
 Load: function(){
 var myself = this;
 caller("meee.php?m=c&i="+this.index, 'GET', function(o){
 var onload = function(){
 if(this.varLoaded) return;
 this.varLoaded = true;
 myself.loaded = true;
 var canvas = document.createElement('canvas');
 canvas.width = 50;
 canvas.height = 50;
 var ctx = canvas.getContext('2d');
 ctx.drawImage(myself.el.children[0], 0, 0);
 myself.data = ctx.getImageData(0,0,50,50).data;
 Solver.Loaded(myself);
 };
 var img = new Image();
 img.onload = onload;
 myself.el.appendChild(img);
 img.src = o.image;
 if(img.complete) img.onload();
 if(o.done){
 Solver.fields[o.done[0]].done = true;
 Solver.fields[o.done[1]].done = true;
 Solver.done += 2;
 }
 });
 },
 GetPixel: function(x, y){
 return [this.data[200*y+4*x], this.data[200*y+4*x+1], this.data[200*y+4*x+2]];
 },
 Compare: function(f){
 if(this.diff[f.index] || this.done || f.done) return;
 var d = 0;
 for(var x=5; x<45; x++){
 for(var y=5; y<45; y++){
 d += ColorDiff(this.GetPixel(x, y), f.GetPixel(x, y));
 }
 }
 this.diff[f.index] = d;
 f.diff[this.index] = d;
 },
 FindPair: function(){
 var d, mind = 100000000, mini = 0;
 for(var i in this.diff){
 d = this.diff[i];
 if(d < mind){
 mind = d;
 mini = i;
 }
 }
 this.pair = mini;
 return mini;
 }
};

var Solver = {
 fields: [],
 loaded: 0,
 done: 0,
 pair: 0,
 
 Init: function(){
 var cn = gel.children, el;
 for(var i=0; el=cn[i]; i++){
 if(el.tagName == "A"){
 this.fields.push(new field(el, i));
 }
 }
 var f;
 for(var i=0; f=this.fields[i]; i++){
 f.Load();
 }
 },
 Loaded: function(f){
 this.loaded++;
 if(this.loaded == this.fields.length){
 this.GetDistances();
 }else if(!f.done){
 var f1;
 for(var i=0; f1=this.fields[i]; i++){
 if(f1.loaded && (f1.index != f.index)){
 f.Compare(f1);
 }
 }
 }
 },
 GetDistances: function(){
 var tt = +new Date();
 var f1, f2;
 for(var i=0; f1=this.fields[i]; i++){
 for(var j=i+1; f2 = this.fields[j]; j++){
 f1.Compare(f2);
 }
 }
 console.log(new Date()-tt);
 this.FindPairs();
 },
 FindPairs: function(){
 var f1, f2;
 for(var i=0; f1=this.fields[i]; i++){
 if(f1.pair || f1.done) continue;
 f2 = f1.FindPair();
 this.fields[f2].pair = i;
 }
 this.PairStep();
 },
 PairStep: function(){
 var f1, f2;
 this.pair = 0;
 for(var i=0; f1=this.fields[i]; i++){
 if(f1.done) continue;
 f2 = this.fields[f1.pair];
 var method = this.done==58 ? 'GET' : 'HEAD';
 caller("meee.php?m=c&i="+f1.index, method, function(o){ Solver.StepGot(o, f1); });
 caller("meee.php?m=c&i="+f2.index, method, function(o){ Solver.StepGot(o, f2); });
 break;
 }
 },
 StepGot: function(o, f){
 f.done = true;
 this.done++;
 if(o.html){
 gel.className = "info";
 gel.innerHTML = o.html;
 }else{
 if(this.pair) this.PairStep();
 else this.pair++;
 }
 }
};

var gel = document.getElementById("game");
gel.innerHTML = "";
caller("meee.php?m=s", 'GET', function(o){
 if(!o.html){
 alert('Errorek :(');
 reload();
 return;
 }
 gel.className = "info meme";
 gel.innerHTML = o.html;
 Solver.Init();
});

 

Co Wy na to?

 

Ocena poziomu trudności nie pokrywa się z wnioskami z czasu spędzonego nad zadaniem, bowiem średnia trudność przez Was wskazana to 4.33. Było za to bez wątpienia dla Was ciekawe, gdyż tu zgodnie oceniliście wszyscy je na 5. Dwie opinie się w ankiecie pojawiły, które teraz przytoczę:

Maciek Stasiełuk (SocialFreaks.pl) napisał:

Zadanie najbardziej zbliżone do łamania prawdziwych aplikacji FB, a takich zagadek właśnie oczekiwałem. Szkoda że pojawiło się dopiero na końcu bo ten etap mógłby spokojnie weryfikować użytkowników wcześniej. W następnej edycji chciałbym widzieć więcej właśnie takich - jak najbardziej zbliżonych do rzeczywistości - zadań. Jako duży minus muszę jednak wskazać dużą zależność od łącza, niestety obecnie przebywam na bardzo wolnym połączeniu co sprawiło że sporo marudziłem w trakcie :) +5 sekund więcej i nie musiałbym robić tyle podejść :)

Prawie wszystkie zadania były inspirowane w jakimś stopniu spotkanymi w sieci konkursami. A to oczywiście najbardziej :) Jeśli chodzi o zalezność od sieci - rzekłbym "broken by design". Jeśli nie byłoby zależne, to i złamanie go nie stanowiłoby takiego problemu, jakim miało być. Właśnie ze względu na to zadanie ostrzegałem, że słabe łącza mogą rodzić niedogodności. Ale wydaje mi się, że kryterium zaliczenia było na tyle zjadliwe, że dobrze zoptymalizowany kod i tak dawał sobie radę.

Moje zdanie częściowo potwierdza w swoim komentarzu Michał Szumigaj:

Tutaj mi się przydało rozpoznawanie kształtów z zadania poprzedniego. Miałem duży problem z osiągnięciem wyznaczonego czasu ale po dużej optymalizacji kodu, spokojniejszym wietrze i mniejszym wpływie promieni słonecznych na piasek udało się.

Moge tylko dodać, iż dobierałem termin zawodów tak, aby wpływ przyciągania Wenus na przepustowość łącz internetowych w Polsce był możliwie mały.

Wasze rozwiązania

Wszystkie cztery rozwiązania, które otrzymałem, prezentuję poniżej:

Arek pisze:

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.

 

Forever alone (me.html + j2.php + sim.php): - robię kolejkę pobieranych obrazków i odpalam w JSie, - każdego zwrotnego base'a od razu wysyłam na serwer php'a, gdzie jest zapisywany, przerabiany na B&W, a tablice pikseli zrzucane do pliku txt, - po zakończeniu kolejki wysyłam do php'a prośbę o kolejkę kliknięć (sim.php), która jest tworzona na podstawie porównania tablic pikseli wszystkich plików (90%+ podobieństwa, aby matchować parę).

Oraz do pobrania pliki me.html (klikajcie prawym i "Zapisz jako...", bo inaczej otworzy jako stronę i wykonanie JS przeniesie Was na inną lokację) oraz j2.php i sim.php(zazipowane oczywiście ze względów "sekuryti").

Z kolei Jacek zadanie skomentował tak:

Od zadania 5. wolałem ściągnąć jej cały source na dysk lokalny, przeeedytować leciutko kod źródłowy gry i/lub dodać swoją własną funkcję solve() następującą po odpaleniu gry. W ten sposób mogłem szybko edytować i testować wszelkie rozwiązania.

 

Musiałem jeszcze jedynie odpalić chrome poprzez komendę "chrome.exe --disable-web-security", aby pozbyć się komunikatu XmlHttpRequest error: Origin null is not allowed by Access-Control-Allow-Origin.

Zadanie 8. to po prostu klikanie wszystkich obrazków pokolei, porównanie przy uzyciu Resemble.JS oraz klikanie w międzyczasie odkrytych już par.

I paczuszka z wszystkimi plikami do tego zadania - cc8.zip

Natomiast od Maćka otrzymałem następujący komentarz:

Nad zadaniem 8 nie miałem już za bardzo siły siedzieć, nawet miałem się poddać i powiem szczerze że udało się dopiero w ostatniej próbie. Winą było bardzo słabe połączenie u mnie w rodzinnej miejscowości gdzie spędzałem weekend. Ale wiem że nie mam prawa marudzić (i zresztą wcale nie marudzę, nie chce żeby to było tak odebrane :)) bo było wcześniej zapowiadane że trzeba sobie zapewnić dobre łącze. W ramach porównania zrobiłem sobie teraz test ponownie już na normalnym łączu i nie licząc kilku prób z moimi missclickami uzyskałem za pierwszym razem 185s, myląc się w trakcie kilka razy. Myślę więc że spokojnie można zejść do 170-175s. A wtedy ciągle uderzałem w 215-220 sekund, nawet przy idealnych podejściach.

 

Bardzo mnie też tutaj ciekawią rozwiązania innych, bo przypuszczam że mogło być sporo różnych sposobów obejścia, jako że nie było trywialnego błędu sugerującego odpowiedź jak w innych zadaniach (a może nie zauważyłem czegoś?). Początkowo chciałem użyć algorytmów do rozpoznawania obrazków z poprzedniego zadania, ale stwierdziłem że szybciej będzie jak sam poklikam. W załączniku masz więc jedynie zestaw poprawek który uprzyjemniał mi grę :)

Oraz załączony plik - lvl8.js

I na deser rozwiązanie od Michała Szumigaj z takim oto komentarzem:

Tylko tak jak poprzednio kod nie jest piękny, 10 godzin walki robi swoje. Zadanie 8. Tutaj walczyłem z rozpoznawaniem tych obrazków. Usuwanie szumu i porównywanie podobnie jak w poprzednim zadaniu. Niestety charakterystyki obrane przy porównywaniu były za mało wystarczające (tego kodu już tam nie ma), czas pracy algorytmu też nie był zadowalający. Chwilkę sobie odpocząłem i wpadł mi do głowy inny pomysł. Przecież jestem człowiekiem i "sieć neuronowa" w moim mózgu jest lepiej "oprogramowana" i "nauczona" niż jakakolwiek w wersji cyfrowej. Więc zastosowałem siebie do porównywania obrazków, zwyczajnie ich nie ukrywam i podczas ładowania ich wkładam pary na stos. Umieszczone obrazki na stosie oznaczam. Następnie algorytm bierze zapisane pary i wygrywa.

Oraz oczywiście rozwiązanie - level8h.js

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: