Home

Conway’s Game of Life implemented in SmallBasic

2009/09/16

At work we have a new junior system administrator. Given the fact that he is junior and lacks even programming experience, I gave him the following assignment:

– Implement Conway’s Game of Life. Pick the programming language of your choice, the user interface of your choice, read anything you believe is relevant, ask anyone (including me) for advice, make the assumptions that suit you (and document them). Just someday come back with a demo.

Life’s rules are simple:

  • Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
  • Any live cell with more than three live neighbours dies, as if by overcrowding.
  • Any live cell with two or three live neighbours lives on to the next generation.
  • Any dead cell with exactly three live neighbours becomes a live cell.

His language of choice is PHP (as I said he lacks programming experience and PHP is the only language he has ever written anything meaningful in). Given that a system administrator must be proficient at least in sh, awk, Perl and some Python (and VBScript or Windows PowerShell if working in a Windows environment) I expect a change of choice soon. He will see the light of C later.

Upon hearing about the assignment a colleague made an unfortunate humorous attempt to challenge me: If I am to put an assignment to the junior administrator, why don’t I implement it too? Due to the law of unintended consequences, this was an unfortunate remark that was done in front of the junior administrator (more on why this was a bad choice of timing later).

Given the situation I decided to write a simple implementation. To make it interesting, I decided that I would use a language that I had never used before, and I flipped a coin, the choices being Processing and Microsoft’s Small Basic (which is different from this Small Basic). 1:30 hours later I knew enough Small Basic to begin. And this ugliness is what I came up with:

GraphicsWindow.Title = "Conway's Game of Life"
GraphicsWindow.Top = 0
GraphicsWindow.Left = 0
GraphicsWindow.BackgroundColor = "SteelBlue"
GraphicsWindow.BrushColor = "White"
GraphicsWindow.Height = 250
GraphicsWindow.Width = 250
GraphicsWindow.CanResize = "True"

maxI = 20
maxJ = 20
size = 10

one = "one"
started = "False"

For i = 1 To maxI
  For j = 1 To maxJ
    x = (i - 1) * size
    y = (j - 1) * size
    GraphicsWindow.FillRectangle(x, y, size, size)
    cell[one][i][j] = "White"
  EndFor
EndFor

GraphicsWindow.MouseDown = OnMouseDown

Sub OnMouseDown
  If (started = "True") then
    Program.End()
  EndIf


  x = GraphicsWindow.MouseX
  y = GraphicsWindow.MouseY
  
  ix = Math.Ceiling(x / size)
  iy = Math.Ceiling(y / size)
  
  If (ix > maxI) Then
    Goto start
  EndIf

  If (iy > maxJ) Then
    Goto start
  EndIf

  If (cell[one][ix][iy] = "White") Then
    cell[one][ix][iy] = "Black"
    GraphicsWindow.BrushColor = "Black"
  Else
    cell[one][ix][iy] = "White"
    GraphicsWindow.BrushColor = "White"
  EndIf
  
  GraphicsWindow.FillRectangle((ix - 1) * size, (iy - 1) * size, size, size)
  Goto skip
  
  start:
  started = "True"
  StartLife()
  
  skip:
EndSub

Sub StartLife
  label:
  If (one = "one") Then
    one = "two"
    now = "one"
    next = "two"
  Else
    one = "one"
    now = "two"
    next = "one"
  EndIf
  
  For i = 1 To maxI
    For j = 1 To maxJ
      live = 0    
      
      x0 = i - 1
      x1 = i + 1
      y0 = j - 1
      y1 = j + 1
      
      cell[next][i][j] = "White"
    
      If (x0 = 0) Then
        x0 = maxI
      EndIf
      
      If (x1 > maxI) Then
        x1 = 1
      EndIf
      
      If (y0 = 0) Then
        y0 = maxJ
      EndIf
      
      If (y1 > maxJ) Then
        y1 = 1
      EndIf
      
      If (cell[now][i][y0] = "Black") Then
        live = live + 1
      EndIf
      
      If (cell[now][x1][y0] = "Black") Then
        live = live + 1
      EndIf
      
      If (cell[now][x1][j] = "Black") Then
        live = live + 1
      EndIf
      
      If (cell[now][x1][y1] = "Black") Then
        live = live + 1
      EndIf
      
      If (cell[now][i][y1] = "Black") Then
        live = live + 1
      EndIf
      
      If (cell[now][x0][y1] = "Black") Then
        live = live + 1
      EndIf
      
      If (cell[now][x0][j] = "Black") Then
        live = live + 1
      EndIf
      
      If (cell[now][x0][y0] = "Black") Then
        live = live + 1
      EndIf
      
      If (cell[now][i][j] = "Black") Then
        If (live = 2) Then
          cell[next][i][j] = "Black"
        EndIf
        
        If (live = 3) Then
          cell[next][i][j] = "Black"
        EndIf
      Else
        If (live = 3) Then
          cell[next][i][j] = "Black"
        EndIf
      EndIf
        
      If (cell[now][i][j] = cell[next][i][j]) Then
      Else
        GraphicsWindow.BrushColor = cell[next][i][j]
        GraphicsWindow.FillRectangle((i - 1) * size, (j - 1) * size, size, size)
      EndIf
        
    EndFor
  EndFor
  Goto label
EndSub

[ Update: The above program is available from the Small Basic website: CVS703 ]

It had been years since I had programmed with global only variables. The program is very simple (and slow). You can specify your patterns (for example a glider) in the white tableau where the game takes place. Next you click anywhere in the empty area and the game begins. The next click ends the game.

As is documented in the Wikipedia page the program considers “the left and right edges of the field to be stitched together, and the top and bottom edges also, yielding a toroidal array. The result is that active areas that move across a field edge reappear at the opposite edge. Inaccuracy can still result if the pattern grows too large, but at least there are no pathological edge effects.”

Why Life as an assignment?

I have before me a junior system administrator who is an eager young mind. He has to learn how to program. He does not need to do that by implementing a Fibonacci or a n! function. Life is far more interesting and enjoyable, it has a lot of documentation available, and opens the door to stuff like cellular automata. From his reaction, questions and effort I see that it was a good choice for a first assignment.

How does one become a system administrator?

The process is no different than how one became an engineer in the 19th century and up to the end of WWII:

  • One became an engineer after a long (and most of the times underpaid) apprenticeship next to an engineer. By increasing experience, one would get to the point to be recognized as one.
  • Or, he could pay (expensive) fees and be trained and certified in specific engineering equipment by the makers of the equipment.
  • Finally one could go to the University and study to become an engineer.

Does this sound familiar? And yes there exist Universities (~6) that offer System Administration courses.

So why was the timing bad and the comment inappropriate?

A master-apprentice relationship is based on trust. No one is allowed to violate that trust with the exception of the student alone. In fact the very moment this happens the apprentice has “graduated”. By making a comment along the lines of “how can you place assignments on others that you cannot complete?” even jokingly, you contaminate the relationship. Doing that is irresponsible, especially when one is not willing to undertake the task of becoming the (new) master.

So now the master is placed in the unfortunate position to prove his ability. Well yes I did that. It cost me about 3 hours which I consider totally lost. I could have done other things and this choice was ripped off of me. Even worse, the apprentice’s efforts with regards to the exercise are damaged: He now has in front of him code which is supposed to be correct. And even unconsciously he will follow the above design. This is not what I wanted. I wouldn’t mind him looking other people’s code, even copy pasting some, just as long as it is not mine. We are not supposed to replicate our way of thinking, we are supposed to show people how to think! And for this assignment, this is lost.

Why a programming only exercise?

Would it have been better if I had asked him to implement a distributed system that passes around messages? How many things can one read at the same time to complete a task? How to program in a language, how to implement an algorithm in that language, read about the network stack, the socket interface and the operating system? Gradually there will be such assignments.

For now, I feel I should have not flipped the coin and should have tried Processing instead.

[ Update: I did implement it in Processing the very next day ]

Advertisements

8 Responses to “Conway’s Game of Life implemented in SmallBasic”

  1. kangelos Says:

    My favorite test/exercise that I give to juniors is a depth first directory traversal using recursive functions ! Then I switch it to width first.

  2. agou Says:

    If I had a new job, and got an (irrelevant to the job) “assignment” from my supervisor, I would probably be insulted.

  3. adamo Says:

    @kangelos:
    Thank you for his next assignment :)

    @agou:
    Relevance is judged by the supervisor, not the apprentice. Those who feel insulted can always quit.

    However, since in my book a system administrator must be able to write programs (not 10 line shell scripts), I need to verify that. Life is a simple algorithm and does not require operating system knowledge. Operating Systems internals and Network stacks will follow.

    Would it have been more productive to send him off doing end user support?

  4. Georg Says:

    OMG! A new Sith pair is slowly breeding… (“Rule of Two” etc.)


  5. I, too, think that Processing would have been a good choice, but I’m curious what made you consider a BASIC dialect in the first place?

  6. mperedim Says:

    I think everyone missed the important question:

    Would it have been better if I had asked him to implement a distributed system that passes around messages? … Gradually there will be such assignments.

    R u hiring? :)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: