## Voters

### April 6, 2012

It’s election year in the United States, and in today’s exercise we have an election simulation. It comes to us from chapter “Five Easy Pieces” in A. K. Dewdney’s book The Armchair Universe, which is a compilation of some of Dewdney’s “Computer Recreations” columns in Scientific American. Dewdney calls his simulation voters.

The simulation is simple. A rectangular x-by-y grid contains cells that represent voters. Each cell has eight horizontally, vertically or diagonally adjacent neighbors, with the grid wrapping around on all sides to form a torus. Each cell can contain one of two values, which we call 0 and 1, not necessarily in order, instead of Democrat or Republican. At each time step, one cell, chosen at random, changes its allegiance to that of one of its eight neighbors, chosen at random; in some cases that random choice leaves the allegiance unchanged.

The current state of the simulation is displayed on the screen, with easily distinguishable symbols for 0 and 1. The simulation continues until it reaches a steady state — totalitarianism — in which all cells have the same value. It is mesmerizing to watch the screen as voting blocks form and changing allegiances sweep across the grid.

Your task is to write a program that displays the simulation described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 9 Responses to “Voters”

1. phillip said

here’s my python version; much the same idea.
voters

2. Mike said

Python 2.7 version with graph display using the built-in turtle graphics module.

```from random import choice, randint
from turtle import *

NROWS = 10
HNROWS = NROWS/2
NCOLS = 10
HNCOLS = NCOLS/2

DOTSIZE = 20
COLOR = ('red', 'blue')

def sim():
reset()
hideturtle()
penup()
speed(0)
delay(0)

voter = [[choice(COLOR) for c in range(NCOLS)] for r in range(NROWS)]

for r in range(NROWS):
for c in range(NCOLS):
x = (c - HNCOLS)*DOTSIZE
y = (r - HNROWS)*DOTSIZE
goto(x,y)
dot(20, voter[r][c])

n = sum(row.count(COLOR) for row in voter)

while 0 < n < NROWS*NCOLS:
c, r  = randint(0, NCOLS-1), randint(0, NROWS-1)
dc,dr = choice(((-1, 1), ( 0, 1), ( 1, 1),
(-1, 0),          ( 1, 0),
(-1,-1), ( 0,-1), ( 1,-1)))
nc,nr = (c + dc)%NCOLS, (r + dr)%NROWS

if voter[r][c] != voter[nr][nc]:
voter[r][c] = voter[nr][nc]
goto((c - HNCOLS)*DOTSIZE, (r - HNROWS)*DOTSIZE)
dot(20, voter[r][c])

n += 1 if voter[nr][nc] == COLOR else -1

print "{} wins!".format(COLOR[n == 0])

if __name__ == "__main__":
sim()

```
3. ardnew said

if i could vote up comments, +1 to Mike for turtle graphics

4. ardnew said

Here’s a perl implementation, with comments!

```use strict;
use warnings;

my \$MAX_ROWS = 50;
my \$MAX_COLS = 50;

#
# generates a grid whose dimensions are randomly selected
# from 2 to MAX_ROWS and 2 to MAX_COLS. each component is
# randomly selected to be 0 or 1.
#
sub rand_grid
{
my (\$c, \$r, @g) = (int(rand((shift) - 2) + 2),
int(rand((shift) - 2) + 2));

push @g, [map {int(rand(2))} (0 .. \$r)] for (0 .. \$c);
return @g;
}

#
# prints the grid, one row per line
#
sub print_grid
{
print +(join '', @\$_).\$/ foreach @_;
}

#
# randomly selects one of the 8 neighbors of a given (x,y)
# coordinate
#
sub rand_neighbor
{
my (\$x, \$y, \$n, \$m) = @_;

my @c = ([-1,-1],[-1, 0],[-1, 1],[ 0,-1],
[ 0, 1],[ 1,-1],[ 1, 0],[ 1, 1]);

my @d = @{\$c[int(rand(@c))]};

return ((\$x + shift @d) % \$m,
(\$y + shift @d) % \$n);
}

#
# checks if the population has reached a totalitarian state
#
sub totalitarian
{
my \$s = "";
\$s .= join '', @\$_ foreach @_;

return \$s eq "1" x length \$s ||
\$s eq "0" x length \$s;
}

#
# Main routine
#
sub main
{
# generate the random grid
my @grid = rand_grid(@_);

# determine our grid's dimensions
my (\$m, \$n) = (0+@grid, 0+@{\$grid});

# continue until we reach a steady state
while (not totalitarian(@grid))
{
# randomly pick a cell
my (\$y, \$x) = (int(rand(\$m)), int(rand(\$n)));

# randomly pick one of its neighbors
my (\$j, \$k) = rand_neighbor(\$x, \$y, \$n, \$m);

# change our cell's allegience
\$grid[\$y][\$x] = \$grid[\$j][\$k];

# print our current state
print_grid(@grid);
print +('-' x \$n).\$/;
}
}

main(\$MAX_ROWS, \$MAX_COLS);
```
5. […] It’s called “Voters” and the full description of the problem can be found here. I wrote a terminal output version and then deleted that when I started working on a GTK3+Cairo GUI […]

6. […] An exercise described here. […]

7. ashokmenon said

Written for Ruby 1.9.3, using Curses, run it in a terminal, and give it two arguments, the width and height in grid units of the grid:

```require "curses"
include Curses

class Simulation

def initialize x, y
@x = x
@y = y

@grid = []
@y.times { @grid << [] }

populate_random()
end

def populate_random
@y.times   do |j|
@x.times do |i|

@grid[j][i] = rand(2)

end
end
end

def display

@grid.map { |row|

row.map { |x|
x == 1 ? "*" : " "

}.join("")
}.join("\n")

end

def complete?
flat = @grid.flatten

(flat -  == []) or (flat -  == [])
end

def random_neighbour x, y
ran_x = (x + rand(3) - 1) % @x
ran_y = (y + rand(3) - 1) % @y

@grid[ran_y][ran_x]
end

def tick
coord_x = rand(@x)
coord_y = rand(@y)

@grid[coord_y][coord_x] = random_neighbour( coord_x, coord_y )
end

end

s = Simulation.new(ARGV.to_i, ARGV.to_i)

init_screen()
until s.complete?

s.tick
setpos(0,0)
refresh()

end
```
8. soulguidedtelescope said

In JavaScript:

http://jsbin.com/azebew/edit#preview

9. Python implementation:

```from random import randint
def simulate():
table = [[randint(0,1) for i in range(5)] for j in range(5)]

while not allSame(table):
#pick random cell
i, j = randint(0,4), randint(0,4)

#pick random neighbor
m, n = randint(i-1, i+1), randint(j-1, j+1)
while m not in range(0,5) or n not in range(0,5):
m, n = randint(i-1, i+1), randint(j-1, j+1)

#get neighbor's value
table[i][j] = table[m][n]

displayTable(table)

def allSame(table):
for i in table:
for j in i:
if j != table:
return False
return True

def displayTable(table):
print
for i in table:
for j in i:
print j,
print
```