Selejtező megoldások 2019

Megkértünk pár csapatot, hogy meséljék el, hogyan álltak neki, milyen nehézséggel találkoztak a feladatok megoldása közben. A csapatok hozzájárultak a megosztásukhoz, illetve párnál még a forrást is megtaláljátok.

A csapatoknak még egyszer köszönjük a hozzájárulást ;)

Tégla

#include<iostream> char S[9];auto&L=std::cin;int C,H,I,N,P[99];main(){for(L>>N;C>P[C];L>>S;for(puts(H?"Lali":S);!H?L>>C>>H,H=P[--C]^(P[C]-=H):1;(H^C)

A feladatot az alábbiak alapján oldottuk meg:

Az alap feladat egy ismert probléma, a Nim játék megoldása volt. Erre létezik már kész algoritmus, mi ennek egy saját implementációjából indultunk ki a kód rövídítéséhez:

A játék megnyerése azon múlik, hogy az adott állásban, amikor soron vagyunk az úgynevezett Nim-sum értéke 0-e. (A Nim-sum a kupacokban található téglák számának bitenkénti xor-a.) Ha nem 0 akkor úgy döntünk a játék elején, hogy mi kezdünk, ellenkező esetben pedig az ellenfél. Amikor soron vagyunk, akkor úgy kell lépnünk, hogy a Nim-sum-ot 0-vá tegyük. Ekkor az ellenfél csak úgy tud lépni, hogy ezt elrontsa. Ha e szerint a stratégia szerint járunk el, akkor biztosan megnyerjük a játékot.

A kód lerövidítéséhez természetesen a whitespacek eltávolítása és a változó nevek egy karakteressé tételén kívül sok egyéb trükkre is szükség volt. Például:

1. A main függvényt hivatalosan "int main()"-ként kell deklarálni, de a fordító engedi pusztán a "main()"-t.

2: A globálisan definiált int-ek default 0-ra inicializálódnak, ezt az algoritmusunk majdnem az összes változó esetén kihasználja.

3: C++-ban a , operator-t utasítások közé helyezve egy olyan kifejezést kapunk, aminek a , álltal elválaszott tagjai sorban kiértékelődnek és az egész kifejezés értéke, az utolsó rész értéke lesz. Ezt felhasználva az if-ek és ciklusok belsejét össze lehet tömöríteni és megspórolni a {-ket.

3: Érdemes meggondolni, hogy milyen módon írunk ciklust. Ha csak egy végtelen ciklusra van szükségünk, akkor a "for(;;){}" a legrövidebb. Az "a:goto a;" ugyanolyan hosszú ugyan de van egy nagy hátránya a for-hoz képest. A for belsejében a ;-k között 3 utasítást eltudunk helyezni: egyet behozva a for előttről, egyet a for belsejének legelejéről és egyet a for belsejének legvégéről. Ez 3 karakter (;) megspórolását jelenti. Pl: "for(L>>N;C>P[C];". Itt a "H^=P[C++]" logikusan az "L>>P[C];" után állna, de egy ;-t megspórolunk ha bevisszük. (A tényleges legrövidebb talán a main rekurzív meghívása (7 karakter), de ekkor nem tudunk kezdeti inicalizációt csinálni.)

4: if-eket nem érdemes használni. Egy if feltétel minden egyéb nélkül is 4 karakter: if().Ellenben a ? : operator csak 2 és egy "ingyen" felhasználható else ágat is ad nekünk. Az egyetlen megkötés, hogy

a : két oldalán lévő kifejezés értéke ugyanolyan típusú legyen, ezt a , segítségével egymás mellé írt kifejezések segítségével könnyű elérni.

5: Az algortimus könnyen szeparálható két részre, a kezdeti állapot beolvasására és a játékra melyeket külön külön is lehet "optimalizálni". A beolvasásnál például több módszerrel is próbálkoztunk, de a legrövidebbnek az std::cin használata bizonyult. Ezt elégszer használtuk a kódban ahhoz, hogy megérje elmenteni a referenciáját egy 1 betűs változóban: "auto&L=std::cin;"

6: A változókat érdemes újra felhasználni, amibe az elején beolvastunk, az később jó lehet egy köztes érték tárolására. Sőt, ha tudjuk, hogy egy érték mi lesz egy számítás után (a mi lépésünk után a Nim-sum 0 lesz), akkor az eddig azt tároló változót is újra használhatjuk addig amíg később megint meg kell változnia. A kódon talán még lehetne rövdíteni, mivel a játék során nem használjuk fel az N értékét, a beolvasáskor pedig az I értékét. Ezeket talán összelehetne vonni, vagy csak egy plusz segéd változóként felhasználni.

7: A kód hosszán természetesen az algoritmus struktúrája is sokat változtat, az elején például mindig újra számoltuk a Nim-sum értékét (egy makróval) de ennél sokkal jobbnak bizonyult, ha inkább folyamatosan karban tartottuk. Nagyon sok egyéb optimalizációt tett ez lehetővé.

8: Szerencsére az ellenőrző rendszer nem figyelte, hogy a programunk helyesen terminál-e hanem a jó megoldáskor automatikusan bezárta. Ezért nem volt szükség ellenőrizni van-e még tégla valamelyik kupacban, hanem elég volt egy végtelen ciklus :)

Tom és Gerry megoldása

Múzeum

Több lépcsőben közelítettük meg a megoldást:

1. Véletlen szerű helyekre kamerákat generáltunk, és felépítettünk egy cache-t, hogy 1-1 kamera mit lát. A random helyeken túl az összes csúcspontot is felvettük, mint lehetséges kamerahely, mert azoknak nagy valószínűséggel nagy a betekintése, illetve így biztosan nem marad ki olyan tárgy, amelyet 1 db kamera sem láthat. A cache felépítésénél figyeltünk arra, hogy kidobáljuk azokat a kamerákat, amelyek egy másik kamerának a részhalmaza a látott tárgyak tekintetében. Egy kamera akkor látott egy tárgyat, ha nem volt olyan falszakasz, amely metszette a kamera-tárgy szakaszt.

2. Kompakt GA-val közelítettük meg, hogy melyik legyen az a K db kamera, amelyet lehelyezünk. A default kompakt GA-nál 0.5-ről indulnak a valószínűségek, mi ezt úgy manipuláltuk meg, hogy súlyoztuk ezt a kezdeti értéket annak függvényében, hogy hány tárgyat lát a kamera, illetve ugyan ezt a tárgyat hány másik kamera ér el. Az eredeti kompakt GA-nél diszkrét 1-0 értékeket aggregálunk a végén, hogy letegyük, illetve ne tegyük le a kamerát az adott helyre. Mi nem végeztünk bináris tresholdot, hanem meghagytuk a double értékeket, ezt rendeztük sorba, és ebből vettük a K db legfelsőt. Ebből a K elemből eldobtuk azokat, amelyek nem értek el egy minimális küszöbértéket.

3. Minden egyes GA részeredményt megpróbáltunk iteratívan javítani, hogy hozzáadunk még 1-1 kamerát, vagy elveszünk, hogy az aktuális fittness javuljon.

A fittnes egyszerűen csak pontozást tartalmazta, azaz 5* látott tárgy - felhasznált kameraszám.

Elméletileg csak akkor nem raktunk már le több kamerát, ha minden tárgyat látunk. A végeredmény excelen látszik, hogy volt olyan feladat, ahol hagytunk meg kamerát, viszont nem találtunk meg minden tárgyat, tehát rossz volt az a függvényünk, ami meghatározta, hogy egy kamera lát-e egy tárgyat.

Utolsó megoldása