Date: Thu, 18 Mar 2010 15:55:28 -0400
From: David Applegate <david(AT)research.att.com>

Here is a simple 3-state 5-neighbor CA that produces the toothpick structure:

3 states: {0, H, V}:  0 = empty, H, V = middle of horizontal/vertical toothpicks.

Initial state: all 0, except center V

Transitions:

 0      V      *      *
*0*->H *0*->H H00->V 00H->V
 V      0      *      *

Note that although the transitions would conflict for something like
 V
H00
 0
this can't arise because the transitions only put H on odd cells, V on
even ones.  Also, note that although it's a 5-neighbor CA, each rule
only looks at horizontal or vertical neighbors.

This gives the mathematica

toothpickrules = {
  {{_,0,_},{_,0,_},{_,V,_}} -> H,
  {{_,V,_},{_,0,_},{_,0,_}} -> H,
  {{_,_,_},{H,0,0},{_,_,_}} -> V,
  {{_,_,_},{0,0,H},{_,_,_}} -> V,
  {{_,_,_},{_,c_,_},{_,_,_}}  :> c};
Count[Flatten[#], V | H] & /@
   CellularAutomaton[toothpickrules, {{{V}}, 0}, 60]

Since this CA marks the centers, but not the endpoints, it doesn't
give A147614.  A variant on Eric Rowland's automaton is the following 5-state
one, which can be stated quite succinctly:
   If you are 0 and have a vertical neighbor V, change to |
   If you are | and have a vertical neighbor not V, change to H
   If you are 0 and have a horizontal neighbor H, change to -
   If you are - and have a horizontal neighbor not H, change to V
This CA runs at half speed - it can be viewed that on one iteration
the center of a toothpick is placed, and on the next its endpoints
arrive.  It turns out that only one rule is applicable on each
iteration, so on iteration 4n+1, |'s will be created, on iteration
4n+2, H's will be created, etc.

The mathematica is

toothpickrules2 = {
  {{_,_,_},{_,0,_},{_,V,_}} -> "|",
  {{_,V,_},{_,0,_},{_,_,_}} -> "|",
  {{_,_,_},{_,"|",_},{_,Except[V],_}} -> H,
  {{_,Except[V],_},{_,"|",_},{_,_,_}} -> H,
  {{_,_,_},{H,0,_},{_,_,_}} -> "-",
  {{_,_,_},{_,0,H},{_,_,_}} -> "-",
  {{_,_,_},{_,"-",Except[H]},{_,_,_}} -> V,
  {{_,_,_},{Except[H],"-",_},{_,_,_}} -> V,
  {{_,_,_},{_,c_,_},{_,_,_}}  :> c};
Count[Flatten[#], V | H] & /@
   CellularAutomaton[toothpickrules2, {{{V}}, 0}, 121]
Count[Flatten[#], Except[0]] & /@
   CellularAutomaton[toothpickrules2, {{{V}}, 0}, 121]

Because the automata runs at half speed, the iteration counts are
doubled to give the same sequence prefix.

-Dave