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 7 - Znajdź 10 różnic

Cheat Champ - Cheat Champ -
napisał Jakub Caban

Zadanie 7 z zawodów Cheat Champ, czyli szukanie 10 różnic. Wredne obrazki i mało widoczne różnice zapewniają kupę zabawy. Jaki algorytm sobie z nimi poradzi?

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

Jak już się otrząsnęliście po poprzednim zadaniu, czas najwyższy na kolejne zmaganie z zadaniami z Cheat Champ. Muszę przyznać dobrze się bawiłem szukając obrazka do tego zadania. Bo może ktoś się zastanawia, w jaki sposób generowane były te grafiki? Otóż znalazłem duży fractal art (darmowy oczywiście), który w każdym miejscu coś miał (aby różnice były widoczne) i zawsze wycinałem z niego losowy fragment. I na niego nakładałem różnice przez obrót piksli w kwadracie 25x25. Dla utrudnienia najpierw nakładałem 10 takich obrotów na oba obrazki, a potem na jednym z nich dodawałem kolejne 10. I tak powstało:

7. Znajdź 10 różnic

Jak zwykle przytoczę najpierw opis samego zadania:

Troll face wziął się za fałszowanie dzieł sztuki! Możemy go powstrzymać tylko przez szybkie wykrycie jego błędów fałszerskich. Jako ekspert do spraw deratyzacji zostałeś wydelegowany do tego zadania. Nie zawiedź nas!

Zasady gry: Po kliknięciu "rozpocznij" na ekranie pojawią się dwa obrazki różniące się w dokładnie 10 miejscach. Twoim zadaniem jest wskazać te miejsca - masz tylko 10 kliknięć, więc nie klikaj tam, gdzie nie ma różnic!

Zasady zaliczenia: Uzyskaj czas poniżej sekundy Tolerancja sieciowa: 4s

7

Zadanie miało skłonić uczestników do chwili refleksji i kombinowania. I najwyraźniej się udało. Z 9 osób, które dotarły do tego poziomu 7 go rozwiązało. Patrząc na liczby prób widzę rozstrzał od 4 do 134, ze średnią 47.55. Jeśli popatrzymy tylko na tych, którzy to zadanie zrobili, to mamy rozstrzał pomiędzy 14 a 134 ze średnią 59. Najszybciej to zadanie zostało rozwiązanie w godzinę 7 minut i 29 sekund, a najdłużej zatrzmało kogos na 2 godziny 34 minuty i 20 sekund. Daje to średni czas dokładnie 1 godziny i 49 minut.

Niezłym też treningiem oczu jest próba rozwiązania go na czas tak normalnie. Mój rekord to 35s - ktoś był lepszy?

Sama treść bezpośrednio wskazuje nam, co trzeba zrobić. Po prostu pobrać 2 obrazki, znaleźć na nich 10 różnic i wskazać miejsca kliknięcia, które na pewno będą wewnątrz różniących się obszarów. Spójrzmy więc na dobry początek, co dzieje się w ramach aplikacji konkursowej:

var gel = null;
 function gimmefrac(){
 gel = document.getElementById("game");
 gel.innerHTML = "";
 callMe("frac.php?f=a", function(o){
 if(!o.html){
 alert('Errorek :(');
 reload();
 return;
 }
 new Preloader(o.html, function(html){
 gel.innerHTML = html;
 clicker.Init();
 timer.tInit();
 });
 }, true);
 var clicker = {
 top: 35,
 side: 35,
 size: 350,
 ell: null,
 elr: null,
 data: [],
 Init: function(){
 this.ell = document.getElementById("frac0");
 this.elr = document.getElementById("frac1");
 this.ell.onclick = function(e){ clicker.Click(this, e); };
 this.elr.onclick = function(e){ clicker.Click(this, e); };
 },
 Click: function(el, e){
 if(!e) e = window.event;
 var x = e.pageX;
 var y = e.pageY;
 do{
 x -= el.offsetLeft;
 y -= el.offsetTop;
 }while(el = el.offsetParent);
 this.data.push(x+"_"+y);
 this.AddMine(x, y);
 if(this.data.length == 10){
 this.Finish();
 }
 },
 AddMine: function(x, y){
 var el = document.createElement("div");
 el.className = "clicker";
 el.style.top = this.top+y-4+"px";
 el.style.left = this.side+x-5+"px";
 gel.appendChild(el);
 el = document.createElement("div");
 el.className = "clicker";
 el.style.top = this.top+y-4+"px";
 el.style.right = this.side+this.size-x-5+"px";
 gel.appendChild(el);
 },
 Finish: function(){
 timer.tStop();
 var t = timer.tGet();
 callMePost("frac.php?f=q&t="+t, "data="+this.data.join("$"), function(o){
 gel.innerHTML = o.html;
 }, true);
 }
 }
 }

