On this page:
7.1 Warmup:   Filtering on Array  Lists
7.1.1 Abstraction and Naming
7.1.2 Mutation
7.2 Warmup:   working with for-each and counted-for loops
7.3 Combining Array  Lists
7.3.1 Interweaving
7.4 Nested Array  Lists, and practice with indices
7.4.1 Multiplication tables
7.4.2 Magic squares
7.5 The 15 Puzzle using impworld
8.12

Lab 7: Working with ArrayLists and Mutable worlds🔗

Goals: The goals of this lab is to get practice with designing methods on array lists, and working with a mutable version of the big-bang library.

Related files:
  tester.jar  

In every problem in this lab, whenever you create a loop, leave a comment above it explaining the purpose-statement for that loop.

7.1 Warmup: Filtering on ArrayLists🔗

We talked about this as a between-lectures exercise, but if you have not written this code out explicitly, do so. If you have, move on to the second section of the lab.

Define a utilities class, and in it define a method with the signature
<T> ArrayList<T> filter(ArrayList<T> arr, Predicate<T> pred)
with Java’s built-in definition of the Predicate<T> interface. This method should produce a new ArrayList<T> containing all the items of the given list that pass the predicate. Be sure not to mutate the input list.

7.1.1 Abstraction and Naming🔗

Next, define filterNot, which has the same signature as filter, but keeps all of the elements filter does not.

As you can see, there is a lot of overlap between filter and filterNot. Abstract these two methods by defining a new method with the header:

<T> ArrayList<T> customFilter(ArrayList<T> arr, Predicate<T> pred, boolean keepPassing)

filter and filterNot are now essentially convenience methods that call customFilter. To anyone using the util class, their intent is clear just based on the names of filter and filterNot. As the designer of the util class, you only have to write one complex method. Whenever you want to create a method whose behavior can be configured by one or two simple boolean flags, it is a good idea to name each of these options and have one abstracted method do the heavy lifting.

7.1.2 Mutation🔗

Now, define a method with the signature
<T> void removeFailing(ArrayList<T> arr, Predicate<T> pred)
that modifies the given list to remove everything that fails the predicate. Note: A simple for-each loop here will fail. Why?

You should attempt to solve this puzzle in two different ways, using both kinds of loops we discussed in class. Both of them have drawbacks. In a comment, explain why the simplest solution doesn’t work, and why both of your proposed solutions do.

Be sure to test this carefully.

Next, define removePassing and customRemove, analgous to filterNot and customFilter above.

7.2 Warmup: working with for-each and counted-for loops🔗

Design and implement methods for foldl and foldr on ArrayLists. Which kind of loop do you need to use to implement each one? Why?

7.3 Combining ArrayLists🔗
7.3.1 Interweaving🔗

Define a method with the following signature:
<T> ArrayList<T> interweave(ArrayList<T> arr1, ArrayList<T> arr2)

The method should interweave the two lists in order, so the first element of the output list comes from arr1, the second from arr2, the third from arr1, etc. If one list runs out before the other, the output list should finish with just elements from the longer list.

Next, define a method with the following signature:
<T> ArrayList<T> interweave(ArrayList<T> arr1, ArrayList<T> arr2, int getFrom1, int getFrom2)

This should work similarly to interweave, but instead of getting an element from arr1, then arr2, then arr1, etc., this should get (up to) getFrom1 elements from arr1, then (up to) getFrom2 elements from arr2, then (up to) getFrom1 elements from arr1, etc. For instance, given two lists ["A", "B", "C", "D", "E", "F"] and ["w", "x", "y", "z"], if we took three elements at a time from the first list, and two elements at a time from the second, we should produce ["A", "B", "C", "w", "x", "D", "E", "F", "y", "z"]. Similarly to the basic interweave, if one list runs out before the other, the list should finish with just elements from the longer list.

Then, redefine the first version of interweave as a call to this more general (and more complex) one.

7.4 Nested ArrayLists, and practice with indices🔗

Just as we could have ILists containing ILists, so too we can have nested ArrayLists. In the problems below, you’ll need to use counted-for loops, and probably some accumulator variables, to keep track of indices or other positional information.

7.4.1 Multiplication tables🔗

Design a method timesTable that takes in two numbers, r and c, and produces a multiplication table with r rows and c columns, counting from 1. So for example, timesTable(3, 4) ought to produce everything from 1 * 1 = 1 up to 3 * 4 = 12. Your result should be an ArrayList<ArrayList<Integer>>, such that answer.get(i).get(j) should equal i * j.

7.4.2 Magic squares🔗

A magic square is a square grid of numbers, such that every row, column and the two diagonals all add up to the same number. For example, the 3-by-3 magic square is

8  1  6

3  5  7

4  9  2

There’s a simple pattern to generate a magic square whose size is odd: first, start in the center of the top row and fill in a 1. Next, move “up and right”, by one row and one column, wrapping around from top to bottom and right to left as needed, and fill in numbers as you go. (In our example, the 2 is in the bottom right corner, and the 3 is in the middle left.) If the next square you’re trying to fill is already filled in, then drop down one row but don’t move over one column. (In our example, the 4 therefore goes beneath the 3.) Keep following this pattern until the square is full.

Design a method ArrayList<ArrayList<Integer>> magicSquare(int size) that can create a magic square of any odd size.

7.5 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.

The impworld library uses methods that return void, and you must use side effects to change the current world to update it between ticks and on key events...but you still need to figure out how to test it!

The 15 puzzle consists of four rows of four tiles, with one tile missing. Each tile has a number, and tiles can move into the hole if they are adjacent to it. Represent this information as follows:

// Represents an individual tile class Tile {
// The number on the tile. Use 0 to represent the hole int value;
...
// Draws this tile onto the background at the specified logical coordinates WorldImage drawAt(int col, int row, WorldImage 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 hole // extra: handle "u" to undo moves ...
}
}

To construct the tiles, you’ll need to construct 4 rows of 4 tiles each. Which loop structure (for-each or counted-for) do you think will be most appropriate here? (Hint: you’ll need two loops, one nested inside the other.)

Implement swapping two tiles by their indices — how will this have to change from the swap method we did in class?

This is similar to the perennial argument over whether scrolling "up" on a laptop trackpad should scroll the content up or scroll the viewport up. Everyone is convinced their preferred approach is correct...

To handle moving the tiles, you’ll need to determine whether a given move direction is currently possible: for example, if the hole is in the top-left corner, then you cannot move the hole any further up or left. It is up to you to interpret a keystroke of e.g. "left" as either “move the hole 1 cell left” or “move the tile to the right of the hole left to fill the hole”, 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);
}
}
Obviously, you’ll need to write tests, too!

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 — you just have to figure out how to undo it!

Reminder: read the The Image Library for documentation on how the image library works.