Wireworld: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Ruby}}: simplify)
Line 497: Line 497:


<lang ruby>class WireWorld
<lang ruby>class WireWorld
EMPTY = ' '
HEAD = 'H'
TAIL = 't'
CONDUCTOR = '.'

def initialize(string)
def initialize(string)
p string if $DEBUG
max_row = 0
max_row = 0
@grid = string.each_line.collect do |line|
@grid = string.each_line.collect do |line|
line.chomp!
line.chomp!
max_row = [max_row, line.length].max
max_row = [max_row, line.length].max
line.each_char.collect {|char| Cell.new(char)}
line.each_char.collect do |char|
case char
when EMPTY, HEAD, TAIL, CONDUCTOR then char
else EMPTY
end
end
end
end
@width = max_row
@width = max_row
@height = grid.length
@height = @grid.length
p @grid if $DEBUG
pad_grid
pad_grid
end
end
attr_reader :grid, :width, :height


# initialize from a file
def self.open(filename)
def self.open(filename)
self.new(File.read(filename))
self.new(File.read(filename))
Line 520: Line 528:
@grid.each do |row|
@grid.each do |row|
if @width > row.length
if @width > row.length
row.concat(Array.new(@width - row.length, Cell.new(' ')))
row.concat(Array.new(@width - row.length, EMPTY))
end
end
end
end
Line 527: Line 535:
# the "to_string" method
# the "to_string" method
def to_s
def to_s
@grid.inject('') do |str, row|
@grid.inject('') {|str, row| str << row.join('') << "\n"}
end
str << row.join('') << "\n"

# transition all cells simultaneously
def transition
@grid = @grid.each_with_index.collect do |row, y|
row.each_with_index.collect do |state, x|
transition_cell(state, x, y)
end
end
end

# how to transition a single cell
def transition_cell(current, x, y)
case current
when EMPTY then EMPTY
when HEAD then TAIL
when TAIL then CONDUCTOR
else neighbours_with_state(HEAD, x, y).between?(1,2) ? HEAD : CONDUCTOR
end
end
end
end


# find the neighbour cells of a position in the grid
# given a position in the grid, find the neighbour cells with a particular state
def neighbours(x, y)
def neighbours_with_state(state, x, y)
neighbours = []
count = 0
([x-1, 0].max .. [x+1, @width-1].min).each do |xx|
([x-1, 0].max .. [x+1, @width-1].min).each do |xx|
([y-1, 0].max .. [y+1, @height-1].min).each do |yy|
([y-1, 0].max .. [y+1, @height-1].min).each do |yy|
neighbours << @grid[yy][xx] unless x == xx and y == yy
next if x == xx and y == yy
count += 1 if state(xx, yy) == state
end
end
end
end
neighbours
count
end
end


# return the state of a cell given a cartesian coordinate
# transition all cells
def transition
def state(x, y)
changed = 0
@grid[y][x]
new_grid = []
@grid.each_with_index do |row, y|
new_row = []
row.each_with_index do |cell, x|
new_cell = cell.transition( neighbours(x,y) )
changed += 1 if cell != new_cell
puts "#{cell} -> #{new_cell}" if $DEBUG
new_row << new_cell
end
new_grid << new_row
end
@grid = new_grid
changed
end
end


# run a simulation up to a limit of transitions, or until a recurring
# pattern is found
def run(iterations = 25)
def run(iterations = 25)
seen = []
puts "size = #{width} x #{height}" if $DEBUG
puts self
seen = [@grid.to_s]
count = 0
count = 0
loop do
loop do
puts
transition
count += 1
puts self
puts self
puts
if seen.include?(@grid.to_s)

if seen.include?(@grid)
puts "I've seen this grid before... after #{count} iterations"
puts "I've seen this grid before... after #{count} iterations"
break
break
end
end
if count == iterations
if count == iterations
puts "ran through #{iterations} iterations"
puts "ran through #{iterations} iterations"
break
break
end
end
seen << @grid.to_s
end
end
end


