# Rule 110 with Turtle

I like repl.it a lot and from time to time I use it for 10 liners instead of my command line. Especially when I do not want to install a brand new language implementation or even creating a new Python environment for five minutes.

I was thinking about Rule 110 and how most of the examples I’ve seen from hobbyists are ASCII based as opposed to more proper, nicer graphics by researchers of the CA area. And I was thinking whether using Turtle could be used to display it a bit better in one’s spare time. That is because I still have not figured out how TkInter works with repl.it. It turns out that you can make something nice with Turtle:

I have pasted the rather rudimentary, repl.it ready, python code here.

Because WordPress.com does not always render MarkDown properly, you may need to read a copy of this post here.

One of the things I learned by reading AIM 239 is the Game of Life and Cellular Automata. One particular kind of one dimensional cellular automata, Rule 110 popped by my twitter stream the other day, so I thought I could try and code it with the minimal Haskell subset that I can handle.

Rule 110 is special because it is proven to be able to simulate a Turing machine. Head over to its Wikipedia page if you want to learn more about the proof and the interesting story around it.

Rule 110 starts with a string of zeros and ones and a transition table that decides the next state of the automaton. If you put each line of the strings after the other, interesting patterns can emerge. Let’s see the transition state:

Current pattern 111 110 101 100 011 010 001 000
New state for center cell 0 1 1 0 1 1 1 0

If you look closely, you can use a list of eight digits and its index in order to encode the above state transitions:

```rule110 = [
0, -- ((0,0,0), 0)
1, -- ((0,0,1), 1)
1, -- ((0,1,0), 1)
1, -- ((0,1,1), 1)
0, -- ((1,0,0), 0)
1, -- ((1,0,1), 1)
1, -- ((1,1,0), 1)
0  -- ((1,1,1), 0)
] :: [Int]
```

But what about the transitions of the leftmost and rightmost digit you might think. Let’s assume that their missing neighbor is zero. Therefore, given an initial state and a rule that governs the transitions, we may calculate the next state with:

```nextState :: [Int] -> [Int] -> [Int]
nextState state rule =
[ rule !! x |
let t = [0] ++ state ++ [0],
i <- [1..(length(t)-2)],
let x = (t !! (i-1)) * 4 + (t !! i) * 2 + (t !! (i+1))
]

-- construct an infinite sequence of next states
sequenceState :: [Int] -> [Int] -> [[Int]]
sequenceState state rule =
[state] ++ sequenceState (nextState state rule) rule
```

Example:

```*Main> state = [0,1,1,0]
*Main> nextState state rule110
[1,1,1,0]
```

One of the most interesting patterns occurs when we begin with the right most digit being 1 and all the rest being zeros:

```*Main> state = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1] :: [Int]
*Main> x = take 30 \$ sequenceState state rule110
*Main> showState x
*
**
***
** *
*****
**   *
***  **
** * ***
******* *
**     ***
***    ** *
** *   *****
*****  **   *
**   * ***  **
***  **** * ***
** * **  ***** *
******** **   ***
**      ****  ** *
***     **  * *****
** *    *** ****   *
*****   ** ***  *  **
**   *  ***** * ** ***
***  ** **   ******** *
** * ******  **      ***
*******    * ***     ** *
**     *   **** *    *****
***    **  **  ***   **   *
** *   *** *** ** *  ***  **
*****  ** *** ****** ** * ***
**   * ***** ***    ******** *
*Main>
```

The output was somehow pretty printed:

```showState [] = return ()
showState state = do
-- putStrLn \$ show (state !! 0)
putStrLn \$ [ c | d <- (state !! 0), let c = if d == 0 then ' ' else '*' ]
showState \$ tail state
```

I wish I can find time and play more with cellular automata. I kind of find a day every five years or so.

Update: Here is a pattern using Rule 90:

```                             *
*
* *
*
* *
*   *
* * * *
*
* *
*   *
* * * *
*       *
* *     * *
*   *   *   *
* * * * * * * *
*
* *
*   *
* * * *
*       *
* *     * *
*   *   *   *
* * * * * * * *
*               *
* *             * *
*   *           *   *
* * * *         * * * *
*       *       *       *
* *     * *     * *     * *
*   *   *   *   *   *   *   *
```

# Η ψυχολογία των sprite

Ο φίλος μου ο Παναγιώτης άλλαξε το cover page του σε αυτό εδώ και με πήγε χρόνια πίσω.

Τότε που μαζευόμασταν στο σπίτι του Τάκη και παίζαμε στην Amiga Kick Off 2. Ο Παναγιώτης είχε αναπτύξει την θεωρία της “ψυχολογίας του sprite” για να εξηγήσει κάποιες ενέργειες των παικτών στο γήπεδο. Γελάγαμε μεν, αλλά δεν είναι πως είχε άδικο ο Παναγιώτης. Γιατί δεν ξέρω για το Kick Off 2, αλλά στον Pac Man, τα φαντάσματα είχαν συγκεκριμέμενες, καθόλου τυχαίες συμπεριφορές:

In an interview, creator Toru Iwatani stated that he had designed each enemy with its own distinct personality in order to keep the game from becoming impossibly difficult or boring to play.[4] More recently, Iwatani described the enemy behaviors in more detail at the 2011 Game Developers Conference. He stated that the red enemy chases Pac-Man, and the pink and blue enemies try to position themselves in front of Pac-Man’s mouth.[5] Although he claimed that the orange enemy’s behavior is random, the game’s code reveals that it actually chases Pac-Man most of the time, but also moves toward the lower-left corner of the maze when it gets too close to Pac-Man.

Το ήξερα χρόνια αυτό, από όταν είχα διαβάσει για τις μυρωδιές, αλλά μόλις μου το θύμισε μια φωτογραφία.

# clickomania

Clickomania, ο απόλυτος χρονοφάγος. Για χρόνια έπαιζα μια εκδοχή του παιχνιδιού που έτρεχε σαν Java Applet κάπου στο Brown (εάν τη θυμάται κανείς, ας μου στείλει το (πεθαμένο) URL). Όμοια και η εκδοχή του που περιλαμβάνεται στο Axim X3 με έχει συντροφέψει σε πάμπολλες διαδρομές με το λεωφορείο. Ψάχνοντας μετά από καιρό το site του παιχνιδιού, είδα πως έχει και Ελληνική μετάφραση.

Μην το παίξετε. Έχετε προειδοποιηθεί.

# Παιδικά παιχνίδια

Προτιμητέα αυτά χωρίς μπαταρίες.

Rule.-

# Eternity II

Μια παρέα παιδικών φίλων πίνει καφέ:

– Που είναι ο Σ. σήμερα;
– Δε θα έρθει. Έχει κολλήσει με ένα παζλ.
– Παζλ; Τι παζλ είναι αυτό;
– Το λένε Eternity. Eternity II για την ακρίβεια.

Σειρά μου…

# Sudoku

Αυτό μπορείτε να το στείλετε στον DBA σας: Sudoku solver γραμμένος σε SQL (ΟΚ με features που έχει η Oracle 10g). Και για ποικιλία στον τοπικό σας Perl / Python / Ruby / PCRE guru μπορείτε να δείξετε αυτόν τον solver γραμμένο με regular expressions.

[via LtU]