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

Posted by programmingpraxis
Filed in Exercises
9 Comments »

9 Responses to “Voters”

  1. phillip said
    April 6, 2012 at 4:54 PM

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

  2. Mike said
    April 7, 2012 at 12:16 AM

    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[0]) 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[0] else -1
        
    print "{} wins!".format(COLOR[n == 0])

if __name__ == "__main__":
    sim()
  3. ardnew said
    April 8, 2012 at 3:58 AM

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

  4. ardnew said
    April 8, 2012 at 7:07 AM

    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[0]});

  # 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. Code! Code! Code! said
    April 8, 2012 at 6:06 PM

    […] 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. Voters « From C/C++ to Python said
    April 12, 2012 at 10:24 PM

    […] An exercise described here. […]

  7. ashokmenon said
    April 15, 2012 at 10:44 AM

    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 - [0] == []) or (flat - [1] == [])
  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[0].to_i, ARGV[1].to_i)

init_screen()
until s.complete?
  
  s.tick
  setpos(0,0)
  addstr( s.display )
  refresh()
  
end
  8. soulguidedtelescope said
    April 21, 2012 at 11:46 PM

    In JavaScript:

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

  9. Benjamin Samson said
    May 16, 2012 at 2:56 AM

    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[0][0]:
				return False
	return True

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

Leave a comment