simulate a random self-avoiding walk in python

To simulate a random self-avoiding walk in Python, we can use an algorithm that generates a path of random steps and checks each step to ensure that it does not intersect with any of the previous steps. Here's an example implementation:

main.py
import random

def generate_self_avoiding_walk(n):
    """Generate a random self-avoiding walk of length n"""
    path = [(0, 0)]  # start at the origin
    while len(path) < n:
        # generate a random step
        x, y = path[-1]
        move = random.choice([(1, 0), (-1, 0), (0, 1), (0, -1)])
        next_step = (x + move[0], y + move[1])
        
        # check if new step intersects with any previous steps
        if next_step in path:
            continue
            
        # if new step is valid, add it to the path
        path.append(next_step)
        
    return path
590 chars
20 lines

This function generates a self-avoiding walk of length n starting at the origin. It uses random.choice to select a random direction to move in (up, down, left, or right) and checks if the new step intersects with any of the previous steps using the built-in in operator. If the new step is valid, it is added to the path and the process repeats until the desired length is reached.

Note that this algorithm can take a long time to generate long walks, as the probability of finding a valid step decreases as the path gets longer. There are more efficient algorithms for generating self-avoiding walks, but this simple approach is easy to understand and implement.

gistlibby LogSnag