Lab 10: Iterators and Imperative Worlds
Goals: We’re going to practice with Iterators and Iterable and implement the 15 Puzzle
using the Impworld library —
Submission: Submit your solutions to zipStrict, zipLists and concat. You may submit your solution to cycle for extra credit. To earn the extra credit, cycle must be correct and well-tested. You may define these methods in a class named IteratorUtils. Your solutions are due at the end of your lab period and will be submitted individually.
10.1
Iterators
Given the pair class:
class Pair<L, R> { L left; R right; Pair(L left, R right) { this.left = left; this.right = right; } }
<X, Y> Iterator<Pair<X,Y>> zipStrict(ArrayList<X> arr1, ArrayList<Y> arr2)
The method should return an Iterator of pairs of corresponding elements. If the lists are of different sizes, an exception should be thrown.
<X, Y> Iterator<Pair<X,Y>> zipLists(ArrayList<X> arr1, ArrayList<Y> arr2)
The method should return an Iterator of pairs of corresponding elements. If the lists are of different sizes, only return pairs up to the size of the shorter one.
Combining Iterators
<T> Iterator<T> concat(Iterator<T> iter1, Iterator<T> iter2)
The method should produce a new Iterator that concatenates the two Iterators (similar to append on lists). Note that this method should terminate even if iter1 or iter2 is an infinitely large Iterator.
Iterating Forever
<T> Iterator<T> cycle(Iterable<T> iterable)
The method should produce an iterator that cycles through the elements of iterable forever. For example, if the iterable were the list 1,2,3, then the iterator produced should be the iterator of 1,2,3,1,2,3,1,2,3,1,2,3.... Note that this method should terminate even if iterable’s iterator is infinite.
Hint: Look carefully at the signature above, and recall our discussion in class about what to do to “start over from the beginning”...
Warning: The iterator produced won’t always have a new element to return. When wouldn’t it? What (pretty tiny) test case could you write to trigger this behavior?
The 15 Puzzle using impworld
The funworld library used methods (like onTick or onKeyEvent) that returned new World objects, which made testing easier: you could compare the old World to the new one.
You could also return objects that were instances of different subclasses of World, as you might have done on Assignment 5: World programs, to represent different “phases” of your gameplay. That’s not quite so easy to do with impworld...
The 15 puzzle consists of four rows of four tiles, with a space where one tile is missing. Each tile has a number, and tiles can move into the space if they are adjacent to it. You can play the game here.
Represent the information needed for this world program as follows:
// Represents an individual tile class Tile { // The number on the tile. Use 0 to represent the space int value; ... // Draws this tile onto the background at the specified logical coordinates WorldScene drawAt(int col, int row, WorldScene background) { ... } } class FifteenGame extends World { // represents the rows of tiles ArrayList<ArrayList<Tile>> tiles; ... // draws the game public WorldScene makeScene() { ... } // handles keystrokes public void onKeyEvent(String k) { // needs to handle up, down, left, right to move the space // extra: handle "u" to undo moves ... } }
To construct the tiles, you’ll need to construct 4 rows of 4 tiles each in a random order with a space in one of the positions. Which loop structure (for-each or counted-for) do you think will be most appropriate here? (Hint: you’ll likely need two loops, one nested inside the other.)
Implement swapping two tiles by their indices —
To handle moving the tiles, you’ll need to determine whether a given move direction is currently possible: for example, if the space is in the top-left corner, then you cannot move the space any further up or left. It is up to you to interpret a keystroke of e.g. "left" as either “move the space 1 cell left” or “move the tile to the right of the space left to fill the space, and similarly for the other keys. You may find that one interpretation is more intuitive than the other, but it is a rather subjective choice. Be sure to document in you code which interpretation you chose!
To start the game, create a Run configuration as usual, set the main class to tester.Main, and set the arguments to ExampleFifteenGame. Then create the ExampleFifteenGame class with at least this method:
class ExampleFifteenGame { void testGame(Tester t) { FifteenGame g = new FifteenGame(); g.bigBang(120, 120); } }
To handle undoing moves: create another field in the FifteenGame class
that is an ArrayList<String>, which you’ll update on each keystroke by
adding the key that was just pressed to the front of the list. When the "u"
key is pressed, the most recent move (if any) will then be stored at the front
of the list —
Reminder: read the The Image Library for documentation on how the image library works.