A python script, that makes svg file "generated.svg" with n`th order Serpinsky triangle and a difficult labirint

algo.py

from typing import *

class edge:
    def __init__(self, s, e, l):
        self.start = s
        self.end = e
        self.length = l
    def __repr__(self):
        return f"({self.start}, {self.end}, {self.length})"
    start : int
    end : int
    length : float

def cruskate(n : int, graph : List[edge]):  # n - number of vertexes
    m = len(graph)

    tree_data = [i for i in range(n)]
    res = []
    graph.sort(key = lambda e: e.length)

    for e in graph:
        if tree_data[e.start] != tree_data[e.end]:
            res.append((e.start, e.end))

            bad_color = tree_data[e.start]
            good_color = tree_data[e.end]

            for i, col in enumerate(tree_data):
                if col == bad_color:
                    tree_data[i] = good_color
    return res


if __name__ == '__main__':
    ex_n = 5
    ex_graph = [edge(0, 4, 1), edge(2, 3, 2), edge(0, 1, 3), edge(1, 4, 4), edge(1, 2, 5), edge(4, 2, 6), edge(4, 3, 7)]
    f_res = cruskate(ex_n, ex_graph)
    print(f_res)

labirint_generator.py

from triangle_generator import *
from algo import *

import random

grid_w = 100
grid_h = 100

x_num = 100
y_num = 100

w = x_num * grid_w
h = y_num * grid_h

class point:
    x : float
    y : float
    def __init__(self, x, y):
        self.x = x
        self.y = y

"""
point_index: int = 0
point_indexes: Dict[Tuple[int, int], int] = {}
points : List[Tuple[int, int]] = []
"""

def generate_normal_house() -> List[Tuple[Tuple[int, int], Tuple[int, int]]]:
    all_edges = []
    for ix in range(x_num):
        for iy in range(y_num):
            point_index = ix + x_num * iy
            length = random.random()
            next_index = -1
            if ix != x_num - 1:
                next_x = ix + 1
                next_index = next_x + x_num * iy
                all_edges.append(edge(point_index, next_index, length))

            if iy != y_num - 1:
                next_y = iy + 1
                next_index = ix + x_num * next_y
                all_edges.append(edge(point_index, next_index, length))

    cruskated = set(cruskate(x_num * y_num, all_edges))


    res = []
    for _e in all_edges:
        e = (_e.start, _e.end)
        if e in cruskated:
            continue
        ix_first = e[0] % x_num
        iy_first = e[0] // x_num

        if e[0] == e[1] - 1:
            # Vertical
            upper_point = (ix_first + 1, iy_first)
            bottom_point = (ix_first + 1, iy_first + 1)
            res.append((upper_point, bottom_point))
        else:
            # Horizontal

            left_point = (ix_first, iy_first + 1)
            right_point = (ix_first + 1, iy_first + 1)
            res.append((left_point, right_point))

    return res



def generate_house() -> List[edge]:
    is_critical = lambda val, max_val: val == 0 or val == max_val
    res : List[edge] = []
    edge_coords : List[Tuple[point, point]] = []
    point_coords : List[point] = []


    def get_indexed_point(x : int, y : int) -> Tuple[int, int, int]:
        # global point_index, points, point_indexes
        p = (x, y)
        if p in point_indexes:
            return x, y, point_indexes[p]
        else:
            this_point_index = point_index
            point_indexes[p] = this_point_index
            points.append(p)
            point_index += 1
            return x, y, this_point_index


    # Vertical
    for ix in range(1, x_num - 1):
        for iy in range(y_num - 1):
            i_first = get_indexed_point(ix, iy)
            i_second = get_indexed_point(ix, iy + 1)
            length = random.random()

            res.append(edge(i_first[2], i_second[2], length))

    print(points)
    print(point_indexes)
    print(res)
    print()

    # Horizontal:
    for ix in range(x_num - 1):
        for iy in range(1, y_num - 1):
            i_first = get_indexed_point(ix, iy)
            i_second = get_indexed_point(ix + 1, iy)
            length = random.random()

            res.append(edge(i_first[2], i_second[2], length))

    print(points)
    print(point_indexes)
    print(res)

    return res


def draw_labirint():
    output = [f"<svg xmlns=\"http://www.w3.org/2000/svg\" height = \"{h}\" width = \"{w}\" >"]
    res_house = generate_normal_house()

    draw_line(output, (0, 0), (w, 0))
    draw_line(output, (0, 0), (0, h))

    draw_line(output, (0, h), (w, h))
    draw_line(output, (w, 0), (w, h))

    for e in res_house:
        draw_line(output, (e[0][0] * grid_w, e[0][1] * grid_h), (e[1][0] * grid_w, e[1][1] * grid_h))

    out_file = open("labirint.svg", "w")
    for index, line in enumerate(output):
        if index != 0 and index != len(output):
            line = "\t" + line + "\n"
        else:
            line = line + "\n"
        out_file.write(line)
    out_file.write("</svg>")
    out_file.close()

if __name__ == '__main__':
    draw_labirint()

triangle_generator.py

import math
from typing import *
import random

def make_point_from_tuple(t : Tuple[float, float], precision : int = 4) -> str:
    return f"{round(t[0], precision)},{round(t[1], precision)}"

def round_tuple(t : tuple, precision : float = 4) -> tuple:
    return tuple([round(i, precision) for i in t])

def rand_tuple(max_x : int, max_y : int):
    return random.random() * max_x, random.random() * max_y


def rand_hex():
    return hex(random.randrange(16, 256))[2:]


def rand_rgb():
    return '#' + rand_hex() + rand_hex() + rand_hex()


def draw_triangle(p1 : Tuple[float, float], p2 : Tuple[float, float], p3: Tuple[float, float], array : list, color : str = "black"):
    str_coords = f"{make_point_from_tuple(p1)} {make_point_from_tuple(p2)} {make_point_from_tuple(p3)}"
    tag = f"<polygon points=\"{str_coords}\" class = \"triangle\" fill = \"{color}\" />"
    array.append(tag)

def draw_line(canvas : List[str], p1 : Tuple[int, int], p2 : Tuple[int, int], color : str = "black", width : int = 5):
    p1 = round_tuple(p1)
    p2 = round_tuple(p2)
    canvas.append(
        f"<line x1 = \"{p1[0]}\" y1 = \"{p1[1]}\" x2 = \"{p2[0]}\" y2 = \"{p2[1]}\" stroke = \"{color}\" stroke-width = \"{str(width)}\"/>"
    )


def find_odd_point( points : list, coord_index : int, min_or_max : bool ):
    # If min_or_max == True, looking for bigger
    res_point = points[0]
    for p in points:
        this_bigging = p[coord_index] > res_point[coord_index]
        if not (min_or_max ^ this_bigging):  # (min_or_max and this_bigging) or (not min_or_max and not this_bigging):
            res_point = p

    return res_point


def tuple_plus(t1 : Tuple, t2 : Tuple) -> Tuple:
    assert len(t1) == len(t2)
    return tuple([t1[i] + t2[i] for i in range(len(t1))])

def mul_tuple(t : tuple, multiplier : float):
    return tuple([t[i] * multiplier for i in range(len(t))])

def div_tuple(t : tuple, divider : float):
    return mul_tuple(t, 1 / divider)

def tuple_minus(t1 : Tuple, t2 : Tuple) -> Tuple:
    return tuple_plus(t1, mul_tuple(t2, -1))


# Main drawer function:
def draw_speransky_fillage(to_plot_array : List[str], p1 : Tuple[float, float], p2 : Tuple[float, float], p3 : Tuple[float, float],
                           recursion_limit : int, color = "white"):
    if not recursion_limit:
        return

    points = [p1, p2, p3]
    upper_point = find_odd_point(points, 1, False)
    lefter_point = find_odd_point(points, 0, False)
    righter_point = find_odd_point(points, 0, True)

    left_side_vector = (tuple_minus(upper_point, lefter_point))
    right_side_vector = (tuple_minus(upper_point, righter_point))
    down_side_vector = (tuple_minus(righter_point, lefter_point))

    left_middle = tuple_plus(lefter_point, div_tuple(left_side_vector, 2))
    right_middle = tuple_plus(righter_point, div_tuple(right_side_vector, 2))
    down_middle = tuple_plus(lefter_point, div_tuple(down_side_vector, 2))

    draw_triangle(left_middle, right_middle, down_middle, to_plot_array, color)

    upper_triangle = [upper_point, left_middle, right_middle]
    lefter_triangle = [lefter_point, left_middle, down_middle]
    righter_triangle = [righter_point, down_middle, right_middle]

    for tr in (upper_triangle, lefter_triangle, righter_triangle):
        # noinspection PyTypeChecker
        draw_speransky_fillage(to_plot_array, *tr, recursion_limit - 1, color)


def make_speransky_svg(filename : str, side_size : int, recursion_limit : int):
    triangle_height = side_size * math.sqrt(3) / 2
    triangle_points = [(0, triangle_height), (side_size / 2, 0), (side_size, triangle_height)]

    res = []
    out_file = open(filename, "w")
    res.append(f"<svg xmlns=\"http://www.w3.org/2000/svg\" height = \"{triangle_height}\" width = \"{side_size}\" >")
    # noinspection PyTypeChecker
    draw_triangle(*triangle_points, res, "black")

    # Main white filler:
    # noinspection PyTypeChecker
    draw_speransky_fillage(res, *triangle_points, recursion_limit)

    res.append(f"</svg>")
    for i in range(1, len(res) - 1):
        res[i] = "\t" + res[i]
    out_file.write("\n".join(res))
    out_file.close()


if __name__ == '__main__':
    make_speransky_svg("generated.svg", 100000, 11)