CODE CHALLENGES
EXTRA GYAKORLÁS

Állapottér-keresés · optimalizálás · tervezés

Code
Challenges

Klasszikus problémák, amelyekben az algoritmust, az állapotot és a korlátokat is neked kell megtervezned.

20
új feladat
8
közepes
7
nehéz

4 hét · 20 új platformfeladat · 5/hét

Heti Code Challenge útvonal

Hetente öt eltérő algoritmikus nézőpont. A kis címke egy szóban mutatja, miért került a feladat a hétre.

Alapok · állapottér-keresés

Kezdés: állapot, lépés, cél

Könnyű

1. Wolf, Goat and Cabbage

A gazda egyszerre csak egy utast vihet át; a farkas nem maradhat a kecskével, a kecske pedig a káposztával.

Cél
Legkevesebb átkelés
Módszer
BFS · gráfmodellezés
Közepes

2. Missionaries and Cannibals

Három-három utas kel át kétférőhelyes csónakkal; ahol vannak misszionáriusok, nem lehetnek kevesebben a kannibáloknál.

Cél
Legrövidebb érvényes lépéssor
Módszer
BFS · korlátos átmenetek
Közepes

3. Sliding 8-Puzzle

Rendezd a 3×3-as táblát a célállapotba úgy, hogy mindig csak az üres mezővel szomszédos csempét csúsztathatod el.

Cél
Legkevesebb lépés
Módszer
BFS vagy A* · Manhattan-távolság
Könnyű

4. Water Jug Problem

Az 5 és 3 literes kancsóval, töltéssel, ürítéssel és átöntéssel mérj ki pontosan 4 litert.

Cél
4 liter kimérése
Módszer
BFS · állapottér-keresés

Középhaladó · optimalizálás és gráfok

Költség, útvonal, sorrend

Közepes

5. Bridge and Torch — Extended

A 1, 2, 5, 8, 12 és 15 perces átkelők közül legfeljebb ketten mehetnek egyszerre, a lámpának mindig velük kell lennie.

Cél
Minimális összidő
Módszer
Dijkstra · uniform-cost search
Közepes

6. Warehouse Robot

A robot falak között csomagokat visz a depóba. Egy üres lépés 1, csomaggal 2 energiaegység.

Cél
Minden csomag minimális energiával
Módszer
Dijkstra vagy A*
Közepes

7. Train Shunting Puzzle

Az A, B, C, D kocsikból veremként működő mellékvágánnyal állítsd elő a D, B, C, A sorrendet — vagy döntsd el, lehetséges-e.

Cél
Célrendezés vagy lehetetlenség
Módszer
DFS · backtracking · veremszimuláció
Nehéz

8. Fuel-Constrained Shortest Path

A 10 egységes tartállyal rendelkező jármű súlyozott gráfban halad; az állomásokon fix áron tankolhat, és útdíjak is lehetnek.

Cél
Legolcsóbb megvalósítható út
Módszer
Dijkstra · (csúcs, üzemanyag) állapot

Haladó · kombinatorikus keresés és tervezés

Nagy állapottér, okos korlátozások

Nehéz

9. Sokoban

Told a ládákat a raktárban a tárolómezőkre. A ládák csak tolhatók, a falak és a beragadt ládák zsákutcát okozhatnak.

Cél
Minden láda tárolón, kevés tolással
Módszer
A* vagy BFS · deadlock-felismerés
Közepes

10. N-Queens

Helyezz el N királynőt egy N×N táblán úgy, hogy egyik se támadhassa a másikat.

Cél
Egy megoldás vagy az összes darabszáma
Módszer
Backtracking · constraint satisfaction
Nehéz

11. Elevator Scheduling

Egy hatszintes épületben egy lift legfeljebb két utast vihet. Egy szint megtétele 1 egység, be- és kiszállás ingyenes.

Cél
Minden utas minimális utazási költséggel
Módszer
BFS vagy Dijkstra · súlyozott átmenetek
Nehéz

12. Key and Door Maze

A labirintusban kulcsok és a hozzájuk tartozó zárt ajtók vannak; a jó útvonalhoz a kulcsokat megfelelő sorrendben kell összegyűjteni.

Cél
Kijutás a legkevesebb lépéssel
Módszer
BFS vagy A* · (pozíció, kulcs-bitmask)
Közepes

13. Lézeres páncélterem

Juss el a széfhez egy N×M-es rácson. Az azonos színű lézermezőket a megfelelő kar kapcsolja ki, de egyszerre legfeljebb három szín karjainak állapotát tarthatod nyilván.

Cél
Legkevesebb lépés vagy −1
Módszer
BFS · (sor, oszlop, kar-bitmask)
Közepes

14. Munkagépek üzemanyag-utántöltése

Rendezd sorba a futási idejű, típusozott feladatokat. Két azonos típus indítása közé legalább K időegység hűlés kell; minimalizáld a teljes befejezési időt.

Cél
Optimális sorrend és összidő
Módszer
Greedy · max-heap
Nehéz

15. Dinamikus hídátkelés súlykorláttal

A lámpa mindig egy embernél van, a hídon egyszerre lévők összsúlya pedig nem haladhatja meg W-t. Egy vagy több ember kelhet át, ha a teherbírás engedi.

Cél
Minimális idő és lépéssor
Módszer
Dijkstra · súlyszűrt részhalmazok
Nehéz

16. Nim: legrövidebb nyerő sorozat

Három kavicskupacból egy lépésben egy kiválasztott kupacból 1…K kavics vehető el. Mindkét játékos optimálisan játszik.

Cél
Győzelemhez vezető legkevesebb lépés és első lépés
Módszer
Minimax · Grundy-számok
Nehéz

17. Legolcsóbb repülőút K átszállással

Találd meg az A-ból B-be vezető legolcsóbb utat legfeljebb K átszállással. Légitársaság-váltáskor plusz díjat kell fizetni.

Cél
Legkisebb összköltség vagy −1
Módszer
Bellman–Ford vagy Dijkstra · (város, megállás, cég)

← Vissza a tanulóközponthoz