YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Elementary Cellular Automaton - Intro to Computer Science

Get Embed Code
2 Languages

Showing Revision 6 created 05/25/2016 by Udacity Robot.

  1. For this question I'm going to explain
    how we take an input string,
  2. which in this case is
    dot dot dot x dot dot dot dot,
  3. and we change it according to some rules.
  4. Now the rules are:
  5. look at three characters in the string
  6. and change the middle one
  7. according to the rules that we have here.
  8. Don't worry about the numbers for
    the moment, I'll come to those later.
  9. So for this particular three,
  10. we have dot dot x.
  11. Now dot dot x says change
    the middle element
  12. so that it's an x.
  13. So on the next string, the new string,
  14. that position is going to be an x.
  15. The position before it
  16. dot dot dot
  17. well dot dot dot becomes a dot
  18. in the middle.
  19. Now at the ends
  20. we want to link around
  21. so this dot here
  22. has to its left a dot
  23. and to its right a dot,
  24. so we have dot dot dot again
  25. and dot dot dot says change the middle
  26. to a dot.
  27. Now moving along,
  28. the next one we have to
    fill in is dot x dot.
  29. Dot x dot says change the middle to an x.
  30. x dot dot,
  31. change the middle to an x
  32. dot dot dot again,
  33. middle is a dot
  34. dot dot dot, middle is a dot
  35. dot dot and then
  36. the first one is the last one here
  37. so dot dot dot again is a dot.
  38. Now that completes
    one change of the string
  39. and we're going to repeat that again.
  40. So, That's the first generation.
  41. This is the second generation.
  42. Now normally when you do this, you'd
    start at the beginning of the string
  43. but just to explain it, it was easier
    to show you one in the middle.
  44. So this time we'll do it
    from the beginning of the string.
  45. So looking at the line above,
  46. we see that the first
    element in the string
  47. has a dot to its left,
  48. and a dot to its right,
    so it's dot dot dot,
  49. so that's a dot.
  50. Now we have dot dot x,
  51. and dot dot x, that's number two here,
  52. gives me an x.
  53. dot x x is an x,
  54. x x x is a dot.
  55. x x dot, is a dot.
  56. x dot dot is an x.
  57. dot dot dot, is a dot.
  58. And dot dot dot is also a dot.
  59. And we can continue like that.
  60. And so after five generations,
  61. we have the string
    dot dot dot x x dot x x.
  62. And you see we have quite
    an interesting pattern building up.
  63. Now, we can do this for lots of different
  64. choices of these dots and x's
  65. in blue, on the second line.
  66. In fact, we can do it
    in 256 different ways.
  67. And in order to decide what
  68. pattern we're going to use, what rules rather,
  69. we can give this rule a number.
  70. Now, wherever I've got an x on the bottom row,
  71. I'm going to add up those numbers,
  72. so 2 + 4 + 8 + 16,
  73. and that gives me 30.
  74. So this here uses pattern 30.
  75. Now instead of pattern 30, we could
    choose a different pattern.
  76. Let's say we choose pattern 69.
  77. Now 69, is equal to,
  78. now we have to look at these
    numbers above and
  79. work out how to make 69
  80. out of those numbers.
  81. Well, 128 doesn't go into 69,
    so we don't need any of those.
  82. 64 does so we want a 64.
  83. We don't want any 32's.
  84. We don't want any 16's, nor 8.
  85. But we do need 4,
  86. don't need 2, and we do need 1.
  87. So 64 + 4 + 1, 69.
  88. So that means, that we want 1.
  89. That means were going
    to replace dot dot dot,
  90. the middle element by an x.
  91. No 2's. We do have a 4.
  92. We don't have an eight.
  93. We don't have 16.
  94. We don't have 32.
  95. We do have 64,
  96. and we don't have 128.
  97. So, we could start off
    with the same input as before,
  98. which was, dot dot dot x dot dot dot dot.
  99. So when we have a dot at the beginning,
  100. its neighbor on the left is a dot,
  101. and its neighbor on the right is a dot,
  102. we have dot dot dot,
    and that's replaced with an x.
  103. dot dot dot again, is an x.
  104. dot dot x, is a dot.
  105. Remember, we are looking down here.
  106. dot x dot, That's number 4, is an x.
  107. x dot dot is a dot.
  108. dot dot dot is an x.
  109. and dot dot dot is an x, as well.
  110. So that's line 1.
  111. Continuing with the same thing,
    I'll fill in a few more lines,
  112. so that we can see
    what happens with the pattern.
  113. And now I come to line 6,
  114. I see that I am getting exactly
    the same as I had in line 5,
  115. which means that line 7
    will also be exactly the same.
  116. Now, some of the values give you
    these patterns that just becomes stable,
  117. others are just chaotic and so there's
    lots of different things going on
  118. that can be quite interesting to look at.
  119. Now to come to the actual code.
  120. What I'm asking you to do is to take as input, a string,
  121. which is a string of dots and x's,
  122. a pattern number, which is between 0 and 255,
  123. and you're going to have to use that
    to work out where the dots and x's go.
  124. You will be supplied
    with this information here,
  125. in other words, the numbers
    that correspond with the x x dot.
  126. which is the pattern that you look up.
  127. And finally, a number of generations,
    and that's a positive integer.
  128. 1,2,3,4 and so on.
  129. And your output should be the generation,
  130. or the string at that generation n.
  131. So, for instance, if the
    input string was, as we have here,
  132. the pattern was 69
  133. and the generation was five,
  134. you would return '.x.x.x.x'