Zasadniczo nic zaskakującego. Interesuje nas tylko fakt, że dane początkowe pobieramy przez zapytania do frac.php?f=a, w ramach których mamy obiekt z własnością html zawierającą po prostu kod HTML rysujący obrazki. Po wykonaniu 10 kliknięć ich pozycje są wysyłane do frac.php?f=q z parametrem GET t jako czas rozwiązywania oraz w danych POST jako data wszystkie współrzędne kliknięć oddzielone znakiem $.

Rozpocznijmy więc knucie rozwiązania. Na pewno rozpoczniemy od zapytania do frac.php?f=a, aby z wynikowego kodu HTML pobrać obrazki. Ja osobiście do ich pobrania wykorzystuję zapytania AJAX wykorzystując XHR level 2, a konkretniej pobranie danych binarnych z serwera. Doświadczenie kiedyś mi pokazało, że w ten sposób szybciej te dane są rysowane jako obrazek. Ale różnica nie jest wielka, więc generalnie sposób pobrania obrazków z serwera nie był tutaj istotny. W rozwiązaniu wzorcowym możecie po prostu poznać ciekawostkę, która kiedyś może się przydać.

Kiedy już pobierzemy obrazki należy przygotować się do ich analizy. Ja tworzę dla każdego z nich obiekt w JS, którego konstruktor rzutuje je na element CANVAS i pobiera tablicę danych o kolejnych pikslach (czyli getImageData). Ponieważ z obrazków interesują mnie tylko wartości RGB kolejnych piksli jedyną metodą Imgdata jest GetPixel, która po prostu zwraca tablicę 3 elementów - wartości odpowiednio R, G i B dla pikla w punkcie (x, y). Daje mi to w czasie przeszukania jednej tablicy dane o tych wartościach, więc dosyć szybko.

Zanim jednak przejdę do samego porównywania warto jeszcze wiedzieć, czego szukamy. Różnice zawsze są w kwadracie 25x25, więc musimy piksle skupić w takich właśnie kształtach. Dodatkowo różnice zawsze są od siebie oddalone o przynajmniej 5 piksli (o czym mogę wiedzieć tylko ja - chyba, że ktoś się przyjrzał i wyciągnął taki wniosek). Ważne jest zasadniczo tylko to, że nie nachodzą na siebie. Przygotowałem więc do przechowywania tych kształtów Rectangle. Obiekt taki będzie przechowywał współrzędne swojego górnego lewego rogu i będzie posiadał jedynie metodę sprawdzającą, czy zadany piksel należy do niego. Dodatkowo będzie zliczał, ile piksli zostało do niego wrzuconych. Warto tu właśnie dodać, że punkty odległe o 5px od danego Rectangle zaliczam jako należące do niego - taka heureza, która wyszła przy testowaniu rozwiązania.

Jak dotąd jest łatwo. To teraz pokrótce omówię ideę na szukanie tych różnic. Będę szedł pikslami po kolei (akurat w rozwiązaniu z góry na dół i z lewej na prawo) i szukał współrzędnych, które różnią się na obu obrazkach. Następnie po znalezieniu różnicy sprawdzę, czy należy do jakiegoś stworzonego już Rectangle. Jeśli tak, to do niego go dodam. Jeśli nie, to uznam, że jest górnym lewym rogiem nowego Rectangle. W idealnym świecie otrzymałbym w ten sposób 10 obiektów Rectangle z różnicami i wystarczyłoby wysłać informację o kliknięciu w każdy.

Ale nasz świat nie jest idealny. A przynajmniej autor zadania jest trolem, bo zamiast skorzystać z bezstratnej kompresji (np. PNG), to prezentuje obrazki jako JPEGi. W ten sposób te 10 różnic wpływa (nawet przy maksymalnej jakości JPEGa) na kompresję całego obrazka, w wyniku czego różnice w pojedynczych pikslach pojawiają się tu i tam. Pierwszym więc istotnym problemem jest porównywanie pojedynczych piksli. Oczywiście stosuję do tego metrykę taksówkarską (czyli biorę sumę różnic wartości kolejnych kanałów kolorów). Ale żeby różnicę uznać za różnicę ta wartość musi w moim rozwiązaniu wynieść ponad 100. Czemu dokładnie tyle? Bo po prostu testując rozwiązanie wyszło mi, że tyle działa prawie zawsze. Taka heureza, nic więcej. I chyba nie ma metody, na lepsze (i równie szybkie!) porównywanie piksli. A może jakąś znacie?

