Throughout this project, there will be “puzzle-y” elements. If these do not interest you, feel free to ask a TA what we mean; we’ll be very free with hints about the puzzles.

Note that the last day of office hours for the quarter is Friday, March 8. There will be no office hours the weekend of finals week, because TAs need to prepare for their finals too.

Introduction

Hello! Welcome to the last project for CS 2. This project will work a bit differently than the previous ones. This time, we are allowing you to explore the entire design space which means the following:

You can create as many Java files as you want as you’re going through the project.
You can approach the problems in any way (that doesn’t violate the collab policy) that gets you the answer (e.g., you can write programs in a different programming language if you feel like it)
The parts of this project will get progressively more difficult with the A tests being likely the hardest algorithmic problem in the course as a whole.
For any credit, you must push all code you write for every task to your repository. Even if the gitlab tests pass, if you do not have your code pushed, you may not receive any credit.

Have fun!

Working with Graphputer

graphputer is a server which uses a “graph memory model” instead of the standard “array memory model”. At all times, an instance of graphputer is “at” a single node and can traverse to other memory nodes that are adjacent to that node in the graph. Every node can store a single byte (a number between 0 and 255). To get the value of a node, you can view the “memory-mapped IO” nodes using the corresponding graphputer website.

There are two access points to graphputer.

You can traverse the memory and run commands using the provided Repl.java program. To compile and run the Repl.java program, use the commands javac Repl.java, followed by java Repl in a terminal.
You can view the output of the memory-mapped IO (aka mmio) using your browser at the website that graphputer outputs when you run Repl.

Unfortunately, graphputer is extremely finicky and will reboot (generating a new version of memory) every time you access the website (including refreshing the page). So, be careful!

Part 1: `mmio`

The “starting” node that graphputer generates is a dummy node with a random name. First, explore memory a bit using Repl.java, you’ll find that there are a series of mmio nodes which can be displayed using the frob command. All of these nodes have a value which you can view on the graphputer website.

You should begin by trying to display all of these values and determining what they mean. Try to do it by hand first by running the given Repl.java. You’ll notice very quickly that you need to write a script. To do this, you should copy Repl.java to a new file and modify it to do the traversal for you. You might find the split by tabs using \t useful if you choose to use the ls command in this part.
Once you find the node values, you may want to look at and use one of your previous projects… You should submit the message you found to gitlab in the part1.txt file.

Graphputer commands for this part

pwd: This command will tell you the name of the node you’re currently at.
ls: This command will list all of the neighbor nodes of the current node you’re at. (Note that node names are separated by \t.)
cd: This command will move you to an adjacent node.
frob: This command will toggle the display of the current node in the browser output upon refreshing the browser. (Reminder that refreshing the page causes graphputer to reboot!)
reboot: This command will “reboot” graphputer which creates a new copy of memory and resets the current node to be the initial node in the memory graph.

Note that all commands (in this part and the others) take approximately the same amount of time for graphputer to run. The only exception is that the time needed to display the result of ls is linear in the number of nodes being displayed.

Part 2: Animals and Occupations

Following Part 1, you should infer an occupation and animal based on the text you decrypted. Find the relevant node in graphputer’s memory embedded after the mmio nodes. There will be a hex number associated with that node. You should submit that hex number to gitlab in the part2.txt file for this part.

Part 3: Teleportation and Turtles

Now we move on to a full exploration of the entire graph. WARNING: This is by far the hardest algorithmic task in the entirety of CS 2. You’ve been warned.

Unfortunately for us, graphputer only lets us visit a single node at a time. This means “backtracking”, which is necessary for exploring the entirety of the memory graph, is basically impossible. However! Graphputer provides a way to make particular nodes “save points” that can be “teleported” to later. Specifically, the touch command can cycle through 256 possible “save values”. Every time you run the touch command, the current node’s save value increases by one (wrapping around to 0, as it can only store a single byte). If you have previously touched a node, you can teleport to it using teleport # where # is the “save value”. If you have multiple nodes with the same “save value”, graphputer will refuse to decide for you which node to go to and error.

Your task for this part is to explore the directed part of the graph and find something interesting to work with. The final result will be a string you can submit to gitlab in the part3.txt file.