What is a good teaching example/application for jagged arrays (2d arrays with irregular row lengths)?

Question

We are teaching an AP CS class and the topic of 2d-arrays is coming up. There are plenty of cool and approachable sample applications for standard rectanglular arrays - matrix math, MIDI music, sudoku, connect-4, game-of-life, etc....

However, it's hard to think of examples for 2d-arrays with non-uniform row lengths, aka "jagged" or "ragged" arrays. Here's a simple example:

{{1,2,3},
{4,5},
{6,7,8,9}
}

The ideal example would be simple or common enough for students to have the intuition for the task, but interesting enough to see how irregular-sized rows can be useful and even natural in certain situations.

Some ideas we've already floated but am not yet convinced I love: Pascal's triangle/Plinko, graphs represented with adjacency lists.

Addendum: Many good ideas so far. One clarification - I would love examples that would NOT be better implemented as an array of lists; adjacency lists for graphs, for example, are likely better that way.

Answer 1

Hmm, here are a few ideas:

1. Calculating student GPA where the grades are all stored in an array of arrays, and the different semesters have different numbers of courses.
2. Make a lookup table of prime factors.
3. Consider an array of arrays of paths to hike, and local maximum / local minimum elevations passed along the way. Since there will be a different number of local maxima/minima along the way, the array will naturally be jagged. Figure out which hiking path involves the least climbing.
4. Same as above, but now instead store the elevation every x number of meters. Since the hiking paths are somewhat different lengths, the array will naturally be jagged. Determine which path has the lowest average slope for a hiker who has difficulty with hills.
5. (More advanced than AP, probably) Many Sudoku variants often suggest jagged arrays.

Also, for what it's worth, if you organize your midi-like events by time, it's actually ragged. Different numbers of notes are played (or stop playing) at different times. If you play a triad, you will have three events. If you play a triad at the same time as you stop playing a previous melodic note, you now have four events.

Answer 2

I would suggest the game KenKen. Although it is played on a square board, one can easily represent the constraints as a ragged array. Represent each constraint as a single line in a file. Each line contains a variable number of "tokens".

The first token contains an operation and value (e.g. +6) with the remaining tokens are a list of the cells in that constraint. The cell location could be represented as a pair of comma separated indices (e.g. 3,1) or in a spreadsheet like notation (e.g. B5). In either case the line can be split on whitespace resulting in a ragged array. However, variation in the lengths will not be very great.

I've thought about combining this with Sudoku to show inheritance. Both KenKen and Sudoku are played on a square board and share the constraints that each row/column must contain unique values from a range. They are different in how the additional constraints are defined.

Answer 3

Transportation:

Presuming that your location has some form of public transportation, there will be intersection points where multiple lines meet. Lacking public transit locally, there is still the nearest commercial airport. In many cities the bus, or rail, system has a hub, which makes a good example for a larger data-set.

At the chosen point, multiple bus lines connecting, the bus terminal, or airport, create a 'table' of the departures, grouped by route number, destination, carrier, etc.

Selecting one bus stop I frequent, there are 5 different buses which stop there. One is a short circulator, one is a long-range route with frequent service, and the others are 'normal' routes. Creating a 2-dimensional array with only those five routes gives a nicely 'ragged' array.