seen << @grid
class Cell
EMPTY = ' '
count += 1
transition
HEAD = 'H'
TAIL = 't'
CONDUCTOR = '.'

def initialize(char)
unless [EMPTY, HEAD, TAIL, CONDUCTOR].include?(char)
if $DEBUG
warn "found invalid character '#{char}' -- ignoring it and using empty"
end
char = EMPTY
end
end
@state = char
end
attr_reader :state

def empty?; @state == EMPTY; end
def head?; @state == HEAD; end
def tail?; @state == TAIL; end
def conductor?; @state == CONDUCTOR; end

def transition(neighbours)
p [neighbours] if $DEBUG
next_state = if empty? then EMPTY
elsif head? then TAIL
elsif tail? then CONDUCTOR
elsif neighbours.count {|cell| cell.head?}.between?(1,2) then HEAD
else CONDUCTOR
end
self.class.new(next_state)
end

def to_s
@state
end
def inspect
@state.inspect
end
def ==(other)
@state == other.state
end
end
end
end
Line 630: Line 601:
ww = WireWorld.open('wireworld.data')
ww = WireWorld.open('wireworld.data')
ww.run
ww.run

puts "---------------"


program = DATA.read
program = DATA.read
ww = WireWorld.new(program)
ww = WireWorld.new(program)
ww.run(10)
ww.run


__END__
__END__
> ..
.......
.......
> tH...... .Ht
> .. </lang>
HHHHHHH
.......
.......</lang>


Outputs
Outputs
Line 714: Line 685:
t .
t .
.H.t ......
.H.t ......

I've seen this grid before... after 11 iterations
I've seen this grid before... after 11 iterations
---------------
.......
..
.......
tH...... .Ht
HHHHHHH
..
.......

.......
..
.tH..... Ht.
..

.H
..tH.... t..
.H

Ht
...tH..H ...
Ht

t.
....tH.t ...
t.

..
.....tH. ...
..

H.
......tH ...
H.

tH
.......t ...
tH

.t
........ H..
.t

..
........ tH.
..


..
.......
H.....H
........ .tH
..
ttttttt
H.....H
.......


..
HH...HH
tH...Ht
........ ..t
..
.......
tH...Ht
HH...HH


..
ttH.Htt
........ ...
.tH.Ht.
..
HHH.HHH
.tH.Ht.
ttH.Htt


..
..t.t..
........ ...
H.t.t.H
..
ttt.ttt
H.t.t.H
..t.t..


I've seen this grid before... after 13 iterations
HH...HH
</pre>
tH...Ht
.......
tH...Ht
HH...HH
I've seen this grid before... after 5 iterations</pre>


=={{header|Tcl}}==
=={{header|Tcl}}==

Revision as of 17:00, 10 September 2009

Task
Wireworld
You are encouraged to solve this task according to the task description, using any language you may know.

Wireworld is a cellular automaton with some similarities to Conway's Game of Life. It is capable of doing sophisticated computations (e.g., calculating primeness!) with appropriate programs, and is much simpler to program for.

A wireworld arena consists of a cartesian grid of cells, each of which can be in one of four states. All cell transitions happen simultaneously. The cell transition rules are this:

Input State Output State Condition
empty empty
electron head  electron tail 
electron tail  conductor
conductor electron head  if 1 or 2 cells in the neighborhood of the cell are in the state “electron head”
conductor conductor otherwise

To implement this task, create a program that reads a wireworld program from a file and displays an animation of the processing. Here is a sample description file (using “H” for an electron head, “t” for a tail, “.” for a conductor and a space for empty) you may wish to test with, which demonstrates two cycle-3 generators and an inhibit gate: 

tH.........
.   .
   ...
.   .
Ht.. ......

While text-only implementations of this task are possible, mapping cells to pixels is advisable if you wish to be able to display large designs. The logic is not significantly more complex.

