Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Cellular Automata are truly fascinating. The ones that are usually talked about are the binary ones, i.e., the ones representable by a number. However, those, in my opinion, have been done to death. Ternary CAs are more interesting, but we have all of ASCII to consider! What fun could that be!

Instead of deciding a ruleset for each character, I will use a simple deciding rule which I will talk about soon. To decide the next generation, we look at the three "top" cells, much like a cellular automata. Observe an example:


The "top" of Y is WER, being the cells above-and-right, above, and above-and left. Y will be the result of the function I'm about to define, which is a function on three-char strings. The "top" of X is QW, or a space filling in the non-existent/missing cell.

Now, for the fun function! I call this sequence the XOROR sequence for a reason. Let A be the top-left cell charcode, B be the above cell charcode, and C be the top-right cell charcode. Then, the resulting cell is the character whose charcode is (A XOR B) OR C, that is, (A^B)|C. (If a resulting value is greater than 126, then it is set to (CHARCODE % 127) + 32. Nothing is done if a value is less than 32.) Here is an example of the seed Hello, World!:

S: Hello, World!
0: mmmo/c_ z}~)e
   m = ( )^(H)|(e) = (32^72)|101 = 104|101 = 109 (m)
    m = (H)^(e)|(l) = (72^101)|108 = 45|108 = 109 (m)
1: mmo/c_<   +wl
2: mo/c_<c< + |;
3: o/c_<c  ?+  g
4: oc_<c c??4+gg
5: 0_<c c  4+ o 
6: _<c ccc4??ooo
7:  c ccc4 ?o o 
8: ccccc4w? pooo
9: cccc4w h   o 
A: ccc4wc hh ooo
B: cc4wc4kh ooo 
C: c4wc4  #ooo o
D: wwc4w4#ooo oo
E: wc4wwc oo oo 
F: w4wwc4oo oo o
G: wwwc4   oo oo
H: wwc4w4 oo oo 
I: w4wwc4oooo oo
J: wwwc4  oo oo 
K: wwc4w4oo oo o
L: wc4wwo  oo oo
M: w4wwo8ooo oo 
N: wwwo8  o oo o
O: wwo8w8oooo oo

And we can proceed on for a while hereafter. This modification of the string is called the XOROR sequence.

Objective You are to write a program or function that does one of the following tasks:

  1. Given a string s and a number n >= 0, output the nth string on the XOROR sequence with seed s, with n = 0 being the first transformation of the string.
  2. Given a string s, output (for programs) or generate (for functions/generators) an infinite stream of the XOROR sequence with seed s. You may choose to stop if the sequence repeats, but this is not necessary.

s will always only consist of printable ASCII characters, from space to tilde plus tabs (no newlines.)

This is a , so the shortest program in bytes wins.

share|improve this question
I'm having trouble parsing the sentence "So, whatever function I am about to define on a three-char string, Y will become." Could this be reworded: "Y will be the result of the function I'm about to define, a function on three-char strings."? – hYPotenuser Mar 4 at 17:59
All of the os make it look like a zerg rush. – mbomb007 Mar 4 at 18:24
Observation: Since XOR and OR preserve the number of bits and all ASCII is 7 bits, the only case when a CHARCODE is > 126 is if it is 127. Therefor, you can just replace it with a space (32) since 127%127+32==32. – CAD97 Mar 4 at 21:24
Why is n=0 not the original string? – Neil Mar 4 at 21:59
@FatalSleep As for you first complaint, I stated that, if no cell is present, the result is a space, so it would rather be (d^!)|(space). As for you second question, you perform (CHAR%127)+32 after the XOROR is performed. – Cᴏɴᴏʀ O'Bʀɪᴇɴ Mar 5 at 16:24

10 Answers 10

up vote 4 down vote accepted

MATL, 33 31 bytes


This works in release 13.1.0 of the language/compiler, which predates the challenge.

The first input is the number, the second is the string.

Try it online!

Q           % take input (number) implicitly and add 1
:"          % repeat that many times
  32XK      %   push 32 (space). Copy to clipboard K.
  h         %   concatenate. Takes input (string) implicitly the first time
  Kwh       %   push space, swap, concatenate
  3YC       %   overlapping blocks of length 3 as columns of 2D array
  P         %   flip upside-down 
  o         %   convert to numbers
  2$1Z}     %   separate the three rows and push them
  Z~        %   bitwise XOR (note the rows are in reverse order)
  Z|        %   bitwise OR
  127KYX    %   replace 127 by space using regexprep, which converts to char
            % end loop
            % implicitly display
share|improve this answer

Mathematica, 133 bytes


It would be nice to make a CellularAutomaton[] solution work, but I kept coming up short. Anyone?

Edit: some pretty pictures (click to enlarge)

plotCA[str_, n_] := ArrayPlot[NestList[foo[str],n], ColorFunction -> "Rainbow"]

plotCA["Hello, World!", 60]:

60 iterations of "Hello, World!"

plotCA[bXORnotb, 100]:

100 iterations of Hamlet soliloquy

plotCA[raven, 100]:

100 iterations of Poe

share|improve this answer
Can't you just give CellularAutomaton your update function? (The actual rule number with 127 valid states would be insane.) – Martin Ender Mar 4 at 21:10
@MartinBüttner You can, but it's a drag trying to account for the behavior at the edges, to get it to be compliant with the spec. BlockMap[] was just shorter. – hYPotenuser Mar 4 at 21:24

Java, 193 185 bytes

Because Java.

-8 bytes by switching to looping rather than recursing to make it an anonymous function

Returns the n'th iteration of XOROR on s.

(s,n)->{String o=s;for(;n-->=0;){o="";for(int i=0;i<s.length();i++){char c=(char)((i>1?s.charAt(i-1):' ')^s.charAt(i)|(i<s.length()-1?s.charAt(i+1):' '));o+=c>126?' ':c;}s=o;}return o;}

Readable version:

static BiFunction<String, Integer, String> f = (s,n)->{
    String o=s;
    for(;n-->=0;) {
        o = "";
        for (int i=0;i<s.length();i++) {
            char c=(char)((i>1?s.charAt(i-1):' ')^s.charAt(i)|(i<s.length()-1?s.charAt(i+1):' '));
            o+=c>126?' ':c;
    return o;

public static void main(String[]a) {
    System.out.println(f.apply("Hello, World",1));

Pretty much a literal implementation of the spec, with a recursive loop to apply the operation n times. Some bytes were saved, however, with my observation that the CHARCODE>126 clause will only ever happen with CHARCODE==127, which results in saving SPACE instead of DEL.

I ran my code over a few arbitrarily chosen strings and found this wonderful cycle:

share|improve this answer
This answer looks ok! – Cᴏɴᴏʀ O'Bʀɪᴇɴ Mar 5 at 16:25
3! – The Vee Mar 6 at 12:06

CJam, 38 bytes

lri){2S*\*3ew{)\:^|_'~>{i127%' +}&}%}*

Test it here.


l                e# Read string.
ri               e# Read n.
){               e# Run this block n+1 times...
  2S*\*          e#   Wrap in two spaces.
  3ew            e#   Get all (overlapping) substrings of length 3.
  {              e#   Map this block over all those substrings...
    )\           e#     Pull off the third character and put it below the other two.
    :^           e#     Take XOR of the other two.
    |            e#     OR with the third one.
    _'~>         e#     Duplicate and check if it's greater than '~'.
    {i127%' +}&  e#     If so, mod 127, add to space.
share|improve this answer
I think you can save a few bytes with lri){2S*\*3ew{)\:^|}%127c' er}* because the chars pre-modulo operation never exceed 127 – Luis Mendo Mar 5 at 0:57

Haskell, 123 bytes

import Data.Bits
f s=toEnum.a<$>zipWith3(((.|.).).xor)(32:s)s(tail s++[32])
a x|x>126=32|1<2=x
tail.iterate( fromEnum)

This returns an infinite stream of the XOROR sequence. Usage example (print the first 5 elements of the seed "Hello, World!"):

*Main> mapM_ print $ take 5 $ (tail.iterate( fromEnum)) "Hello, World!"
"mmmo/c_ z}~)e"
"mmo/c_<   +wl"
"mo/c_<c< + |;"
"o/c_<c  ?+  g"
"oc_<c c??4+gg"

How it works:

tail.iterate( fromEnum)               -- repeat forever: convert to ASCII
                                           -- value and call f, discard the first
                                           -- element (the seed).

                                           -- one iteration is:
  zipWith3(   )(32:s) s (tail s++[32])     -- zip the elements from the three lists
                                           -- (space:s), s and tail of s ++ space,
                                           -- e.g. s = "Hello!":
                                           --   | Hello|
                                           --   |Hello!|
                                           --   |ello! |
                                           -- (shortest list cuts off)

         ((.|.).).xor                      -- the function to zip with is a
                                           -- point-free version of (x xor y) or z

toEnum.a<$>                                -- adjust every element >126 and convert
                                           -- back to characters
share|improve this answer

PHP, 186 bytes (with n) | 177 bytes (infinite)

It turned out that infinite printing is shorter...

// With n
function x($s,$n){while($n-->=0){for($i=0,$r='';$i<strlen($s);$i++){$b=ord($s[$i-1])or$b=32;$a=ord($s[$i+1])or$a=32;$t=($b^ord($s[$i]))|$a;$r.=chr($t>126?($t%127)+32:$t);}$s=$r;}echo$s;}

// Infinite
function i($s){while(true){for($i=0,$r='';$i<strlen($s);$i++){$b=ord($s[$i-1])or$b=32;$a=ord($s[$i+1])or$a=32;$t=($b^ord($s[$i]))|$a;$r.=chr($t>126?($t%127)+32:$t);}echo$s=$r;}}

Ungolfed with n:

function x($s, $n) { // $s - string to process; $n - which string to output
  while ($n-- >= 0) {
    for ($i = 0, $r = ''; $i < strlen($s); $i++) {
      $b = ord($s[$i - 1]) or $b = 32;
      $a = ord($s[$i + 1]) or $a = 32;
      $t = ($b ^ ord($s[$i])) | $a;
      $r .= chr($t > 126 ? ($t % 127) + 32 : $t);
  $s = $r;
  echo $s;

Ungolfed infinite:

function x($s) { // $s - string to process
  while (true) {
    for ($i = 0, $r = ''; $i < strlen($s); $i++) {
      $b = ord($s[$i - 1]) or $b = 32;
      $a = ord($s[$i + 1]) or $a = 32;
      $t = ($b ^ ord($s[$i])) | $a;
      $r .= chr($t > 126 ? ($t % 127) + 32 : $t);
    echo $s = $r;
share|improve this answer
It can still be golfed a lot. For instance, function i($s){for(;;$i=0,print$s=$r)for($r='';$i<strlen($s);$r.=chr($t>126?32:$t))$t=((o‌​rd($s[$i-1])?:32)^ord($s[$i]))|(ord($s[++$i])?:32);} is 141 bytes long (-36 bytes). – Blackhole Mar 5 at 17:16


Nth-Sequence (212)

void x(char*s,int l,int n){for (;n-->0;) {char*t=new char[l-1](),w;for(int i=0;i<l-1;i++)t[i]=((w=(((i-1>= 0)?s[i-1]:32)^s[i])|((i+1<l-1)?s[i+1]:32))>126)?((w%127)+32):w;for(int i=0;i<l-1;i++)s[i]=t[i];delete[]t;}}


void x(char*s, int l, int n){
    for (;n-- > 0;) {
        char*t=new char[l-1](),w;
        for(int i = 0;i < l-1; i++)
            t[i] = ((w = (((i-1>= 0) ? s[i-1] : 32)^s[i]) | ((i+1 < l-1) ? s[i+1] : 32)) > 126) ? ((w % 127) + 32) : w;

        for(int i = 0; i < l-1; i++)
            s[i] = t[i];

Nth-Sequence using pointer syntax instead of array syntax to make this all the more confusing: (231)

void x(char*s,int l,int n){for(int x=0;x++<n;) {char*t=new char[l-1](),w;for(int i=0;i<l-1; i++)*(t+i)=((w=(((i-1>= 0)?*(s+i-1):32)^*(s+i))|((i+1<l-1)?*(s+i+1):32))>126)?((w%127)+32):w;for(int i=0;i<l-1;i++)*(s+i)=*(t+i);delete[]t;}}


void x(char* s, int l, int n){
    for (;n-- > 0;) {
        char*t = new char[l-1](),w;
        for(int i = 0; i < l-1; i++)
            *(t+i) = ((w = (((i-1>= 0) ? *(s+i-1) : 32)^ *(s+i)) | ((i+1<l-1) ? *(s+i+1) : 32)) > 126) ? ((w%127)+32) : w;

        for(int i = 0;i < l-1; i++)
            s[i] = t[i];

Debug Function (For Fun)

void d(char* seed, int len, int nth) {
    for (int n = 0; n++ < nth;) {
        char* tout = new char[len - 1]();
        for (int i = 0; i < len - 1; i++) {
            char x, y, z;
            x = ((--i >= 0) ? seed[i] : 32);
            y = seed[++i];
            z = ((++i < len - 1) ? seed[i] : 32);
            char w = (x ^ y) | z;
            tout[--i] = (w > 126) ? ((w % 127) + 32) : w;

            cout << "[" << x << " " << y << " " << z << "] " << w << endl;

        for (int i = 0; i < len - 1; i++)
            seed[i] = tout[i];
        delete[] tout;
        cout << endl;
share|improve this answer
Pretty sure the results say you must output the result, not simply return it. – Mooing Duck Mar 6 at 18:01
I wrote a C++ version from scratch, compared to yours and then merged them, and got this, at 158 bytes: – Mooing Duck Mar 6 at 18:42
@MooingDuck Nice! Could probably reduce it further with implicit int by the compiler via moving to C. – FatalSleep Mar 6 at 23:03
of course, go ahead! You already wrote half of that code – Mooing Duck Mar 7 at 0:56

JAVA 240/280 Bytes

The popular Java version at the time I wrote this claimed to be 185 bytes, but there are two significant fudge points. First, the measurement is presumably only for the function, not for the complete working source. Maybe not such a problem. Second, it uses BiFunction without either an import or a fully qualified name. Adding the required bits to run it as-is (then minimizing it, fairly) brought it to 348 bytes. Adding only the fully qualified name of the BiFunction class brings it to 248 bytes.

In contrast, I believe mine is 240 bytes when playing by the same rules (no class, no actual output, just the meat). The full runnable class is 280 bytes, and looks like this (unminified):

class z{
  public static void main(String[] s){
    int L=s[0].length();
    for(int G=Integer.valueOf(s[1]);G-->0;){
      for(int N=0;N<L;N++){
        char C=(char)((N>0?s[0].charAt(N-1):' ')^(s[0].charAt(N))|(N<L-1?s[0].charAt(N+1):' '));
        s[1]+=C>126?' ':C;
      s[0] =s[1];

Or, minified:

void m(String[] s){int L=s[0].length();for(int G=Integer.valueOf(s[1]);G-->0;){s[1]="";for(int N=0;N<L;N++){char C=(char)((N>0?s[0].charAt(N-1):' ')^(s[0].charAt(N))|(N<L-1?s[0].charAt(N+1):' '));s[1]+=C>126?' ':C;}s[0]=s[1];}return s[0];}
share|improve this answer

Perl, 47 bytes

Includes +2 for -lp

Run with the input on STDIN, e.g. perl -lp <<< "Hello, World!" | head -26

/./s;$_=$_.chop^" $_"|"$' ";y/\x7f/ /;print;redo

This works as is, but replace the \x7f by the corresponding binary value to get the given score

share|improve this answer

Swift: 273 Characters

Wow, Swift is worse than Java! (All those APIs with long names! :P)

func c(s:String,n:Int=0-1){var a=[UInt8](s.utf8);for i in 0...(n>=0 ?n:Int.max-1){var z="";for i in 0..<a.count{let A=i-1<0 ?32:a[i-1],B=a[i],C=i+1<a.count ?a[i+1]:32;var r=A^B|C;r=r<32 ?32:r>126 ?32:r;z+=String(UnicodeScalar(r))};if n<0||i==n{print(z)};a=[UInt8](z.utf8)}}


func cellularAutoma(s: String,n: Int = -1)
    var array = [UInt8](s.utf8)
    for i in 0...(n >= 0 ? n : Int.max - 1)
        var iteration = ""
        for i in 0..<array.count
            let A = i - 1 < 0 ? 32 : array[i - 1], B = array[i], C = i + 1 < array.count ? array[i + 1] : 32
            var r = A ^ B | C
            r = r < 32 ? 32 : r > 126 ? 32 : r
            iteration += String(UnicodeScalar(r))
        if n < 0 || i == n

Thanks to @CAD97 for mentioning that (A^B)|C can only be greater than 126 when it's 127.

I also realized that you don't need parenthesis around A^B|C because XORing is done before ORing, so that saved me a few bytes.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.