[
    12 [05:46,06:46,07:46,08:46,09:46,10:46,11:46,12:46,13:46,14:46,15:46,16:46,17:46,18:46,19:41],
    15 [06:26,06:56,07:21,07:41,07:56,08:16,08:31,08:56,09:19,09:59,10:39,11:19,11:59,12:39,13:19,13:54,14:22,14:42,15:02,15:27,15:47,16:07,16:27,16:47,17:07,17:27,17:46,18:01,18:21,18:36,19:01,19:25,19:55,21:05,22:15,23:25],
    18 [00:15,05:06,05:46,06:10,06:37,06:55,07:10,07:30,07:45,08:00,08:15,08:30,08:45,09:00,09:15,09:30,09:45,10:00,10:12,10:27,10:42,10:57,11:12,11:27,11:42,11:57,12:12,12:27,12:42,12:57,13:12,13:27,13:42,13:57,14:12,14:27,14:42,14:59,15:12,15:27,15:42,15:57,16:12,16:27,16:42,16:57,17:07,17:17,17:27,17:37,17:52,18:07,18:22,18:37,18:52,19:07,19:22,19:42,20:07,20:32,20:57,21:22,21:52,22:22,22:50,23:20],
    43 [04:43,05:13,05:50,06:24,06:51,07:21,07:51,08:21,08:51,09:26,10:01,10:46,11:51,12:56,13:38,14:06,14:51,15:21,15:56,16:26,16:56,17:31,18:05,18:40,19:20,20:40,22:00,23:30],
    71 [06:10,06:46,07:21,07:56,08:31,09:11,09:51,10:49,11:44,12:39,13:34,14:29,15:06,15:41,16:16,16:51,17:26,17:55,18:45,20:00,21:20]
]

Stop #3860

---

Possible sequence of learning:

1. Hypothetical transfer point with an 'even' array, each bus departs in half-hour intervals and has the same number of departures. Develop procedures to process that table.
2. Change the schedule for one route to every 20 minutes, and add an extra couple hours to another route. Now, with a ragged array, see how the procedures break, and how to fix them.
3. Create a new table, based on "live" data. See if the new procedures can handle that, and fix whatever breaks.
4. Add a third dimension by making the table cover both, or all 4, directions buses can depart in. Again, see how well the procedures handle the new dimension, fixing what breaks.
   • The bus stop I used has buses going three different directions (W[15,43], NW[12.71], S[18]) from the one bench. Across the street are two more stops, one with departures in three directions (NE[71], E[15], SE[18,43]) and the other with a single direction (S[12]). By stop there are three elements at the top level, and by direction there six elements.
5. Add another layer of complexity by adding stops to the routes, in a new table. Each route has a number of 'time points' which are usually in a printed/published schedule. The times for each bus, on each route, can become a 3-dimensional table as well.
6. Change the whole data-set by switching from bus stops to a hub, such as an airport, train depot, or truck terminal.

---

Bonus:

With the two sets of tables developed, you are now in a position to move into directed graphs. No longer do the traveling sales agents have to travel some foreign routes to unknown places with "costs" which are hypothetical. Now they can travel to known points in the city with real-world time constraints based on catching buses and making transfer connections.

Answer 4

An example which I think could be useful to you, both because it's a "ragged" array and because students are likely to see it again later if you talk about parsing text, is splitting text by line and by character:

[
  ["G", "o", "o", "d"],
  ["M", "o", "r", "n", "i", "n", "g"],
  ["E", "v", "e", "r", "y", "o", "n", "e", "!"]
]

Answer 5

This "not an answer" is just an attempt to give some perspective to the issue.

We often use arrays to keep track of information. Each entry (I'll call it a "row" here for reasons that will become obvious) holds some data we need to keep. Sometimes the entry for a row is complex, not simple. Sometimes it is just an object of some type, but sometimes it is a collection of things. We can use any sort of collection for an entry (row).

One of the sorts of entries we might consider is an array. Each row of our original array is, itself, an array (though heterogeneous situations are possible also). So, we get an array of arrays. There is nothing in general that says that each of those arrays needs to be of the same length, as the information stored in a row might vary.

But (insight coming) here each of the rows has a definite meaning in your problem, but the "columns" have little or no meaning. Less meaning in any case. The situation isn't symmetric. It may be possible, for example, to swap rows in the array without losing essential information. But it may not be possible to swap columns in the same (lossless) way, though that depends on the problem.

For example, in user Ben I.'s prime factor example, a row contains the prime factors of a given number. But a column is essentially meaningless. In fact, the use of an array, rather than some other collection is optional. It could, as well, have been a tree-set.

Matrices don't have these characteristics, of course. The columns are as meaningful as the rows.