Zdrojové kódy k příkladům a úlohám 34. série KSP (Manim).
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

452 lines 16 KiB Raw Permalink Blame History

 `{` ` "cells": [` ` {` ` "cell_type": "markdown",` ` "id": "36cee816",` ` "metadata": {},` ` "source": [` ` "# Řešení 3. série"` ` ]` ` },` ` {` ` "cell_type": "code",` ` "execution_count": null,` ` "id": "efe16561",` ` "metadata": {},` ` "outputs": [],` ` "source": [` ` "from manim import *"` ` ]` ` },` ` {` ` "cell_type": "markdown",` ` "id": "36ec08cc",` ` "metadata": {},` ` "source": [` ` "## Grafový algoritmus"` ` ]` ` },` ` {` ` "cell_type": "code",` ` "execution_count": null,` ` "id": "e7a3da39",` ` "metadata": {},` ` "outputs": [],` ` "source": [` ` "%%manim -v WARNING -qh GraphAlgorithm\n",` ` "\n",` ` "from random import *\n",` ` "import networkx as nx\n",` ` "\n",` ` "\n",` ` "class GraphAlgorithm(Scene):\n",` ` " def construct(self):\n",` ` " seed(0xDEADBEEF)\n",` ` "\n",` ` " n = 14\n",` ` " p = 3 / n\n",` ` "\n",` ` " # generujeme, dokud nemáme spojitý graf\n",` ` " graph = None\n",` ` " while graph is None or not nx.is_connected(graph):\n",` ` " graph = nx.generators.random_graphs.gnp_random_graph(n, p)\n",` ` "\n",` ` " g = (\n",` ` " Graph(graph.nodes, graph.edges, layout_config={\"seed\": 0})\n",` ` " .scale(2.7)\n",` ` " .rotate(PI / 12)\n",` ` " )\n",` ` "\n",` ` " explored = set()\n",` ` "\n",` ` " def dfs(v, position_object):\n",` ` " \"\"\"Rekurzivní DFS, které posouvá position_object.\"\"\"\n",` ` " neighbours = list(graph.neighbors(v))\n",` ` "\n",` ` " for w in neighbours:\n",` ` " if w in explored:\n",` ` " continue\n",` ` "\n",` ` " # Manim bohužel neorientovaný graf bere jako orientovaný\n",` ` " edge = (v, w) if (v, w) in g.edges else (w, v)\n",` ` "\n",` ` " unexplored_neighbours = [w for w in neighbours if w not in explored]\n",` ` " unexplored_neighbour_edges = [\n",` ` " (a, b)\n",` ` " for a, b in g.edges\n",` ` " if (a == v and b in unexplored_neighbours)\n",` ` " or (b == v and a in unexplored_neighbours)\n",` ` " ]\n",` ` "\n",` ` " # pokud existují neprozkoumaní sousedé, obarveme je\n",` ` " if len(unexplored_neighbours) != 0:\n",` ` " self.play(\n",` ` " *[\n",` ` " g.vertices[q].animate.set_color(ORANGE)\n",` ` " for q in unexplored_neighbours\n",` ` " ],\n",` ` " *[\n",` ` " g.edges[e].animate.set_color(ORANGE)\n",` ` " for e in unexplored_neighbour_edges\n",` ` " ],\n",` ` " )\n",` ` "\n",` ` " explored.add(w)\n",` ` "\n",` ` " # animace přesunu do sousedního vrcholu\n",` ` " # má dvě části - nejprve začneme posun a poté změníme barvy (a flashneme)\n",` ` " \n",` ` " # používáme tu drobný hack - změna barvy posune hrany dopředu, což vypadá špatně\n",` ` " # proto na modrou obarvíme i vrchol v, což jej vyzvedne před ně\n",` ` " # elegantnější řešení je použít z_index, který si objasníme v příštím díle seriálu\n",` ` " self.play(\n",` ` " AnimationGroup(\n",` ` " position_object.animate.move_to(g.vertices[w]),\n",` ` " AnimationGroup(\n",` ` " Flash(g.vertices[w], color=BLUE, flash_radius=0.3),\n",` ` " g.edges[edge].animate.set_color(BLUE),\n",` ` " g.vertices[v].animate.set_color(BLUE),\n",` ` " g.vertices[w].animate.set_color(BLUE),\n",` ` " *[\n",` ` " g.vertices[q].animate.set_color(WHITE)\n",` ` " for q in unexplored_neighbours\n",` ` " if q != w\n",` ` " ],\n",` ` " *[\n",` ` " g.edges[(a, b)].animate.set_color(WHITE)\n",` ` " for (a, b) in unexplored_neighbour_edges\n",` ` " if (a, b) != edge\n",` ` " ],\n",` ` " ),\n",` ` " lag_ratio=0.45,\n",` ` " )\n",` ` " )\n",` ` "\n",` ` " dfs(w, position_object)\n",` ` " self.play(position_object.animate.move_to(g.vertices[v]))\n",` ` "\n",` ` " self.play(Write(g))\n",` ` "\n",` ` " # vyznačení startovního vrcholu\n",` ` " start_vertex = 0\n",` ` "\n",` ` " # objekt, který se posouvá podle toho, na jakém vrcholu jsme\n",` ` " position_object = (\n",` ` " Circle(fill_color=BLUE, fill_opacity=1, stroke_color=BLUE)\n",` ` " .move_to(g.vertices[start_vertex])\n",` ` " .scale(0.15)\n",` ` " )\n",` ` "\n",` ` " self.play(\n",` ` " Flash(g.vertices[start_vertex], color=BLUE, flash_radius=0.3),\n",` ` " g.vertices[start_vertex].animate.set_color(BLUE),\n",` ` " )\n",` ` "\n",` ` " self.add(position_object)\n",` ` "\n",` ` " # spuštění DFS\n",` ` " explored.add(start_vertex)\n",` ` " dfs(start_vertex, position_object)\n",` ` "\n",` ` " self.remove(position_object)\n",` ` " self.play(Unwrite(g))"` ` ]` ` },` ` {` ` "cell_type": "markdown",` ` "id": "e6f13b54",` ` "metadata": {},` ` "source": [` ` "## Fibonacciho posloupnost"` ` ]` ` },` ` {` ` "cell_type": "code",` ` "execution_count": null,` ` "id": "fc2941bf",` ` "metadata": {},` ` "outputs": [],` ` "source": [` ` "%%manim -v WARNING -qh --disable_caching FibonacciSequence\n",` ` "\n",` ` "from random import *\n",` ` "\n",` ` "\n",` ` "class FibonacciSequence(MovingCameraScene):\n",` ` " def create_square(self, size):\n",` ` " \"\"\"Vytvoření čtverce dané velikosti.\"\"\"\n",` ` " return VGroup(Square(side_length=size), Tex(f\"\${size}^2\$\").scale(size))\n",` ` "\n",` ` " def get_camera_centering_animation(self, squares):\n",` ` " \"\"\"Animace k vycentrování kamery na čtverce.\"\"\"\n",` ` " h = squares.height * 1.5\n",` ` " return self.camera.frame.animate.set_height(h).move_to(squares)\n",` ` "\n",` ` " def construct(self):\n",` ` " squares = VGroup(self.create_square(1))\n",` ` "\n",` ` " self.camera.frame.move_to(squares).set_height(squares.height * 1.5)\n",` ` " self.camera.frame.save_state()\n",` ` "\n",` ` " self.play(Write(squares[0]))\n",` ` "\n",` ` " n = 7\n",` ` "\n",` ` " # vytvoření čtverců a jejich animování\n",` ` " a = 1\n",` ` " b = 1\n",` ` " directions = [RIGHT, UP, LEFT, DOWN]\n",` ` " for i in range(n):\n",` ` " b = b + a\n",` ` " a = b - a\n",` ` "\n",` ` " direction = directions[i % 4]\n",` ` "\n",` ` " new_square = self.create_square(a).next_to(squares, direction, buff=0)\n",` ` " squares.add(new_square)\n",` ` "\n",` ` " self.play(\n",` ` " FadeIn(new_square, shift=direction * a / 3),\n",` ` " self.get_camera_centering_animation(squares),\n",` ` " )\n",` ` "\n",` ` " dot = Dot().move_to(squares[0].get_corner(LEFT + UP)).scale(0.5)\n",` ` "\n",` ` " path = TracedPath(dot.get_center)\n",` ` "\n",` ` " def update_camera_position(camera):\n",` ` " \"\"\"Updater k pozicování kamery nad tečkou.\"\"\"\n",` ` " camera.move_to(dot.get_center())\n",` ` "\n",` ` " self.wait(1)\n",` ` "\n",` ` " # začátek spirály\n",` ` " self.play(\n",` ` " squares.animate.set_color(DARK_GRAY),\n",` ` " AnimationGroup(\n",` ` " self.camera.frame.animate.restore().move_to(dot),\n",` ` " Write(dot),\n",` ` " lag_ratio=0.5,\n",` ` " ),\n",` ` " )\n",` ` "\n",` ` " # nesmíme zapomenout TracedPath přidat do scény, aby byla vykreslována\n",` ` " self.add(path)\n",` ` " \n",` ` " self.camera.frame.add_updater(update_camera_position)\n",` ` "\n",` ` " center_dot = dot.copy()\n",` ` " self.add(center_dot)\n",` ` "\n",` ` " a = 0\n",` ` " b = 1\n",` ` " for i in range(n + 1):\n",` ` " # pole directions je definováno proti směru hodinových ručiček, proto\n",` ` " # sousední dvojice odpovídají bodům ve čtvercích, okolo kterých chceme otáčet\n",` ` " direction = directions[i % 4] + directions[(i + 1) % 4]\n",` ` " b = b + a\n",` ` " a = b - a\n",` ` "\n",` ` " # při každém čtvrtotočení zoomujeme zhruba o poměr sousedních fibonacciho\n",` ` " # čísel, což je phi (zlatý řez); číslo zmenšujeme, aby animace vypadala lépe\n",` ` " phi = (1 + 5 ** (1 / 2)) / 2\n",` ` " zoom_coefficient = phi * 0.9\n",` ` " \n",` ` " self.play(\n",` ` " Rotate(\n",` ` " dot,\n",` ` " about_point=squares[i].get_corner(direction),\n",` ` " angle=PI / 2,\n",` ` " ),\n",` ` " self.camera.frame.animate.scale(zoom_coefficient),\n",` ` " rate_func=linear,\n",` ` " )\n",` ` "\n",` ` " # po dotočení již nechceme držet kameru nad bodem, ani dále tracovat cestu\n",` ` " self.camera.frame.clear_updaters()\n",` ` " path.clear_updaters()\n",` ` "\n",` ` " self.play(self.get_camera_centering_animation(squares))\n",` ` " \n",` ` " self.wait(1)\n",` ` "\n",` ` " # fadeouty + hezké odspirálení\n",` ` " self.play(\n",` ` " FadeOut(squares),\n",` ` " FadeOut(dot),\n",` ` " AnimationGroup(\n",` ` " Unwrite(path, run_time=2),\n",` ` " AnimationGroup(Flash(center_dot, color=WHITE), FadeOut(center_dot)),\n",` ` " lag_ratio=0.9,\n",` ` " ),\n",` ` " )"` ` ]` ` },` ` {` ` "cell_type": "markdown",` ` "id": "8188912d",` ` "metadata": {},` ` "source": [` ` "## Langtonův mravenec"` ` ]` ` },` ` {` ` "cell_type": "code",` ` "execution_count": null,` ` "id": "cad4e39c",` ` "metadata": {},` ` "outputs": [],` ` "source": [` ` "%%manim -v WARNING -qh LangtonAnt\n",` ` "\n",` ` "from random import *\n",` ` "\n",` ` "\n",` ` "class Ant:\n",` ` " \"\"\"Třída mravence (pro čistší kód).\"\"\"\n",` ` "\n",` ` " deltas = [(-1, 0), (0, -1), (1, 0), (0, 1)]\n",` ` "\n",` ` " def __init__(self, position):\n",` ` " self.position = position\n",` ` " self.orientation = 0\n",` ` "\n",` ` " def __get_orientation_delta(self):\n",` ` " \"\"\"O kolik má mravenec posunout.\"\"\"\n",` ` " return self.deltas[self.orientation]\n",` ` "\n",` ` " def __rotate_by_delta(self, delta):\n",` ` " \"\"\"Otočení mravence do libovolného směru o násobek 90 stupňů.\"\"\"\n",` ` " self.orientation = (self.orientation + delta) % len(self.deltas)\n",` ` "\n",` ` " def rotate_left(self):\n",` ` " \"\"\"Otočení mravence doleva.\"\"\"\n",` ` " self.__rotate_by_delta(-1)\n",` ` "\n",` ` " def rotate_right(self):\n",` ` " \"\"\"Otočení mravence doprava.\"\"\"\n",` ` " self.__rotate_by_delta(1)\n",` ` "\n",` ` " def move_forward(self):\n",` ` " \"\"\"Posunutí mravence dopředu.\"\"\"\n",` ` " dx, dy = self.__get_orientation_delta()\n",` ` " self.position[0] += dx\n",` ` " self.position[1] += dy\n",` ` "\n",` ` " def update(self, states):\n",` ` " \"\"\"Posunutí a otočení mravence a upravení stavu.\"\"\"\n",` ` " x, y = self.position\n",` ` "\n",` ` " # znegování pole, na kterém mravenec stojí\n",` ` " states[y][x] = not states[y][x]\n",` ` "\n",` ` " # otočení\n",` ` " if states[y][x]:\n",` ` " self.rotate_right()\n",` ` " else:\n",` ` " self.rotate_left()\n",` ` "\n",` ` " # posunutí\n",` ` " self.move_forward()\n",` ` "\n",` ` "\n",` ` "class LangtonAnt(MovingCameraScene):\n",` ` " def construct(self):\n",` ` " n = 15\n",` ` " state = [[False for _ in range(n)] for _ in range(n)]\n",` ` " squares = [[Square() for _ in range(n)] for _ in range(n)]\n",` ` " squares_vgroup = VGroup(*[*sum(squares, [])]).arrange_in_grid(columns=n, buff=0)\n",` ` "\n",` ` " ant = Ant([n // 2, n // 2])\n",` ` " ant_object = (\n",` ` " SVGMobject(\"ant.svg\")\n",` ` " .set_height(squares_vgroup[0].height * 0.7)\n",` ` " .rotate(PI / 2)\n",` ` " )\n",` ` "\n",` ` " self.play(FadeIn(squares_vgroup), Write(ant_object))\n",` ` "\n",` ` " self.wait(1)\n",` ` "\n",` ` " step_count = 100\n",` ` "\n",` ` " # kolik iterací na začátku a na konci je pomalých\n",` ` " slow_start_iterations = 5\n",` ` " slow_end_iterations = 3\n",` ` "\n",` ` " # jak rychlé jsou animace\n",` ` " slow_run_time = 1\n",` ` " fast_run_time = 0.07\n",` ` "\n",` ` " for i in range(step_count):\n",` ` " x, y = ant.position\n",` ` "\n",` ` " new_color = state[y][x]\n",` ` " rect = squares[y][x]\n",` ` "\n",` ` " running_time = (\n",` ` " fast_run_time\n",` ` " if slow_start_iterations < i < step_count - slow_end_iterations\n",` ` " else slow_run_time\n",` ` " )\n",` ` "\n",` ` " # otáčení mravence\n",` ` " self.play(\n",` ` " Rotate(ant_object, PI / 2 * (1 if new_color else -1)),\n",` ` " run_time=running_time,\n",` ` " )\n",` ` "\n",` ` " # posunutí mravence\n",` ` " ant.update(state)\n",` ` " nx, ny = ant.position\n",` ` "\n",` ` " self.play(\n",` ` " rect.animate.set_fill(BLACK if new_color else WHITE, 1),\n",` ` " ant_object.animate.move_to(squares[ny][nx]),\n",` ` " self.camera.frame.animate.move_to(squares[ny][nx]),\n",` ` " run_time=running_time,\n",` ` " )\n",` ` "\n",` ` " self.wait(1)\n",` ` "\n",` ` " # zjistíme, které čtverce jsou aktuálně bílé\n",` ` " white_squares = VGroup()\n",` ` "\n",` ` " for i in range(n):\n",` ` " for j in range(n):\n",` ` " if state[i][j]:\n",` ` " white_squares.add(squares[i][j])\n",` ` "\n",` ` " # oddálíme a vycentrujeme na tyto čtverce\n",` ` " self.play(\n",` ` " self.camera.frame.animate.move_to(white_squares).set_height(\n",` ` " white_squares.height * 1.2\n",` ` " )\n",` ` " )\n",` ` "\n",` ` " self.play(FadeOut(squares_vgroup), FadeOut(ant_object))"` ` ]` ` }` ` ],` ` "metadata": {` ` "kernelspec": {` ` "display_name": "Python 3 (ipykernel)",` ` "language": "python",` ` "name": "python3"` ` },` ` "language_info": {` ` "codemirror_mode": {` ` "name": "ipython",` ` "version": 3` ` },` ` "file_extension": ".py",` ` "mimetype": "text/x-python",` ` "name": "python",` ` "nbconvert_exporter": "python",` ` "pygments_lexer": "ipython3",` ` "version": "3.10.2"` ` }` ` },` ` "nbformat": 4,` ` "nbformat_minor": 5` ```} ``` ``` ```