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.

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 616 other followers

%d bloggers like this: