Exercise: The Nesting Dolls

A toy shop's product page needs three numbers from each set of nesting dolls: how many dolls, the color of the smallest, and how much shelf they take side by side. Work each one out without a loop, name where each one stops, and let the tests check your answers.

Apprentice · Data Structures · Updated

By

Here's the ticket from Little Wooden Things, a toy shop that sells nesting dolls online:

Each doll set in our catalog is stored the way it's packed: the outside doll, holding the next doll, and so on down to a solid one that doesn't open. Our product page needs three things worked out from it:

  1. How many dolls are in the set. Sets come in 3, 5, 7 and 10 pieces, and the workshop makes a 50-piece set for the holidays.
  2. The color of the smallest doll, the solid one at the very middle, for the "find the tiny one" label.
  3. The total height of the dolls standing side by side, from a list of their heights in cm, so customers know how much shelf they need. Don't change the list: the page shows it afterward.

One rule from our lead developer: no loops in these three. This is practice for our folder tool, where loops run out, so each function works on the outside doll, or the first height, and hands the rest back to itself.

It's a warm-up, on purpose: three small jobs on a straight line of dolls, so the two parts of every function like this are easy to see. The tests check all three, a 50-doll set and a 100-number list included, and you name where each function stops.

Before you start

You need one language set up, as in Setup: VS Code and Your Language. The exercise is written in all five of the course's languages; pick the one you use.

Get the exercise code

Open this lesson's GitHub repository, github.com/ask-codey/exercise-ds-nesting-dolls, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

git clone https://github.com/ask-codey/exercise-ds-nesting-dolls.git

Git makes a folder, exercise-ds-nesting-dolls, with the exercise code inside.

The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:

  • the Doll class: each doll has a color and the doll inside it, or nothing inside (null, or None in Python) when it's the solid one. You don't need to change it;
  • your code: one file with three functions to finish (the repository's README.md names the file for each language);
  • the tests that check your functions. You don't need to change them;
  • a demo program that tries your functions on a set of five dolls: Red, Orange, Yellow, Green and Blue.

In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.

What to do

Every function is already there, with its parameters, and returns 0 or an empty string for now. The comment above each one says what it should return, with examples, and ends with a Base case: line. Here is the first one in Python, as the starter has it (the other languages say the same in their own syntax):

def count_dolls(doll):
    """
    Count the dolls in a set, starting from the outside doll. A solid
    doll (its inside is None) is 1 doll; any other doll is 1 doll, plus
    the dolls inside it.

    Red > Orange > Yellow > Green > Blue -> 5
    a solid Blue doll on its own -> 1

    Base case: (write it here)
    """
    return 0
  1. Count the dolls. Finish countDolls (count_dolls in Python, CountDolls in C#): how many dolls are in a set, starting from the outside doll.
  2. Find the smallest doll. Finish smallestDoll. It returns the color of the solid doll at the very middle of the set.
  3. Add up a list. Finish sumList. It returns the total of a list of numbers: the first number, plus the total of the rest of the list. An empty list adds up to 0, and the list itself must be left as it was.
  4. Name where each one stops. On each function's Base case: line, write in a few words when that function stops calling itself, and what it returns then.

Check your work

Each language has its own command, run in the terminal in your language's folder (Terminal > New Terminal in VS Code). The repository's README.md has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (npm install).

Language Run the tests Run the demo
C# dotnet test dotnet run --project NestingDolls
Java ./mvnw test (.\mvnw test in PowerShell) java src/main/java/Demo.java
Python python -m pytest python demo.py
JavaScript npm test node demo.js
TypeScript npm test node demo.ts

At first all 8 tests fail. That's expected: each function you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: Red, Orange, Yellow, Green and Blue make 5 dolls.

<details> <summary>Stuck?</summary>

  • Where to look: the ticket asks for what How Big Is This Folder? Recursion calls recursion: each function handles the outside doll (or the first number) and calls itself on the rest. Its CountDolls is your first function.
  • Write the base case first. Ask: what's the smallest version of this problem, the one I can answer without calling the function again? For the dolls it's the solid doll; for the list it's an empty list.
  • Then trust the call. In the recursive case, assume the function already works on the smaller piece (the doll inside, or the rest of the list) and use what it gives back, as 1 + CountDolls(doll.Inside) does.
  • smallestDoll doesn't add anything on the way back. It passes the answer from the solid doll straight back out.
  • The rest of a list is a new, shorter list: numbers.GetRange(1, numbers.Count - 1) in C#, numbers.subList(1, numbers.size()) in Java, numbers[1:] in Python, and numbers.slice(1) in JavaScript and TypeScript. None of them changes the list itself.
  • A stack overflow (a RecursionError in Python, a RangeError in JavaScript and TypeScript) means a base case is missing or never reached: The Folder Tool That Never Stopped: Base Cases has the two rules to check.

</details>

When you're done

Every test is green, and the demo prints the same four lines in every language:

Dolls in the set: 5
The smallest doll: Blue
Heights in cm: 14, 11, 8, 5, 2
Total height in cm: 40

Now trace one of your functions on paper, the way Where Do the Waiting Calls Wait? The Call Stack did: how many frames are on the call stack when sumList reaches its base case for the five heights? (Counting the demo's own frame, there are seven: the demo, then one call for each of the five lists from five numbers down to one, and one more for the empty list.)

Then write countDolls again with a while loop, in a scratch file. Which version reads better to you, and which keeps fewer calls waiting?

<details> <summary>Why Should I Choose This?</summary>

Open this once your tests are green.

  • For these three jobs, a loop would do just as well. The dolls are a straight line: each one holds at most one doll, and a list is a line too. A while loop walks a line in the same O(n) time and keeps no calls waiting, so for a straight line in real code it's usually the better choice. 5,000 Folders Deep: Recursion or a Loop? says so in the next chapter.
  • So why practice on dolls? Because they make the two parts easy to see: one base case, one recursive case, one call at a time. On the 50-doll set your function keeps 50 calls waiting, which the call stack handles easily.
  • Where recursion is the right choice: the folder tool. A folder can hold several folders, each holding more, to any depth, and no fixed set of loops reaches every level. The same two questions you just answered (what's the smallest version, and how do I hand back a smaller piece?) are all it takes.

</details>

Where else does this shape show up?

You've worked with "a thing that holds a smaller thing of the same kind". Before you open the answers, think of three other places, at work or in daily life, where something holds smaller copies of its own shape, possibly many levels deep.

<details> <summary>Some answers</summary>

  • Folders on your computer, the folder tool's job: folders inside folders, as deep as anyone made them.
  • A comment thread where people reply to replies.
  • A shop's categories: Clothing holds Shoes, which holds Running Shoes.
  • A company's org chart: a manager's team holds managers with teams of their own.
  • The JSON an API sends back, with objects inside objects.
  • Boxes packed inside boxes for shipping.

</details>

Submit your exercise

The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.

  1. On GitHub, click +, then New repository. Name it (for example exercise-ds-nesting-dolls), choose Public, and click Create repository. Leave out the README: your folder already has one.

  2. In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:

    git remote set-url origin https://github.com/your-name/exercise-ds-nesting-dolls.git
    git add .
    git commit -m "My solution"
    git push -u origin main
    
  3. Paste your repo's address, such as https://github.com/your-name/exercise-ds-nesting-dolls, into Submit your exercise on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.

Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.

So what

Three different jobs, and each came down to the same two questions: what's the smallest version I can answer at once, and how do I hand a smaller piece back to myself? Ask those two questions about any recursive problem, and you're most of the way to the code, including the folder tool, which is next.

Key terms

Related