CS 1 Placement Exam, Academic Year 2023-2024

In either case, the file(s) must submitted be in the Problem 1 Assignment on CodePost.

In this problem, you are to write a program that simulates the operation of a one-dimensional cellular automaton. Many of you are familiar with Conway’s "game of life", which is a two-dimensional cellular automaton; a one-dimensional cellular automaton is much simpler, and for this problem your program will simulate a particularly simple one-dimensional cellular automaton. If you like, you can read background material on one-dimensional cellular automata on the internet before attempting this problem; here is a good link, and here is another. You will be implementing a particularly simple kind of one-dimensional cellular automaton called an "elementary cellular automaton", with some additional restrictions described below. Note: do not write a game-of-life simulation for this problem, or you will fail the placement exam! Also, do not call your program "GameOfLife" or something similar, or you will lose marks. One-dimensional cellular automata are not the same as two-dimensional ones, although they are related.

A one-dimensional cellular automaton consists of a one-dimensional array which stores numerical values. For this problem, the numerical values will be either 0 (off) or 1 (on). The contents of the array are initially randomly assigned to be either 0s or 1s (roughly 50% of each; it doesn’t have to be exactly 50%, but it does have to be random). Each location in the array is referred to as a "cell" of the array. The contents of the array are altered to give the next generation, which depends on the previous generation and on an update rule. The update rule will compute the new value of each cell depending on the previous value of the cell, as well as the previous values of its left and right neighbors. So the new value of cell 22 (for instance) will depend on the previous values of cells 21, 22, and 23. There are many possible ways of writing an update rule, and we’ll get back to this shortly.

After the program generates its initial array, it will print it to the terminal as a line of 0s and 1s (with no spaces or newlines between the digits). So the initial line might look like this (for an array of 70 cells):

NOTE: This is the format we want for the output (each generation on one line, with no spaces between cell values).

After this, your program will generate the next generation, print it as above, generate the next generation after that, print it, and so on until some given number of generations have been printed. For instance, if 30 generations would be printed (in addition to the original generation, making 31 generations in all), the output might look something like this:

Note that there is a pattern to the 0s and 1s (try squinting your eyes if you find it difficult to see). Some update rules give interesting patterns, and others don’t. Your program will be able to simulate a variety of update rules.

In general, there are 256 different possible update rules you could use (since there are 8 possible previous states for a given cell and its immediate neighbors (0 0 0, 0 0 1, 0 1 0, 0 1 1, 1 0 0, 1 0 1, 1 1 0, and 1 1 1) , and each state could give rise to either a 0 or a 1 in the next generation, giving 2⁸ or 256 different update rules). We will simplify this somewhat as follows: the update rule will sum the states of a cell and its immediate neighbors, and choose a particular next state based on the sum. The possible sums are 0, 1, 2, and 3, representing the case of all 0s, one 1, two 1s, and three 1s. An update rule is specified by giving a next state for each possible sum. For instance, an update rule might be [0, 1, 1, 0], which says that if the sum is 0 or 3, the next state is a 0; otherwise the next state is a 1. It’s not hard to see that using sums for update rules will give rise to 2⁴ or 16 different update rules.

You may have noticed that there is a problem with updating the cells on either end of the array, because these cells are missing one neighbor. The way to deal with that is to assume that the missing neighbor has a value of 0. So, to update the first cell in the array (which we’ll call cell 0), you will need the previous values of cell 0 and cell 1, which you add to give the sum. Similarly, if there are 70 cells in the array, updating the rightmost cell (which we’ll call cell 69, using 0-based indexing) will require the previous values of cell 68 and cell 69, which are again added to give the sum.

One very important aspect of simulating a one-dimensional cellular automaton is that you should not overwrite the contents of the previous generation while computing the next generation. Put differently, you will need two arrays while doing the update: the array of the previous values, and the array of the next values. You will go through the previous values and compute the next values (one for each cell), filling up the next value array without altering the previous value array. After you have finished computing the next values, you no longer need the previous values and you can dispose of that array (or, if you prefer, you can copy the next values into the previous value array). If this is not done, your simulation will not work properly and you won’t pass the exam.

Now let’s talk about the interface of your program. Your program must be runnable from a terminal (e.g. the Terminal application in Mac OS X, xterm or konsole or gnome-terminal in Linux, or the console application or Windows Terminal in Windows), and it will take six command-line arguments (not counting the name of the program). These represent:

If you don’t know what a command-line argument is or how to read command-line inputs in your computer language, you should learn about this before solving this problem. Asking the user to interactively enter inputs is not acceptable, so make sure to get this right. Otherwise, your program will be considered to be broken.

So, a sample run of the program might look like this (in a Linux or Mac OS X terminal; the $ is the terminal prompt which you don’t type):

(Here, we are assuming that your program is in Python, but Java is acceptable too.)

Notice that there are 70 digits per line (70 cells in a generation), and 31 lines (the initial generation + 30 subsequent generations). The 0 1 0 0 numbers are the update rule for this run of the program; they say that if the sum for a particular cell is 1, the value of the cell in the next generation will be 1; if the sum is 0, 2, or 3 the next value of the cell will be 0. You can check that this is in fact the case.

The output format should be exactly as shown above, except that if you have a different number of generations or a different number of cells in a generation, the display will be respectively deeper/wider. We will penalize you if you put spaces between the 0s and the 1s, put blank lines between the lines of numbers, have all the numbers on a single line, etc. (This exam is partly an exam to see if you can read a specification and complete it exactly as instructed.)

Note that you will need to use a random number generator to generate the initial generation. You can use a library function for your chosen language; you certainly shouldn’t write your own random number generator, unless you have a lot of free time!

Please make sure that all of your code is inside of functions and/or methods, even if it would be easy to have some of the code outside of functions and methods (which is the case in Python). This even includes the code that handles command-line arguments. For Python we allow this exception: you can have a single line that calls a function at the end of the program.

One final thing: if your program receives incorrect inputs (too few command-line arguments, or incorrect ones i.e. non-numbers, negative numbers or numbers other than 0 or 1 in the update rule), it should print a meaningful error message and quit. It should not continue to execute, fail silently, crash, or interactively prompt the user for correct inputs. You should allow any integer number of cells >= 1, and any number of generations >= 0. If there are 0 generations, just print out the first (random) generation.

In either case, the file must be in the problem2 directory in your zip file.

This problem is a classic computer science problem called "the tower of Hanoi" which illustrates how recursion coupled with a divide-and-conquer strategy can enable you to trivially solve a problem which appears to be very difficult. Note that there are several different ways to solve this problem; we want you to do this recursively because the whole point of this problem is to see if you are comfortable using recursion. (Non-recursive solutions will fail the placement exam, so don’t submit one.)

The set-up for the problem is as follows. You have three pegs, on which there are some disks of different sizes. All the disks start on the first peg. The disks on the first peg should be set up so that all the disks have different sizes and larger disks are always underneath smaller disks. No disk is smaller than size 1. The other two pegs start off empty. Your job is to move all the disks to the second peg so that they end up in the same order as they were on the first disk (with the smaller disks on top of the larger ones). You can only move one disk at a time, and a disk can only be moved to an empty peg or to a peg whose top disk is larger than the disk being moved. Disks do not have to be placed on pegs in consecutive order i.e. it’s OK to have disk 5 on top of disk 10 (but not on top of disk 4).

The algorithm to solve this problem goes like this. We’ll call our pegs peg A, peg B, and peg C. Assume you want to move the top M disks (where M <= N) from peg A to peg B.

Both of these cases should be handled in the same method. Also, use this exact algorithm (not some variant of it). In particular, don’t use a non-recursive variant of the algorithm (yes, they exist!).

Amazingly enough, that’s all there is to it. Recursive algorithms may seem like magic, but they can be understood by analogy with mathematical induction. With mathematical induction, you want to prove that something is true for all numbers N > 1. To do this, you prove that it’s true for N = 0, and then you show that if it’s known to be true for N-1, it can be proven to be true for N. Given that, you can show that it’s true for any N > 0. Here, we see that we can move 1 disk (N = 1). If we know that we can move N-1 disks, then it’s clear that we can move N disks (that’s the recursive case).

Another useful thing to do is to take a small example (for instance, with disks of sizes 3, 2, and 1 on peg 1) and work through the above algorithm on pencil and paper until you convince yourself that it does work.

Your program will be called as follows:

(assuming you’re using Python; for Java, it would be java Hanoi n1 n2 ....)

where $ is the terminal prompt and n1 n2 ... are the sizes of the disks that start on the first peg (these are command-line arguments). If no numbers are supplied, the script should print out a helpful usage message and exit. For instance, if you are calling the program with 4 disks: 4 3 2 1, it will look like this:

What this means is that the first peg will start off with four disks of sizes 4, 3, 2, and 1, with the largest (4) on the bottom, then 3, then 2 and 1 on the top.

Alternatively, if you are calling the program with 3 disks: 10 4 2, you will invoke the program like this:

You can see that the disk sizes do not have to be consecutive integers. In this case, the first peg will start off with a disk of size 10 at the bottom, then a disk of size 4, and then a disk of size 2 at the top.

All disk sizes must be positive integers; anything else should give rise to an error message and a usage message describing how to call the program correctly. However, you can give inputs like this:

or like this:

These are not invalid invocations of the program (so they don’t give rise to a usage message), but the algorithm will not work on them, so eventually the program will fail. When it does, it should print out a meaningful error message and exit. We will use inputs like these to test how your program handles errors.

Your program should define a class called Hanoi which encapsulates all the state variables of the problem. Not defining a Hanoi class will result in your failing the placement exam. Instances of the Hanoi class should have an explicit representation of which disks are on which pegs at any given time.

Here are the methods your program should contain:

Note that it’s not enough to just have methods with these names. They must work exactly as described above, or you will fail the test.

You may (in fact, you almost certainly will) want to define other methods as well, which is OK. For instance, you may want to define a helper method called by solve that takes some arguments.

In addition, you should print out the state of the problem (using your display function or method) before you start and after each move. The display should look exactly like this (for 8 disks numbered 1 through 8):

where A:, B:, C: identify the pegs and the numbers identify the disks. The "bottom" of the pegs are to the left and the "top" of the pegs are to the right. Make sure that printouts for successive moves are separated by at least one blank line. The final printout should show all the disks on peg B, so if there were 8 disks from 8 down to 1 initially, the first printout would be:

and the final printout would be:

As mentioned above, successive states of the game should be separated by a blank line when printed out. The spaces between the numbers are not optional! Your program should work for arbitrary numbers of disks and the output needs to be readable in all cases, except that for very large numbers of disks on a peg it’s OK if the line wraps on the terminal. Put differently, each peg’s printout should be on a single line.

Note that you need to supply the <error message>, which arises because the algorithm wants to put the 10 disk on top of the 4 disk, which is invalid. (The algorithm given above assumes that disks start out in descending order on one disk; if they don’t, it won’t work correctly.)

This problem is intended to test your knowledge of object-oriented programming, your ability to define and use data structures, your ability to handle error situations, and your ability to write recursive code. Therefore, in addition to just solving the problem, we want your solution to have the following features:

We realize that such a simple program can probably be solved more simply than by doing it the way we recommend, but we are trying to see how much you know about object-oriented programming, designing data structures and recursion, so please do it our way.