Rule 30

In Fun Life, we looked at Conway's Game of Life and implemented it in functional style. In this post, we see another cellular automation - Stephen Wolfram's Rule 30 in action. We see what makes it work and also get acquainted with other related automata. Lastly, I share notes from my implementation.

Example array of bits

Let's say we have a 10 element array of bits. Each bit may either be in a 1 state or 0 state. We can represent the array as above. Blacks represent 1s and whites 0s.

Each element bit of the array, makes a 3 bit pattern along with its adjoining neighbours on both sides. The pattern comprises the neighbouring left bit, itself and the neighbouring right bit in that order. Example, the 3 bit pattern that element 2 forms with its neighbours is 001. The pattern that element 6 forms is 100.

How Rule 30 works?

Assume a given array of bits represents 1 generation. Rule 30 says that each element in the next generation mutates to a new state governed by the following bit pattern mappings. Since there can be 3 bits in a pattern, there are 2^3 = 8 mappings.

Note: The out of bounds neighbouring bits of extreme elements (0 and 9 in the example) may be treated as default 0s or default 1s depending on the cellular automata. For Rule 30 assume they default to 0s.

If we read the new state bits, it is 00011110 or 30 in binary. This is the basis for the name Rule 30.

Applying Rule 30

In the above representation, indices 0 thru 9 is our original array. Indices 10 thru' 19 is the new generation. We can see element 2->0 change to element 12->1, based on the new state from pattern 001. We can also see element 5->1 change to element 15->0, based on the new state from pattern 110

Apply Rule 30 to yield yet another row...

Elements 20 thru 29 is the new generation. We can now see element 15->0 change back to element 25->1, based on the new state from pattern 001

Friends of Rule 30

There could be similar other rules based on other integers. In fact, since there are 3 bits, there could be 256 possible cellular automata or rule systems. Rule 0 to Rule 255. Most of these have simple uninteresting behaviours. Along with Rule 30, we will look at it's interesting friends - Rules 135, 149, 90 and 102.

To explore different automata, it's useful to re-state the rules in a generic way.

Rules

Let's animate these !

