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.

About these ads

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[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

    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[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. [...] 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 - [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

    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[0][0]:
    				return False
    	return True
    
    def displayTable(table):
    	print 
    	for i in table:
    		for j in i:
    			print j,
    		print 		
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: