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.
453 lines
16 KiB
453 lines
16 KiB
2 years ago
|
{
|
||
|
|
"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
|
||
|
|
}
|