Stupně odloučení (Degrees)

Nejnovější verze Pythonu, kterou byste v tomto kurzu měli používat, je Python 3.12.

Napište program, který určí, kolik „stupňů odloučení“ od sebe dělí dva herce.

$ python degrees.py large
Loading data...
Data loaded.
Name: Emma Watson
Name: Jennifer Lawrence
3 degrees of separation.
1: Emma Watson and Brendan Gleeson starred in Harry Potter and the Order of the Phoenix
2: Brendan Gleeson and Michael Fassbender starred in Trespass Against Us
3: Michael Fassbender and Jennifer Lawrence starred in X-Men: First Class

Kdy úkol dokončit

Do 2027-06-30T23:59:00+00:00

Jak získat pomoc

Ptejte se prostřednictvím Ed!
Ptejte se prostřednictvím kterékoli z komunit CS50!

Výchozí informace

Podle hry Six Degrees of Kevin Bacon lze kohokoli v hollywoodském filmovém průmyslu propojit s Kevinem Baconem nejvýše šesti kroky. Každý krok spočívá v nalezení filmu, v němž oba herci hráli.

V této úloze chceme najít nejkratší cestu mezi libovolnými dvěma herci výběrem posloupnosti filmů, která je propojí. Například nejkratší cesta mezi Jennifer Lawrence a Tomem Hanksem má délku 2: Jennifer Lawrence a Kevin Bacon hráli ve filmu „X-Men: First Class“ a Kevin Bacon a Tom Hanks hráli ve filmu „Apollo 13“.

Můžeme to formulovat jako problém prohledávání: naše stavy jsou lidé. Naše akce jsou filmy, které nás přesouvají od jednoho herce ke druhému. Je pravda, že film nás může propojit s více různými herci, ale pro tuto úlohu to nevadí. Počáteční a cílový stav určují dva lidé, které se snažíme propojit. Pomocí prohledávání do šířky můžeme najít nejkratší cestu od jednoho herce ke druhému.

Začínáme

Stáhněte výchozí kód z https://cdn.cs50.net/ai/2023/x/projects/0/degrees.zip a rozbalte jej.

Porozumění výchozímu kódu

Výchozí kód obsahuje dvě sady datových souborů CSV: jednu v adresáři large a druhou v adresáři small. Obě obsahují soubory se stejnými názvy a strukturou, ale small je mnohem menší datová sada pro snazší testování a experimentování.

Každá datová sada se skládá ze tří souborů CSV. Pokud CSV neznáte, jde jednoduše o způsob uspořádání dat v textovém formátu: každý řádek odpovídá jednomu záznamu a jeho hodnoty oddělují čárky.

Otevřete small/people.csv. Uvidíte, že každý člověk má jedinečné id, které odpovídá jeho id v databázi IMDb. Má také name a rok birth.

Poté otevřete small/movies.csv. Zde uvidíte, že také každý film má jedinečné id, dále title a year, ve kterém byl uveden.

Nyní otevřete small/stars.csv. Tento soubor vytváří vztah mezi lidmi v people.csv a filmy v movies.csv. Každý řádek je dvojice hodnot person_id a movie_id. První řádek po hlavičce například uvádí, že člověk s id 102 hrál ve filmu s id 104257. Porovnáním s people.csv a movies.csv zjistíte, že tento řádek říká, že Kevin Bacon hrál ve filmu „A Few Good Men“.

Dále si prohlédněte degrees.py. Nahoře je definováno několik datových struktur pro uložení informací ze souborů CSV. Slovník names umožňuje vyhledat člověka podle jména: mapuje jména na množinu odpovídajících id, protože více herců může mít stejné jméno. Slovník people mapuje id každého člověka na další slovník obsahující jeho name, rok birth a množinu všech movies, ve kterých hrál. Slovník movies mapuje id každého filmu na další slovník obsahující jeho title, rok uvedení year a množinu všech jeho stars. Funkce load_data načítá data ze souborů CSV do těchto struktur.

Funkce main v tomto programu nejprve načte data do paměti. Adresář, ze kterého se načítají, lze zadat argumentem příkazového řádku. Pak uživatele vyzve k zadání dvou jmen. Funkce person_id_for_name zjistí id daného člověka; pokud má více lidí stejné jméno, vyzve uživatele k upřesnění. Poté zavolá funkci shortest_path, která vypočítá nejkratší cestu mezi oběma lidmi, a cestu vypíše.

Funkce shortest_path však zatím není implementována. To bude váš úkol!

Specifikace

Doplňte implementaci funkce shortest_path tak, aby vracela nejkratší cestu od člověka s id source ke člověku s id target.

Pokud existuje cesta ze source do target, funkce má vrátit seznam, jehož každá položka je další dvojice (movie_id, person_id) na cestě od zdroje k cíli. Každá dvojice má být n-tice dvou řetězců.
- Pokud by například návratová hodnota shortest_path byla [(1, 2), (3, 4)], znamenalo by to, že zdroj hrál ve filmu 1 s člověkem 2, člověk 2 hrál ve filmu 3 s člověkem 4 a člověk 4 je cílem.
Pokud existuje více cest s minimální délkou od zdroje k cíli, funkce může vrátit kteroukoli z nich.
Pokud mezi dvěma herci žádná cesta neexistuje, funkce má vrátit None.
Můžete volat funkci neighbors_for_person, která přijímá id člověka a vrací množinu dvojic (movie_id, person_id) pro všechny lidi, kteří s tímto člověkem hráli v některém filmu.

Kromě funkce shortest_path byste v souboru neměli nic měnit. Můžete však napsat další funkce a případně importovat další moduly standardní knihovny Pythonu.

Nápověda

Implementace prohledávání z přednášky kontroluje dosažení cíle při vyjmutí uzlu z fronty čekajících uzlů (frontier). Účinnost můžete zvýšit kontrolou cíle již při přidávání uzlů: pokud zjistíte cílový uzel, nemusíte ho přidávat do frontier a můžete řešení ihned vrátit.
Kód z příkladů v přednášce můžete převzít a upravit. Již jsme vám poskytli soubor util.py s implementacemi Node, StackFrontier a QueueFrontier z přednášky. Můžete je používat a případně upravit.

Testování

Pokud chcete, můžete po nastavení check50 ve svém systému spustit následující příkaz pro ověření správnosti kódu. Není to povinné; můžete úkol jednoduše odevzdat podle kroků na konci specifikace a stejné testy se spustí na našem serveru. V každém případě kód také sami zkompilujte a otestujte!

check50 ai50/projects/2024/x/degrees

Následujícím příkazem zkontrolujte styl svého kódu pomocí style50.

style50 degrees.py

Pamatujte, že kromě modulů standardní knihovny Pythonu nesmíte importovat žádné jiné moduly než ty, které jsou zde výslovně povoleny. Jinak se nejen nespustí check50, ale ani submit50 nebude moci úkol ohodnotit, protože používá check50. Pokud k tomu dojde, pravděpodobně jste importovali něco nepovoleného nebo výchozí kód jinak změnili způsobem, který zadání nepovoluje. Existují nástroje, které některé projekty značně zjednodušují, ale to zde není cílem: učíte se na nižší úrovni. Pokud zde není řečeno, že je můžete používat, používat je nesmíte.

Jak úkol odevzdat

Navštivte tento odkaz, přihlaste se účtem GitHub a klikněte na Authorize cs50. Poté zaškrtněte políčko udělující týmu kurzu přístup k vašim odevzdaným pracím a klikněte na Join course.
Nainstalujte Git a volitelně nainstalujte submit50.
Pokud máte nainstalovaný submit50, spusťte
```
submit50 ai50/projects/2024/x/degrees
```
Jinak pomocí Gitu odešlete práci do https://github.com/me50/USERNAME.git, kde USERNAME je vaše uživatelské jméno GitHub, do větve pojmenované ai50/projects/2024/x/degrees.

Pokud kód odevzdáváte přímo pomocí Gitu místo submit50, nezahrnujte do odevzdávané práce adresáře large ani small. submit50 je vyřadí automaticky. Zahrňte pouze soubory, které máte podle výše uvedené specifikace skutečně upravit.

Práce by měla být ohodnocena do pěti minut. Pak můžete na https://cs50.me/cs50ai zobrazit aktuální postup!

Poděkování

Informace poskytla IMDb. Použito se svolením.