CSCI 136 - Spring 2026

Data Structures

Home | Lectures | Labs | Handouts | CS@Williams

Lab 7 (In Person): The Two Towers

Your goal this week is to solve a difficult problem using Iterators. In fact, the problem is so difficult that there is no known efficient solution, so we will use "brute force" to try all possibilities, keeping track of the best we've seen so far. The idea is that we will use an Iterator to go through these possibilities.

The Two Towers Problem

Goal. Suppose that we are given n uniquely-sized cubic blocks and that each block has a distinct face area between 1 and n. If we build two towers by stacking these blocks, how close can we make their heights? The following two towers, built by stacking 15 blocks, differ in height by only 129 millionths of an inch (each unit is one-tenth of an inch):

The total height of the two towers can be computed by summing the heights of all the blocks. Since the height of each block is the square root of its face area, this is:

Rephrasing the goal. The total height of the two towers is h. This means that the smaller of the two towers has height at most h/2. This leads to an observation: we make the two towers as close as possible in height when the smaller tower is as tall as possible. Since the smaller tower has height at most h/2, we can solve the two towers problem by finding the subset of blocks with the largest total height that does not exceed h/2.

Implementation. In this lab, we will represent a set of n blocks with an ArrayList<Integer>, and we will construct an Iterator that returns each of the 2n subsets, one at a time. We will try each subset, keeping track of the best so far: in other words, we keep track of the subset whose height gets closest to h/2 without exceeding it.

How to Iterate Through Subsets

How can the iterator store a subset of the n items in our ArrayList? Here is one effective method.

We will store a single integer called subset to keep track of a subset of the n items. The ith item in the list is in the subset if and only if the ith bit of subset is 1.

For example, let's say that n is 4, and subset is 0101 in binary. This means that the current subset contains the 0th and 2nd block in the ArrayList.

Storing subsets in this way helps us iterate. We start with subset = 0, and we continue iterating until subset = 2n. (This is already implemented in the starter code.)

Of course, an int only has 32 slots. We will only use this method for n < 31 to make sure that an int has enough slots for all n blocks. (Our method will be very slow for n that large anyway.)

Let's reiterate in the context of the Two Towers lab. We want to try all possible subsets of blocks—for each subset, we'll see if it's the best smaller tower we've seen so far (in other words, the tower with height closest to h/2 without going over). We will build an iterator to iterate through all possible subsets by storing each subset as an integer. Therefore, to solve this problem we need to do two things: (1) create the iterator to go through all subsets, and (2) create a loop that uses the iterator to go through all possible subsets, keeping track of the best seen so far.

Task 1: Making the Iterator

In this task, you will complete the HeightIterator.java class. It is in two parts.

First, fill in the code for the method public boolean bitSet(int num, int slot) . The method should return true if slot slot in num contains a 1, and false otherwise. Remember that slot is 0-indexed.

Then, fill in the code for the next() method. This method should return an ArrayList<Integer> containing all elements of areas that have a 1 in the corresponding bit slot. You should build this ArrayList<Integer> using a loop, then increment subset, and finally return the ArrayList<Integer>.

Test your code using the main method in HeightIterator.java. It should print all 8 subsets of [1,2,3] (make sure there are 8 of them, and no duplicates).

Task 2: Testing All Subsets

In this task you will complete the TwoTowers.java class. Let's first look at the methods given to you in the starter code.

Fill in the method findBest(ArrayList areas, double target). It should create a HeightIterator object, and should create another variable to store the best ArrayList found so far. Then, it should iterate through all ArrayLists of blocks given by the HeightIterator. For each ArrayList, you should find the height of the subset using getHeight(). If the height is: (1) no more than target, and (2) larger than the height of the best subset seen so far, then you should update the best to be this subset.

Test your code using n = 1 and n = 2. You can do this using java TwoTowers 1 and java TwoTowers 2. If these solutions look reasonable, submit to Gradescope for further tests.

Task 3: Submit

Submit your code to Gradescope (Lab 07) and ensure it passes all autograder tests.

It's time to add, commit, and push your code files. Enter each of the following commands into your terminal one at a time. (The PDF instructions from Lab00 have more extensive instructions for how to do this.)

git add TwoTowers.java HeightIterator.java
git commit -m "finished with lab 7"
git push

After you commit, log into evolene.cs.williams.edu. Click on your repo, then Lab07, then TwoTowers.java and HeightIterator.java, and make sure that you can see the modifications you made. If you can see the changes, you're all set!