Forth

<lang forth> 16 constant w 

8 constant h
rows w * 2* ;

1 rows constant row h rows constant size

create world size allot world value old old w + value new

init world size erase ;
age new old to new to old ;
foreachrow ( xt -- )
 size 0 do  I over execute  row +loop drop ;

0 constant EMPTY 1 constant HEAD 2 constant TAIL 3 constant WIRE create cstate bl c, char H c, char t c, char . c,

showrow ( i -- ) cr
 old + w over + swap do I c@ cstate + c@ emit loop ;
show ['] showrow foreachrow  ;


line ( row addr len -- )
 bounds do
   i c@
   case
   bl of EMPTY over c! endof
   'H of HEAD  over c! endof
   't of TAIL  over c! endof
   '. of WIRE  over c! endof
   endcase
   1+
 loop drop ;
load ( filename -- )
 r/o open-file throw
 init  old row + 1+  ( file row )
 begin  over pad 80 rot read-line throw
 while  over pad rot line
        row +
 repeat
 2drop close-file throw
 show cr ;


+head ( sum i -- sum )
 old + c@ HEAD = if 1+ then ;
conductor ( i WIRE -- i HEAD|WIRE )
 drop 0
 over 1- row - +head
 over    row - +head
 over 1+ row - +head
 over 1-       +head
 over 1+       +head
 over 1- row + +head
 over    row + +head
 over 1+ row + +head
 1 3 within if HEAD else WIRE then ;

\ before: empty head tail wire

create transition ' noop , ' 1+ , ' 1+ , ' conductor ,

\ after: empty tail wire head|wire

new-state ( i -- )
 dup  old + c@
 dup cells transition + @ execute
 swap new + c! ;
newrow ( i -- )
 w over + swap do I new-state loop ;
gen ['] newrow foreachrow age ;
wireworld begin gen 0 0 at-xy show key? until ;

</lang>

Output: 

s" wireworld.diode" load
                
        ..      
 tH...... .Ht   
        ..      
                
                
                
                
 ok
gen show                
                
        ..      
 .tH..... Ht.   
        ..      
                
                
                
                 ok
gen show 
                
        .H      
 ..tH.... t..   
        .H      
                
                
                
                 ok
gen show 
                
        Ht      
 ...tH..H ...   
        Ht      
                
                
                
                 ok
gen show 
                
        t.      
 ....tH.t ...   
        t.      
                
                
                
                 ok
gen show 
                
        ..      
 .....tH. ...   
        ..      
                
                
                
                 ok
gen show 
                
        H.      
 ......tH ...   
        H.      
                
                
                
                 ok
gen show 
                
        tH      
 .......t ...   
        tH      
                
                
                
                 ok
gen show 
                
        .t      
 ........ H..   
        .t      
                
                
                
                 ok
gen show 
                
        ..      
 ........ tH.   
        ..      
                
                
                
                 ok
gen show 
                
        ..      
 ........ .tH   
        ..      
                
                
                
                 ok
gen show 
                
        ..      
 ........ ..t   
        ..      
                
                
                
                 ok
gen show 
                
        ..      
 ........ ...   
        ..      
                
                
                
                 ok

J

The example circuit: <lang J> circ0=:}: ] ;. _1 LF, 0 : 0 tH........ . . 

  ...

. . Ht.. ..... ) </lang> A 'boarding' verb board and the next cell state verb nwS: <lang J>

board=: ' ' ,.~ ' ' ,. ' ' , ' ' ,~ ]

