Elementary Cellular Automaton – Intro to Computer Science

Elementary Cellular Automaton – Intro to Computer Science

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’

7 thoughts on “Elementary Cellular Automaton – Intro to Computer Science”

  1. I have (O=dots H=X)
    Did I mess up and tell me where and why, if I did

  2. Does it matter if the rule 1 .x. in your pattern equals one or does it have to be like …equals x or dot? Basically does it matter what the top symbols are and the symbol it equals?

Leave a Reply

Your email address will not be published. Required fields are marked *