Cvičení 10: Grafy

slovnik.txt

• Graf lze reprezentovat maticí sousednosti, seznamem hran nebo seznamem odchozích hran
• Budeme používat seznam odchozích hran.

• Pro graf na obrázku bude reprezentace vypadat takto:
• G je proměnná typu dictionary, indexujeme ji jménem (číslem) uzlu, hodnota je pole, které obsahuje seznam uzlů, které jsou dosažitelné

G = {}
G [0] = [1 ,2 ,5]
G [1] = [0 ,2]
G [2] = [0 ,1 ,3]
G [3] = [2]

Mějme orientovaný graf, který má uzly očíslované od 1 do N. Hrany v tomto grafu jsou zadány v souboru, který na jedné řádce obsahuje definici jedné hrany, tedy dvě čísla:

• první číslo je číslo uzlu ze kterého vede hrana
• druhé číslo je číslo uzlu do kterého vede tato hrana

Napište program path.py, který z příkazové řádky načte jméno souboru s definicí hran a číslo startovního uzlu a číslo koncového uzlu. Program vytiskne jednu z nejkratších cest ze startovního uzlu do cílového uzlu.

Program otestujte na tomto souboru:

1 2
1 9
2 3
2 6
3 4
3 8
4 6
4 1
5 4
5 8
6 8
6 9
7 4
7 5
8 7
8 3
9 5
9 1

Výsledek pro cestu z uzlu 2 do uzlu 5 je:

2 6 9 5

• Úkolem je napsat program, který určí možné pohyby “kobylky” v hexagonálním hnízdě (inspirováno hrou HIVE).

• Vstup:
  • Jméno textového souboru na příkazové řádce (sys.argv[1])
  • Soubor obsahuje na každé řádce tři celá čísla p q v, kde (p, q) jsou souřadnice buňky v hexagonálním gridu a v je její hodnota. Hodnota buňky kóduje následující:
    • v = 0: buňka je prázdná,
    • v = 1: buňka je obsazená, a
    • v = 2: na buňce je umístěna kobylka.
  • Vstupní soubor obsahuje definici tzv. hrací desky.
  • Je zaručeno, že vstupní soubor existuje a obsahuje validní definici problému.
  • Kobylka je na desce pouze jedna.

• Výstup:
  • Program určí souřadnice všech buněk, kam se kobylka z výchozí pozice může dostat, a vypíše je na standardní výstup.
  • Souřadnice jsou vypsány ve formátu [ [p1, q1], [p2, q2], … , [pn, qn] ], přičemž platí, že výstup je seřazen vzestupně nejdříve dle p a následně dle q.
  • Pokud se kobylka nikam nemůže dostat, je výstup programu []

• Odevzdání: program grasshopper.py nahrajte do Brute, úloha HW09.

• Pohyb kobylky
  • Z výchozí pozice se kobylka může pohnout na nejbližší neobsazené místo ve všech šesti směrech a musí platit, že mezi aktuální pozicí a novou pozicí musí být alespoň jedna obsazená buňka.
  • Kobylka se nesmí pohnout, pokud by při jejím skoku došlo k rozpojení hnízda - všechny neprázdé buňky (hnízdo) tvoří jednu komponentu souvislosti.

• Pro správný výpis řešení doporučujeme uložit výsledek (tj. seznam buňek, kam se kobylka může dostat) do pole, přičemž každá buňka bude souřadnice [p, q].
• Je potřeba zajistit, aby kobylka neskákala mimo herní desku.
• Pole seřadíme a vypíšeme takto:

solution = [ [1, 2], [1, -1], [-1, 4] ]   # priklad reseni 
solution.sort()
print(solution)                           # takto vypsane reseni bude akceptovano Brutem

• Informace k práci s hexagonálním gridem.

• Modře jsou obsazené buňky, červeně je výchozí pozice kobylky, zeleně jsou místa, kam se kobylka může dostat.
• Výstupem vašich programů bude seznam zelených buněk.

