Simulate the Wireworld cellular automaton

24

4

Wireworld is a cellular automaton that was designed to be resemble electrons flowing through wires. Its simple mechanics allow the construction of digital circuits. It has even permitted the construction of an entire computer.

Your mission is to create the shortest Wireworld implementation in your language of choice.

Each cell in the grid has one out of four states. The four states are "blank," "copper," "electron head," or "electron tail."

  • A blank cell will always remain a blank cell
  • An electron head will always become an electron tail
  • An electron tail will always become copper
  • A copper cell will become an electron head iff exactly one or two out of its eight neighbors are electron heads, otherwise it will remain copper

This competition will have a similar style to the Shortest Game of Life competition, but with a few changes.

  • The grid must be at least 40 by 40 cells
  • The edges of the grid must NOT wrap around (not a torus). Treat cells outside of the field as being constantly "blank."
  • It must be possible for the users to enter their own starting configuration.
  • Staring at blank screens is not fun. The program must visually display the simulation as it is running.

This is code golf, fewest bytes wins.

PhiNotPi

Posted 2012-12-24T17:30:06.193

Reputation: 26 739

Answers

6

ALPACA, 82 chars

ALPACA is a language specifically designed for cellular automatons.

o is nothing; c is conductor; e is electron; t is electron tail.

state o " ";
state c "c" to e when 1 e or 2 e;
state e "e" to t;
state t "t" to c.

DanTheMan

Posted 2012-12-24T17:30:06.193

Reputation: 3 140

When was this language released ? Are there any links for the language ? – Optimizer – 2015-07-03T16:18:57.907

@Optimizer Here you go! I didn't make the language.

– DanTheMan – 2015-07-03T16:21:01.023

4Cool. Right language for the right challenge.. – Optimizer – 2015-07-03T16:35:33.857

6

APL, Dyalog (131)

{h t c←1↓⍵∘=¨F←' htc'⋄⎕SM∘←1 1,⍨⊂N←F[1+⊃+/H h(t∨c≠H←c∧S↑1 1↓1 2∊⍨⊃+/+/K∘.⊖(K←2-⍳3)∘.⌽⊂¯1⌽¯1⊖h↑⍨2+S←25 79)ר⍳3]⋄∇N⊣⎕DL÷4}↑{79↑⍞}¨⍳25

The output is displayed in the ⎕SM window. The simulation runs endlessly. The grid is 79x25 because that's the default size of the ⎕SM window. The electron head is h, tail is t, copper is c. The program reads the starting configuration from the keyboard as 25 lines.

Explanation:

  • ↑{79↑⍞}¨⍳25: read the 79x25 grid
  • h t c←1↓⍵∘=¨F←' htc': get three matrices, one with the heads, one with the tails and one with the copper. Also set F to the string ' htc'.

  • ⎕SM∘←1 1,⍨⊂N←F[1+⊃+/...ר⍳3]: The "..." part is a vector of length three, where the elements are matrices showing the new heads, tails, and copper respectively. The heads are multiplied by 1, the tails by 2, and the copper by 3, then we sum these matrices together and add one, giving a matrix of indices into F. N becomes the new state, in the same format as the input, and it is shown on the ⎕SM screen starting from the top-left corner.

  • ¯1⌽¯1⊖h↑⍨2+S←25 79: Add a border of blanks to h by growing it by two rows and columns, then rotating it one right and one down.

  • ⊃+/+/K∘.⊖(K←2-⍳3)∘.⌽⊂: Rotate the matrix in all eight directions and then sum the resulting matrices together, giving the amount of neighbours that are heads on each position.

  • 1 2∊⍨: Set only those positions to 1 which have 1 or 2 neighbours.

  • S↑1 1↓: Remove the border we added earlier.

  • H←c∧: The new heads are all those copper cells that have 1 or 2 head neighbours.

  • t∨c≠H: The new copper cells are all old tails, and all old copper cells that have not become heads.

  • H h(...): The new heads are H as calculated above, the new tails are the old heads, and the new copper cells are as calculated above.

  • ∇N⊣⎕DL÷4: Wait 1/4th of a second, then run the function again on N.

marinus

Posted 2012-12-24T17:30:06.193

Reputation: 30 224

I think it'd be better if it could contain a 40 by 40 grid. – mbomb007 – 2015-07-16T14:38:30.363

4

GolfScript (125 120 105 100 chars)

