Exercise: Menus Inside Menus
A restaurant is putting its menu online, with sections inside sections and a tasting menu ten levels deep on the way: count every dish, find the chef's pick, and print the whole menu as an outline, with code that works at any depth. The tests check all three, ten levels down included.
Journeyman · Data Structures · Updated
Here's the ticket from the owner of the restaurant in Sections Inside Sections: Recursion on Nested Data:
We're putting our dinner menu online, and the website needs three things from it:
- How many dishes there are, for the "every dish made here" line on the home page.
- The priciest dish, for the "chef's pick" banner. If two cost the same, the one that comes first on the menu.
- The whole menu as an outline: each section's name, its dishes as
Name $pricetwo spaces in, and the sections inside it two more spaces in.It has to keep working when I add sections. I add them all the time. Today the menu is three levels deep, and next month's tasting menu is ten courses, each one served inside the last.
You've met every piece of this in the chapter. The tests use the dinner menu, a section nested three levels down, and the owner's tasting menu, ten sections deep, so code written for today's depth won't pass.
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-nested-menus, 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-nested-menus.git
Git makes a folder, exercise-ds-nested-menus, with the exercise code inside.
The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:
- the menu: a
MenuItemis a dish, with a name and a price in whole dollars; aMenuSectionhas a name, its own dishes and the sections inside it; and a sample file builds the dinner menu from the lesson. You don't need to change them; - your code: one file with three functions to finish (the repository's
README.mdnames 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 the dinner menu.
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, nothing (null, or None in Python) or an empty list 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_items(section):
"""
Count every dish on the menu: this section's own items, plus the
items in every section inside it, at every level.
the dinner menu -> 11
its Mains section (Pasta and Grill, two dishes each) -> 4
a section with nothing in it -> 0
Base case: (write it here)
"""
return 0
- Count the dishes. Finish
countItems(count_itemsin Python,CountItemsin C#): every dish in the section and in every section inside it. - Find the most expensive dish. Finish
mostExpensive. It returns the dish itself. When two dishes cost the same, keep the first one found, checking a section's own dishes before the sections inside it. A menu with no dishes at all returns nothing. - Print the menu. Finish
menuLines. It returns the menu as a list of lines: the section's name; each of its dishes asName $price, two spaces in; then each inner section's lines, two more spaces in. - Name where each one stops. On each function's Base case: line, write in a few words when that function stops calling itself.
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 NestedMenus |
| 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 11 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: Coffee and Tea both cost $3, and Coffee comes first.
<details> <summary>Stuck?</summary>
- Where to look: the ticket asks for what Sections Inside Sections: Recursion on Nested Data builds: recursion on nested data. One function per job handles one section and calls itself for each section inside, and combines what comes back.
TotalPricethere is yourcountItemswith a different sum. - The base case hides in the loop. A section with no sections inside runs its inner loop zero times, so it needs no
ifof its own. mostExpensivemight get nothing back from an inner section with no dishes. Check for that before you compare prices, and replace your best dish only when another costs strictly more, checking a section's own dishes before its inner sections.- For
menuLines, indent what comes back. Every line an inner section gives you gets two more spaces in front, and that works at every depth. (Or write a helper function with adepthparameter, likePrintSections: either works.) - The tasting-menu test fails but the others pass? Your code reaches a fixed number of levels. Look for a loop inside a loop inside a loop, and hand the inner section back to the same function instead.
</details>
When you're done
Every test is green, and the demo prints the same 22 lines in every language:
Dishes on the menu: 11
Most expensive: Grilled Salmon $19
Dinner Menu
Starters
Garlic Bread $6
Soup of the Day $7
Mains
Pasta
Spaghetti $14
Lasagna $16
Grill
Burger $13
Grilled Salmon $19
Desserts
Apple Pie $7
Ice Cream $5
Drinks
Hot Drinks
Coffee $3
Tea $3
Cold Drinks
Lemonade $4
Now try the owner's next idea: in your sample menu file, add a Specials section inside Grill, with a Steak at $24. Without changing a line of your functions, the demo should count 12 dishes, name Steak as the most expensive, and print Specials two spaces deeper than Grill.
<details> <summary>Why Should I Choose This?</summary>
Open this once your tests are green.
- One loop per level: three nested loops pass the dinner menu, and a fourth passes the three-level test. We tried it: a four-loop version passes 10 of the 11 tests and fails the tasting menu, which is ten sections deep. Every new level means new code, and the owner adds levels all the time.
- Recursion: one function per job handles one level and hands each inner section back to itself, so the tasting menu, or a menu a hundred levels deep, needs no new code. Each dish and section is looked at once, O(n), and the calls waiting at once are one per level: 10 for the tasting menu, nowhere near the call stack's limit.
- A loop with a stack of your own, from 5,000 Folders Deep: Recursion or a Loop?, works too, and it's the choice when the nesting can go thousands of levels deep. A menu never does, and for
menuLinesthe order of the lines matters, so the pile would have to be handled in reverse. Here recursion reads like the menu itself.
</details>
Where else does this shape show up?
You've written the three jobs every app does with nested data: count, find and show. Before you open the answers, think of three other places, at work or in daily life, where an app has to count, find or show something nested to a depth nobody can promise.
<details> <summary>Some answers</summary>
- A disk tool (the folder tool from this module) shows how big each folder is, and lists them as a tree.
- A comment section counts every reply, and shows each one indented under the comment it answers.
- An online shop counts the products in Clothing, including Shoes and Running Shoes, and shows the categories as a menu.
- A company's org chart finds everyone who reports to a manager, however many levels down.
- A code editor's outline shows a file's classes, the methods inside them, and the blocks inside those.
- The JSON an API sends back often has objects inside objects, and code that reads it walks it the same way.
</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.
On GitHub, click +, then New repository. Name it (for example
exercise-ds-nested-menus), choose Public, and click Create repository. Leave out the README: your folder already has one.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-nested-menus.git git add . git commit -m "My solution" git push -u origin mainPaste your repo's address, such as
https://github.com/your-name/exercise-ds-nested-menus, 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.
What Module 4 unlocks
You can now take a problem apart into smaller copies of itself, and that's the key to Module 4, Searching and Sorting. Binary search finds a song in a million by halving the list again and again, and merge sort and quicksort, two of the fastest sorts there are, sort a list by sorting its halves, recursively, and putting them together. You'll write both, and see where their O(log n) and O(n log n) come from.
So what
Folders, categories, comment threads and org charts all have this shape, and you just wrote the three jobs every app does with them: count, find, and show. The same few lines work at any depth, including levels nobody has added yet, which is exactly what the owner's ticket asked for.