Warsztat.GD

Społeczność => Compo i bitwy => Cykliczne Warsztatowe Compo => Wątek zaczęty przez: Dab w Listopad 03, 2015, 12:09:06

Tytuł: Compo "Zrozumieć programowanie" - 03-17.11.2015 [wyniki]
Wiadomość wysłana przez: Dab w Listopad 03, 2015, 12:09:06
Z okazji premiery książki "Zrozumieć programowanie" (http://warsztat.gd/news/1318/zrozumiec_programowanie_-_zapowiedz_konkursu) której autorem jest nie kto inny jak Gynvael Coldwind (http://forum.warsztat.gd/index.php?action=profile;u=665) mamy dla was nietypowe Compo.

1. Celem Compo jest napisanie aplikacji która będzie przetwarzała bitmapy.
2. Przykładowa bitmapa dostępna jest pod adresem http://warsztat.gd/files/warsztat.bmp
3. Aplikacja na podstawie zadanej bitmapy oraz współrzędnych źródła światła powinna wyliczyć które piksele bitmapy mogą być oświetlone, a które są zasłonięte przez przeszkody. Ilustuje to poniższy schemat (za Red Blob Games/Amit Patel):
(http://warsztat.gd/files/visibility2.png)
4. Znaczenie kolorów bitmapy wejściowej (indeksy - bitmapa jest w trybie 8BPP):
5. Bitmapa wyjściowa również musi być w trybie 8BPP, gdzie następujące indeksy oznaczają:
6. Program (zgłoszenie użytkownika) musi działać na platformie Windows.
7. Program będzie uruchamiany w jednym z dwóch trybów:
Aplikacje będą oceniane w trzech różnych kategoriach. Nagrodą w każdej z nich jest książka "Zrozumieć programowanie" Gynvael Coldwinda.

1. Wydajność. Organizatorzy Compo dokonają pomiarów wydajności i dokładności działania zgłoszeń po czym wybrane zostanie najlepsze rozwiązanie.

2. Wizualizacja. Ta część będzie oceniana przez uczestników jak w trakcie tradycyjnego Compo (głosowanie). Oceniana będzie interaktywna część działania aplikacji.

3. Mystery challenge! Przykładowy plik (http://warsztat.gd/files/warsztat.bmp) skrywa pewną tajemnicę. Kto pierwszy będzie w stanie znaleźć ukrytą wiadomość? :)

Compo trwać będzie od chwili ogłoszenia do 17.11.2015 24:00 CET
Zgłoszenia należy wysyłać na adres [email protected]

W sprawach nieujętych regulaminem tej edycji obowiązują zasady ogólne: http://forum.warsztat.gd/index.php?topic=29527.0
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Kyroaku w Listopad 03, 2015, 15:23:19
Co to jest za dziwny format, że FreeImage, ani SDL go wczytać nie chce ? :D
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Dab w Listopad 03, 2015, 15:58:29
No cóż, zadanie jest z pogranicza gamedevu i security. Plik jest poprawny... z małą niespodzianką. ;)
(md5sum: 9043e60ce248ac88809f5155838b4620)
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: hashedone w Listopad 03, 2015, 20:28:12
Z tego wynika, że najlepiej samemu zakodować otwieranie bitmapy - jest chociaż określone która wersja nagłówka DIP jest użyta? Sam nagłówek to w sumie nie problem, można pominąć, ale pytanie czy implementacja i ewentualne testowanie RLE i innych bzdur z nowoczesnych nagłówków to też część zadania? Oczywiście nie chodzi mi o plik przykładowy - tam można łatwo sprawdzić, ale pytanie o złośliwość przy testowaniu.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Dab w Listopad 03, 2015, 21:37:45
Nie przewidujemy dodatkowych utrudnień przy testowaniu, pliki testowe będą w tym samym formacie co przykładowy.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Gynvael Coldwind w Listopad 03, 2015, 21:45:39
Serio FreeImage/SDL go nie obsługują? Hah, a to zabawne.
To standardowy BMP 8-bit RLE - szczerze nie spodziewałem się, że liby będą miały z nim problem (szczególnie, że przeglądałem sporo implementacji loaderów BMP i większość z nich sobie spokojnie z RLE 8-bit radziła).
No nic, wygląda na to, że jest to nieprzewidziane utrudnienie pod tytułem "znajdź lib ogarniający RLE8" ew. "napisz samemu dekoder RLE8" (format jest trywialny).

Natomiast jak Dab pisał - nie planujemy być złośliwi przy testach jeśli chodzi o format pliku - będzie to to samo co w przypadku pliku testowego.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: hashedone w Listopad 03, 2015, 21:55:29
RLE8 nie jest trudny, ale nie znam na pamięć co jeszcze w tych nagłówkach BMP może w teorii siedzieć dlatego pytam - też jestem bardzo zdziwiony, że popularne biblioteki sobie z tym nie radzą.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: lethern w Listopad 03, 2015, 21:58:40
Nie chce nic mówić, ale firefox też go poprawnie nie czyta/nie wyświetla
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Gynvael Coldwind w Listopad 03, 2015, 22:13:46
O, ciekawe. Opera też wyświetla tak jak Firefox.
Natomiast MSPaint / IrfanView / Chrome / IE / GIMP nie mają problemów.
Ciekawe co tam w Firefoxie/Operze namieszali...
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Kyroaku w Listopad 03, 2015, 22:32:57
Cytuj
To standardowy BMP 8-bit RLE - szczerze nie spodziewałem się, że liby będą miały z nim problem (szczególnie, że przeglądałem sporo implementacji loaderów BMP i większość z nich sobie spokojnie z RLE 8-bit radziła).
Ależ nie mają problemu.
Zarówno FreeImage, jak i SDL poprawnie czytają 8-bit RLE. Nie czytają tylko i wyłącznie waszej bitmapki :D
Wczytałem to photoshopem i zapisałem w formacie 8-bit RLE.
Wczytało się :)

Cytuj
O, ciekawe. Opera też wyświetla tak jak Firefox.
Jeśli chodzi o częsciową niezgodność kolorów pikseli, to paint też sobie nie radzi. Co dziwniejsze, mimo, że obraz jest źle wyświetlany, to po zapisaniu go do "normalnego" formatu wszystko się zgadza :)

Wasze dzieło zagina cyber-przestrzeń :)
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: albireo w Listopad 03, 2015, 23:04:13
Jeśli chcecie sprawdzać dokładność działania, to pasowałoby podać parę szczegółów, jak:
- czy źródło światła jest punktowe (i czy w takim wypadku leży w środku piksela, czy w węźle siatki), czy obszarowe (cały piksel, a może koło o średnicy piksela),
- kiedy piksel uznajemy za oświetlony: jeśli światło dociera do niego w jakikolwiek sposób, jeśli dociera do jego środka, oświetla 50% powierzchni czy może oświetla go w całości
- czy piksel blokujący światło jest kwadratem, czy kołem (w tym drugim przypadku ukośne linie będą miały prześwity).
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Gynvael Coldwind w Listopad 04, 2015, 01:07:10
Ależ nie mają problemu.
Zarówno FreeImage, jak i SDL poprawnie czytają 8-bit RLE. Nie czytają tylko i wyłącznie waszej bitmapki :D
Wczytałem to photoshopem i zapisałem w formacie 8-bit RLE.
Wczytało się :)
Fun fact - ten BMP był wygenerowany przez GIMP ^_-
Mógłbyś mi wysłać plik wygenerowany photoshopem na mejla? [email protected]

Jeśli chodzi o częsciową niezgodność kolorów pikseli, to paint też sobie nie radzi.
Hmm, sprawdziłem na MSPaint na Windows 7 i 10 i na obu wygląda OK. Z jakiej wersji painta korzystałeś?

Co dziwniejsze, mimo, że obraz jest źle wyświetlany, to po zapisaniu go do "normalnego" formatu wszystko się zgadza :)

Wasze dzieło zagina cyber-przestrzeń :)
^_- What the... ;)


@albireo
Jeśli chodzi o dokładność, to przede wszystkim sprawdzimy, czy bitmapa nie została zmniejszona przed wyliczeniem światła. Nie mieliśmy w planach czepiać się drobnych różnic w wynikach (takich na poziomie pojedynczych pikseli).

Odpowiadając na Twoje pytania:
- światło punktowe; ad w którym miejscu piksela leży punkt - ja bym zostawił tu dowolność, chyba, że Dab się ze mną nie zgodzi
- "kiedy piksel uznajemy za oświetlony" -tu bym też zostawił dowolność
- piksel jest kwadratem i między pikselami nie ma prześwitów (nawet, jeśli stykają się tylko rogami)

Dab, co sądzisz o tym?
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Dab w Listopad 04, 2015, 01:24:46
Przyjmijmy takie założenia:
- światło punktowe położone na środku piksela
- kiedy piksel oświetlony - dopuszczamy dowolność w implementacji
- piksele są kwadratami bez prześwitów