Idąc dalej - o kolejnej heurezie napisałem wcześniej, czyli uznawanie niedobitków w okolicy istniejącego Rectangle za należące do niego. Tak na prawdę tą blokadę na serwerze odsuwającą od siebie różnice dodałem widząc, że po prostu jest potrzeba, bo inaczej wynikowe obrazki będą świrować totalnie. Tutaj warto zwrócić uwagę na jeden fakt - idąc od lewej u góry systematycznie w dół i w prawo mamy gwarancję, że jeśli dobrze szukamy różnic, to zawsze najpierw znajdziemy górny lewy róg do Rectangle. Niby oczywiste, ale warto wspomnieć.

Świat jest również wredny w dalszej części. Okazuje się bowiem, że wynikowo tych Rectangle jest praktycznie zawsze ponad 10. Rekordowo mi chyba nawet do dwudziestu w testach ta wartość skoczyła. Tutaj za to przydaje się wcześniej opisany licznik piksli z różnicami, które wpadły do danego obiektu. W ten sposób możemy listę różnic posortować malejąco według tegoż licznika i po prostu wziąć pierwszych 10 z nich jako najbardziej prawdopodobne prawdziwe różnice.

Jeszcze słowa dwa o wyborze miejsc do klikania. Nie wiem, czy ktoś się na to naciął, czy nie, ale przy weryfikacji był dodatkowy prosty filtr behawioralny. Brał on po prostu współrzędne relatywne punktów kliknięcia wewnątrz kwadratów, liczył ich wariancję i jeśli była za mała - stwierdzał, że grał automat zamiast człowieka i odrzucał ten wynik. Więc jeśli ktoś spotkał komunikat "Wspomaganie się maszynami przy pracy z zabytkami jest ściśle zabronione!" - to właśnie tutaj wpadł. Aby tego uniknąć należało randomizować choć trochę punkty klikania tak, jak by to robiła ręka człowieka. Ktoś się na ten smaczek naciął?

Tak właśnie powstało rozwiązanie wzorcowe. Od razu powiem - nie działa w 100% przypadków. Powiedziałbym wręcz, że daje dobre wyniki w 80-90% z nich. Ale to w zupełności wystarczy tutaj. Aby przejść dalej, wystarczy, że zaskoczy raz, a więc nawet szansa na sukces 10% by wystarczała - nie trzeba tyle czasu, co ja, poświęcać na dopasowywanie parametrów. Ale jako, że wzorcowe, to starałem się je dopieścić w granicach dostępnego mi czasu. Tak więc poniżej listing do wszystkiego, co napisałem powyżej. Należy go 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 Loader(src){
 var xhr = new XMLHttpRequest();
 xhr.open('GET', src, true);
 xhr.responseType = 'blob';
 
 xhr.onload = function(e){
 if(this.status == 200){
 var blob = this.response;
 var img = document.createElement('img');
 img.onload = function(e) {
 window.URL.revokeObjectURL(img.src);
 Compare.Loaded(new Imgdata(img));
 };
 img.src = window.URL.createObjectURL(blob);
 }
 };
 
 xhr.send();
};

var Imgdata = function(el){
 this.el = el;
 this.el.varInit = true;
 this.canvas = document.createElement("canvas");
 this.canvas.width = 350;
 this.canvas.height = 350;
 this.ctx = this.canvas.getContext('2d');
 this.ctx.drawImage(this.el, 0, 0);
 this.data = this.ctx.getImageData(0,0,350,350).data;
};
Imgdata.prototype = {
 el: null,
 canvas: null,
 ctx: null,
 data: [],
 
 GetPixel: function(x, y){
 return [this.data[1400*y+4*x], this.data[1400*y+4*x+1], this.data[1400*y+4*x+2]];
 }
};

var Rectangle = function(x, y){
 this.x = x;
 this.y = y;
};
Rectangle.prototype = {
 x: 0,
 y: 0,
 width: 25,
 height: 25,
 margin: 5,
 cnt: 1,
 
 IsIn: function(x, y){
 var isin = x >= this.x-this.margin && x <= this.x+this.width+this.margin && y >= this.y-this.margin && y <= this.y+this.height+this.margin;
 if(isin) this.cnt++;
 return isin;
 }
};

var Compare = {
 imgdata: [],
 diffs: [],
 rects: [],
 data: [],
 
 Init: function(src1, src2){
 Loader(src1);
 Loader(src2);
 },
 Loaded: function(imgdata){
 this.imgdata.push(imgdata);
 if(this.imgdata.length == 2){
 this.FindDifferences();
 this.Rectangle();
 callMePost("frac.php?f=q&t=1", "data="+this.data.join("$"), function(o){
 gel.innerHTML = o.html;
 }, true);
 }
 },
 FindDifferences: function(){
 for(var x=0; x<350; x++){
 for(var y=0; y<350; y++){
 var c1 = this.imgdata[0].GetPixel(x, y);
 var c2 = this.imgdata[1].GetPixel(x, y);
 var diff = this.ColorDiff(c1, c2);
 if(diff > 100){
 this.diffs.push([x, y]);
 }
 }
 }
 },
 ColorDiff: function(c1, c2){
 return Math.abs(c1[0]-c2[0])+Math.abs(c1[1]-c2[1])+Math.abs(c1[2]-c2[2]);
 },
 Rectangle: function(){
 var p, r, isin;
 for(var i=0; p=this.diffs[i]; i++){
 isin = false;
 for(var j=0; r=this.rects[j]; j++){
 if(r.IsIn(p[0], p[1])){
 isin = true;
 break;
 }
 }
 if(!isin){
 this.rects.push(new Rectangle(p[0], p[1]));
 }
 }
 
 this.rects.sort(function(a, b){ return b.cnt-a.cnt; });
 for(var j=0; (r=this.rects[j]) && j<10; j++){
 this.data.push(this.Oscilate(r.x+12)+"_"+this.Oscilate(r.y+12));
 }
 },
 Oscilate: function(val){
 return val-5+Math.round(10*Math.random());
 }
};

