Understanding Nested Iteration: a Key to Success in RB101

In my judgment being able understand nested iteration on a conceptual and practical level is a key to success in RB101. This is not a surprise since this complex topic presents itself in both curriculum content and practice problems. This article is written for the student who is new to programming and is overwhelmed by the palindrome_substrings problem that features nested iteration in the “Introduction to PEDAC process” Assignment from Lesson 4.

Nested iteration stretches a beginning programmer’s ability to its maximum boundaries because of the complexity needed to perform such a task. There are many things that can go wrong. Even a small error in syntax or implementation is exacerbated by the multiple moving parts and actions taking place. When an unexpected value is returned it can be very difficult to pinpoint where exactly the error has occurred. In other words, it’s easy to get lost in the code.

Understanding With an Example

Photo by Hafidh Satyanto on Unsplash

Understanding a difficult topic can be made easier through a comparison to a simple to understand real life example. This can help to solidify a mental model that can then be applied with more confidence to novel examples of the topic. Thus, when a mental model is firmly established the abstract becomes more comprehensible.

A simple example that I drafted to understand nested iteration better is the task of collecting coins from parking meters (imagine that parking meters still accept coins). Let’s examine the tasks to see how this can be applied to nested iteration.

This is a relatively simple and easy to understand process. For this example there will be an outer iteration and an inner, nested, iteration. Within the inner iteration an action will take place.

This is a helpful example because it represents each iteration as movement. The outer iteration is walking. The inner iteration is going over the coins. Mentally, this can be a useful approximation of what happens during iteration over data structures since they can be thought of as being traversed.

Modeling the example in code

Given the following array where each subarray represents a parking meter and each element in the array represents a coin type.

Array Provided

The task is to calculate the total quarters, dimes and nickels by returning a hash. The hash will have the coin type as a key and an integer count as a value. The expected output will be this:

Expected Output

Given the data structure that will be traversed as well as the expected output a higher level algorithm can be composed within the context of this example.

Coding Strategy: Outsource to helper methods

For problems of nested iteration like this there seem to be two main coding strategies:

1) To code it all in one place within a single method

Although there is a certain sense of security that comes from solving a problem within a single method this approach can be problematic with nested iteration since it is difficult to test the different parts of the method as it is being built. Additionally, if an error occurs it is difficult to pinpoint where the error occurred to troubleshoot and remedy it.

2) To outsource functionality to helper methods

Using multiple methods increases the conceptual burden to a certain extent since helper methods must be constructed independently and plugged in. However, for difficult problems with nested iteration the trade off is worth it since it allows for testing on the go as well as simpler troubleshooting. This is the strategy I have elected to demonstrate with this example. This strategy will break down a complex problem into smaller, simpler problems.

Building the main method

A framework for the main method is illustrated in the code snippet below. Within the context of this problem initializing the hash to track the coins and returning it is straightforward (lines 2 and 11 ). Likewise, the outer iteration on line 4 is fairly simple to implement. It’s the nested iteration and subsequent actions within this that are difficult to represent in code. The commented out notes will help bridge the gap between concept and code. It’s apparent that we need a method to tally the coins and that this helper method will interact with both the block parameter parking_meter and the meter_count hash. Simply put those will be the arguments supplied to the helper method.

Main Method Framework

Building the helper method

This is the substantial part of the problem. It’s a good idea to revisit the algorithm and add additional details:

Additional Details for Helper Method

Using the details from the algorithm the helper method can be drafted. In the code snippet below the parameters are parking_meter and meter_count which we’ve already determined. It’s been named tally_coins! as a descriptive name appended with ! since the meter_count hash will be mutated (the counts will be incremented). Lastly, the iteration on line 2 will consider the index of each element of the array, this is an important detail.

Helper Method Framework

Referring to the code snippet below, the next step is adding functionality to determine the type of coin and increment the corresponding hash key/value pair appropriately. Conditional logic is used with an if expression to identify the index of the current iteration. Depending on the index the appropriate value of meter_count is accessed via bracket notation and incremented.

tally_coins! Helper Method Implementation

Testing the Helper Method

A benefit of using a helper method is that this key detail in the solution can be tested independently. This is important since after a successful test one can conclude that the helper method will work as anticipated. This will give a higher level of confidence when working through a complex problem as well as eliminate an option to troubleshoot if things are to go wrong. If something has been verified to work at an acceptable level it cannot be the source of an error. The helper method in this example can be tested independently and apart from any other code. In the code snippet below an empty meter_count is successfully incremented by tally_coins! .

Independent Testing of the Helper Method

Plugging the Helper Method Into the Main Method

It’s as simple as line 5. There is a functional and tested tally_coins! helper method. This helper method performs the nested iteration and operations needed. The method is called for each outer iteration. The code snippet below shows another benefit of using helper methods: simplicity. The code below is much simpler to read and understand than a solution that doesn’t rely on helper methods.

Main Method With Helper Method

Running the Code

At this point one can anticipate the code will produce the correct output because of the benefits of independently testing the helper method. That is the point of being in control of the code: solutions are tested along the way and problems are identified and corrected.

Final Code

Putting It All Together

With nested iteration the difficulty isn’t really with the individual steps in isolation. It’s the interaction of these steps within a nested context that adds a substantial burden of difficulty. Having both a conceptual understanding and functional ability with nested iteration is a key to success in RB101 and beyond. This means having a familiar mental model as well as the capability to apply that model to solve problems in code. I encourage new programmers to experiment with their own mental models and example problems to increase their ability and confidence.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store