n%{.,,{1${.0=,:w[1,*]\+2*>3<}:^~`{zip^''+.4=5%'`X '@{+}*(7&1>'iX'>+=}+w,%}%"\033[H\033[J"@n*+puts 6.?.?}do

Note that I'm counting the \033 as one character each, because they can be replaced by a literal ESC character. This uses ANSI control codes, so relies on a compatible tty. Also note that frames are printed starting with the input grid.

There is some overlap with Generate a grid of sums, which also uses the Moore neighbourhood.

Encoding: blank space => ; electron head => i; electron tail => `; copper => X.

The pause between iterations is the time required to calculate 4665646656. Changing 6.?.? to another expression allows you to control the speed; the next slowest for the same character count is 7.?.?, which is much slower (the output is 22 times as big, and it's not a linear complexity calculation).

For a test case, I've been using

`iXXXXXXXXX
X   X      
   XXX     
X   X      
i`XX XXXXXX

from the Rosetta Code Wireworld challenge.

Peter Taylor

Posted 2012-12-24T17:30:06.193

Reputation: 41 901

3

Python (243 214)

Tried to make a cross between usability and characters. The grid is 40x40. Input is given on stdin. An electron head is h, electron tail is t, copper is c, anything else is blank.

import os
f=raw_input()
while 1:f=''.join('h'if(i=='c')&(0<sum(1 for i in[-1,1,-39,-40,-41,39,40,41]if f[e+i:e+i+1]=='h')<3)else't'if i=='h'else'c'if i=='t'else f[e]for e,i in enumerate(f));os.system('cls');print f

The while loop (line 3) uncompressed (will not work if placed in code):

while 1:
 for e,i in enumerate(f):
  if(i=='c')&(0<sum(1 for i in[-1,1,-39,-40,-41,39,40,41]if f[e+i:e+i+1]=='h')<3):f[e]='h'
  elif i=='h':f[e]='t'
  elif i=='t':f[e]='c'
  else:f[e]=f[e]  #redundant, but Python needs this to run
 os.system('cls') #cls is shorter than clear, so I used that
 print f

beary605

Posted 2012-12-24T17:30:06.193

Reputation: 3 904

I think you can replace lines 5-7 with a single expression: g[e]='h'if(t=='c')&...else't'if i=='h'else'c'if i=='t'else i. Not sure if that works exactly as is, but something along those lines should work – Strigoides – 2013-01-04T12:47:20.637

3

Python 371 341 chars

Yeah, it's not that short, but it has an interactive gui!

import matplotlib.pylab as l,scipy.ndimage as i
r=round
w=l.zeros((40,40),int)-1
p=l.matshow(w,vmax=2)
c=p.figure.canvas
def h(e):
 try:w[r(e.ydata),r(e.xdata)]=[0,2,-1][e.button-1]
 except:x=i.convolve(w==2,l.ones((3,3)),int,'constant');w[:]=w/2+((w==0)&(x>0)&(x<3))*2
 p.set_data(w);c.draw()
c.mpl_connect('button_press_event',h)
l.show()

Instructions:

Click with left mouse button to place wire

Click with right mouse button to clear

Click with middle mouse button to place electron head

Click outside the axes to step the automaton

Geoff Reedy

Posted 2012-12-24T17:30:06.193

Reputation: 2 828

(x>0)&(x<3) -> (0<x<3). :) – beary605 – 2013-01-04T17:06:07.423

2

C, 355 347 300 294 chars

Edit: realized I don't need feof()

Edit: Saved 47 chars! Removed the Sleep, got rid of almost all braces, combined a lot of operations.

Edit: Last one today, since I broke 300 chars. Changed printf to puts, found a cute little optimization with the first comparison.

C does not lend itself well to this sort of problem, but hey, golfing it is fun. This is a pretty brute-force implementation, but I wanted to see how far I could golf it up.

Input is a text file named i. It contains a representation of the starting state, with * for copper, + for electron head, - for electron tail, spaces for empty cells. I'm using the XOR gate from the wiki page for testing.

   ****-+**
  +        ******
   -*******      *
                ****
                *  *****
                ****
   ********      *
  +        ******
   -****+-*

char*p,t[42][42],s[42][42];
main(i,r,c,n,j)
{
  for(p=fopen("i","r");fgets(s[i++]+1,40,p););

  for(;;getch(),memcpy(s,t,1764))
    for(j=1;j<41;puts(s[j++]+1))
      for(i=1;i<41;)
      {
        p=t[j]+i;
        r=s[j][i++];
        *p=r==43?45:r;
        if(r==45)
          *p=42;
        if(r==42)
          for(r=-1,n=0;r<2;++r,*p=n&&n<3?43:42)
            for(c=-2;c<1;)
              n+=s[j+r][i+c++]==43;
      }
}

JoeFish

Posted 2012-12-24T17:30:06.193

Reputation: 691

Could cond?43:42 be written 42+(cond)? And I'm sure r=s[j][i++];*p=r==43?45:r;if(r==45)*p=42; can be reduced to r=s[j][i++];*p=r==43?45:r==45?42:r; if not to r=s[j][i++]-43;*p=!r?45:r==2?42:r; – Peter Taylor – 2013-09-10T13:35:37.080

1

QBasic, 309 bytes

Warning: the golfed version is not user-friendly: it has a weird input method, runs as an infinite loop, and doesn't have any delay (thus, runs too fast on some systems). Only run it if you know how to terminate a program in your QBasic environment. The ungolfed version is recommended (see below).

INPUT w,h
SCREEN 9
FOR y=1TO h
FOR x=1TO w
PSET(x,y),VAL(INPUT$(1))
NEXT
NEXT
DO
FOR y=1TO h
FOR x=1TO w
SCREEN,,0
c=POINT(x,y)
d=c
IF c=7THEN d=1
IF c=1THEN d=6
IF c=6THEN
n=0
FOR v=y-1TO y+1
FOR u=x-1TO x+1
n=n-(POINT(u,v)=7)
NEXT
NEXT
d=7+(n=0OR n>2)
END IF
SCREEN,,1,0
PSET(x,y),d
NEXT
NEXT
PCOPY 1,0
LOOP

To run, specify at the input prompt your configuration's width w and height h.1 Then type w*h single-digit codes for the cells (moving left to right, then top to bottom), with

  • 0 = empty
  • 6 = wire
  • 7 = signal head
  • 1 = signal tail

Once you have entered all of the cells, the simulation will begin (and continue forever, until you kill the program).

Ungolfed

A more user-friendly version. To modify the layout, modify the DATA statements at the end.

The code takes advantage of the POINT function, which reads the color value of a pixel from the screen. This means we don't have to store the cells separately as an array. To make sure that all cells update simultaneously, we perform the updates on a second "page." We can toggle the active page using a version of the SCREEN statement, and copy one page's contents to another using the PCOPY statement.

SCREEN 9

EMPTY = 0 ' Black
HEAD = 7  ' Light gray
TAIL = 1  ' Blue
WIRE = 6  ' Brown/orange

' First two data values are the width and height
READ w, h
' The rest are the initial configuration, row by row
' Read them and plot the appropriately colored pixels
FOR y = 1 TO h
  FOR x = 1 TO w
    READ state$
    IF state$ = "" THEN value = EMPTY
    IF state$ = "H" THEN value = HEAD
    IF state$ = "T" THEN value = TAIL
    IF state$ = "W" THEN value = WIRE
    PSET (x, y), value
  NEXT x
NEXT y

' Loop the simulation until user presses a key
DO UNTIL INKEY$ <> ""
  ' Store current time for delay purposes
  t# = TIMER

  FOR y = 1 TO h
    FOR x = 1 TO w
      ' Active page = display page = 0
      SCREEN , , 0
      ' Get the color value of the pixel at x,y
      oldVal = POINT(x, y)
      IF oldVal = EMPTY THEN
        newVal = EMPTY
      ELSEIF oldVal = HEAD THEN
        newVal = TAIL
      ELSEIF oldVal = TAIL THEN
        newVal = WIRE
      ELSEIF oldVal = WIRE THEN
        neighbors = 0
        FOR ny = y - 1 TO y + 1
          FOR nx = x - 1 TO x + 1
            IF POINT(nx, ny) = HEAD THEN neighbors = neighbors + 1
          NEXT nx
        NEXT ny
        IF neighbors = 1 OR neighbors = 2 THEN
          newVal = HEAD
        ELSE
          newVal = WIRE
        END IF
      END IF
      ' Active page = 1, display page = 0
      SCREEN , , 1, 0
      ' Plot the new value on page 1
      PSET (x, y), newVal
    NEXT x
  NEXT y

  ' Copy page 1 to page 0
  PCOPY 1, 0

  ' Delay
  WHILE TIMER >= t# AND t# + 0.2 > TIMER
  WEND
LOOP

DATA 8,5
DATA T,H,W,W,W,W,W,W
DATA W, , , ,W, , , 
DATA  , , ,W,W,W, , 
DATA W, , , ,W, , , 
DATA H,T,W,W, ,W,W,W

1 The maximum values for width and height depend on which screen mode is used. In SCREEN 9, width can be up to 638 and height up to 348. SCREEN 7 has a smaller resolution (max configuration size 318 by 198), but the pixels are bigger and thus easier to see (on DOS QBasic or the DOSBox emulator--unfortunately QB64 just gives a smaller window).

Example run

Ungolfed version on archive.org, with screen mode 7:

Wireworld in QBasic

DLosc

Posted 2012-12-24T17:30:06.193

Reputation: 21 213

1

Python, 234 218 chars

import time
I=input
C=I()
H=I()
T=I()
R=range(40)
while 1:
 for y in R:print''.join(' CHT'[(C+H+2*T).count(x+y*1j)]for x in R)
 H,T=[c for c in C if 0<sum(1 for h in H if abs(c-h)<2)<3and c not in H+T],H;time.sleep(.1)

You input the board as three list of complex numbers representing the coordinates of the cells of copper (which must include the heads and tails lists), heads, and tails. Here's an example:

[3+2j+x for x in range(8)] + [3+4j+x for x in range(8)] + [11+3j+x for x in range(6)] + [2+3j]
[3+2j]
[2+3j]

Note that we eval the input, so you can use arbitrarily complex expressions for lists of complex numbers.

Keith Randall

Posted 2012-12-24T17:30:06.193

Reputation: 19 865