School of Engineering and Computer Science

XMUT103
Assignment 1: Lists and Stacks

Due 16 March , 19 pm

Download zip file of necessary code and data and extract it to an Assig1 folder (eg, in a COMP103 folder in your home folder). It should contain templates for the Java programs that will be marked.

Important note about the style of your code Unlike COMP 102, simply getting code that works may not give you full marks: if your code is written with bad or difficult to read style, you can lose up to 5%. Look at the Java Style page for pointers on good style.

To submit

• DeShredder.java
• Sokoban.java (and any additional files you change or create for Sokoban)

Do not rename these files.

Part 1: DeShredder (Weight: 2/3)

Complete a program that allows a user to reconstruct a collection of images of "shreds" (small square components of a page from a document) into the original document, by first organising the shreds into horizontal strips of shreds, then ordering the strips into a complete document.

The program will start by loading the shreds from a directory. You are given three directories containing shreds of documents: shreds0 contains shreds of an image with coloured lines (the easiest to test your program), and shreds1 and shreds2 contain parts of a program. Each directory contains a sequence of candidate images 1.png, 2.png, 3.png, your program needs to load the images from the directory by adding them to a list of shreds.

After loading the shreds in, the program should display the list of shreds along the top of the window. In order to recover the original document, the user needs to find appropriate shreds and organise them into horizontal strips, then ordering these strips to recover the original document.

The user can use the mouse to drag a shred into the "working strip" (with the red border). When one strip is complete, the user can use the "Complete Strip" button to move the working strip into the list of completed strips displayed below the working strip. When there are multiple completed strips, the user can drag the completed strips around to reorder them, or move a completed strip back to the working strip row in order to modify it.

Core

1. Complete load(...) to create the list of all Shreds in a directory.
2. Complete rotateList() to rotate the list of all Shreds by one step to the left and redisplay.
3. Enable the user to move Shreds from the list of all Shreds into the working strip, move Shreds around inside the working strip, and move Shreds in the working strip back to the list of all Shreds. (Complete doMouse(...) and define additional methods.)

Completion

1. Complete shuffleList() to allow the user to shuffle the Shreds in the list.
2. Complete the completeStrip method to move the working strip to the end of the list of completed strips and initialise a new working strip.
3. Enable the user to change the order of the completed strips, and to move a completed strip back to the working strip (as long as the working strip is currently empty).
   • This will add further option inside doMouse and probably some additional methods.
4. Ensure that the program does not break (NO Exception and NO data loss) no matter where the user presses and releases the mouse. For example, if:
   • there are no Shreds in a list, or
   • the user tries to select (or move) a shred from beyond the ends of the list, or
   • the user tries to move a non-existent completed strip, or
   • the user tries to move a completed strip on top of a non-empty working strip.

Challenge

1. Extend the program to allow the user to save the reconstructed document in a single image file.
   • The loadImage(...) and saveImage(...) methods may be useful.
   • If the strips are not the same length, allow the user to "pad" the strip on the left or the right with white squares.
2. Make the program help the user by highlighting Shreds that might be neighbours of the last Shred in the working strip.
   • You need to work out what constitutes a good match. A close (but not exact) match for the pixels on the neighbouring side of two coloured lines Shreds might be good!
   • What about the text documents?

Part 2: Undo for Sokoban (Weight: 1/3)

Sokoban ("Tui xiang zi" in Chinese) is a very popular computer game and available on many platforms. The game involves controlling a worker in a warehouse who has to push boxes around the warehouse to get them onto their destination spots. The worker can only push one box at a time, and cannot pull boxes.

We have provided a simple implementation of the Sokoban game with four levels. You can control the worker with buttons or keys.

For this assignment, you need to add an undo button to Sokoban. It should use a Stack that contains the history of actions since the beginning of the current level. Every time the player performs a (successful) action, the action should be recorded on the stack. Every time the player clicks the undo button, the program should pop the top action from the history and "undo" it: if it was a move, the worker should be moved back (in the opposite direction of the recorded direction); if it was a push, the worker should be moved back, along with the box that was pushed.

Core

Implement the undo facility for Sokoban:

• Define a history field that contains a Stack of ActionRecord (the class that records information about actions).
• Write code in the methods that perform the actions to create an ActionRecord object and push it on the history stack.
• Write code in the load method to reset the history stack when the level is reset.
• Create an "Undo" button (plus optionally a key mapping from "u" to the undo method).
• Define an undo method that is called when the "Undo" button is clicked, which pops the top ActionRecord off the stack, and reverses the action.

Completion

Implement a "Redo" function. When the user presses "undo", the program should not only pop the ActionRecord that was on the history stack and reverse it, it should also put the ActionRecord onto a redo stack. If the player pressed the "redo" button, it should pop the ActionRecord off the redo stack, redo the action, and put it on the history stack again.

The player could use this to undo all the actions from the end of a game, and then replay all the moves.

Challenge

Make the worker automatically move to a free cell. When the user clicks the mouse on a free cell, if there is a free path from the worker's current position to the new cell, the program would find the path and move the worker automatically along the path.

Hint: It involves searching for a route through the empty cells of the warehouse and then making the worker step along the route. A starting point is just to find straight paths; the full version should find any free path.