11. úkol - Homer's Fridge

Vaší poslední úlohou je vytvoření “komplexního systému” pro podporu zákazníka. Úloha se skládá z implementace šesti samostatných úlolů, které jsou samostatně hodnoceny. Jednotlivé úkoly na sebe mohou navazovat - chyba v implementaci jednoho může způosobit nefunkčnost druhého.

Jedna z nejoblíbenějších aktivit Homera Simpsona je prozkoumávání své lednice. Jakožto nadšenec do moderních technologií si svou lednici (proměnná fridge) nově reprezentoval v Pythonu pomocí datového typu list. Jednotlivé položky listu odpovídají pokrmům v lednici. U každého jídla (food) ho zajímají především dvě věci: název jídla (name) a počet dní, než se dané jídlo zkazí (expiration). Předpokládejme, že počet dní do expirace je vždy přirozené číslo větší nebo rovno nule. Mimochodem, jak by Bart poznamenal, tak jeho táta stejně ani netuší, že nějaká jiná čísla než přirozená existují. Jídlo si tedy Homer reprezentoval jako objekt Food se zmíněnými dvěma vlastnostmi (name a expiration).

class Food:
    def __init__(self, name, expiration):
        self.name = name
        self.expiration = expiration
 
fridge = [Food("beer", 4), Food("steak", 1), Food("hamburger", 1), Food("donut", 3)]

Ve výše uvedené lednici má Homer tedy čtyři věci: pivo, steak, hamburger a koblihu. S tím, že pivo se mu zkazí za čtyři dny, steak a hamburger zítra (za jeden den) a kobliha mu tam vydrží ještě tři dny.

Aby se Homer z konzole dozvěděl, co v lednici má, tak si napsal následující metodu openFridge(fridge), která mu jeho virtuální lednici „otevře“. Tzn., projde daný list (fridge) a jednotlivé položky (food) vypíše do konzole včetně názvu jídla a expirace.

def openFridge(fridge):
    print("Following items are in Homer's fridge:")
    for food in fridge:
        print("{0} (expires in: {1} days)".format(
            str(food.name), str(food.expiration))
        )

Volání takovéto funkce i s jejím výpisem lze vidět níže (vyzkoušejte si).

openFridge(fridge)
 
Following items are in Homer's fridge:
beer (expires in: 4 days)
steak (expires in: 1 days)
hamburger (expires in: 1 days)
donut (expires in: 3 days)

Vaším úkolem je do šablony homer.py implementovat následující funkce.

Vžijte se do Homera Simpsona a vytvořte si další metodu sami. Bude to metoda s názvem maxExpirationDay(fridge), která Vám vrátí nejdelší expirační hodnotu ze všech jídel v lednici. V případě prázdné lednice bude funkce vracet hodnotu -1.

print(maxExpirationDay(fridge))
 
4

Pro výše uvedenou lednici metoda vrátí číslo čtyři, jelikož se jedná o maximální expirační hodnotu, kterou má pivo (To, že se jedná o pivo, Homera momentálně nezajímá).

Dále by Homer chtěl mít přehled o tom, kolik jídel s danou expirační dobou v lednici má. Proto chce vytvořit metodu histogramOfExpirations(fridge), jež mu vrátí pole/list, kde index pole/listu odpovídá době expirace a hodnota na tomto indexu odpovídá počtu jídel s touto expirační dobou.

histogram = histogramOfExpirations(fridge)
print(histogram)
 
[0, 2, 0, 1, 1]

Z uvedeného výstupu vidíme, že v lednici není žádné jídlo, které by nevydrželo do zítra (tzn., zkazilo by se dnes), protože v poli na indexu 0 je 0. Ovšem dvě jídla vydrží už jenom jeden den (steak a hamburger), protože na indexu 1 je hodnota 2. Dále pak víme, že nemáme žádné jídlo, které by mělo expirační hodnotu dva dny, jelikož na indexu 2 je hodnota 0. Obdobně jedno jídlo (donut) vydrží tři dny, atd.

(Nápověda: délka výstupního listu bude rovna maxExpirationDay(fridge) + 1, využijte proto tuto metodu v implementaci).

Homera napadla neobvykle geniální myšlenka: seřadit jídlo v lednici vzestupně podle expirační doby (tzn. od nejnižší po nejvyšší), aby se náhodou nestalo, že na konci lednice zůstane jídlo, na které se včas nedostane a on by o něho tak přisel. Na to ale Bart drze poznamenal, že táta neumí porovnávat čísla, takže nemůže implementovat ani triviální Bubble sort. Ještě než stihl Homer Barta chytit pod krkem, tak chytrá Lisa přišla s tím, že porovnávání v tomto případě ani není potřeba, nicméně se musí postupovat přesně podle toho, co nadiktuje.

Nejprve je třeba vytvořit funkci cumulativeSum(histogram) postupně nasčítavající jednotlivé hodnoty histogramu z předchozího úkolu.

print(cumulativeSum(histogram))
 
[0, 2, 2, 3, 4]

Výstupní pole je tedy stejné délky jako histogram a první hodnota na indexu 0 je také shodná s první hodnotou v histogramu. Avšak další hodnoty kumulativní sumy jsou už rovny součtu hodnoty v histogramu na dané pozici s předchozí hodnotou v kumulativní sumě. Jelikož Homer nechápal, tak mu Lisa dala pár dalších příkladů volání této funkce:

print(cumulativeSum([1, 2, 3, 4]))
[1, 3, 6, 10]
 
print(cumulativeSum([1, 1, 1, 1]))
[1, 2, 3, 4]
 
print(cumulativeSum([2, 0, 0, 1]))
[2, 2, 2, 3]

Lisa následně tvrdí, že výstupní pole kumulativní sumy lze využít k určení indexu, na kterém se bude dané jídlo nacházet v seřazeném poli. Můžeme tudíž rovnou vytvořit funkci ´´sortFoodInFridge(fridge)´´ vracející seřazené jídlo v lednici podle expirační doby. Postup je následující:

1. procházíme postupně původní lednici (list fridge)
2. zjistíme si expirační hodnotu aktuálního jídla
3. v poli kumulativní sumy pod indexem odpovídající hodnotě z předchozího bodu odečteme jedničku, tuto nově aktualizovanou hodnotu nazvěme „posInd“
4. hodnota „posInd“ nyní odpovídá indexu aktuálního jídla (z bodu jedna) v nově seřazeném poli, vložíme ho tedy na toto patřičné místo
5. opakujeme postup pro další položku v lednici, dokud nedojdeme na konec lednice

Homer sice nechápal, co vlastně dělal, ale dopracoval se k tíženému výsledku:

openFridge(sortFoodInFridge(fridge))
 
Following items are in Homer's fridge:
hamburger (expires in: 1 days)
steak (expires in: 1 days)
donut (expires in: 3 days)
beer (expires in: 4 days)

Bart si všiml, že výše uvedené řazení není stabilní a celou Homerovou práci tím chtěl zesměšnit. Načež Lisa odvětila, že se to dá lehce napravit, když se pořadí prvků (food) vstupního pole (fridge) ve funkci sortFoodInFridge(fridge) před samotným voláním otočí. Homer se tedy rozhodl, že naimplementuje metodu reverseFridge(fridge), která převrátí pořadí jídel v lednici.

openFridge(reverseFridge(fridge))
 
Following items are in Homer's fridge:
donut (expires in: 3 days)
hamburger (expires in: 1 days)
steak (expires in: 1 days)
beer (expires in: 4 days)

Výsledné řazení pak bude vypadat takto:

openFridge(sortFoodInFridge(reverseFridge(fridge)))
 
Following items are in Homer's fridge:
steak (expires in: 1 days)
hamburger (expires in: 1 days)
donut (expires in: 3 days)
beer (expires in: 4 days)

Poslední funkcionalita, na kterou se Homer nejvíce těší, se jmenuje eatFood(name, fridge). Jejím účelem je vyndat požadované jídlo (podle názvu v name) z lednice (fridge). V případě duplicity jídla (například v lednici budou dva donuty) funkce odstraní vždy to jídlo s nejnižší expirační dobou. Funkce vrací novou instanci lednice bez požadovaného jídla, pokud se ho podaří najít. V opačném případě se vrátí pouze kopie původní lednice. Jídlo v lednici nijak nepřerovnávejte.

openFridge(
    eatFood("donut",
        [Food("beer", 4), Food("steak", 1), Food("hamburger", 1),
        Food("donut", 3), Food("donut", 1), Food("donut", 6)]
    ))
 
Following items are in Homer's fridge:
beer (expires in: 4 days)
steak (expires in: 1 days)
hamburger (expires in: 1 days)
donut (expires in: 3 days)
donut (expires in: 6 days)

Za úlohu je možno získat 6 bodů.