
Title:
Elementary Cellular Automaton  Intro to Computer Science

Description:

For this question I'm going to explain
how we take an input string,

which in this case is
dot dot dot x dot dot dot dot,

and we change it according to some rules.

Now the rules are:

look at three characters in the string

and change the middle one

according to the rules that we have here.

Don't worry about the numbers for
the moment, I'll come to those later.

So for this particular three,

we have dot dot x.

Now dot dot x says change
the middle element

so that it's an x.

So on the next string, the new string,

that position is going to be an x.

The position before it

dot dot dot

well dot dot dot becomes a dot

in the middle.

Now at the ends

we want to link around

so this dot here

has to its left a dot

and to its right a dot,

so we have dot dot dot again

and dot dot dot says change the middle

to a dot.

Now moving along,

the next one we have to
fill in is dot x dot.

Dot x dot says change the middle to an x.

x dot dot,

change the middle to an x

dot dot dot again,

middle is a dot

dot dot dot, middle is a dot

dot dot and then

the first one is the last one here

so dot dot dot again is a dot.

Now that completes
one change of the string

and we're going to repeat that again.

So, That's the first generation.

This is the second generation.

Now normally when you do this, you'd
start at the beginning of the string

but just to explain it, it was easier
to show you one in the middle.

So this time we'll do it
from the beginning of the string.

So looking at the line above,

we see that the first
element in the string

has a dot to its left,

and a dot to its right,
so it's dot dot dot,

so that's a dot.

Now we have dot dot x,

and dot dot x, that's number two here,

gives me an x.

dot x x is an x,

x x x is a dot.

x x dot, is a dot.

x dot dot is an x.

dot dot dot, is a dot.

And dot dot dot is also a dot.

And we can continue like that.

And so after five generations,

we have the string
dot dot dot x x dot x x.

And you see we have quite
an interesting pattern building up.

Now, we can do this for lots of different

choices of these dots and x's

in blue, on the second line.

In fact, we can do it
in 256 different ways.

And in order to decide what

pattern we're going to use, what rules rather,

we can give this rule a number.

Now, wherever I've got an x on the bottom row,

I'm going to add up those numbers,

so 2 + 4 + 8 + 16,

and that gives me 30.

So this here uses pattern 30.

Now instead of pattern 30, we could
choose a different pattern.

Let's say we choose pattern 69.

Now 69, is equal to,

now we have to look at these
numbers above and

work out how to make 69

out of those numbers.

Well, 128 doesn't go into 69,
so we don't need any of those.

64 does so we want a 64.

We don't want any 32's.

We don't want any 16's, nor 8.

But we do need 4,

don't need 2, and we do need 1.

So 64 + 4 + 1, 69.

So that means, that we want 1.

That means were going
to replace dot dot dot,

the middle element by an x.

No 2's. We do have a 4.

We don't have an eight.

We don't have 16.

We don't have 32.

We do have 64,

and we don't have 128.

So, we could start off
with the same input as before,

which was, dot dot dot x dot dot dot dot.

So when we have a dot at the beginning,

its neighbor on the left is a dot,

and its neighbor on the right is a dot,

we have dot dot dot,
and that's replaced with an x.

dot dot dot again, is an x.

dot dot x, is a dot.

Remember, we are looking down here.

dot x dot, That's number 4, is an x.

x dot dot is a dot.

dot dot dot is an x.

and dot dot dot is an x, as well.

So that's line 1.

Continuing with the same thing,
I'll fill in a few more lines,

so that we can see
what happens with the pattern.

And now I come to line 6,

I see that I am getting exactly
the same as I had in line 5,

which means that line 7
will also be exactly the same.

Now, some of the values give you
these patterns that just becomes stable,

others are just chaotic and so there's
lots of different things going on

that can be quite interesting to look at.

Now to come to the actual code.

What I'm asking you to do is to take as input, a string,

which is a string of dots and x's,

a pattern number, which is between 0 and 255,

and you're going to have to use that
to work out where the dots and x's go.

You will be supplied
with this information here,

in other words, the numbers
that correspond with the x x dot.

which is the pattern that you look up.

And finally, a number of generations,
and that's a positive integer.

1,2,3,4 and so on.

And your output should be the generation,

or the string at that generation n.

So, for instance, if the
input string was, as we have here,

the pattern was 69

and the generation was five,

you would return '.x.x.x.x'