Druhá série třicátého čtvrtého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Dostává se k vám druhé číslo hlavní kategorie 34. ročníku KSP.

Opět se můžete těsit několik praktických i teoretických úloh, speciálně bychom vás chtěli upozornit na jednu kompetitivní úlohu s procházkou po Brně. V této sérii se také objeví pokračování Manimového seriálu, ale jeho zadání bude dostupné až po ukončení minulé série.

Odměny & na Matfyz bez přijímaček

• Termín série: 20. prosince 2021 ve 32:00 (tedy další ráno v 8:00)
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Třem nejúspěšnějším řešitelům kompetitivní úlohy pošleme sladkou odměnu.

Zadání úloh

• 34-2-1: Skupinová jízdenka
• 34-2-2: Lezení
• 34-2-3: Na Hroších pláních
• 34-2-4: Brněnská procházka
• 34-2-S: Manimujeme – skupiny, transformace a updatery
• 34-2-X1: Převod čísel

34-2-1 Skupinová jízdenka (9 bodů)

Alice a Bob plánují navštívit Carol. Alice bydlí v Adršpachu, Bob v Břeclavi a Carol v Chebu. Alice i Bob chtějí jet vlakem firmy HippoExpres, která právě vyhlásila slevu na skupinové jízdné. Proto se jim vyplácí sejít se v nějakém městě po cestě a odtamtud už jet společně.

Vymyslete algoritmus, který jim cestu naplánuje. Dostanete mapu železniční sítě: neorientovaný graf, jehož vrcholy jsou stanice a hrany tratě mezi nimi, ohodnocené vzdálenostmi v kilometrech. Dále dostanete cenu jednotlivého i skupinového jízdného v korunách za kilometr. Zjistěte, kde se mají Alice s Bobem sejít, aby je cesta stála co nejméně.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: První řádek vstupu obsahuje 4 celá čísla: počet stanic n, počet tratí m, cenu jednotlivého jízdného v Kč za km, cenu skupinového jízdného v Kč za km. Následujících m řádků popisuje jednotlivé trati. Na každém z nich jsou 3 celá čísla: koncové stanice trati a délka trati v kilometrech. Stanice číslujeme od 1 do n, číslo 1 je Adršpach, 2 Břeclav a 3 je Cheb.

Formát výstupu: Vypište jediné číslo: nejmenší možnou cenu, kterou Alice s Bobem dohromady zaplatí za jízdenky.

4 5 1 1
1 4 3
2 4 3
3 4 3
1 3 5
2 3 5

9

Řešení

34-2-2 Lezení (10 bodů)

Sportovní lezení na olympijských hrách sestává ze tří disciplín: lezení na rychlost, bouldering a lezení na obtížnost. Počet trestných bodů, které lezec dostane za disciplínu, odpovídá jeho pořadí (počítáno od 1). Celkový počet trestných bodů je součin trestných bodů za jednotlivé disciplíny. Vítězem se stává lezec, který má nejmenší počet celkových trestných bodů, podobným způsobem se seřadí zbylí lezci.

Například pokud by lezec A skončil v disciplínách na 1., 4. a 7. místě a lezec B na 2., 13. a 1. místě, pak dostane lezec A celkem 1 ·4 ·7 = 28 trestných bodů a umístí se tak až za lezcem B s 2 ·13 ·1 = 26 trestnými body.

První dvě disciplíny již proběhly a je známé pořadí všech n lezců v obou dvou disciplínách. Náš nejlepší lezec je mistrem v lezení na obtížnost a věří si na první místo v této disciplíně. I tak ale netuší, jaké bude výsledné pořadí. Pomůžete mu zjistit, na jaké nejhorší příčce se může umístit, pokud by se mu skutečně podařilo skončit první v lezení na obtížnost, ale ostatní by se mohli v lezení na obtížnost seřadit libovolně?

Řešení

34-2-3 Na Hroších pláních (12 bodů)

Na Hroších pláních byla objevena obrovská naleziště čokolády! Všichni organizátoři KSPčka se tam hned rozjeli, aby si každý z nich vykolíkoval svůj claim – území, kde bude těžit.

Každý claim má tvar n-úhelníku v rovině (ne nutně konvexního). V jeho vrcholech jsou zapíchané kolíky, po obvodu očíslované postupně od 1 do n. Každý organizátor má svou barvu kolíků, ale i tak je proklatě obtížné zjistit, jestli se nějaké dva claimy protínají. Vymyslete algoritmus, který to pozná.

Vymyslete algoritmus, který na vstupu dostane souřadnice kolíků určujících dva n-úhelníky claimů. Na výstup vypíše buď souřadnice nějakého bodu ležícího v průniku obou claimů, nebo sdělí, že claimy žádný společný bod nemají. Pokud se dva claimy jenom dotknou (vrcholem nebo hranou), za průnik to nepovažujeme.

Lehčí varianta (za 8 bodů): Vyřešte případ, kdy oba n-úhelníky jsou konvexní.

Řešení

34-2-4 Brněnská procházka (14 bodů)

Kevin chce zorganizovat dlouhou procházku po Brně a okolí, ale nechce se zbytečně dívat na stejná místa vícekrát. Proto se rozhodl, že zvolí poněkud netradiční omezení na trasu procházky.

Brno je ohodnoceným neorientovaným grafem, kde vrcholy odpovídají křižovatkám a hrany ulicím. Ulice jsou celočíselně ohodnoceny jejich délkou v metrech. Vaším úkolem je najít co nejdelší cestu, ze které nezahlédnete žádnou jinou ulici dvakrát (tedy pokud vezmete libovolné dva vrcholy cesty, které po sobě těsně nenásledují, tak mezi nimi nebude v grafu existovat hrana). Začít i skončit můžete na libovolném vrcholu, jen od sebe také musí udržet vzdálenost dvou hran. Nejdelší cesta je ta, která má největší součet délek hran, na počtu hran Kevinovi nezáleží.

Toto je speciální soutěžní úloha se statických vstupem, kde všichni řešitelé dostanou stejný vstup a přes Odevzdávátko pak odevzdají nejlepší řešení, které se jim povede najít. Obodování úlohy provedeme až po konci série a to tak, že nejlepší řešení dostane plný počet bodů a ostatní řešení dostanou body odstupňovaně podle toho, jak byla dobrá. Zároveň slibujeme, že každé korektní řešení dostane alespoň jeden bod.

V průběhu série se můžete s ostatními porovnávat pomocí průběžné online výsledkovky. Upozorňujeme, že se v ní mohou vyskytnout i řešení od organizátorů.

Jde o těžkou úlohu, pro kterou neslibujeme existenci efektivního algoritmu na nalezení optimálního řešení. Pro inspiraci, jak k této úloze přistoupit, se můžete podívat na vzorová řešení minulé soutěžní úlohy 33-3-4. Vezměte ale na vědomí, že jde o výrazně odlišnou úlohu, a tak budete muset zvolit jiný přístup a rozhodně se vám vyplatí experimentovat.

Tuto úlohu také doporučujeme začít řešit včas, vstupní data jsou relativně velká a bude se vám velmi hodit čas na postupné vylepšování vašeho řešení.

Formát vstupu: Na prvním řádku dostanete počet vrcholů N a počet ulic M. Následuje N řádků s definicemi vrcholů ve formátu v lat lon, kde v je číslo vrcholu a lat a lon popisují GPS souřadnice – ty se mohou hodit pro vizualizace, ale nijak je není potřeba použít pro počítání délek. Vstup zakončuje M řádků s definicemi hran. Na každém řádku je popsána jedna hrana trojicí čísel oddělenou mezerami: v₁, v₂ a D. Taková hrana spojuje vrcholy v₁ a v₂ a má celočíselnou délku D metrů. Vrcholy jsou indexované od nuly.

Formát výstupu: Na první řádek vypište celkovou délku nalezené cesty v metrech. Poté vypište čísla vrcholů v pořadí, ve kterém je cesta navštěvuje, každé na samostatný řádek.

Odevzdávátko spočítá délku cesty a přidá odevzdané řešení do průběžné výsledkovky. Upozorňujeme, že od každého řešitele bereme v potaz vždy jeho poslední odevzdané řešení, i kdyby si tím měl zhoršit skóre. Proto vám doporučujeme si svá řešení ukládat, abyste je případně mohli odevzdat znovu.

Zdroje: Graf k této úloze jsme získali zpracováním dat z projektu OpenStreetMap.

6 7
0 49.16298 16.56755
1 49.16316 16.56767
2 49.16319 16.56854
3 49.16328 16.56858
4 49.16328 16.56951
5 49.17429 16.55060
0 2 15
0 4 10
1 2 5
1 3 20
2 5 1
3 4 5
3 5 2

40
3
1
2
0

Řešení

34-2-X1 Převod čísel (10 bodů)

Kevin začal řešit úkol do informatiky. Chtěli po něm, aby převáděl čísla mezi desítkovou a dvojkovou soustavou. Ale tento úkol ho po chvíli přestal bavit, a tak začal převádět čísla i mezi jinými soustavami. Vaším úkolem bude mu s těmito převody pomoct. Vymyslete program, který bude převádět čísla ze soustavy o základu A do soustavy o základu B.

Na vstupu dostanete nejprve dvojici čísel A a B následovanou N čísly mezi 0 a A-1 značící vstupní číslo v soustavě o základu A. Výstupem vašeho programu bude posloupnost čísel mezi 0 a B-1 reprezentující totéž číslo, ale v soustavě o základu B.

Ve vašem programu ovšem nemůžete pracovat s libovolně velkými čísly v konstantním čase. Nemůžete tedy převést číslo na vstupu do jednoho čísla a to pak dále převádět do výstupní soustavy. Můžete ale předpokládat, že v konstantním čase umíte pracovat v čísly velikosti O((A+B)^k) pro nějakou pevnou konstantu k.

Nápověda: Existují algoritmy, které násobí n-ciferná čísla s časovou složitostí O(n^c) pro 1≤ c<2. Najdete je například v Průvodci labyrintem algoritmů v kapitole Rozděl a panuj. Ve svém řešení můžete takový algoritmus používat jako podprogram, aniž byste ho museli sami popisovat.

Řešení

34-2-S Manimujeme – skupiny, transformace a updatery (15 bodů)

Úvod

Tento díl a všechny nadcházející budou nově doprovázeny odkazy na dokumentaci, která funkce a třídy popisuje podrobněji a rovněž obsahuje jejich zdrojový kód. Pokud si u některé třídy/metody nejste jisti, jak přesně se chová či jaké parametry navíc má, tak dokumentace je správné místo, kam se podívat.

Hlavní stránka je na tomto odkazu: https://docs.manim.community/en/stable/reference.html

Odkaz na Jupyter notebook tohoto dílu je zde: https://mybinder.org/v2/gh/ksp/ksp-serial-34.git/HEAD?labpath=serial2.ipynb

Práce se skupinami objektů

from manim import *

class VGroupExample(Scene):
    def construct(self):
        s1 = Square(color=RED)
        s2 = Square(color=GREEN)
        s3 = Square(color=BLUE)

        s1.next_to(s2, LEFT)
        s3.next_to(s2, RIGHT)

        self.play(Write(s1), Write(s2), Write(s3))

        group = VGroup(s1, s2, s3)

        # aplikace škálování na celou skupinu
        self.play(group.animate.scale(1.5).shift(UP))

        # na skupině můžeme indexovat
        self.play(group[1].animate.shift(DOWN * 2))

        # změna barvy se aplikuje na všechny objekty
        self.play(group.animate.set_color(WHITE))
        self.play(group.animate.set_fill(WHITE, 1))

VGroup [doc] také obsahuje funkce k uspořádávání objektů. Nejjednodušší je funkce arrange [doc], která uspořádá objekty vedle sebe podle toho, v jakém pořadí byly do konstruktoru VGroup vloženy:

from manim import *
from random import seed, uniform

class ArrangeExample(Scene):
    def construct(self):
        seed(0xDEADBEEF)

        # používáme *, protože VGroup bere samotné objekty (viz minulý příklad)
        circles = VGroup(
            *[
                Circle(radius=0.1)
                .scale(uniform(0.5, 4))
                .shift(UP * uniform(-3, 3) + RIGHT * uniform(-5, 5))
                for _ in range(12)
            ]
        )

        self.play(FadeIn(circles))

        # uspořádání vedle sebe
        self.play(circles.animate.arrange())

        # různé odsazení a směry
        self.play(circles.animate.arrange(direction=DOWN, buff=0.1))
        self.play(circles.animate.arrange(buff=0.4))

Parametr buff nastavuje mezery mezi jednotlivými objekty a dá se použít ve většině funkcí, které nějakým způsobem posouvají objekty k jiným, jako například next_to [doc]. Parametr direction určuje směr, ve kterém budou objekty uspořádány.

Obecnější variantou funkce arrange je funkce arrange_in_grid [doc], která objekty uspořádá do pravidelné mřížky:

from manim import *
from random import seed, uniform

class ArrangeInGridExample(Scene):
    def construct(self):
        seed(0xDEADBEEF)

        circles = VGroup(
            *[
                Circle(radius=0.1)
                .scale(uniform(0.5, 2))
                .shift(UP * uniform(-3, 3) + RIGHT * uniform(-5, 5))
                for _ in range(9 ** 2)
            ]
        )

        self.play(FadeIn(circles))

        # uspořádání do mřížky
        self.play(circles.animate.arrange_in_grid())

        # různé odsazení a počet řádků/sloupců
        self.play(circles.animate.arrange_in_grid(rows=5, buff=0))
        self.play(circles.animate.arrange_in_grid(cols=12, buff=0.3))

Kromě parametru buff rovněž přijímá parametry rows a cols, které určují počet řádků a sloupců, které má mřížka mít.

Přidávání a odebírání objektů

from manim import *

class AddRemoveExample(Scene):
    def construct(self):
        square = Square(fill_color=WHITE, fill_opacity=1)
        small_scale = 0.6

        triangle = Triangle(fill_opacity=1).scale(small_scale).move_to(square)

        self.play(Write(square))

        # přidání trojúhelníku pod čtverec
        self.bring_to_back(triangle)
        self.play(square.animate.shift(LEFT * 2))

        circle = Circle(fill_opacity=1).scale(small_scale).move_to(square)

        # přidání kruhu pod čtverec
        self.bring_to_back(circle)
        self.play(square.animate.shift(RIGHT * 2))

        square2 = (
            Square(stroke_color=GREEN, fill_color=GREEN, fill_opacity=1)
            .scale(small_scale)
            .move_to(square)
        )

        self.remove(triangle)

        # stejné jako self.add
        # přidání dopředu tu spíš nechceme, ale je dobré vidět co dělá
        self.bring_to_front(square2)

        self.play(square.animate.shift(RIGHT * 2))

O podrobnějším fungování scény se budeme bavit v některém s následujících dílů. Prozatím je dobré si uvědomit, že objekty přidané na scéně mají určené pořadí, ve kterém se vykreslují (určené tím, v jakém pořadí objekty do scény přidáváme).

Překrývající se animace

from manim import *

class AnimationGroupExample(Scene):
    def construct(self):
        c1 = Square(color=RED)
        c2 = Square(color=GREEN)
        c3 = Square(color=BLUE)

        VGroup(c1, c2, c3).arrange(buff=1)

        # každá další animace se spustí v polovině té předchozí (0.5)
        self.play(AnimationGroup(Write(c1), Write(c2), Write(c3), lag_ratio=0.5))

        # každá další animace se spustí v desetině té předchozí (0.1)
        self.play(AnimationGroup(FadeOut(c1), FadeOut(c2), FadeOut(c3), lag_ratio=0.1))

        # jedna z animací může být rovněž skupina, která může mít sama o sobě zpoždění
        self.play(
            AnimationGroup(
                AnimationGroup(Write(c1), Write(c2), lag_ratio=0.1),
                Write(c3),
                lag_ratio=0.5,
            )
        )

        # lag_ratio může být i záporné (animace se budou spouštět obráceně)
        self.play(AnimationGroup(FadeOut(c1), FadeOut(c2), FadeOut(c3), lag_ratio=-0.1))

Překrývání animací funguje implicitně v rámci třídy VGroup, kterou jsme si ukazovali výše. Některé animace jako Write mají defaultně nastavený lag_ratio, který se propaguje do skupiny a objekty se tedy animují postupně:

from manim import *

class VGroupLagRatioExample(Scene):
    def construct(self):
        squares = VGroup(Square(), Square(), Square()).arrange(buff=0.5).scale(1.5)

        # postupné vykreslení čtverců
        self.play(Write(squares))

        # FadeOut lag_ratio má nulové, animace se vykonají najednou
        self.play(FadeOut(squares))

        squares.set_color(BLUE)

        # lag_ratio můžeme manuálně nastavit tak, aby se čtverce vykreslily najednou
        self.play(Write(squares, lag_ratio=0))

        self.play(FadeOut(squares, lag_ratio=0.5))

Práce s pozorností

from manim import *