var gel = document.getElementById("game");
var tmpe = document.createElement("div");
callMe("frac.php?f=a", function(o){
 if(!o.html){
 alert('Errorek :(');
 reload();
 return;
 }
 tmpe.innerHTML = o.html;
 Compare.Init(tmpe.children[0].src, tmpe.children[1].src);
}, true);

Co Wy na to?

Po poprzednim zadaniu to wydało Wam się wyraźnie łatwiejsze. W skali trudności daliście mu średnią 3.75. Za to zainteresowało wszystkich - średnia 5.00 nie pozostawia złudzeń. Wasze opinie też tym razem bardzo połechtały moją dumę.

Kasjan napsiał:

Doszukiwałem się tutaj jakiejś steganografii, ale zadania okazały się bardziej realne i z życia wzięte, super!

Maciek Stasiełuk (SocialFreaks.pl):

To zadanie to była dla mnie okazja do nauczenia się czegoś nowego, zaliczam je więc jako bardzo ciekawe.

Michał Szumigaj za to trochę sie zapędził:

Przez przypadek zrobiłem rozpoznawanie kształtów w JS

To zadanie miało zmusić do myślenia, bo nie było jakimś standardem. I zmusiło - cieszę się niezmiernie.

Wasze rozwiązania

Na chwilę obecną mam od Was cztery rozwiązania, które 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.

Porównywanie obrazków (frac.html + j.php): - w momencie preloadowania obrazków wysyłam ich adresy do php'a, - przetwarzam obrazy i robię funkcję diffującą na pixelach, - szukam piksela który jest w centrum pola o rozmiarach 24x24 różnych pikseli, - zwracam wyniki do przeglądarki i leci wynik

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

Komentarz Jacka jest natomiast następujący:

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.

Rozwiązanie zadania 7. to po prostu skorzystanie z Resemble JS. Pozwala na szybkie znalezienie różnic między 2 obrazkami. Musiałem jeszcze jednak odpowiednio je pogrupować w "kwadraty", aby znaleźć 10 większych różnic. Skrypt działa dosyć heurystycznie, ale wystarczył, aby przeszedł przy 5-6 próbie.

I oczywiście paczka z plikami do zadania siódmego - cc7.zip.

Maciek natomiast o swoim rozwiązaniu pisze:

Do rozwiązania zadania 7 ładuję dodatkowo całą zew. bibliotekę która miała mi pomóc, ale w zasadzie interesująca jest w niej tylko metoda hack() którą dodałem. Z założenia nie ma rozwiązywać zadania za każdym razem, a jedynie robić to z dużym prawdopodobieństwem. W prawdziwym konkursie potrzebowałem na to około 5 prób (po skończeniu pisania skryptu, wcześniej oczywiście potrzebowałem dużo prób żeby do tego dojść). Teraz gdy testowałem skrypt ponownie zadziałał już za drugim razem. BTW: musiałeś coś zmienić z ładowaniem obrazków od czasu konkursu bo doszło mi parę błędów na aplikacji treningowej, ale poprawiłem skrypt.

Jego rozwiązanie do pobrania - lvl7.js. A odnośnie aplikacji treningowej - działa na innym serwerze oraz pod inną domeną. To są oczywiście zmiany, które mogą wpłynąć na rozwiązanie, jednak były nieuniknione.

Michał Szumigaj takim komentarzem okrasa swoje rozwiązanie:

Tylko tak jak poprzednio kod nie jest piękny, 10 godzin walki robi swoje. Mały komentarz do kodu z zadaniem 7. Wykrywam różnice między obrazkami porównując je pixel po pixelu, potem wyszukuje tych różnic i tutaj ustawiłem blokadę na odległość środków tych kwadracików. Co nie zawsze jest prawdą, bo czasem mogą na siebie nachodzić te różnice. Ale wystarczy wywołać kod klika razy i uda mu się.

A jego rozwiązanie prezentuje się tak - level7h.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: