Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Computer Recreations

Computer Recreations

When teaching programming, it's difficult to come up with examples and exercises that are both not too complicated yet still interesting. This talk will revisit a historical source of interesting programming ideas: the 1980s Computer Recreations column in "Scientific American".

Andrew Kuchling

February 20, 2016
Tweet

More Decks by Andrew Kuchling

Other Decks in Education

Transcript

  1. Computer Recreations OR, REDISCOVERING THE 1980S FOR PROGRAMMING FUN Andrew

    Kuchling amk @ amk.ca speakerdeck.com/akuchling/computer-recreations
  2. #1: Cellular automata 4 5 4 1 0 4 3

    5 1 (N = 6) If a cell is in state n, And has a neighbour in state n+1, Then the cell changes to state n+1
  3. #1: Cellular automata 4 5 4 1 0 4 3

    5 1 5 0 5 1 1 4 4 0 1
  4. @classmethod def __init__(self, width=WIDTH, height=HEIGHT): self.board = {} self.width =

    width self.height = height for i in range(width): for j in range(height): board.board[(i,j)] = random.randrange( 0, NUM_STATES)
  5. def step(self): ”Do one iteration step of the cellular automaton"

    new = self.board.copy() for i in range(self.width): for j in range(self.height): new[(i,j)] = self.cell_rule(i, j) self.board.update(new)
  6. def cell_rule_4_cell_neighbourhood(self, x, y): "Evaluate the rule for a single

    cell…” value = self.board[x,y] successor = (value + 1) % NUM_STATES for (i, j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]: neighb = self.board.get((x+i, y+j)) if neighb == successor: return successor else: return value
  7. 1 B 1 C 0 C 0 B 1 A

    0 A 1 B 0 A 1 A 1 C 0 B 0 C
  8. 1 B 1 C 0 C 0 B 1 A

    0 A 1 B 0 A 1 A 1 C 0 B 0 C
  9. 1 B 1 C 0 C 0 B 1 A

    0 A 1 B 0 A 1 A 1 C 0 B 0 C 1 B 1 A 1 A 1 C 0 A 0 A
  10. Generation 0 Best score in pool: 75% Environment = 00100110100010011010

    Prediction = 01000100100110010010 Worst score in pool: 20% Environment = 00100110100010011010 Prediction = 11101101011101110101
  11. Generation 100 Best score in pool: 90% Environment = 00100110100010011010

    Prediction = 00100100100010010010 Worst score in pool: 45% Environment = 00100110100010011010 Prediction = 10001100011110110110
  12. Generation 1500 Best score in pool: 95% Environment = 00100110100010011010

    Prediction = 00100110100110011010 Worst score in pool: 50% Environment = 00100110100010011010 Prediction = 00001000110000100011
  13. Perfect score found! In 5248 generations Environment = 00100110100010011010 Prediction

    = 00100110100010011010 0 1 A D,0 B,0 B A,0 C,0 C A,1 A,1 D E,1 B,1 E F,0 E,0 F D,1 B,1
  14. " = −1 or " = −1 (+) (+) =

    (+) (+) (-) = (-) (+) = (-) (-) (-) = (-) #3: Iterated functions
  15. >>> c = 0.5 + 2j ; c (0.5+2j) >>>

    c2 = complex(1,3) ; c2 (1+3j) >>> c2.real, c2.imag (1.0, 3.0) >>> abs(c2) 3.1622776601683795
  16. , = ,-. " + Now, repeat: 0 = 0

    Pick a complex number
  17. , = ,-. " + 0 = 0 = 0.1

    n Zn 1 0.1 2 0.11 3 0.1121 4 0.11256641 5 0.112671196660288 6 0.112694798556861 7 0.112700117621771 55
  18. , = ,-. " + 0 = 0 = -1.5

    + 0.5j n Zn 1 -1.5 + 0.5j 2 0.5 - 1j 3 -2.25 - 0.5j 4 3.3125 + 2.75j 5 1.9101+ 18.71875j 6 -348.24 + 72.01j 7 116085 -50154j
  19. , = ,-. " + 0 = 0 = 0.1

    + 0.4j n Zn 1 0.1 + 0.4j 2 -0.05 + 0.48j 3 0.1279 + 0.352j 4 0.00754559 + 0.3099584j 5 0.0039827261978 + 0.3953223619930j 6 0.0562639077838 + 0.4031489214554j 7 -0.059363425551 + 0.3546345325201j
  20. def iterate(c, max_iterations=100): "Iterates z**2 + c, for up to

    max_iterations” z = 0j for i in range(max_iterations): z = z**2 + c if abs(z) > 2.0: return (i+1) else: return 0
  21. def compute_grid(self, im_width, im_height): cx, cy = self.get_center() x_inc, y_inc

    = (self.width / (im_width / 2), …) grid = np.zeros((im_width, im_height)) for i in range(im_width): for j in range(im_height): coord = complex((cx - self.width) + i * x_inc, (cy - self.height) + j * y_inc) count = iterate(coord) grid[i,j] = count return grid
  22. # Vectorized code from Jean-Francois Puget def compute_grid_vectorized(self,im_width,im_height,maxiter=100): # …

    set up np.linspace() for x and y … c = np.array([complex(x,y) for x in rx for y in ry]) c = c.reshape((im_width,im_height)) grid = np.zeros(c.shape) z = np.zeros(c.shape, np.complex64) for it in range(maxiter): notdone = np.less(z.real*z.real + z.imag*z.imag, 4.0) grid[notdone] = it z[notdone] = z[notdone]**2 + c[notdone] return grid