class AttentionExample(Scene):
    def construct(self):
        c1 = Square()

        labels = [
            Tex("Flash"),
            Tex("Indicate"),
            Tex("Wiggle"),
            Tex("FocusOn"),
            Tex("Circumscribe"),
        ]

        # labely posuneme dolů (pod čtverec)
        for label in labels:
            label.shift(DOWN * 1.5).scale(1.5)

        def switch_labels(i: int):
            """Animace přeměny jednoho labelu na druhého."""
            return AnimationGroup(
                FadeOut(labels[i], shift=UP * 0.5),
                FadeIn(labels[i + 1], shift=UP * 0.5),
            )

        self.play(Write(c1))

        self.play(FadeIn(labels[0], shift=UP * 0.5), c1.animate.shift(UP))

        # Flash
        self.play(Flash(c1, flash_radius=1.6, num_lines=20))

        # Indicate
        self.play(AnimationGroup(switch_labels(0), Indicate(c1), lag_ratio=0.7))

        # Wiggle
        self.play(AnimationGroup(switch_labels(1), Wiggle(c1), lag_ratio=0.7))

        # FocusOn
        self.play(AnimationGroup(switch_labels(2), FocusOn(c1), lag_ratio=0.7))

        # Circumscribe
        self.play(AnimationGroup(switch_labels(3), Circumscribe(c1), lag_ratio=0.7))

U animací Flash, Indicate a Circumscribe je užitečný parametr color, který mění barvu z defaultní žluté na jinou.

Transformace

Ten nejběžnější je animace Transform [doc], která jeden objekt plynule přetransformuje na druhý.

from manim import *

class BasicTransformExample(Scene):
    def construct(self):
        c = Circle().scale(2)
        s = Square().scale(2)

        self.play(Write(c))

        self.play(Transform(c, s))

Je však potřeba dávat pozor na to, s jakým objektem po transformaci pracujeme. Transform totiž přetransformuje první objekt na druhý, který následně ze scény odstraní. To znamená, že při následujících transformacích je potřeba stále používat originální objekt, jinak se budou dít prapodivné věci:

from manim import *

class BadTransformExample(Scene):
    def construct(self):
        good = [Circle(color=GREEN), Square(color=GREEN), Triangle(color=GREEN)]
        bad = [Circle(color=RED), Square(color=RED), Triangle(color=RED)]

        # uspořádání do mřížky - nahoře dobré, dole špatné
        VGroup(*(good + bad)).arrange_in_grid(rows=2, buff=1)

        self.play(Write(good[0]), Write(bad[0]))

        self.play(
            Transform(good[0], good[1]),
            Transform(bad[0], bad[1]),
        )

        self.play(
            Transform(good[0], good[2]),
            Transform(bad[1], bad[2]),
        )

Pokud vám toto chovaní přijde neintuitivní, je možné použít ReplacementTransform [doc], která po přeměně odstraní první objekt a chování výše se tedy prohodí.

Mimo jiné existuje ještě TransformMatchingShapes, která se přeměnu snaží dělat chytře – části prvního objektu, které odpovídají částem druhého, transformuje přesunem:

from manim import *

class TransformMatchingShapesExample(Scene):
    def construct(self):
        ksp_matching = Tex("KSP").scale(5)
        ksp_full_matching = Tex("Korespondenční Seminář z Programování")

        ksp_regular = ksp_matching.copy().set_color(BLUE)
        ksp_full_regular = ksp_full_matching.copy().set_color(BLUE)

        VGroup(ksp_matching, ksp_regular).arrange(direction=DOWN, buff=1)
        ksp_full_matching.move_to(ksp_matching)
        ksp_full_regular.move_to(ksp_regular)

        self.play(Write(ksp_matching), Write(ksp_regular))

        self.play(
            TransformMatchingShapes(ksp_matching, ksp_full_matching),
            Transform(ksp_regular, ksp_full_regular),
        )

Chová se stejně jako ReplacementTransform – po transformaci je potřeba přistupovat k objektu, na který bylo transformováno. V kódu rovněž k ušetření kódu používáme metodu copy [doc], která vytváří kopie Manimových objektů.

Updatery

V Manimu se k podobným věcem hodí updatery. Jedná se o funkce obsahující libovolný kód, které jsou připojené k nějakému objektu a jsou Manimem volány každý vykreslovaný snímek:

from manim import *

class SimpleUpdaterExample(Scene):
    def construct(self):
        square = Square()
        square_label = Tex("A neat square.").next_to(square, UP, buff=0.5)

        self.play(Write(square))
        self.play(FadeIn(square_label, shift=UP * 0.5))

        def label_updater(obj):
            """Updater, který posune objekt nad čtverec.

            První parametr (obj) je vždy objekt, na který je updater přidaný."""
            obj.next_to(square, UP, buff=0.5)

        # popisek čtverce chceme mít fixně nad čtvercem
        square_label.add_updater(label_updater)

        # vždy zůstává nad čtvercem
        self.play(square.animate.shift(LEFT * 3))
        self.play(square.animate.scale(1 / 2))
        self.play(square.animate.rotate(PI / 2).shift(RIGHT * 3 + DOWN * 0.5).scale(3))

        # odstranění updateru můžeme udělat přes remove_updater
        square_label.remove_updater(label_updater)
        self.play(square.animate.scale(1 / 3))
        self.play(square.animate.rotate(PI / 2))

Kromě posouvání nebo změny barev se může hodit objekt s updaterem měnit (například když sledujeme nějakou pozici). K tomu použijeme funkci become [doc], která přemění libovolný Manimový objekt na nějaký jiný:

from manim import *

class BecomeUpdaterExample(Scene):
    def format_point(self, point):
        """Formátování dané souřadnice na [x, y]."""
        return f"[{point[0]:.2f}, {point[1]:.2f}]"

    def construct(self):
        circle = Circle(color=WHITE)

        def circle_label_updater(obj):
            """Updater pro label, který jej posouvá nad bod a nastavuje jeho text."""
            obj.become(Tex(f"p = {self.format_point(circle.get_center())}"))
            obj.next_to(circle, UP, buff=0.35)

        self.play(Write(circle))

        circle_label = Tex()

        # používáme tu trochu trik k šetření kódu - updater voláme proto,
        # abychom nastavili popisek na základní hodnotu a pozici
        circle_label_updater(circle_label)

        self.play(FadeIn(circle_label, shift=UP * 0.3))

        circle_label.add_updater(circle_label_updater)

        # tato animace se bude pravděpodobně renderovat dlouho, protože
        # updater v každém snímku vytváří Tex objekt, což nějakou dobu trvá
        self.play(circle.animate.shift(RIGHT))
        self.play(circle.animate.shift(LEFT * 3 + UP))
        self.play(circle.animate.shift(DOWN * 2 + RIGHT * 2))
        self.play(circle.animate.shift(UP))

Kód kromě become obsahuje také funkci get_center [doc], která vrátí tříprvkové pole určující pozici středu objektu na scéně. Nás ovšem zajímají pouze hodnoty x a y, které jsou na pozicích 0 a 1.

Úlohy

K odevzdávání úloh lze animaci vytvořit buď online přímo v Jupyteru pro tento díl (na konci dokumentu je kostra pro každou z úloh, do které ji jde přímo doprogramovat), nebo i lokálně, pokud máte nainstalovný Manim.

Odevzdávejte celý zdrojový kód v zazipovaném (a nezaheslovaném) archivu.

V každé z úloh tohoto i nadcházejících dílů je cílem naprogramovat animaci obecně, ne jen pro jeden vstup. Animace by za vás měl dělat nějaký algoritmus, rozhodně byste je neměli programovat manuálně (pohyb za pohybem).

Úkol 1 – Trojúhelník [3b]

Naprogramujte animaci pohybujícího se trojúhelníka:

Body a úsečku jde definovat přes třídy Dot [doc] a Line [doc]:

from manim import *

class LineExample(Scene):
    def construct(self):
        p1 = Dot()
        p2 = Dot()

        points = VGroup(p1, p2).arrange(buff=2.5)

        line = Line(start=p1.get_center(), end=p2.get_center())

        self.play(Write(p1), Write(p2))

        self.play(Write(line))

K vytvoření kruhu se hodí funkce Circle.from_three_points [doc], která vytvoří objekt kruhu ze tří daných bodů:

from manim import *

class CircleFromPointsExample(Scene):
    def construct(self):
        p1 = Dot().shift(LEFT + UP)
        p2 = Dot().shift(DOWN * 1.5)
        p3 = Dot().shift(RIGHT + UP)

        dots = VGroup(p1, p2, p3)

        # vytvoření kruhu ze tří bodů
        circle = Circle.from_three_points(p1.get_center(), p2.get_center(), p3.get_center(), color=WHITE)

        self.play(Write(dots), run_time=1.5)
        self.play(Write(circle))

