Category Archives: Difficulty Level 8

Golden Dragon Curve Fractal (Source Code)

Posted on by

Draw a dragon curve based on the golden ratio. At each recursion, the first recursion step turns 32.89 degrees to the left and move 0.74 times the original distance; the second recursion step turns 46.99 degrees to the right and move 0.55 times the original distance. Please check out this web page on mathematical details of the golden dragon.

The following show the recursions depths from 0 to 3.

Recursion Depth 0
Recursion Depth 1
Recursion Depth 2
Recursion Depth 3

The following figure is generated not by the recursion depth but by stopping the recursion when the distance becomes smaller than 1.

Golden Dragon Curve

Source Code:

import turtle
import math

screen = turtle.Screen()
screen.title('Golden Dragon Curve - PythonTurtle.Academy')
screen.setup(1000,1000)
screen.setworldcoordinates(-1000,-1000,1000,1000)
turtle.speed(0)
turtle.hideturtle()
turtle.pencolor('gold')
screen.bgcolor('royal blue')
screen.tracer(0,0)

golden_ratio = (1+5**0.5)/2
r1 = r = (1/golden_ratio)**(1/golden_ratio)
r2 = r1**2
angle1 = math.acos((1+r**2-r**4)/(2*r))
angle2 = math.acos((1+r**4-r**2)/(2*r**2))
print(r1,r2,math.degrees(angle1),math.degrees(angle2))

def golden_dragon(x1,y1,x2,y2,turn,n):
    dist = ((x2-x1)**2 + (y2-y1)**2)**0.5
    if dist<1:
        turtle.goto(x2,y2)
        return
    angle = math.atan2(y2-y1,x2-x1)
    if turn:
        px = x1+dist*r1*math.cos(angle+angle1)
        py = y1+dist*r1*math.sin(angle+angle1)
    else:
        px = x1+dist*r2*math.cos(angle-angle2)
        py = y1+dist*r2*math.sin(angle-angle2)
    golden_dragon(x1,y1,px,py,True,n-1)
    golden_dragon(px,py,x2,y2,False,n-1)

turtle.up()
turtle.goto(-500,-200)
turtle.down()
golden_dragon(-500,-200,700,-200,True,3)
screen.update()

Cesàro (Torn Squares) Fractal with Python Turtle (Source Code)

Posted on by

Cesàro (Torn Squares) Fractal is a variation of Koch Snowflake. In Cesàro Fractal the degree to turn can vary from 60 degrees to 90 degrees. Koch Snowflake line only curves 60 degrees.

Instead of choosing a degree to turn, Cesàro Fractal is easier to implement by setting the ratio of original length for each of the 4 segments. For Koch snowflake, the ratio is 1/3. For Cesàro Fractal the ratio can range from 1/3 to 1/2. The following is the Cesàro Fractal with different ratios:

Cesàro Fractal with 1/3 Ratio
Cesàro Fractal with Ratio 0.4
Cesàro Fractal with Ratio 0.47
Cesàro Fractal with Ratio 0.49

Source Code:

import turtle
import math

screen = turtle.Screen()
screen.title('Cesàro (Torn Square) Fractal - PythonTurtle.Academy')
screen.setup(1000,1000)
screen.setworldcoordinates(-1000,-1000,1000,1000)
screen.tracer(0,0)
turtle.speed(0)
turtle.hideturtle()
turtle.fillcolor('blue')

# ratio is between [1/3, 1/2)
def Cesàro(x1,y1,x2,y2,ratio):
    dist = ((x2-x1)**2+(y2-y1)**2)**0.5
    if dist<50:
        turtle.goto(x2,y2)
        return
    direction = math.atan2(y2-y1,x2-x1)
    px1, py1 = x1+dist*ratio*math.cos(direction), y1+dist*ratio*math.sin(direction)    
    px3, py3 = x1+dist*(1-ratio)*math.cos(direction), y1+dist*(1-ratio)*math.sin(direction)
    ptx, pty = (px1+px3)/2, (py1+py3)/2
    d = ((dist*ratio)**2 - (dist*(1-2*ratio)/2)**2)**0.5
    px2, py2 = ptx+d*math.cos(direction+math.radians(90)), pty+d*math.sin(direction+math.radians(90))
        
    Cesàro(x1,y1,px1,py1,ratio)
    Cesàro(px1,py1,px2,py2,ratio)
    Cesàro(px2,py2,px3,py3,ratio)
    Cesàro(px3,py3,x2,y2,ratio)

