Vejce

Určete nejvyšší patro, z něhož můžete vejce ještě hodit, aby se nerozbilo!

Chceme vytvořit algoritmus pro určení pevnosti daného typu vajec. Všechna vejce mají stejnou pevnost. Pevnost vajec měříme tak, že je pouštíme z paneláku z různých pater. Pevnost vejce je definována jako číslo nejvyššího patra, z něhož můžete vejce pustit, aby se ještě nerozbilo. Pokud je P pevnost vejce, pak pustíte-li ho z patra číslo P nebo nižšího, vejce se nerozbije (a můžete ho použít pro další test); pustíte-li ho z patra P+1 nebo vyššího, vejce se rozbije (a znovu ho už použít nemůžete). Pokud se vejce rozbije už při pádu z prvního patra, je P = 0. Pokud má panelák N pater, je nejvyšší možná pevnost vajec P = N.

Vstupem algoritmu by měla být výška paneláku (tj. největší pevnost vejce, kterou můžete “změřit”) a počet vajec, která máte k dispozici pro experimenty (a nevadí nám, že se při experimentech rozbijí). S daným počtem vajec by měl algoritmus určit pevnost vajec co nejrychleji, tj. s co nejmenším počtem hodů vejce z paneláku.

Zkuste si rozmyslet:

• Jak byste postupovali, kdybyste měli k dispozici jediné vejce?
• Jak byste postupovali, kdybyste měli k dispozici vajec, kolik chcete?
• Jak byste postupovali, kdybyste měli k dispozici 2, 3, … vejce?

Vaším úkolem je naprogramovat strategii experimentu, tedy algoritmus, který bude postupně volit patra, z nichž chcete pouštět vejce, v závislosti na tom, zda vejce předchozí test “přežilo” nebo ne.

V modulu solver.py vytvořte funkci determine_egg_strength(), s následujícími vstupy a výstupy:

Funkce egg_survives_floor() simuluje upuštění vejce z jistého patra. Může být definována např. takto:

def egg_survives_floor(floor):
    return floor <= 18

Tato funkce odpovídá tomu, že pevnost vejce je 18. Váš algoritmus samozřejmě toto číslo nebude znát, může jen volat funkci egg_survives_floor a zjišťovat tak, zda vejce pád přežilo nebo ne.

Asi nejjednodušším algoritmem, který danou úlohu řeší, je postup, kdy budete postupovat od nejnižšího patra k nejvyššímu, dokud se vejce nerozbije. Takové řešení může vypadat třeba takto:

def determine_egg_strength(n_floors, n_eggs, egg_survives_floor):
    for floor in range(n_floors):
        if not egg_survives_floor(floor+1):
            return floor
    return n_floors

Pokud tuto funkci zavoláme s výše definovanou funkcí egg_survives_floor(), dostaneme očekávaný výsledek:

>>> determine_egg_strength(30, 10, egg_survives_floor)
18

Toto řešení je validní, vždy najde správnou pevnost vejce a potřebuje vždy jen jedno vejce. Zároveň ale tato strategie není nejlepší, protože nevyužila všechna vejce, které měla k dispozici pro experiment. Lze postupovat mnohem chytřeji!

• Váš algoritmus bude otestován na sadě testovacích případů.
• Jeden testovací případ je dvojice hodnot n_floors, n_eggs.
• Pokud dojde při kterémkoli testu k chybě, získáte 0 bodů.
• Pro každý testovací případ bude váš algoritmus otestován pro všechny možné pevnosti vajec 0, …, n_floors, a zaznamená se dílčí skóre - nejvyšší počet testů, který jste potřebovali k určení pevnosti vejce.
• Skóre vaší strategie je pak součet dílčích skóre přes všechny testovací případy.
• Vaše skóre se pak porovná se skóre triviálního algoritmu výše a optimálního algoritmu a na základě toho bude určen poměrný počet bodů.

Příklad hodnocení triviálního algoritmu:

• Předpokládejme, že sada testovacích případů je ( (5, 1), (10, 2), (20, 3) ).
• Výše uvedený triviální algoritmus
  • pro testovací případ (5,1) a pro pevnost vejce 1 potřebuje 1 hod, pro pevnost vejce 2 potřebuje 2 hody, … pro pevnost vejce 5 potřebuje 5 hodů, takže jeho dílčí skóre je 5,
  • pro testovací případ (10, 2) a pro pevnost vejce 1 potřebuje 1 hod, … pro pevnost vejce 10 potřebuje 10 hodů, takže jeho dílčí skóre je 10,
  • pro testovací případ (20, 3) … má dílčí skóre 20.
• Celkové skóre vašeho algoritmu tak je 20 + 10 + 5 = 35.