Blog

This is the first part of a three part series about making the Twitter bot @BotfonsNeedles. In this part, I will write a Python 3 program that

• uses a Monte Carlo method to approximate \(\pi\) with Buffon’s needle problem, and
• produces an image with the Python library Pillow

In the second part, I’ll explain how to use the Twitter API to

• post the images to Twitter via the Python library Tweepy, and
• keep track of all of the Tweets to get an increasingly accurate estimate of \(\pi\).

In the third part, I’ll explain how to

• Package all of this code up into a Docker container
• Push the Docker image to Amazon Web Services (AWS)
• Set up a function on AWS Lambda to run the code on a timer

Buffon’s needle problem

Buffon’s needle problem is a surprising way of computing \(\pi\). It says that if you throw \(n\) needles of length \(\ell\) randomly onto a floor that has parallel lines that are a distance of \(\ell\) apart, then the expected number of needles that cross a line is \(\frac{2n}\pi\). Therefore one way to approximate (\pi) is to divide \(2n\) by the number of needles that cross a line.

I had my computer simulate 400 needle tosses, and 258 of them crossed a line. Thus this experiment approximates \(\pi \approx 2\!\left(\frac{400}{258}\right) \approx 3.101\), about a 1.3% error from the true value.

Modeling in Python

Our goal is to write a Python program that can simulate tossing needles on the floor both numerically (e.g. “258 of 400 needles crossed a line”) and graphically (i.e. creates the PNG images like in the above example).

The RandomNeedle class.

We’ll start by defining a RandomNeedle class which takes

• a canvas_width, \(w\);
• a canvas_height, \(h\);
• and a line_spacing, \(\ell\).

It then initializes by choosing a random angle (\theta \in [0,\pi]) and random placement for the center of the needle in \[(x,y) \in \left[\frac{\ell}{2}, w -\,\frac{\ell}{2}\right] \times \left[\frac{\ell}{2}, h -\,\frac{\ell}{2}\right]\] in order to avoid issues with boundary conditions.

Next, it uses the angle and some plane geometry to compute the endpoints of the needle: \[\begin{bmatrix}x\\y\end{bmatrix} \pm \frac{\ell}{2}\begin{bmatrix}\cos(\theta)\\ \sin(\theta)\end{bmatrix}.\]

The class’s first method is crosses_line, which checks to see that the \(x\)-values at either end of the needle are in different “sections”. Since we know that the parallel lines occur at all multiples of \(\ell\), we can just check that \[\left\lfloor\frac{x_\text{start}}{\ell}\right\rfloor \neq \left\lfloor\frac{x_\text{end}}{\ell}\right\rfloor.\]

The class’s second method is draw which takes a drawing_context via Pillow and simply draws a line.

import math
import random

class RandomNeedle:
  def __init__(self, canvas_width, canvas_height, line_spacing):
    theta = random.random()*math.pi
    half_needle = line_spacing//2
    self.x = random.randint(half_needle, canvas_width-half_needle)
    self.y = random.randint(half_needle, canvas_height-half_needle)
    self.del_x = half_needle * math.cos(theta)
    self.del_y = half_needle * math.sin(theta)
    self.spacing = line_spacing

  def crosses_line(self):
    initial_sector = (self.x - self.del_x)//self.spacing
    terminal_sector = (self.x + self.del_x)//self.spacing
    return abs(initial_sector - terminal_sector) == 1

  def draw(self, drawing_context):
    color = "red" if self.crosses_line() else "grey"
    initial_point  = (self.x-self.del_x, self.y-self.del_y)
    terminal_point = (self.x+self.del_x, self.y+self.del_y)
    drawing_context.line([initial_point, terminal_point], color, 10)

By generating \(100\,000\) instances of the RandomNeedle class, and keeping a running estimation of (\pi) based on what percentage of the needles cross the line, you get a plot like the following:

The NeedleDrawer class

The NeedleDrawer class is all about running these simulations and drawing pictures of them. In order to draw the images, we use the Python library Pillow which I installed by running

pip3 install Pillow

When an instance of the NeedleDrawer class is initialized, makes a “floor” and “tosses” 100 needles (by creating 100 instances of the RandomNeedle class).

The main function in this class is draw_image, which makes a \(4096 \times 2048\) pixel canvas, draws the vertical lines, then draws each of the RandomNeedle instances.

(It saves the files to the /tmp directory in root because that’s the only place we can write file to our Docker instance on AWS Lambda, which will be a step in part 2 of this series.)

from PIL import Image, ImageDraw
from random_needle import RandomNeedle

class NeedleDrawer:
  def __init__(self):
    self.width   = 4096
    self.height  = 2048
    self.spacing = 256
    self.random_needles = self.toss_needles(100)

  def draw_vertical_lines(self):
    for x in range(self.spacing, self.width, self.spacing):
      self.drawing_context.line([(x,0),(x,self.height)],width=10, fill="black")

  def toss_needles(self, count):
    return [RandomNeedle(self.width, self.height, self.spacing) for _ in range(count)]
 
  def draw_needles(self):
    for needle in self.random_needles:
      needle.draw(self.drawing_context)

  def count_needles(self):
    cross_count = sum(1 for n in self.random_needles if n.crosses_line())
    return (cross_count, len(self.random_needles))

  def draw_image(self):
    img = Image.new("RGB", (self.width, self.height), (255,255,255))
    self.drawing_context = ImageDraw.Draw(img)
    self.draw_vertical_lines()
    self.draw_needles()
    del self.drawing_context
    img.save("/tmp/needle_drop.png")
    return self.count_needles()

Next Steps

In the next part of this series, we’re going to add a new class that uses the Twitter API to post needle-drop experiments to Twitter. In the final part of the series, we’ll wire this up to AWS Lambda to post to Twitter on a timer.