I recently wrote a post on Pascal's Triangle and in this post I will write a program in Python to implement a Galton Board simulator, a Galton Board being an actual physical gadget following the Pascal Triangle's probabilistic characteristics.
This is the graphic I used in the previous post to illustrate a five-row Pascal's Triangle.
A key characteristic of Pascal's Triangle is that if you start at the top and than trace a path downwards, randomly choosing to go left or right, each number you land on tells you how many different paths there are to that number. The probability of taking any path is
Pascal's Triangle Path Probability
0.5number of rows - 1
(We subtract 1 from the row count as there is no choice involved on the first row, there only being one number.)
So for example in the 5-row triangle above the probability of taking a particular path is
5-Row Pascal's Triangle Path Probability
0.54 = 0.0625
The total number of paths is 16 so the total probability is
5-Row Pascal's Triangle Total Path Probabilities
0.0625 * 16 = 1
Probabilities always add up to 1, indicating certainty - if you start at the top and keep going, whatever path you take and wherever you end up, you are certain to get to one of the numbers in the last row. Another key characteristic of Pascal's Triangle is that the probabilities build up row by row into an approximation of the normal distribution.
This is all very abstract but the concept can be made physical with a contraption called a Galton Board, named after Sir Francis Galton but also called a bean machine of quincunx. It is a bit like a simple pinball machine with pegs arranged in the pattern of a Pascal's Triangle and mounted vertically to let gravity do the work of propelling balls from one peg to the next. There also need to be containers of some kind to catch the balls from each final destination so they can be counted. There are plenty of images and videos if you want to do a quick search.
The Simulation
Implementing a software simulation of a Galton Board is straightforward: we just need a data structure representing the board and code simulating the random passage of balls through it. We also need to keep a running total of how many balls have taken each path, and finally some kind of visual display of what is happening.
I will use the very rudimentary graphical and animation abilities of the terminal for this project, but the data structure and associated logic can be used with any environment offering graphical output such as more sophisticated terminal output using curses, or perhaps Tkinter. To this end I will keep the data structures and logic completely separate from the visual output so a new output can be "plugged in".
The actual mechanism I will use to do this is to pass functions to the functions controlling the board. These will be called when something happens requiring the graphical output to be updated. The code can therefore be used with any form of output by just passing the appropriate functions.
Specifically there are three things a Galton Board can do which require an update to the visual output:
- The board can be created
- A ball can move
- A total can be incremented
When any of these things happens the specified function will be called, the Galton Board code itself having no responsilibity for or knowledge of how the visual output is handled.
Aside from the file containing the main function there are two other files, one for the Galton Board code and one for the functions which draw the output. The latter file can be replaced with any other providing it has a set of functions with the same parameters.
Coding
Create a new folder and within it create these empty source code files. You can download the source code as a zip or clone/download from Github if you prefer.
- galtonboard.py
- galtonboardview.py
- main.py
Source Code Links
In galtonboard.py type or paste the following code.
galtonboard.py
import math from random import choice import time GREEN = "\x1B[94m" RESET = "\x1B[0m" class GaltonBoard(object): """ Implements the logic of a Galton Board. No UI is provided in this class, instead 3 functions are provided as arguments to init which are called by the class whenever anything happens which requires a UI update. """ def __init__(self, rowcount = 7, ballcount = 40, on_init = None, on_ball_moved = None, on_total_changed = None): """ Simply set the attributes of the class from init arguments or to defaults """ self.board = [] self.rowcount = rowcount self.ballcount = ballcount self.totals = [] self.gridrows = 0 self.gridcolumns = 0 self.ballx = 0 self.bally = 0 self.prevballx = 0 self.prevbally = 0 self.pause_ms = 100 self.on_init = on_init self.on_ball_moved = on_ball_moved self.on_total_changed = on_total_changed def initialize(self): """ Initializes the data structure to represent the Galton board """ # need to allow for spaces between pegs and a larger space above the pegs for balls to drop self.gridrows = ((self.rowcount * 2) - 1) + 3 self.gridcolumns = (self.rowcount * 2) + 1 rowpegcount = 1 pegsdrawn = 0 # this centres the top peg horixontally firstpegx = math.floor(self.gridcolumns / 2) pegx = firstpegx pegy = 3 # create a list for totals of the necessary size self.totals = [0] * (self.rowcount + 1) self.prevballx = -1 self.prevbally = -1 # create 2D array of pegs using letter 'O' to indicate a peg for r in range(0, self.gridrows): self.board.append(['*'] * self.gridcolumns) for c in range(0, self.gridcolumns): if r == pegy and c == pegx and pegsdrawn < rowpegcount: self.board[r][c] = 'O' pegsdrawn+=1 pegx+= 2 else: self.board[r][c] = ' ' if r > 2 and (r%2) == 0: rowpegcount+=1 pegsdrawn = 0 firstpegx-=1 pegx = firstpegx pegy+= 2 # don't forget to call the function to tell the UI to draw the new board if self.on_init: self.on_init(self) def start(self): """ Sets the board running in a big loop for the specified number of balls """ for b in range(1, self.ballcount + 1): # set ball horizontal position to centre self.ballx = math.floor(self.gridcolumns / 2) for r in range(0, self.gridrows): self.bally = r # if we hit a peg move left or right if self.board[r][self.ballx] == 'O': self.ballx += choice([-1, 1]) if self.on_ball_moved: self.on_ball_moved(self) self.prevballx = self.ballx self.prevbally = self.bally if r < (self.gridrows - 1): time.sleep(self.pause_ms/1000) # calculate index of totals for current ball position if self.ballx == 0: totalindex = 0 else: totalindex = int(self.ballx / 2) self.totals[totalindex] += 1 if self.on_total_changed: self.on_total_changed(self, totalindex, b)
The Galton Board functionality is implemented as a class, and in __init__ we simply create a number of attributes, either with default values or with values set from arguments.
The initialize method sets the gridrows and gridcolumns attribute values, and then creates a few variables for use in the main task of initialising the board. It then sets self.totals to a list large enough to hold all totals, and sets prevballx and prevbally to -1; we will see these being used later.
Within a pair of loops we add a list to the board for each row, so the board data structure is a list of lists. We then set the individual values per row to a space or the letter "O" for a peg. If we have reached the end of the row we need to alter a few variable values ready for the next row.
Finally we call on_init to let whatever UI has been plugged in know it needs to draw the newly created board.
The last method is start which iterates the ballcount, and then iterates the rows in a nested loop. If the ball hits a peg it needs to randomly move left or right, for which I have used the random module's choice function to get either -1 or 1. This is then added to the ball's horizontal position, effectively moving it left or right. We then call the on_ball_moved to force the UI to update. The UI uses prevballx and prevbally to overwrite the previous ball position, so we then need to reset these to the current positions ready for the next iteration. We can then have a bit of a rest for the specified time.
After each ball has made its way to the bottom of the grid we need to increment the relevant total and let the UI know by calling on_total_changed.
Now let's move on to galtonboardview.py.
galtonboardview.py
import os import math import sys import time # ANSI terminal colour codes RED = "\x1B[91m" GREEN = "\x1B[92m" RESET = "\x1B[0m" X_OFFSET = 2 Y_OFFSET = 6 def __clear_screen(): """ Hopefully this is cross-platform enough: no guarantees! """ os.system('cls' if os.name=='nt' else 'clear') def __gotoxy(x, y): """ Uses ANSI terminal codes to move cursor """ print("%c[%d;%d%s" % (0x1B, y, x, "H"), end="") sys.stdout.flush() def on_init(gb): """ To be called by a GaltonBoard object when the board has first been created Just draws an empty board """ __clear_screen() print("-----------------") print("| codedrome.com |") print("| Galton Board |") print("-----------------\n") for r in range(0, gb.gridrows): print(' ', end=""); for c in range(0, gb.gridcolumns): print(gb.board[r][c], end="") print("") print("") # draw buckets for r in range(0, 16): for c in range(0, gb.rowcount + 2): print(GREEN + "| " + RESET, end="") print(GREEN + "%d" % abs(r - 16) + RESET) def on_ball_moved(gb): """ Called by GaltonBoard object when ball moves. """ # delete ball if it has a previous position if gb.prevballx >= 0 and gb.prevbally >= 0: __gotoxy(gb.prevballx + X_OFFSET, gb.prevbally + Y_OFFSET) print(" ") # draw ball in new position __gotoxy(gb.ballx + X_OFFSET, gb.bally + Y_OFFSET) print(RED + "o" + RESET, end="") sys.stdout.flush() def on_total_changed(gb, index, count): """ Called by GaltonBoard object when total changes. """ bottom_of_bucket = 4 + gb.gridrows + 19 if index == 0: bucketx = 2 else: bucketx = (index + 1) * 2 # animate ball into bucket starty = bottom_of_bucket - 17 end_y = bottom_of_bucket - gb.totals[index] for y in range(starty, end_y + 1): time.sleep(gb.pause_ms/1000) __gotoxy(bucketx, y-1) print(" ") sys.stdout.flush() __gotoxy(bucketx, y) print(RED + "o" + RESET) sys.stdout.flush() # show totals vertically total_y = bottom_of_bucket + 1 total_x = 2 for t in range(0, gb.rowcount + 1): totalstr = str(gb.totals[t]) for c in range(0, len(totalstr)): __gotoxy(total_x, total_y + c) print("%c" % totalstr[c]) sys.stdout.flush() total_x += 2 # show ball count __gotoxy(2, bottom_of_bucket + 4) print("Ball %d of %d" % (count, gb.ballcount)) sys.stdout.flush()
In galtonboardview.py we have three functions which are called by the Galton Board itself when the UI needs to be updated - on_init, on_ball_moved and on_total_changed. Before that though we need a couple of private functions, __clear_screen which uses an OS system call and __gotoxy which uses ANSI terminal codes.
Now let's look at on_init, which is called by the Galton Board when the board is created and draws an empty board. Firstly we iterate the rows and columns of the grid, printing their contents which will be a space or a letter "O" representing a peg. Then we draw the buckets using the pipe character "|". Here I have used the ANSI terminal code for green and reset which are assigned to variables near the top of the file. The reset code resets output to the default colour.
Next comes on_ball_moved. This checks to see if it is a newly-created ball in its first position; if not it deletes the ball from its previous position by overwriting it with a space. The ball is then written in its new position by printing a letter "o" using the ANSI code for red.
Finally we have on_total_changed which is a bit more complex as we need to animate the ball from the bottom of the board down to the bottom of the bucket or onto any balls already in the bucket. After calculating the positions involved we carry out the animation in a loop. Note the use of time.sleep to introduce a delay into the loop. Finally the total and ball count at the bottom are updated.
main.py
import galtonboard import galtonboardview import sys import os def main(): """ Creates and runs a GaltonBoard index object """ gb = galtonboard.GaltonBoard(7, 40, galtonboardview.on_init, galtonboardview.on_ball_moved, galtonboardview.on_total_changed) gb.initialize() os.system('setterm -cursor off') gb.start() os.system('setterm -cursor on') main()
This is all very simple as we just need to create and initialize the Galton Board, and then set it running. Note that I have turned off the cursor with an OS call while the board is running as it gets in the way, not forgetting to turn it back on later.
Run the program with this command in the terminal.
Running the program
python3.7 main.py
This is an example of what the output looks like after a run.
Program Output
----------------- | codedrome.com | | Galton Board | ----------------- O O O O O O O O O O O O O O O O O O O O O O O O O O O O | | | | | | | | | 16 | | | | | | | | | 15 | | | | | | | | | 14 | | | | | | | | | 13 | | | |o|o| | | | 12 | | | |o|o| | | | 11 | | | |o|o| | | | 10 | | | |o|o| | | | 9 | | | |o|o| | | | 8 | | | |o|o| | | | 7 | | |o|o|o|o| | | 6 | | |o|o|o|o| | | 5 | | |o|o|o|o| | | 4 | | |o|o|o|o| | | 3 | |o|o|o|o|o|o| | 2 | |o|o|o|o|o|o| | 1 0 2 6 1 1 6 2 0 2 2 Ball 40 of 40
The terminal-based output is pretty basic and in particular the animation leaves a lot to be desired. There is also the problem that if any total exceeds the bucket size it will overflow. However, as I mentioned earlier a key feature of this project is that the output is separated from the logic and so can easily be replaced by something better.