Vstup:

-4 8 0
-4 9 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-2 4 0
-2 5 0
-2 6 0
-2 7 0
-2 8 0
-2 9 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 0
-1 7 0
-1 8 0
-1 9 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 1
1 8 1
1 9 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 0
2 7 1
2 8 1
2 9 0
3 0 0
3 1 0
3 2 0
3 3 1
3 4 1
3 5 2
3 6 1
3 7 0
3 8 0
3 9 0
4 0 0
4 1 0
4 2 0
4 3 1
4 4 1
4 5 1
4 6 0
4 7 0
4 8 0
4 9 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 0
5 5 0
5 6 0
5 7 0
5 8 0
5 9 0
6 0 0
6 1 0
6 2 0
6 3 0
6 4 0
6 5 0
6 6 0
6 7 0
7 0 0
7 1 0
7 2 0
7 3 0
7 4 0
7 5 0
8 0 0
8 1 0
8 2 0
8 3 0
9 0 0
9 1 0

Výstup:

[[3, 2], [3, 7], [5, 3], [5, 5]]

Komentář: z výchozí pozice (červeně) je možné doskočit na čtyři zelené pozice.

Vstup:

-4 8 0
-4 9 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-2 4 0
-2 5 0
-2 6 0
-2 7 0
-2 8 0
-2 9 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 0
-1 7 1
-1 8 1
-1 9 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 1
0 7 1
0 8 0
0 9 0
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 1
1 8 0
1 9 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 2
2 7 0
2 8 0
2 9 0
3 0 0
3 1 0
3 2 0
3 3 0
3 4 1
3 5 1
3 6 0
3 7 0
3 8 0
3 9 0
4 0 0
4 1 0
4 2 0
4 3 0
4 4 1
4 5 1
4 6 0
4 7 0
4 8 0
4 9 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 1
5 5 0
5 6 0
5 7 0
5 8 0
5 9 0
6 0 0
6 1 0
6 2 1
6 3 1
6 4 0
6 5 0
6 6 0
6 7 0
7 0 0
7 1 0
7 2 0
7 3 1
7 4 0
7 5 0
8 0 0
8 1 0
8 2 0
8 3 0
9 0 0
9 1 0

Výstup:

[]

Komentář: kobylka nemůže nikam skočit, neboť by došlo k rozpojení hnízda na dvě oddělené části:

Vstup:

-2 4 0
-1 2 1
-1 3 0
-1 4 0
0 0 0
0 1 0
0 2 1
0 3 2
0 4 0
1 0 0
1 1 0
1 2 1
1 3 1
1 4 1
2 0 0
2 1 0
2 2 0
2 3 1
2 4 0
3 0 0
3 1 0
3 2 0
3 3 0
4 0 0
4 1 0

Výstup:

[[0, 1], [2, 1], [3, 3]]

Komentář: kobylka (výchozí pozice je červeně) může skočit na tři zelené buňky:

• Úkolem je napsat program, který určí možné pohyby “mravence” kolem hnízda, přičemž se jedná o pohyb na hexagonální mřížce (inspirováno hrou HIVE).
• Vstup:
  • Jméno textového souboru na příkazové řádce (sys.argv[1])
  • Soubor obsahuje na každé řádce tři celá čísla p q v, kde (p, q) jsou souřadnice buňky v hexagonálním gridu a v je její hodnota. Hodnota buňky kóduje následující:
    • v = 0: buňka je prázdná,
    • v = 1: buňka je obsazená, a
    • v = 2: na buňce je umístěn mravenec.
  • Vstupní soubor obsahuje definici tzv. hrací desky.
  • Je zaručeno, že vstupní soubor existuje a obsahuje validní definici problému.
  • Mravenec je na desce pouze jeden.