nwS=: 3 : 0 

 e=. (<1 1){y
 if. ('.'=e)*. e.&1 2 +/'H'=,y do. 'H' return. end.
 ' t..' {~ ' Ht.' i. e

) </lang> The 'most' powerful part is contained in the following iterating sentence, namely the dyad cut ;. [1]. In this way verb nwS can work on all the 3x3 matrices containing each cell surrounded by its 8 relevant neighbors. <lang J> (3 3 nwS;. _3 board)^: (<10) circuit</lang> Example run: 

   (3 3 nwS;. _3 board)^: (<10) circ0
tH........
.   .     
   ...    
.   .     
Ht.. .....

.tH.......
H   .     
   ...    
H   .     
t... .....

H.tH......
t   .     
   ...    
t   .     
.H.. .....

tH.tH.....
.   H     
   ...    
.   .     
HtH. .....

.tH.tH....
H   t     
   HHH    
H   .     
t.tH .....

H.tH.tH...
t   .     
   ttt    
t   .     
.H.t .....

tH.tH.tH..
.   H     
   ...    
.   .     
HtH. .....

.tH.tH.tH.
H   t     
   HHH    
H   .     
t.tH .....

H.tH.tH.tH
t   .     
   ttt    
t   .     
.H.t .....

tH.tH.tH.t
.   H     
   ...    
.   .     
HtH. .....

Python

<lang python> Wireworld implementation.

from io import StringIO from collections import namedtuple from pprint import pprint as pp import copy

WW = namedtuple('WW', 'world, w, h') head, tail, conductor, empty = allstates = 'Ht. '


infile = StringIO(\ tH......... . . 

  ...

. . Ht.. ......\ )

def readfile(f): 

   'file > initial world configuration'
   world  = f.readlines()
   world  = [row.rstrip('\r\n') for row in world]
   height = len(world)
   width  = max(len(row) for row in world)
   # fill right and frame in empty cells
   nonrow = [ " %*s " % (-width, "") ]
   world  = ( nonrow
              + [ " %*s " % (-width, row) for row in world ]
              + nonrow[:] )    
   world = [list(row) for row in world]
   return WW(world, width, height)

def newcell(currentworld, x, y): 

   istate = currentworld[y][x]
   assert istate in allstates, 'Wireworld cell set to unknown value "%s"' % istate
   if istate == head:
       ostate = tail
   elif istate == tail:
       ostate = conductor
   elif istate == empty:
       ostate = empty
   else: # istate == conductor
       n = sum( currentworld[y+dy][x+dx] == head
                for dx,dy in ( (-1,-1), (-1,+0), (-1,+1),
                               (+0,-1),          (+0,+1),
                               (+1,-1), (+1,+0), (+1,+1) ) )
       ostate = head if 1 <= n <= 2 else conductor
   return ostate

def nextgen(ww): 

   'compute next generation of wireworld'
   world, width, height = ww
   newworld = copy.deepcopy(world)
   for x in range(1, width+1):
       for y in range(1, height+1):
           newworld[y][x] = newcell(world, x, y)
   return WW(newworld, width, height)

def world2string(ww): 

   return '\n'.join( .join(row[1:-1]).rstrip() for row in ww.world[1:-1] )

ww = readfile(infile) infile.close()

for gen in range(10): 

   print ( ("\n%3i " % gen) + '=' * (ww.w-4) + '\n' )
   print ( world2string(ww) )
   ww = nextgen(ww)

</lang>

Sample Output 

  0 =======

tH.........
.   .
   ...
.   .
Ht.. ......

  1 =======

.tH........
H   .
   ...
H   .
t... ......

  2 =======

H.tH.......
t   .
   ...
t   .
.H.. ......

  3 =======

tH.tH......
.   H
   ...
.   .
HtH. ......

  4 =======

.tH.tH.....
H   t
   HHH
H   .
t.tH ......

  5 =======

H.tH.tH....
t   .
   ttt
t   .
.H.t ......

  6 =======

tH.tH.tH...
.   H
   ...
.   .
HtH. ......

  7 =======

.tH.tH.tH..
H   t
   HHH
H   .
t.tH ......

  8 =======

H.tH.tH.tH.
t   .
   ttt
t   .
.H.t ......

  9 =======

tH.tH.tH.tH
.   H
   ...
.   .
HtH. ......

Ruby

Text only.

<lang ruby>class WireWorld 

 EMPTY = ' '
 HEAD = 'H'
 TAIL = 't'
 CONDUCTOR = '.'

 def initialize(string)
   max_row = 0
   @grid = string.each_line.collect do |line|
             line.chomp!
             max_row = [max_row, line.length].max
             line.each_char.collect do |char| 
               case char
               when EMPTY, HEAD, TAIL, CONDUCTOR then char
               else EMPTY
               end 
             end
           end
   @width = max_row
   @height = @grid.length
   pad_grid
 end

 # initialize from a file
 def self.open(filename)
   self.new(File.read(filename))
 end

 # ensure all rows are the same length by padding short rows with empty cells
 def pad_grid
   @grid.each do |row|
     if @width > row.length
       row.concat(Array.new(@width - row.length, EMPTY))
     end
   end
 end

 # the "to_string" method
 def to_s
   @grid.inject() {|str, row| str << row.join() << "\n"}
 end

 # transition all cells simultaneously
 def transition
   @grid = @grid.each_with_index.collect do |row, y| 
             row.each_with_index.collect do |state, x| 
               transition_cell(state, x, y)
             end
           end
 end

 # how to transition a single cell
 def transition_cell(current, x, y)
   case current
   when EMPTY then EMPTY
   when HEAD  then TAIL
   when TAIL  then CONDUCTOR
   else neighbours_with_state(HEAD, x, y).between?(1,2) ? HEAD : CONDUCTOR
   end
 end

 # given a position in the grid, find the neighbour cells with a particular state
 def neighbours_with_state(state, x, y)
   count = 0
   ([x-1, 0].max .. [x+1, @width-1].min).each do |xx|
     ([y-1, 0].max .. [y+1, @height-1].min).each do |yy|
       next if x == xx and y == yy
       count += 1 if state(xx, yy) == state
     end
   end
   count
 end

 # return the state of a cell given a cartesian coordinate
 def state(x, y)
   @grid[y][x]
 end

 # run a simulation up to a limit of transitions, or until a recurring
 # pattern is found
 def run(iterations = 25)
   seen = []
   count = 0
   loop do
     puts self
     puts

     if seen.include?(@grid)
       puts "I've seen this grid before... after #{count} iterations"
       break
     end
     if count == iterations
       puts "ran through #{iterations} iterations"
       break
     end

     seen << @grid
     count += 1
     transition
   end
 end

end

ww = WireWorld.open('wireworld.data') ww.run

puts "---------------"

program = DATA.read ww = WireWorld.new(program) ww.run

__END__ > .. > tH...... .Ht > .. </lang>

Outputs 

tH.........
.   .
   ...
.   .
Ht.. ......

.tH........
H   .
   ...
H   .
t... ......

H.tH.......
t   .
   ...
t   .
.H.. ......

tH.tH......
.   H
   ...
.   .
HtH. ......

.tH.tH.....
H   t
   HHH
H   .
t.tH ......

H.tH.tH....
t   .
   ttt
t   .
.H.t ......

tH.tH.tH...
.   H
   ...
.   .
HtH. ......

.tH.tH.tH..
H   t
   HHH
H   .
t.tH ......

H.tH.tH.tH.
t   .
   ttt
t   .
.H.t ......

tH.tH.tH.tH
.   H
   ...
.   .
HtH. ......

.tH.tH.tH.t
H   t
   HHH
H   .
t.tH ......

H.tH.tH.tH.
t   .
   ttt
t   .
.H.t ......

I've seen this grid before... after 11 iterations
---------------
         ..
  tH...... .Ht
         ..

         ..
  .tH..... Ht.
         ..

         .H
  ..tH.... t..
         .H

         Ht
  ...tH..H ...
         Ht

         t.
  ....tH.t ...
         t.

         ..
  .....tH. ...
         ..

         H.
  ......tH ...
         H.

         tH
  .......t ...
         tH

         .t
  ........ H..
         .t

         ..
  ........ tH.
         ..

         ..
  ........ .tH
         ..

         ..
  ........ ..t
         ..

         ..
  ........ ...
         ..

         ..
  ........ ...
         ..

I've seen this grid before... after 13 iterations

Tcl

Works with: Tcl version 8.6


Library: Tk

<lang tcl>package require Tcl 8.6 package require Tk

  1. The color scheme.
  2. The order is: empty, conductor, electronTail, electronHead

set colors "#000000 #000080 #8080ff #ffffff"

  1. Encapsulate the per-cell logic in a class to simplify it

oo::class create wireCell { 

   variable X Y S0 S1 Neighbours

   constructor {x y state} {

global cells colors upvar 1 at at

set X $x set Y $y

switch -- $state conductor { set S0 1 } electronTail { set S0 2 } electronHead { set S0 3 } default { return -code error "invalid state name \"$state\"" } lappend cells [self] set at($x,$y) [self] pixels put [lindex $colors $S0] -to $x $y 

   }

   # Method used to allow each (non-background) cell to know about its
   # surrouding non-background cells. This makes the connectivity
   # calculations much simpler and faster!
   method initConnectivity {} {

upvar 1 at at foreach dx {-1 -1 -1 0 0 1 1 1} dy {-1 0 1 -1 1 -1 0 1} { set pos [expr {$X+$dx}],[expr {$Y+$dy}] if {[info exists at($pos)]} { lappend Neighbours $at($pos) } } 

   }

   method state {} {return $S0}

   # Perform the transition in two stages, so that we can do the transition
   # "simultaneously" across all cells. The transition0 method calculates
   # what state we're going to change to, and the transition1 method actually
   # moves to the state.
   method transition0 {} {

if {$S0 == 3} { set S1 2 } elseif {$S0 == 2} { set S1 1 } else { set count 0 foreach n $Neighbours { incr count [expr {[$n state] == 3}] } set S1 [expr {($count == 1 || $count == 2) ? 3 : 1}] } 

   }
   method transition1 {} {

if {$S0 != $S1} { global colors set S0 $S1 pixels put [lindex $colors $S0] -to $X $Y } 

   }

}

  1. How to load a layout/program from a file

proc loadWires filename { 

   global cells colors

   # Read the file in
   set f [open $filename]
   set data [read $f]
   close $f

   # Initialize the list of interacting cells and the connectivity map
   set cells {}
   array set at {}

   # Calculate the width of the program
   set lines [split $data \n]
   set len 0
   foreach line $lines {

if {[string length $line] > $len} { set len [string length $line] } 

   }

   # Create the arena image
   image create photo pixels

   # Initialize the image to "empty cell"s; interacting parts will be overlaid
   pixels put [lindex $colors 0] -to 0 0 $len [llength $lines]

   # Parse the input data and create the interacting cells
   set y 0
   foreach line $lines {

set x 0 foreach char [split $line {}] { switch $char { H { wireCell new $x $y electronHead } t { wireCell new $x $y electronTail } . { wireCell new $x $y conductor } } incr x } incr y 

   }

   # Now inform each cell about its connectivity
   foreach cell $cells {

$cell initConnectivity 

   }
   unset at

}

  1. How to perform the animation timestep

proc timeStep {t} { 

   global cells

   # Arm the transition for all interacting cells
   foreach cell $cells {

$cell transition0 

   }
   # Perform the transition for all interacting cells
   foreach cell $cells {

$cell transition1 

   }

   # Reschedule
   after $t [list timeStep $t]

}

  1. Initialize the GUI (such as it is) and load and start the animation

wm title . "Wireworld: [lindex $argv 0]" loadWires [lindex $argv 0] pack [label .l -image pixels] after 1000 timeStep 250</lang>

Retrieved from "https://rosettacode.org/wiki/Wireworld?oldid=127695"