ratio = 0.49
turtle.up()
turtle.goto(-800,800)
turtle.down()
Cesàro(-800,800,-800,-800,ratio)
Cesàro(-800,-800,800,-800,ratio)
Cesàro(800,-800,800,800,ratio)
Cesàro(800,800,-800,800,ratio)

screen.update()

Quadratic Koch Snowflake from a Triangle (Source Code)

Posted on by

The quadratic Koch snowflake starts from a square. Draw the quadratic Koch snowflake starting with a triangle.

Quadratic Koch Snowflake from a Triangle

Source Code:

import turtle

screen = turtle.Screen()
screen.title('Quadratic Koch Curve From Triangle - PythonTurtle.Academy')
screen.setup(1000,1000)
screen.setworldcoordinates(-1000,-1000,1000,1000)
screen.tracer(0,0)
turtle.speed(0)
turtle.hideturtle()
turtle.bgcolor('midnight blue')
turtle.color('white')

def koch(x1,y1,x2,y2):
    distance=((x2-x1)**2 + (y2-y1)**2)**0.5
    if distance<10:
        turtle.up()
        turtle.goto(x1,y1)
        turtle.down()
        turtle.goto(x2,y2)
        return
    turtle.up()
    turtle.goto(x1,y1)
    direction=turtle.towards(x2,y2)
    turtle.seth(direction)
    turtle.fd(distance/3)
    x3,y3 = turtle.xcor(), turtle.ycor()
    turtle.left(90)
    turtle.fd(distance/3)
    x4,y4 = turtle.xcor(), turtle.ycor()
    turtle.right(90)
    turtle.fd(distance/3)
    x5,y5 = turtle.xcor(), turtle.ycor()
    turtle.right(90)
    turtle.fd(distance/3)
    x6,y6 = turtle.xcor(), turtle.ycor()
    koch(x1,y1,x3,y3)
    koch(x3,y3,x4,y4)
    koch(x4,y4,x5,y5)
    koch(x5,y5,x6,y6)
    koch(x6,y6,x2,y2)
    

koch(500,-200,-500,-200)
koch(-500,-200,0,500*3**0.5-200)
koch(0,500*3**0.5-200,500,-200)
screen.update()

Quadratic Koch Snowflake with Python Turtle (Source Code)

Posted on by

The original Koch Snowflake is based on triangles. Draw quadratic Koch snowflake that breaks a line into 4 smaller pieces of 1/3 of the original length as shown.

Depth 1 Recursion
Depth 2 Recursion
Depth 3 Recursion

The following is drawn with 4 initial lines that forms a square.

Quadratic Koch Snowflake

Source Code:

import turtle

screen = turtle.Screen()
screen.title('Quadratic Koch Curve - PythonTurtle.Academy')
screen.setup(1000,1000)
screen.setworldcoordinates(-1000,-1000,1000,1000)
screen.tracer(0,0)
turtle.speed(0)
turtle.hideturtle()
turtle.bgcolor('midnight blue')
turtle.color('white')

def koch(x1,y1,x2,y2):
    distance=((x2-x1)**2 + (y2-y1)**2)**0.5
    if distance<10:
        turtle.up()
        turtle.goto(x1,y1)
        turtle.down()
        turtle.goto(x2,y2)
        return
    turtle.up()
    turtle.goto(x1,y1)
    direction=turtle.towards(x2,y2)
    turtle.seth(direction)
    turtle.fd(distance/3)
    x3,y3 = turtle.xcor(), turtle.ycor()
    turtle.left(90)
    turtle.fd(distance/3)
    x4,y4 = turtle.xcor(), turtle.ycor()
    turtle.right(90)
    turtle.fd(distance/3)
    x5,y5 = turtle.xcor(), turtle.ycor()
    turtle.right(90)
    turtle.fd(distance/3)
    x6,y6 = turtle.xcor(), turtle.ycor()
    koch(x1,y1,x3,y3)
    koch(x3,y3,x4,y4)
    koch(x4,y4,x5,y5)
    koch(x5,y5,x6,y6)
    koch(x6,y6,x2,y2)
    

koch(-400,-400,-400,400)
koch(-400,400,400,400)
koch(400,400,400,-400)
koch(400,-400,-400,-400)
screen.update()

Game of SIM with Python Turtle (Source Code Included)

Posted on by

Game of SIM was invented in 1969 by Gustavus Simmons. In this two player (red and blue) game, each player takes turn to connect two vertices of a hexagon with the player’s color (either red or blue). The first player who draws all three sides of the triangle with the player’s color loses the game. There is always a winner for this game.

Write a Game of SIM with Python and Turtle graphics. Your game should be able to declare the winner when the game ends. You will need to use onclick() even of Turtle graphics.

Game of SIM with Python Turtle

Source Code:

import turtle
import math

screen = turtle.Screen()
screen.setup(800,800)
screen.title("Game of SIM - PythonTurtle.Academy")
screen.setworldcoordinates(-1.5,-1.5,1.5,1.5)
screen.tracer(0,0)
turtle.hideturtle()

def draw_dot(x,y,color):
    turtle.up()
    turtle.goto(x,y)
    turtle.color(color)
    turtle.dot(15)

def gen_dots():
    r = []
    for angle in range(0,360,60):
        r.append((math.cos(math.radians(angle)),math.sin(math.radians(angle))))
    return r

def draw_line(p1,p2,color):
    turtle.up()
    turtle.pensize(3)
    turtle.goto(p1)
    turtle.down()
    turtle.color(color)
    turtle.goto(p2)
    
def draw_board():
    global selection
    
    for i in range(len(dots)):
        if i in selection: draw_dot(dots[i][0],dots[i][1],turn)
        else: draw_dot(dots[i][0],dots[i][1],'dark gray')
        
def draw():
    draw_board()
    for i in range(len(red)):
        draw_line((math.cos(math.radians(red[i][0]*60)),math.sin(math.radians(red[i][0]*60))),\
                  (math.cos(math.radians(red[i][1]*60)),math.sin(math.radians(red[i][1]*60))),\
                  'red')
    for i in range(len(blue)):
         draw_line((math.cos(math.radians(blue[i][0]*60)),math.sin(math.radians(blue[i][0]*60))),\
                  (math.cos(math.radians(blue[i][1]*60)),math.sin(math.radians(blue[i][1]*60))),\
                  'blue')      
    screen.update()

def play(x,y):
    global selection,turn,red,blue
    
    for i in range(len(dots)):
        dist = (dots[i][0]-x)**2 + (dots[i][1]-y)**2
        if dist<0.001:
            if i in selection: selection.remove(i)
            else: selection.append(i)
            break
    if len(selection)==2:
        selection=(min(selection),max(selection))
        if selection not in red and selection not in blue:
            if turn=='red':
                red.append(selection)
            else:
                blue.append(selection)
            turn = 'red' if turn=='blue' else 'blue'
        selection = []
    draw()
    r = gameover(red,blue)
    if r!=0:
        screen.textinput('game over',r+' won!')
        turtle.bye()

def gameover(r,b):
    if len(r)<3: return 0
    r.sort()
    for i in range(len(r)-2):
        for j in range(i+1,len(r)-1):
            for k in range(j+1,len(r)):
                if r[i][0]==r[j][0] and r[i][1]==r[k][0] and r[j][1]==r[k][1]: return 'blue'
    if len(b)<3: return 0
    b.sort()
    for i in range(len(b)-2):
        for j in range(i+1,len(b)-1):
            for k in range(j+1,len(b)):
                if b[i][0]==b[j][0] and b[i][1]==b[k][0] and b[j][1]==b[k][1]: return 'red'
    return 0

selection = []
turn = 'red'
dots = gen_dots()
red = [ ]
blue = [ ]
draw()
screen.onclick(play)
turtle.mainloop()

Merge Sort Animation with Python and Turtle (with Source Code)

Posted on by

In previous sorting animations, we animated selection, insertion, and bubble sort. They are slow O(n^2) slow sorting algorithm. Merge Sort, a divide and conquer algorithm, is a much faster sorting algorithm with the worst case running time of O(n*logn). However, unlike previous sorting algorithms, it requires another array to be able to merge. Implement Merge Sorting and animate it!

Here is the source code:

import turtle
import random
import time

screen = turtle.Screen()
screen.setup(1000,1000)
screen.setworldcoordinates(-1000,-1000,1000,1000)
screen.tracer(0,0)
screen.title('Merge Sort Animation - PythonTurtle.Academy')
turtle.speed(0)
turtle.hideturtle()

def draw_bar(x,y,w,h):
    turtle.up()
    turtle.goto(x,y)
    turtle.seth(0)
    turtle.down()
    turtle.begin_fill()
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.end_fill()

def draw_bars(v,w,n,currenti=-1,currentj=-1):
    turtle.clear()
    x = -400
    wd = 800/n
    for  i in range(n):
        if i == currenti: turtle.fillcolor('red')
        elif i == currentj: turtle.fillcolor('blue')
        else: turtle.fillcolor('gray')
        draw_bar(x,100,wd,v[i])
        x += wd
        
    x = -400
    for  i in range(n):
        turtle.fillcolor('gray')
        draw_bar(x,-900,wd,w[i])
        x += wd
    screen.update()

def merge(v,w,a,b,x,y):
    i,j, k = a,x,a
    while i<=b and j<=y:
        if v[i] < v[j]: w[k],i = v[i], i+1
        else: w[k], j = v[j], j+1
        draw_bars(v,w,n,i,j)
        k += 1
    while i<=b:
        w[k],i,k = v[i],i+1,k+1
        draw_bars(v,w,n,i,j)
    while j<=y:
        w[k],j,k = v[j],j+1,k+1
        draw_bars(v,w,n,i,j)
    for i in range(a,y+1):
        v[i] = w[i]
        draw_bars(v,w,n,i)
    
def merge_sort(v,w,x,y):
    if x >= y:
        return
    m = (x+y)//2
    merge_sort(v,w,x,m)
    merge_sort(v,w,m+1,y)
    merge(v,w,x,m,m+1,y)
    
n = 50
v = [0] * n
w = [0] * n
for i in range(n):
    v[i] = random.randint(1,800)

t1 = time.time()
merge_sort(v,w,0,n-1)
t2 = time.time()
print('elapsed time=', t2-t1)

What’s Next?

Quick Sort Animation

Drawing A Chinese College Entrance Exam Problem

Posted on by

A YouTube channel MindYourDecisions posted a video about an interesting Chinese College Entrance exam question. The following is the screen of the problem posted by MindYourDecisions:

Draw the graph of the function ranging from [-3,3]. Also draw a horizontal line with y value -8/9.

Check out this project for how to draw general function graphs with Python Turtle.

Drawing Barnsley’s Fern with Chaos Game (Solution Included)

Posted on by

Draw Barnsley’s Fern with Chaos Game. The equation for construction is provided in this Wikipedia article.

Barnsley’s Fern with Chaos Game

Solution:

import turtle
import random

screen = turtle.Screen()
screen.title('Barnsley\'s Fern Chaos Game with Python Turtle')
screen.setup(1000,1000)
screen.setworldcoordinates(-6,-1,6,11)
screen.tracer(0,0)
turtle.hideturtle()
turtle.speed(0)
turtle.up()

n = 100000 # number of points to draw
p = (0,0) 
t = turtle.Turtle()
t.up()
t.hideturtle()
for i in range(n):
    t.goto(p)
    t.dot(2,'green') 
    r = random.uniform(0,1)
    if r < 0.01:
        p = (0,0.16*p[1])
    elif r < 0.86:
        p = (0.85*p[0] + 0.04*p[1], -0.04*p[0] + 0.85*p[1] + 1.6)
    elif r < 0.93:
        p = (0.2*p[0] - 0.26*p[1], 0.23*p[0] + 0.22*p[1] + 1.6)
    else:
        p = (-0.15*p[0] + 0.28*p[1], 0.26*p[0] + 0.24*p[1] + 0.44)
        
    if i % 1000 == 0: # update for every 1000 moves, this part is for performance reason only
        t = turtle.Turtle() # use new turutle
        t.up()
        t.hideturtle()
        screen.update()