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.

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 Introducing counted-for loops🔗

(Note: today’s lab is a little bit ahead of where we got to in lecture this week, so you’ll need to read ahead a bit right now to do the next parts of the lab. The TAs will introduce the topic as well, and we’ll go over it more in class next week.)

Suppose we wanted to design build-list, which takes in an integer of items to create, and a function for how to create them, and produces a list of the results. Suppose we want to construct an ArrayList of these results. Could we do so using only the for-each loops we saw in class?

Define a utilities class, and in it design a method buildList that uses a accumulator helper method buildListAccum to count how many remaining items are needed to be created. Read Lecture 22: ArrayLists, at the end of section 22.5, to see a new kind of loop, called a counted-for loop, that makes this counting process less tedious. Then read Lecture 23: For-each loops and Counted-for loops, section 23.1 on trying to design buildList using a counted-for loop.

The counted-for loop allows you to produce the same exact results as the accumulator based helper method does, and that helper deserved a purpose statement...therefore so too does the loop. For now, every time you design a loop, you should have a brief purpose statement above it as a comment that explains what the intended purpose or side-effect of the loop should be.

7.2 Warmup: Filtering on ArrayLists🔗

7.2.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:

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.2.2 Mutation🔗

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.3 Folding over lists🔗

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.4 Combining ArrayLists🔗

7.4.1 Interweaving🔗

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.

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.5 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.5.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.5.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.6 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:

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?

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:

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.