We start with a 43 element bit array. The top most row. We seed it with a 1 in center i.e the 21st index (first cell's index is 0). All other elements are seeded as 0. This is gen0 or the beginning configuration. As the animation starts, we can observe progress for 22 successive generations. The buttons below switch the rule-set. On switch, the top row 43 elements are again seeded with all 0s barring a 1 in the center and we re-play progress for 22 generations. The exceptions are rules 135 and 149. For this, in a black-white reversal, we seed only the center 21st index as 0 and others as 1. The animations run @ 5 fps.

Transforms

In fact, Rule 135 is used in the architecture of a railway station in the UK - Cambridge North. Actually the pattern that can be seen is Rule 135 by day and Rule 30 by night from outside the station. Rule 135 is a Rule 30 transform with black and white reversed. This is because at night, the light from inside the station leaks out causing that effect. From the inside during the day, its Rule 149 which is a Rule 135 (and hence Rule 30) transform. Rule 149 is the mirror image of Rule 135.

Beauty of chaos

Meanwhile, Rule 30 is the smallest integer exhibiting interesting entropy characteristics. It's also a personal favourite of its creator Stephen Wolfram who discovered these in the 80s. So much so that for a while he had rule 30 printed on his business cards:) The unpredictable way in which progressve generations evolve from simple rules with just 1 seeded bit as a starting point is a very surprising result. Reverse engineeering the initial seed gen-0 given an evolved generation gen-n is very hard. Makes you wonder what other beautiful art can be made from similar trivial algorithms!

As with game of life, there is chaotic disorder and emergent sophistication in Rule 30's output. In fact, just based on how the center cell evolves, Wolfram proposed it as potential pseudorandom number generators. Some old versions of his Mathematica engine used Rule 30 to generate random integers.

Notes from implementation

It's helpful to visualize the data using an example. An example 5 element 3 generation animation would be seeded as follows as 1 array of 15 booleans. Notice the lone true element in index 2 in the whole group.

{:depth 0, :cell-life-status [false false true false false
  false false false false false 
  false false false false false]}

Once we begin the animation, in frame 1, the code operates on indices 5 thru' 9. It computes the values for each of those 5 elements based on corresponding bit patterns formed from elements in indices 0 thru 4. After it computes the new state for each of the 5 rows in a new generation, it increments the depth key by 1. In the final frame it operates on elements 10 thru 14. After which, the depth counter exceeds the number of rows in the grid which freezes the animation.

In reality, our grid is 22 generations of a 43 element bit array. That is 1 big bit array of 22 * 43 elements all initialized as false. We refer to this as "big array". We seed element 22 - the center position of the top row, as true and start the animation frame by frame till depth becomes greater than 22.

Each frame operates on the corresponding 43 element segment of the big array.

(defn random-state []
  {:depth 0 :cell-life-status (assoc (vec
    (repeat (* rows cols) (if (contains? #{135 149}  @rule-set) true false))) (/ (dec cols) 2)
    (if (contains? #{135 149} @rule-set) false true))})

(defn exp [x n]
  (reduce * (repeat n x)))

(defn enquire-bit [rule bit]
  (= (exp 2 bit) (bit-and rule (exp 2 bit))))

(defn get-cell-state [num-cols current-state idx]
  (let [nil-as-false #(if (nil? %) (cond
                                     (= 135 @rule-set) true
                                     (= 149 @rule-set) true
                                     :else false) %)

        left-edge?  (zero? (mod idx num-cols))
        right-edge?  (zero? (mod (inc idx) num-cols))
        get-left #(nil-as-false (when (not left-edge?) (get %1 (dec %2))))
        get-this #(nil-as-false (get %1  %2))
        get-right #(nil-as-false (when (not right-edge?) (get %1 (inc %2))))
        triad-idx (- idx num-cols)
        triad [(get-left current-state triad-idx) (get-this current-state triad-idx)
               (get-right current-state triad-idx)]
        to-decimal #(+ %3 (* 2 %2) (* 4 %1))
        bit-to-enquire (apply to-decimal (map #(if (= % false) 0 1) triad))
        ;30 135 (complement of 30), 90 (good design) 102 (good design) 184 (not good design)
        new-state (assoc current-state idx (enquire-bit @rule-set bit-to-enquire))]
    new-state))

(defn gen-next [{:keys [depth cell-life-status]}]
  (let [indices (range (* (inc depth) cols) (+ cols (* (inc depth) cols)))
        new-state (reduce (partial get-cell-state cols) cell-life-status indices)]
    {:depth (inc depth) :cell-life-status new-state}))

(defn update-state [state]
  (if @reset (do (reset! reset false) (random-state))
      (if (> (:depth state) rows) state
          (gen-next state))))

The function get-cell-state returns a new version of the entire grid based on the results of computation of just 1 cell or element.

Since get-cell-state just computes 1 element, but we want 43 elements or 1 row computed every frame, the above function is called as an argument to reduce in the gen-next function.

Back to get-cell-state. In its implementation we use bit arithmetic to enforce the rules in a generic way.

idx is the address of 1 cell in the big array for which we want the new state to be computed. It depends on the 3 bit pattern aka triad of the index of the previous generation i.e cols elements before it. This previous generation index's address is bound to the local variable triad-idx. Once the triad pattern is figured out, it gets converted to decimal between 0 and 7. Say a triad pattern gets converted to the decimal 4. Then our final state is the 4th least significant bit (0th least significant bit is the right most bit of an interger's binary representation) of the rule in question.

to-decimal is the function that converts the triad pattern to decimal.

new-state is the final state computed using enquire-bit [rule bit]. This function applies the passed in bit in a bit-and operation and arrives at the desired state within a rule system. The rule system is deref'd thru' the global @rule-set as it mutates on button action.

(defn draw-state [state]
  (q/background 60 0 180)
  (let [cell-width (/ (q/width) cols)
        cell-height (/ (q/height) rows)]
    (doseq [[i elem] (map-indexed vector (:cell-life-status state))]
      (let [y-pos (quot i cols)
            x-pos (mod i cols)]
        (q/stroke 240 0 180)
        (apply q/fill (if elem [60 0 180] [60 0 360]))
        (q/rect (* x-pos cell-width) (* y-pos cell-height) cell-width cell-height)))))

The draw logic is almost identical to the function we have seen in the Fun Life post. We only change the colouring a little bit so that the animation is grey-ish

(defn example-2 []
  [:div.buttons
   [(if (= @rule-set 30) :button.button.is-dark.is-selected
        :button.button)
    {:on-click
     #(do (reset! rule-set 30) (reset! reset true))} "30"]

   [(if (= @rule-set 135) :button.button.is-dark.is-selected
        :button.button)
    {:on-click
     #(do (reset! rule-set 135) (reset! reset true))} "135"]

   [(if (= @rule-set 149) :button.button.is-dark.is-selected
        :button.button)
    {:on-click
     #(do (reset! rule-set 149) (reset! reset true))} "149"]

   [(if (= @rule-set 90) :button.button.is-dark.is-selected
        :button.button)
    {:on-click
     #(do (reset! rule-set 90) (reset! reset true))} "90"]

   [(if (= @rule-set 102) :button.button.is-dark.is-selected
        :button.button)
    {:on-click
     #(do (reset! rule-set 102) (reset! reset true))} "102"]])

As always, user affordances become easy when we code it up in hiccup-reagent. The key to note here is reset is a cljs atom, whereas rule-set is a reagent atom. Without the reagent atom, we cannot have the stateful buttons functionality.