Due: July 31, 2020
This placement exam will help us identify the right place for you to start in computer science courses at Caltech. It is to your benefit to work through this exam accurately and individually. You should be able to work through this task in a few hours. There is no time limit; however, if the exam takes you more than 10 hours, that is a good indication you should start with CS 1.
Before you begin the exam, please review the notes on the cover letter. These notes answer frequently-asked questions about the CS 1 placement exam. Also carefully review the submission notes and coding notes below.
Return the completed exam by July 31, 11:59pm PDT. Submit your answers by email to email@example.com. Please note that we do not want executables, just the source code you have written. Read the submission notes below for more on this. Note that failure to submit your placement exam correctly may result in you failing the exam.
Questions also may be addressed to firstname.lastname@example.org. Email is preferred, but you may also send questions to Maria Lopez at (626) 395-3034. DO NOT SEND QUESTIONS THAT HAVE ALREADY BEEN ANSWERED BELOW. However, you may ask for clarifications.
The placement exam consists of two problems, described below. You must write programs to answer both problems to pass the exam. Please read the instructions very carefully before you begin! On rare occasions, we have failed students because they have not read the instructions carefully and have submitted incorrect exams. We hate doing this, so if after reading the material below you still have questions for us, please send us an email and we will reply promptly. Also read the submission notes and coding notes below before you begin; failure to abide by the guidelines listed there may result in your failing the exam. That said, these are not difficult problems and writing programs to solve them should be straightforward if your knowledge of programming is equivalent to that of a student who has taken CS 1.
To help ensure that you read the instructions and coding notes, we are putting them before the problems. Please do not skip to the problems right away! If you do, you are very likely to fail the exam on a technicality. That said, the instructions and notes are not complicated and are not designed to trip you up; we simply want you to know what we expect.
As CS 1 uses the Python programming language exclusively, and CS 2 uses the Java programming language exclusively, we ask that you use either (or both) of these languages to write your code. If your submission is written in any other languages, we will politely ask you to resubmit it.
Please use a reasonably current version of the language(s) you are using. For Python, you must use Python 3, ideally the most recent version. For Java, try to use the most recent version as well.
Please submit your placement test answers as a single email attachment containing one (1) zip file. The zip file should contain the following directory structure:
CS1_placement_exam_XXX [directory; replace XXX with your name as described below] /problem1 [directory] ... files for problem 1 ... /problem2 [directory] ... files for problem 2 ... README.txt -- OPTIONAL: any notes you want us to read
The name of the zip file should be
should be replaced with your name. Please don't use spaces; use underscores to
separate your first and last names e.g. if your name is "John Smith", you would
submit a zip file called
CS1_placement_exam_John_Smith.zip. The zip file,
when expanded, should contain a single
CS1_placement_exam_XXX directory (same
XXX as described above); this directory should have two
problem2. They must have those
exact names (all lower-case except for the digit); we will be using automated
scripts to help us grade your submissions, so if they have incorrect names, the
scripts will not work. If you have extra notes on your submissions (e.g. how to
compile them) include them in the
README.txt file in the
CS1_placement_exam_XXX directory. If not, just don't include that file in
your zip file. You shouldn't need to submit any other files. The code for
problem 1 and problem 2 should be independent; if you have a file of utility
functions that is shared between both problems, please include it twice (once in
each directory). Also, please do not send executable programs in your
submission! We don't need them, since we will compile all of your code
ourselves. All of the files in your directories should be in plain text
If your submission is not in the format as described above, we will ask you to resend it in that format. If you don't, your placement exam will not be graded. We expect that you know (or can learn) how to create a zip file with the correct structure.
The files you need to submit for each program will be described in detail below.
It's not a bad idea to ask for a confirmation of receipt once you send us your placement test submission. If you haven't received a response by the beginning of September, there is a decent chance that your submission was lost, so you should probably email us asking for your test result.
The source code files you send should have the proper file extension for
whatever programming language you are writing the answers in. For instance, if
you are sending Python code files, the files should end in
.py, if you are
sending Java code files, the files should end in
.java, and so on. Files
that are not code should end in
.txt unless they have a standard name
(e.g. a Makefile should be called
It's OK to use different languages for each of the problems, though most people will probably want to use the same language.
We shouldn't have to say this, but we will: All of your code must be written by you and you alone. You are not allowed to get any kind of help from anyone else while writing the placement exam. You can consult on-line or printed documentation for the language(s) you use, but you are not allowed to ask questions about the problems either in-person or online before submitting your placement exam. If we find out that you have violated this rule, you will fail the placement exam.
It's OK to look up information about algorithms and/or data structures on the
internet; we're not testing you on your ability to memorize information.
However, if you are using any non-trivial data structures, you must write them
from scratch and not use e.g. library code from the STL or the Java class
libraries. You can use the random number generator(s) provided by your language
instead of writing your own, and you can use the fundamental built-in data
structures of your language (e.g. the
ArrayList Java classes, or
strings, dictionaries or lists in Python) as you like. If you're not sure about
a specific data structure, send us an email and ask us before spending a large
amount of time reimplementing something from the language's standard libraries.
Our standards are extremely high. Therefore, we have a lot of coding guidelines you need to follow when writing your programs. This may take a while to read, but we think that reading it is better than failing the placement exam.
Most importantly: This is not just an exam to see if you know how to program. It's an exam to test your knowledge of programming as a whole. The question we are trying to answer is "Would taking CS 1 be a waste of time for you?" If the answer is clearly "no", then you will probably not pass the placement exam even if you do know how to program at some level. Do not take it personally if you don't pass. It is not a reflection on your intelligence or on your aptitude for programming, just on your current level of knowledge. In fact, every year a number of students who do pass the test end up taking CS 1 anyway. One reason you might want to do this is if you want to be a teaching assistant for CS 1 at some later date. Another might be that you want to learn Python in a low-stress situation.
A corollory to the previous point is this: If your programs work correctly, this does not guarantee that you will pass. It's necessary but not sufficient.
Your code should be written in a professional style. Specifically:
We want you to submit code that we can actually run! That means that it should compile (if it's a compiled language) without errors, it can be run, and when run it produces meaningful output that tests the functionality of your program. Your code should only print output to a terminal; we don't want programs with graphical interfaces (GUIs). If your code does not compile correctly, or if it compiles but does not run, or if it compiles and runs but does not produce correct results, you will fail the placement exam. This applies even if you made a trivial typo in your code which made it fail to compile, so please test your code thoroughly before submitting it! If you want to submit a Makefile and/or some instructions as to how to compile and run your program, that's fine. Also, make sure to test your program with various inputs! In particular, try problem 1 with different numbers of cells in the automata; some people have failed because their code only worked when the number of cells was equal to the number of columns in their terminal. Similarly, test your code with invalid inputs to make sure it handles these correctly; if invalid inputs cause your program to crash, you will fail the exam.
Your code should not produce any warnings or errors when compiled or run with appropriate inputs. Errors will cause you to fail the test. Warnings will result in lost marks, the severity of which depends on how many warnings there are and how significant we judge them to be.
Your code should consist only of the code that you write, and should not contain e.g. files auto-generated as part of an IDE. Similarly, if your code needs to be compiled, it should be compilable without using an IDE and you should indicate how to do this.
We expect you to write comments appropriately in the body of the code. Writing good comments is an extremely important skill for programmers, and one of the most neglected (even among otherwise competent programmers). It is also something we pay a lot of attention to in CS 1. If we have to spend a lot of time figuring out how your code works, you will probably fail. If you have any tricky or confusing code, make sure you explain how it works in comments. (Better yet: don't write tricky or confusing code!) Also, we expect brief comments before every function or method explaining what it does. If your code contains no comments, you will fail the placement exam.
Neatness counts! Keep your lines no longer than 80 characters long, do not
use tabs in your code (use spaces instead), and use indentation and spacing in a
consistent and reasonable fashion. Use meaningful names for variables and
functions (except for trivial variables like loop indices, which can be
single-letter names like
j etc.). The overarching principle is: write
your code so that it is easy to read and understand. This is not optional!
If you have a lot of lines longer than 80 characters or if your code is very
messy, you will lose significant numbers of marks.
Your code should exhibit good program design and good decomposition. If you don't know anything about what constitutes good design in programming you should definitely take CS 1. We expect that you will divide your code into separate functions or methods, each of which does one logically-distinct task (so don't combine updating and printing in one function, for instance). If you write your submission as one big function, or without any functions at all, you will fail the exam. This is true even if you find that it would be easy to write the program as one big function or without using functions at all; we need to see that you know how to write functions (and methods).
Do not use global variables in your code! This is a classic sign of a novice programmer. Also, do not use "effectively global" variables e.g. static class variables in Java classes. These are the same as global variables for all intents and purposes.
When writing code in an object-oriented style (which problem 2 requires), we expect you to use the object-oriented features of the language correctly. In the past, we have often received submissions that use Java without using the object-oriented features (all static methods and static fields). This is not object-oriented programming! It's using Java as if it were an imperative language, and if you do this you will be severely penalized. That said, it is not necessary to use all object-oriented language features; for instance, you don't have to use inheritance in your submissions unless you think it will improve the quality of your answer.
Your code should check any user input (which for these programs means the command-line arguments) for errors and react appropriately. For this exam, "appropriately" means terminating the program with a meaningful error message printed to the terminal. Note that an exception traceback is not a meaningful error message even if it contains such a message; make sure that the output is nicely formatted so that the user can see what went wrong. (However, we encourage the use of exceptions inside the program; just make sure you catch them before printing the ultimate error message to the terminal. Using exceptions inappropriately is a very common cause of lost marks.) Ideally, you should print out a usage message when the inputs are incorrect to show the user how to run the program correctly. Ignoring erroneous inputs or silently substituting valid values is not appropriate; if you do this you will be penalized. Try to think of every way the user could submit bogus inputs and make sure your program can handle all of them. Also, if the user submits incorrect values, do not interactively prompt for correct values; just exit the program after printing the error message or messages.
You should use the exception handling features to signal errors that occur in the body of the code. Failing to do so will result in lost marks. (Exception handling is covered in CS 1, so you are expected to know it.) Do not use catch-all exception handlers when you can use more specific exception handlers.
Finally: don't go completely overboard with these problems. In the past, we have occasionally gotten submissions where the student appeared to be trying to show off everything they knew about the language they were using, making the solution far more complicated than it needed to be. The complexity of the solution should be proportional to the complexity of the problem. If your solution is excessively complex (even if it works properly) we may deduct marks.
For your convenience, here is a quick summary of items that will cause you to automatically fail the placement exam. You might think we are being insanely anal about all of this, and you would be right! You are entering Caltech, and Caltech has very high standards. If you're ready to place out of CS 1, none of these should cause you any problems.
Sending your submissions in the wrong format twice.
Extremely bad (e.g. unreadable) code formatting.
Code that does not compile, or does not run correctly, or runs but doesn't produce the correct output.
Violating the requirements of the individual problems (see below).
Not including any meaningful comments in your code.
Using global variables or effectively global variables.
Very bad program design. This includes (but is not limited to) putting all of your code inside one function, or not having any functions at all.
Not using command-line arguments correctly (e.g. prompting the user for input instead of getting input from the command line).
Not outputting reasonable error messages when given incorrect inputs, or otherwise handling incorrect inputs incorrectly (see above).
In the event that you fail the placement test, we will send you our comments by email explaining how your submission fell short of our standards. However, do not argue with us to try to raise your grade! Unless we have made some gross error (e.g. mistaken your submission for a different one), our decision will stand. Any other attempt to argue with us to change the result will be ignored.
Also, in the event that you fail the test, please don't ask us for a do-over, or ask us if there is any other course you could take (or out-of-course work you could do) instead of taking CS 1. If we feel that you would benefit from taking CS 1, you should take it. Of course, if you don't intend to be a CS major and none of the courses you intend to take require CS 1 as a prerequisite, do whatever you like. But if you do need CS 1 credit, you can only get it by taking CS 1 or placing out of it.
We realize that it isn't pleasant to fail any test, but this is not something you are going to be graded on and it will never appear on your permanent record. We are also not interested in hearing how many programming courses you have taken and gotten As on, how many programming competitions you have won, etc. All of these are fine things to put on your resume, but they are irrelevant to the placement exam. If we failed you, there is some fundamental problem or problems with your programming (at least in the small sample that we've seen), and you will have to take CS 1 to fix these problems. (Usually the problem is not that you're a bad programmer but that you don't know something that CS 1 teaches.) Remember: Caltech is one of the top universities in the entire world, and our standards are extremely high. Most people who fail the placement test have no problem breezing through CS 1 anyway, so we don't feel you will be severely inconvenienced. In many cases, students who failed the CS 1 placement exam aced CS 1 itself and became top-notch CS 1 TAs, making lots of money in the process and getting great recommendation letters from us as a result. So don't worry about it!
Finally, please realize that the CS 1 placement exam is for incoming freshmen only. If you are e.g. a rising sophomore and forgot to take the placement test before coming to Caltech, you can't take it later.
If you are writing your code in Python, submit a single file called
If you are writing your code in Java, submit a single file called
In either case, the file must be in the
problem1 directory in your zip
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:
1110000011010011110011110110011001011111101011010111000000010010111001 0001000100011100001100000001100111000000001000010000100000111110000111 0011101110100010010010000010011000100000011100111001110001000001001000 0100000000110111111111000111100101110000100011000110001011100011111100 1110000001000000000000101000011100001001110100101001011000010100000010 0001000011100000000001101100100010011110000111101111000100110110000111 0011100100010000000010000011110111100001001000000000101111000001001000 0100011110111000000111000100000000010011111100000001100000100011111100 1110100000000100001000101110000000111100000010000010010001110100000010 0000110000001110011101100001000001000010000111000111111010000110000111 0001001000010001100000010011100011100111001000101000000011001001001000 0011111100111010010000111100010100011000111101101100000100111111111100 0100000011000011111001000010110110100101000000000010001111000000000010 1110000100100100000111100110000000111101100000000111010000100000000111 0001001111111110001000011001000001000000010000001000011001110000001000 0011110000000001011100100111100011100000111000011100100110001000011100 0100001000000011000011111000010100010001000100100011111001011100100010 1110011100000100100100000100110110111011101111110100000111000011110111 0001100010001111111110001111000000000000000000000110001000100100000000 0010010111010000000001010000100000000000000000001001011101111110000000 0111110000011000000011011001110000000000000000011111000000000001000000 1000001000100100000100000110001000000000000000100000100000000011100000 1100011101111110001110001001011100000000000001110001110000000100010000 0010100000000001010001011111000010000000000010001010001000001110111000 0110110000000011011011000000100111000000000111011011011100010000000100 1000001000000100000000100001111000100000001000000000000010111000001110 1100011100001110000001110010000101110000011100000000000110000100010001 0010100010010001000010001111001100001000100010000000001001001110111011 0110110111111011100111010000110010011101110111000000011111110000000000 1000000000000000011000011001001111100000000000100000100000001000000000 1100000000000000100100100111110000010000000001110001110000011100000000
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 28 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 24 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,
Linux, or the console application 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. It's not hard in any of the languages we recommend. 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):
$ python3 automaton.py 70 30 0 1 0 0 1110000011010011110011110110011001011111101011010111000000010010111001 0001000100011100001100000001100111000000001000010000100000111110000111 0011101110100010010010000010011000100000011100111001110001000001001000 0100000000110111111111000111100101110000100011000110001011100011111100 1110000001000000000000101000011100001001110100101001011000010100000010 0001000011100000000001101100100010011110000111101111000100110110000111 0011100100010000000010000011110111100001001000000000101111000001001000 0100011110111000000111000100000000010011111100000001100000100011111100 1110100000000100001000101110000000111100000010000010010001110100000010 0000110000001110011101100001000001000010000111000111111010000110000111 0001001000010001100000010011100011100111001000101000000011001001001000 0011111100111010010000111100010100011000111101101100000100111111111100 0100000011000011111001000010110110100101000000000010001111000000000010 1110000100100100000111100110000000111101100000000111010000100000000111 0001001111111110001000011001000001000000010000001000011001110000001000 0011110000000001011100100111100011100000111000011100100110001000011100 0100001000000011000011111000010100010001000100100011111001011100100010 1110011100000100100100000100110110111011101111110100000111000011110111 0001100010001111111110001111000000000000000000000110001000100100000000 0010010111010000000001010000100000000000000000001001011101111110000000 0111110000011000000011011001110000000000000000011111000000000001000000 1000001000100100000100000110001000000000000000100000100000000011100000 1100011101111110001110001001011100000000000001110001110000000100010000 0010100000000001010001011111000010000000000010001010001000001110111000 0110110000000011011011000000100111000000000111011011011100010000000100 1000001000000100000000100001111000100000001000000000000010111000001110 1100011100001110000001110010000101110000011100000000000110000100010001 0010100010010001000010001111001100001000100010000000001001001110111011 0110110111111011100111010000110010011101110111000000011111110000000000 1000000000000000011000011001001111100000000000100000100000001000000000 1100000000000000100100100111110000010000000001110001110000011100000000
(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 severely 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.
If you are writing your code in Python, submit two files called
stack.py (which has the stack implementation) and
hanoi.py (which has
If you are writing your code in Java, submit two files called
(which has the stack implementation) and
Hanoi.java (which has everything
In either case, the file must be in the
problem2 directory in your zip
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.
First, handle the base case i.e. the case that can be solved immediately. Here, the base case is when there is only one disk to move (M = 1). In that case, you just move the disk (assuming that it's legal to move it).
If M > 1, the process is as follows:
Note that steps 1 and 3 involve recursive calls to this algorithm. We call this the recursive case.
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:
$ python3 hanoi.py [n1 n2 ...]
(assuming you're using Python; for Java, it would be
java Hanoi [n1 n2
$ 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:
$ python3 hanoi.py 4 3 2 1
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:
$ python3 hanoi.py 10 4 2
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:
$ python3 hanoi.py 4 10 2
or like this:
$ python3 hanoi.py 4 10 4
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:
display, which prints the current state of the problem (which disks are on
which pegs). Make sure to print out a blank line after printing the state of
the problem. This will ensure that when the entire solution is printed, it's
easy to see what each move did. Failing to do this will result in lost marks.
solve, which solves the problem.
solve should take no arguments.
move, which moves one disk from one peg to another. Check that you aren't
doing an illegal operation (e.g. putting a disk on top of a smaller disk, or
duplicating a disk). If an illegal operation is detected, the program should
exit after printing a meaningful error message.
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
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):
A: 4 1 B: 8 7 6 5 C: 3 2
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:
A: 8 7 6 5 4 3 2 1 B: C:
and the final printout would be:
A: B: 8 7 6 5 4 3 2 1 C:
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.
$ python3 hanoi.py 10 4 2 A: 10 4 2 B: C: A: 10 4 B: 2 C: A: 10 B: 2 C: 4 A: 10 B: C: 4 2 A: B: 10 C: 4 2 A: 2 B: 10 C: 4 A: 2 B: 10 4 C: A: B: 10 4 2 C: $ python3 hanoi.py 4 10 2 A: 4 10 2 B: C: A: 4 10 B: 2 C: A: 4 B: 2 C: 10 A: 4 B: C: 10 2 A: B: 4 C: 10 2 A: 2 B: 4 C: 10 <error message>
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:
As mentioned previously, the tower of Hanoi solver should solve the problem using the recursive algorithm exactly as given above. There are alternative (recursive and non-recursive) ways of solving the problem, but we don't want you to use them, even if you think they're better.
Any invalid command-line arguments (e.g. non-integers) should be caught by your program, which should print a meaningful error message and quit. (A stack traceback is not acceptable.) A program invocation with no command-line arguments should do the same.
Your program should represent the pegs in the problem as stacks (one stack per
peg). Therefore, you will have to define a stack data structure as a
class along with appropriate methods and use them in your tower of Hanoi solving
code. (This should be defined in a separate file called
stack.py (Python) or
stack.java (Java).) Not defining a
Stack class will result in your
failing the placement test.
Stack methods will include methods to push to
the stack, pop from the stack, check if the stack is empty, and examine the
value at the top of the stack (if any). The rest of the program should only
interact with the stacks by calling their methods; the program should never
access the internals of the stack data structure directly even if it can. This
is called creating an "abstraction layer" and it's critical to designing good
software. We will test the stack implementation independently of the rest of
the program to make sure it does what it should.
Stack class should be a generic stack class i.e. one that could
be used in any program that requires stack functionality (not just the tower
of Hanoi program). If you want to add extra functionality specific to the tower
of Hanoi problem, you can do this, but you should subclass the
Stack class so
Stack is still a generic stack class. If you don't know what a stack is
in the context of programming data structures, you should probably do a little
Methods in the
Stack class that can fail (e.g. popping from an empty stack)
should signal such failure appropriately. We will leave it to you to figure out
what an appropriate way of dealing with failure is, but ignoring it is not an
NOTE: You are not allowed to use an existing
Stack class in the
language you are using to write the problem (for instance, the Java
class) should such a class exist; also, don't subclass such a class if it
exists. You need to write the class from scratch using only basic data
structures. If you are in doubt about what constitutes a "basic data structure"
in your language, email us. For Java, using an
ArrayList is definitely OK.
If you think it's useful, you can add additional classes, but don't add extra
files. Put extra classes in the
If you are using Java, do not use static methods in your submission except for
main(). If you are using Python, do not use functions (non-methods) except
for one function that creates an instance of the
Hanoi class and runs the
simulation. If you are using another object-oriented language, we expect a
similar design. Once again, we are trying to see if you know how to program in
an object-oriented style.
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.
[End CS 1 placement exam.]