Voters

April 6, 2012

To keep the display simple, we will use ansi terminal sequences to display a grid with 0 cells shown as spaces and 1 cells shown as asterisks. Here are the ansi terminal sequences we will need:

(define esc (integer->char 27))
(define (cls)
  (display esc) (display #\[)
  (display #\2) (display #\J))
(define (hide-cursor)
  (display esc) (display #\[) (display #\?)
  (display #\2) (display #\5) (display #\l))
(define (show-cursor)
  (display esc) (display #\[) (display #\?)
  (display #\2) (display #\5) (display #\h))
(define (goto x y)
  (display esc) (display #\[) (display x)
  (display #\;) (display y) (display #\H))

Show-cursor isn’t used by the program, but you will need it when you interrupt the program and the cursor remains hidden. Be sure not to write at column 80, because doing so causes the screen to scroll.

We represent the grid as a two-dimensional matrix. The neighbor of a cell is chosen as a random x plus -1, 0 or 1, and likewise for y. This means that occasionally a cell is its own neighbor, but in that case the state of the grid is unchanged, and the simulation goes on to the next state.

The voters function performs the simulation; first it initialized each cell to a random 0 or 1, then enters an infinite loop, at each step choosing a random cell and its random neighbor:

(define (voters)
  (cls) (hide-cursor)
  (let ((grid (make-matrix max-x max-y)))
    (for (x 0 max-x)
      (for (y 0 max-y)
        (matrix-set! grid x y (randint 2))
        (show x y (matrix-ref grid x y))))
    (do () (#f)
      (let* ((x (randint max-x))
             (y (randint max-y))
             (xx (modulo (+ x (randint 3) -1) max-x))
             (yy (modulo (+ y (randint 3) -1) max-y)))
        (matrix-set! grid x y (matrix-ref grid xx yy))
        (show x y (matrix-ref grid x y))))))

The show function displays a single cell. Showing 40 cells across the screen, with a space between each, gives the grid approximately the same spacing in both directions:

(define (show x y v)
  (goto x (+ y y 1))
  (display (if (zero? v) #\space #\*)))
(define max-x 24) (define max-y 39)

And that’s it. It’s fun to watch as one voting block gains dominance, the other fights back, and eventually one or the other dies. It is also fun to watch the anti-voters simulation, in which a random cell takes the opposite value of a random neighbor; as you might guess, where the normal voting simulation tends toward totalitarianism, the anti-voting simulation tends toward anarchy, where neither side can gain dominance over the other.

We used matrices and random numbers from the Standard Prelude. You can see the entire program at http://programmingpraxis.codepad.org/v3UEyvwd.

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