import turtle
import random

# Setup turtle screen and turtle
screen = turtle.Screen()
screen.bgcolor("white")
t = turtle.Turtle()
t.shape("turtle")
t.speed(1)  # Set the speed of the turtle

# Markov chain state transitions
# The turtle can zigzag either left or right with equal probability
states = ["left", "right"]
transition_prob = {
    "left": {"left": 0.5, "right": 0.5},
    "right": {"left": 0.5, "right": 0.5}
}

# Initialize the starting state of the Markov chain
current_state = random.choice(states)

# Function to get the next state based on the current state
def get_next_state(current_state):
    probabilities = transition_prob[current_state]
    next_state = random.choices(list(probabilities.keys()), weights=probabilities.values())[0]
    return next_state

# Turtle zigzag movement to the north
def move_to_north_mark(steps):
    global current_state
    
    for _ in range(steps):
        if current_state == "left":
            t.setheading(315)  # Move diagonally left (north-west)
        else:
            t.setheading(45)   # Move diagonally right (north-east)
        
        t.forward(20)  # Move forward by 20 units
        current_state = get_next_state(current_state)

# Move turtle zigzag towards north for 50 steps
move_to_north_mark(50)

# Finish
turtle.done()