Úkol 2 – Vlna [6b]

Naprogramujte animaci plynule se šířící vlny v bludišti:

Hodit se vám bude převážně arrange_in_grid k pozicování čtverců, AnimationGroup s parametrem lag_ratio pro překrývání barvení a funkce color_gradient [doc], která z daných vstupních barev a počtu výstupních vygeneruje pole barev, které je plynulý přechod mezi vstupními barvami:

from manim import *

class ColorGradientExample(Scene):
    def construct(self):
        rows = 6
        square_count = rows * 9

        colors = ["#ef476f", "#ffd166", "#06d6a0", "#118ab2"]
        squares = [
            Square(fill_color=WHITE, fill_opacity=1).scale(0.3)
            for _ in range(square_count)
        ]

        group = VGroup(*squares).arrange_in_grid(rows=rows)

        self.play(Write(group, lag_ratio=0.04))

        all_colors = color_gradient(colors, square_count)

        self.play(
            AnimationGroup(
                *[s.animate.set_color(all_colors[i]) for i, s in enumerate(squares)],
                lag_ratio=0.02,
            )
        )

        self.play(FadeOut(group))

Zde je textový vstup, který generoval bludiště v autorském řešení:

#######################################################
#  #################            ##                    #
# ##################           ####                   #
# #################            ####                   #
#  ###############             #####               # ##
#      #########               #####               ####
#         ###                  ######            ######
#          ###            ##   #####    ###       #####
#          ####      ########   ####  #####        ## #
#          #####   ##########   ###  ########       # #
#         #####   ###########        ########         #
#         ####   ###########        ##########        #
#        ##      ###########        ##########        #
#      ####     ############      #############       #
#    ######     ############     #############        #
# #########  ## ###########     #########    #        #
# ############### #########     #######               #
# ###############   ######      ######                #
# ###############    #####       ####                 #
#   #############      #                ##            #
#     #  #######                       ########### ####
#          ###         #              #################
# ##                  ####            #################
#####                ######          ##################
######                ######         ##################
# ###      ###        #######  ###   ###############  #
#         ####         ############   ####  #######   #
#        #####          ############          ###     #
#         ###            ##########                   #
#######################################################

Úkol 3 – Hilbert [6b]

Naprogramujte animaci Hilbertovy křivky (nebo nějaké jiné pěkné křivky vyplňující prostor):

Hodit se bude pomocná třída Path (pozor – ta není Manimová, ale naše), která ze vstupního pole bodů vytvoří cestu:

from manim import *

class Path(VMobject):
    def __init__(self, points, *args, **kwargs):
        super().__init__(self, *args, **kwargs)
        self.set_points_as_corners(points)

    def get_important_points(self):
        """Vrátí důležité body křivky."""
        # drobné vysvětlení: Manim k vytváření úseček používá kvadratické Bézierovy křivky
        # - každá taková křivka má čtyři body -- dva krajní a dva řidicí
        # - path.points vrací *všechny* body, což po několika iteracích roste exponenciálně
        #
        # proto používáme funkce get_*_anchors, které vrací pouze krajní body
        # pro více detailů viz https://en.wikipedia.org/wiki/Bézier_curve
        return list(self.get_start_anchors()) + [self.get_end_anchors()[-1]]

class PathExample(Scene):
    def construct(self):
        path = Path([LEFT + UP, LEFT + DOWN, RIGHT + UP, RIGHT + DOWN])

        self.play(Write(path))

        # opraveno po vydání seriálu, předtím jsme používali     path.points]), vysvětlení viz výše
        path_points = VGroup(*[Dot().move_to(point) for point in path.get_important_points()])

        self.play(Write(path_points))

        path2 = path.copy()
        path3 = path.copy()

        self.play(
            path2.animate.next_to(path, LEFT, buff=1),
            path3.animate.next_to(path, RIGHT, buff=1),
        )

        # pozor, tohle není úplně intuitivní
        # LEFT flipne dolů, jelikož určuje osu, přes kterou se objekt přetočí
        self.play(
            path2.animate.flip(),
            path3.animate.flip(LEFT),
        )

Rovněž používáme flip [doc], který objekt přetočí v dané ose.

Tomáš Sláma

Řešení