Zdajemy sobie sprawę że rasteryzacja na liczbach całkowitych rządzi się swoimi prawami wobec czego nasze testy będą uwzględniały dopuszczalną (nie)dokładność.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: albireo w Listopad 04, 2015, 09:17:08
Nie mieliśmy w planach czepiać się drobnych różnic w wynikach (takich na poziomie pojedynczych pikseli).
Tyle że bez doprecyzowania tego co podałem, to w zależności od doboru warunków, różnice w niektórych przypadkach mogłyby być ogromne, założenia Daba dają już dość sensowną porównywalność.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Krzysiek K. w Listopad 04, 2015, 09:30:49
Cytuj
Zdajemy sobie sprawę że rasteryzacja na liczbach całkowitych rządzi się swoimi prawami wobec czego nasze testy będą uwzględniały dopuszczalną (nie)dokładność.
Rasteryzacja czego? Może za dużo swego czasu się bawiłem na OI i ACM, ale mi to wygląda jak typowe zadanie na miotłę i z dodatkiem wektorów na liczbach całkowitych wyznaczenie oświetlenia wygląda że można zrobić o O(1) względem liczby pikseli.


Co do określenia całego zadania widzę tu jeszcze jedno ważne pytanie:
- czy piksel zasłania sam siebie? (tj. czy wszystkie blokujące piksele mają być nieoświetlone, czy zewnętrzna warstwa pikseli jednak ma być oświetlona?)
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: hashedone w Listopad 04, 2015, 09:41:27
Może za dużo swego czasu się bawiłem na OI i ACM, ale mi to wygląda jak typowe zadanie na miotłę i z dodatkiem wektorów na liczbach całkowitych wyznaczenie oświetlenia wygląda że można zrobić o O(1) względem liczby pikseli.
Zaraz ale jak? Jeśli O(1) to znaczy że względem niczego. Ewentualnie może miałeś na myśli O(n) względem liczby pikseli - co by miało jakiś tam sens, chociaż nijak nie potrafię sobie wyobrazić 100% dokładnego algorytmu o takiej złożoności (naiwna implementacja to jakieś n*sqrt(n)*m dla bitmapy kwadratowej o rozmiarze n pikseli dla m świateł, oraz n^2*m dla bitmapy 1*n i m świateł). Myślę że zastosowanie algorytmu o dokładności "good enaugh" a sporo mniejszej złożoności może mieć tu znaczenie.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Krzysiek K. w Listopad 04, 2015, 10:57:22
Cytuj
Jeśli O(1) to znaczy że względem niczego. Ewentualnie może miałeś na myśli O(n) względem liczby pikseli - co by miało jakiś tam sens
Cóż, dawno nie używałem tej notacji i wyszło. Chodziło mi oczywiście o O(n).

Cytuj
chociaż nijak nie potrafię sobie wyobrazić 100% dokładnego algorytmu o takiej złożoności
Jak pisałem - miotła. A w miotle beam tree w którym przedziały są określone wektorami o współrzędnych całkowitych. Drzewo przedziałowe w teoretycznie jest O(log N), ale tutaj przechodzimy elementy po kolei, więc można startować z poprzedniej znalezionej pozycji, więc może się udać dostęp O(1) dla pojedynczego piksela jak się dobrze zakombinuje.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: hashedone w Listopad 04, 2015, 13:13:01
Pomijając rozważania nad rozwiązaniem, które być może idą za daleko więc je utnijmy - Dab, Gyn, pytanie KK jest szczerze mówiąc też dość istotne, mianowicie:
Cytuj
czy piksel zasłania sam siebie? (tj. czy wszystkie blokujące piksele mają być nieoświetlone, czy zewnętrzna warstwa pikseli jednak ma być oświetlona?)
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Dab w Listopad 04, 2015, 13:17:53
Piksele będące przeszkodami powinny być nieoświetlone.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: świrus w Listopad 07, 2015, 20:49:14
Co do RLE, to ja bym ustalił czy bitmapa ma mieć kompresje, gdyż np. taki "stb_image.h" nie obsługuje takich cudów.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: pajadam w Listopad 08, 2015, 00:03:44
@up Przynajmiej jest lekkie utrudnienie ;) Ja sobie poradziłem, nie miałem większego problemu.
Nie udało mi się jednak zapisać skompresowanej bitmapy, więc niestety będzie musiała zostać zapisana bez kompresji. Zostało mi tylko ogarnąć generowanie oświetlenia. Mam już plan brakuje mi implementacji. Pozdrawiam i życzę wszystkim powodzenia :)
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: karol57 w Listopad 08, 2015, 21:58:24
Pokonałem Mystery challenge!, mail poszedł.

