Wireworld: Difference between revisions
(→{{header|Ruby}}: fixed) |
m (→{{header|Tcl}}: added libheader) |
||
| Line 666: | Line 666: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{works with|Tcl|8.6}} |
{{works with|Tcl|8.6}} |
||
<br> |
|||
{{libheader|Tk}} |
|||
<lang tcl>package require Tcl 8.6 |
<lang tcl>package require Tcl 8.6 |
||
package require Tk |
package require Tk |
||
Revision as of 07:56, 10 September 2009
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
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
def initialize(string)
p string if $DEBUG
max_row = 0
@grid = string.each_line.collect do |line|
line.chomp!
max_row = [max_row, line.length].max
line.each_char.collect {|char| Cell.new(char)}
end
@width = max_row
@height = grid.length
p @grid if $DEBUG
pad_grid
end
attr_reader :grid, :width, :height
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, Cell.new(' ')))
end
end
end
# the "to_string" method
def to_s
@grid.inject() do |str, row|
str << row.join() << "\n"
end
end
# find the neighbour cells of a position in the grid
def neighbours(x, y)
neighbours = []
([x-1, 0].max .. [x+1, @width-1].min).each do |xx|
([y-1, 0].max .. [y+1, @height-1].min).each do |yy|
neighbours << @grid[yy][xx] unless x == xx and y == yy
end
end
neighbours
end
# transition all cells
def transition
changed = 0
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
def run(iterations = 25)
puts "size = #{width} x #{height}" if $DEBUG
puts self
seen = [@grid.to_s]
count = 0
loop do
puts
transition
count += 1
puts self
if seen.include?(@grid.to_s)
puts "I've seen this grid before... after #{count} iterations"
break
end
if count == iterations
puts "ran through #{iterations} iterations"
break
end
seen << @grid.to_s
end
end
end
class Cell
EMPTY = ' ' 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
@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
ww = WireWorld.open('wireworld.data') ww.run
program = DATA.read ww = WireWorld.new(program) ww.run(10)
__END__ ....... ....... HHHHHHH ....... .......</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 ....... ....... HHHHHHH ....... ....... ....... H.....H ttttttt H.....H ....... HH...HH tH...Ht ....... 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.. HH...HH tH...Ht ....... tH...Ht HH...HH I've seen this grid before... after 5 iterations
Tcl
<lang tcl>package require Tcl 8.6 package require Tk
- The color scheme.
- The order is: empty, conductor, electronTail, electronHead
set colors "#000000 #000080 #8080ff #ffffff"
- 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 }
}
}
- 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
}
- 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]
}
- 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>