• Výstup:
  • Program určí souřadnice všech buněk, kam se mravenec z výchozí pozice může dostat, a vypíše je na standardní výstup
  • Souřadnice jsou vypsány ve formátu [ [p1, q1], [p2, q2], … , [pn, qn] ], přičemž platí, že výstup je seřazen vzestupně nejdříve dle p a následně dle q.
  • Pokud se mravenec nemůže nikam pohnout, je výsledek []

• Odevzdání: program ant.py nahrajte do Brute, úloha HW09.

• Pohyb mravence
  • Mravenec se smí pohybovat podél hnízda o jedno či více navazujících polí najednou, avšak platí, že pohyb musí splňovat pravidla níže.
  • Mravenec se může pohybovat jen po volných buňkách.
  • Mravenec se vždy musí dotýkat nějakého souseda.
  • Mravenec se nemůže pohnout místami, kudy se hexagonální buňka mravence nevejde (fyzicky):
    • Mravenec se nemůže posunout skrze úzkou mezeru (viz. Příklad 2).
    • Mravenec se nemůže pohybovat na krajích hrací desky (vně desky lze chápat jako překážky).
  • Mravenec může vykonávat pouze pohyb dopředu a nemůže se vracet.
  • Pohyb mravence je vykonán tzv. posunem, tj., do neobsazeného souseda [ps, qs] se může dostat z aktuální pozice [pa, qa] pouze pokud buňky [ps, qs] a [pa, qa] sdílí ještě jednoho volného souseda.
  • Mravenec může opustit svoji pozici pouze pokud všechny neprázdé buňky (hnízdo) tvoří jednu komponentu souvislosti.

• Modře jsou obsazené buňky, červeně je výchozí pozice mravence, zeleně jsou místa, kam se mravenec může dostat
• Výstupem vašich programů bude seznam zelených buněk

• Zde se mravenec nemůže pohybovat, neboť by došlo k rozpojení hnízda (vznikly by dvě komponenty souvislosti)

• Mravenec může navštívit dva sousedy (buňku (-2,4) nelze navštívit posunem)

• Mravenec může navšívit většinu hnízda, ale nemůže se posunou skrz buňḱy (7,5) a (3,9)

• Z výchozí pozice (2,4) se nelze nikam dostat

• Zde lze navštívit celé hnízdo

• Pro správný výpis řešení doporučujeme uložit výsledek (tj. seznam buňek, kam se mravenec může dostat) do pole, přičemž každá buňka bude souřadnice [p, q].
• Je potřeba zajistit, aby se mravenec neposunul mimo herní desku.
• Pole seřadíme a vypíšeme takto:

solution = [ [1, 2], [1, -1], [-1, 4] ]   # priklad reseni 
solution.sort()
print(solution)                           # takto vypsane reseni bude akceptovano Brutem

• Informace k práci s hexagonálním gridem.

Vstup:

-2 4 0
-1 2 0
-1 3 0
-1 4 0
0 0 0
0 1 0
0 2 1
0 3 0
0 4 1
1 0 0
1 1 1
1 2 1
1 3 1
1 4 1
2 0 2
2 1 1
2 2 1
2 3 1
2 4 1
3 0 1
3 1 0
3 2 0
3 3 0
4 0 0
4 1 0

Výstup:

[]

Komentář: mravenec se posunem nemůže nikam dostat

Vstup:

-7 14 0
-6 12 0
-6 13 0
-6 14 0
-5 10 0
-5 11 0
-5 12 0
-5 13 0
-5 14 0
-4 8 0
-4 9 0
-4 10 0
-4 11 0
-4 12 0
-4 13 0
-4 14 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-3 10 0
-3 11 0
-3 12 0
-3 13 0
-3 14 0
-2 4 0
-2 5 0
-2 6 0
-2 7 0
-2 8 0
-2 9 0
-2 10 0
-2 11 0
-2 12 0
-2 13 0
-2 14 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 0
-1 7 0
-1 8 0
-1 9 0
-1 10 0
-1 11 0
-1 12 0
-1 13 0
-1 14 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
0 10 0
0 11 0
0 12 0
0 13 0
0 14 0
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
1 8 0
1 9 0
1 10 0
1 11 0
1 12 0
1 13 0
1 14 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 0
2 7 0
2 8 0
2 9 0
2 10 0
2 11 0
2 12 0
2 13 0
2 14 0
3 0 0
3 1 0
3 2 0
3 3 0
3 4 0
3 5 0
3 6 0
3 7 1
3 8 1
3 9 0
3 10 0
3 11 0
3 12 0
3 13 0
3 14 0
4 0 0
4 1 0
4 2 0
4 3 0
4 4 0
4 5 0
4 6 1
4 7 0
4 8 1
4 9 1
4 10 0
4 11 0
4 12 0
4 13 0
4 14 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 0
5 5 0
5 6 1
5 7 0
5 8 1
5 9 0
5 10 0
5 11 0
5 12 0
5 13 0
5 14 0
6 0 0
6 1 0
6 2 0
6 3 0
6 4 0
6 5 1
6 6 0
6 7 1
6 8 0
6 9 0
6 10 0
6 11 0
6 12 0
6 13 0
6 14 0
7 0 0
7 1 0
7 2 0
7 3 0
7 4 0
7 5 0
7 6 2
7 7 0
7 8 0
7 9 0
7 10 0
7 11 0
7 12 0
7 13 0
7 14 0
8 0 0
8 1 0
8 2 0
8 3 0
8 4 0
8 5 0
8 6 0
8 7 0
8 8 0
8 9 0
8 10 0
8 11 0
8 12 0
8 13 0
9 0 0
9 1 0
9 2 0
9 3 0
9 4 0
9 5 0
9 6 0
9 7 0
9 8 0
9 9 0
9 10 0
9 11 0
10 0 0
10 1 0
10 2 0
10 3 0
10 4 0
10 5 0
10 6 0
10 7 0
10 8 0
10 9 0
11 0 0
11 1 0
11 2 0
11 3 0
11 4 0
11 5 0
11 6 0
11 7 0
12 0 0
12 1 0
12 2 0
12 3 0
12 4 0
12 5 0
13 0 0
13 1 0
13 2 0
13 3 0
14 0 0
14 1 0

Výstup:

[[2, 7], [2, 8], [2, 9], [3, 6], [3, 9], [3, 10], [4, 5], [4, 10], [5, 5], [5, 9], [6, 4], [6, 6], [6, 8], [7, 4], [7, 5], [7, 7]]

Komentář: Mravenec může navštívit následující místa (všimněte si, že do středu hnízda se nedá posunem dostat)

Vstup:

-4 8 0
-4 9 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-2 4 0
-2 5 0
-2 6 1
-2 7 0
-2 8 0
-2 9 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 1
-1 7 1
-1 8 1
-1 9 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 1
0 9 1
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
1 8 1
1 9 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 2
2 7 1
2 8 1
2 9 0
3 0 0
3 1 0
3 2 0
3 3 0
3 4 1
3 5 1
3 6 1
3 7 0
3 8 0
3 9 0
4 0 0
4 1 0
4 2 1
4 3 1
4 4 0
4 5 0
4 6 0
4 7 0
4 8 0
4 9 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 0
5 5 0
5 6 0
5 7 0
5 8 0
5 9 0
6 0 0
6 1 0
6 2 0
6 3 0
6 4 0
6 5 0
6 6 0
6 7 0
7 0 0
7 1 0
7 2 0
7 3 0
7 4 0
7 5 0
8 0 0
8 1 0
8 2 0
8 3 0
9 0 0
9 1 0

Výstup:

[[-2, 5], [-1, 5], [0, 5], [0, 6], [0, 7], [1, 7], [2, 4], [2, 5], [2, 9], [3, 2], [3, 3], [3, 7], [3, 8], [4, 1], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3]]

Komentář: Mravenec může navštívit následující místa