[Python] 시어핀스키와 하노이

from BasicDataStructure import Stack

import turtle

import math

def draw_spiral(my_turtle, line_len):

    if line_len > 0:

        my_turtle.forward(line_len)

        my_turtle.right(90)

        draw_spiral(my_turtle, line_len - 5)

 

def tree(branch_len, t):

    if branch_len > 5:

        t.forward(branch_len)

        t.right(20)

        tree(branch_len - 10, t)

        t.left(40)

        tree(branch_len - 10,t)

        t.right(20)

        t.backward(branch_len)

def triangleFromMid(t : turtle.Turtle, len):

    t.down()

    t.forward(len/2)

    t.left(120)

    t.forward(len)

    t.left(120)

    t.forward(len)

    t.left(120)

    t.forward(len/2)

    t.up()

def triangleFromEdge(t : turtle.Turtle, len):

    t.down()

    t.left(60)

    for i in range(3):

        t.forward(len)

        t.left(120)

    t.right(60)

    t.up()

    

 

def __sierpinski_self_impl(t : turtle.Turtle, len, d : int):

 

    triangleFromEdge(t, len)

    

    if d == 0:

        return

 

    #left

    t.left(120)

    t.forward(len/2)

    __sierpinski_self_impl(t, len/2, d-1)

    #above and right

    for i in range(2):

        t.forward(len/2)

        t.right(120)

        t.forward(len/2)

        __sierpinski_self_impl(t, len/2, d-1)

    t.forward(len/2)

    t.left(120)

 

def sierpinski_self(len, d : int, spd : int):

    t = turtle.Turtle()

    my_win = turtle.Screen()

    t.speed(spd)

    

    triangleFromMid(t, len)

    __sierpinski_self_impl(t, len/2, d)

 

    my_win.exitonclick()

 

class StackWithName:

    def __init__(self, name):

        self.items = []

        self.name = name

    def is_empty(self):

        return self.items == []

    def push(self, item):

        self.items.append(item)

    def pop(self):

        return self.items.pop()

    def peek(self):

        return self.items[len(self.items)-1]

    def size(self):

        return len(self.items)

    def __str__(self) -> str:

        r = ""

        for it in self.items:

            r += str(it) + " "

        return r

 

def __hanoiStackName(l : list[StackWithName]) -> list[StackWithName]:

    a, b, c = (0, 0, 0)

    for s in l:

        if s.name == "stat":

            a = s

        elif s.name == "mid":

            b = s

        else:

            c = s

    return [a,b,c]

 

def hanoi(n : int, i : int, stat : StackWithName, mid : StackWithName, des : StackWithName):

    if i == n:

        for k in range(n, 0, -1):

            stat.push(k)

        l = __hanoiStackName([stat, mid, des])

        print(f"stat : {l[0]}\nmid : {l[1]}\ndes : {l[2]}\n")

 

    if i == 1:

        des.push(stat.pop())

        l = __hanoiStackName([stat, mid, des])

        print(f"stat : {l[0]}\nmid : {l[1]}\ndes : {l[2]}\n")

    else:

        hanoi(n, i-1, stat, des, mid)

        des.push(stat.pop())

        l = __hanoiStackName([stat, mid, des])

        print(f"stat : {l[0]}\nmid : {l[1]}\ndes : {l[2]}\n")

        hanoi(n, i-1, mid, stat, des)

    

class Point:

    def __init__(self, x, y) -> None:

        self.x = x

        self.y = y

 

    def __add__(self, o : "Point") -> "Point":

        return Point(self.x + o.x, self.y + o.y)

    

    def __sub__(self, o : "Point") -> "Point":

        return Point(self.x - o.x, self.y - o.y)

    

    def midPoint(self, o : "Point") -> "Point":

        return Point( (self.x + o.x) / 2, (self.y + o.y) / 2)

    

    def midPointTuple(self, o : "Point") -> tuple:

        return ((self.x + o.x) / 2, (self.y + o.y) / 2)

    

    def toTuple(self) -> tuple:

        return (self.x, self.y)

 

    def __truediv__(self, d) -> "Point":

        return Point(self.x /2, self.y/2)

def triangle(t : turtle.Turtle, p1 : Point, p2 : Point, p3 : Point) :

    t.up()

    t.goto(p1.toTuple())

    t.down()

    for i in [p2, p3, p1]:

        t.goto(i.toTuple())

    t.up()

def __sierpiski_impl(t : turtle.Turtle, lvl : int, left: Point, top : Point, right : Point):

    if lvl == 0:

        return

    

    triangle(t, left, top, right)

    __sierpiski_impl(t, lvl-1, left, left.midPoint(top), left.midPoint(right))

    __sierpiski_impl(t, lvl-1, top.midPoint(left), top, top.midPoint(right))

    __sierpiski_impl(t, lvl-1, right.midPoint(left), right.midPoint(top), right)

def sierpinski(len, lvl : int, speed : int) : 

    t = turtle.Turtle()

    win = turtle.Screen()

    h = len*(math.sqrt(3)/2)/3

    left = Point(-len/2, -h)

    top = Point(0, 2*h)

    right = Point(len/2, -h)

    t.speed(speed)

 

    __sierpiski_impl(t, lvl, left, top, right)

    win.exitonclick()

 

 

Sierpinski_self ------------------------------------------------------------------

 

 

 

 

Sierpinski -----------------------------------------------------------------------