5. Bitmapa wyjściowa również musi być w trybie 8BPP, gdzie następujące indeksy oznaczają:
  • 0 - światło nie dociera do danego piksela
  • 255 - światło dociera do danego piksela
Mam dwa pytanka:
1. Jaki jest zasięg światła (dowolny/ustalony, nieskończony)?
1b. Jeżeli nie nieskończony to ma to być binarnie (255 i 0), czy można zrobić płynnie (np. 128 - 50,2%; 129 - 50.6% itd)?
1c. Jak dowolny to rozumiem, że nie może = 1 px :D
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Lerhes w Listopad 09, 2015, 15:48:46
Walczyłem jak lew z tym plikiem, ale niestety nie udało mi się odszukać zakodowanej wiadomości :(
O ile to możliwe, proszę o sprawdzenie czy karol57 dobrze rozwiązał zagadkę (czego oczywiście mu życzę), bo jeżeli nie to wracam do dłubania :D.
Bardzo mnie ciekawi gdzie ta ukryta wiadomość się znalazła :) - jeżeli rozwiązanie Karola jest dobre, to proszę o informacje jak została ona zakodowana.
Lerhes
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: karol57 w Listopad 09, 2015, 17:36:20
Zagadkę rozwiązałem dobrze, ale okazało się że byłem trzeci.

Co do rozwiązania to uważam, że najlepiej je ujawnić (jeżeli w ogóle) dopiero po zakończeniu compo i zrobić jakąś listę tych co sobie poradzili.

// EDIT:
Światło raczej nie pójdzie mi tak dobrze, więc będę musiał się postarać z GUI.

Co do złego wyświetlania bitmapy to (przynajmniej Firefox) zakłada, że drugi nagłówek to BITMAPINFOHEADER, a nie BITMAPV4HEADER i myśli, że paleta kolorów jest znacznie wcześniej niż znajduje się w rzeczywistości.

Mam jeszcze jedno pytanie: Kodem się dzielimy, czy nie?
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Dab w Listopad 10, 2015, 00:25:45
Prosimy na razie nie publikować rozwiązania do ukrytej wiadomości - dajmy każdemu szansę do pogłówkowania.

Światło ma nieskończony zasięg. Piksele powinny być albo w pełni oświetlone (255) albo zaciemnione (0).  Do oświetlenia piksela wystarczy żeby dosięgało go przynajmniej jedno źródło światła.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Dab w Listopad 16, 2015, 00:56:26
Jak tam postępy? :)
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: karol57 w Listopad 17, 2015, 16:16:30
Ja odpadam, nie dam rady. Mam tylko obliczanie swiatla, ale jest dosyć wolne i pomija część pikseli. Ani tego poprawić, ani gui raczej nie zdążę napisać, więc zostaje mi wieczna chwała za 3 miejsce w Mystery Challenge ^^

//EDIT: W wiadomości wysłałem tylko odszyfrowany tekst i opis gdzie był ukryty, wysyłać kod i/lub nick z forum czy nie ma takiej potrzeby?
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: pajadam w Listopad 17, 2015, 23:38:47
Projekt poleciał.

Niestety nie wyszło do końca tak jakbym chciał... przysiadłem nad nim porządnie dopiero dzisiaj, zabrakło czasu na poprawki. Wydajność leży a nadmiar niepotrzebnych i co gorsza powtarzających się if'ów aż prosi się o wywalenie, ale nie ma czasu ;) Na szczęście programu da się używać :)

Mam nadzieje że poszło wam lepiej niż mi :D

Pozdrawiam, Adam.
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: Compo w Grudzień 09, 2015, 15:31:45
Wyniki Compo: http://warsztat.gd/news/1323/zrozumiec_programowanie_-_wyniki_compo

Cytuj
W kategorii Wydajność i Interakcja zwycięzcą został Adam Pajkert.

W kategorii Security miejsca na podium zajęli:

1. Dominik Olejnik

2. Tomasz Danielewski

3. Karol Rudnik
Tytuł: Odp: "Zrozumieć programowanie" - compo!
Wiadomość wysłana przez: karol57 w Grudzień 15, 2015, 12:29:00
Jej III miejsce. W takim razie chciałem podziękować za książkę. Książkę dostałem gdzieś koło 6, ale nie miałem czasu napisać.

Jeżeli chodzi o samą książkę to fajnie się ją czyta, szczególnie (jak w moim przypadku) ktoś lubi wiedzieć jak wszystko działa na niskim poziomie, a nie chce mu się szukać każdej pierdółki z osobna.