Exercise: The Word Counter

A year of the gym's member comments, 300,000 words, and a report that has to finish in under 2 seconds: count every word, list the ten members use most, and find the words used only once. The tests check it on a short story and on a full year.

Apprentice · Data Structures · Updated

By

Here's the ticket from the gym's manager:

Members leave a comment in our app after each visit ("the pool was cold again", "loved the new spin bikes"). A year of comments comes to about 300,000 words, about 30,000 of them different. I want three things from them:

  1. How many times each word was used.
  2. The ten words members use most, most used first. Words used the same number of times go from A to Z, so the list is the same every time we run it.
  3. Every word used only once, from A to Z. That's where the one-off complaints and the typos hide.

Our first version kept a list of the words with their counts, and searched that list for every word it read. On a year of comments it ran for between 10 seconds and over 2 minutes, depending on the language, and the app froze while it did. The whole report, all three parts, has to take under 2 seconds.

Writers use the same report to catch a word they lean on too hard, search engines count words to decide what a page is about, and spam filters count them to spot the words spammers use. The tests run yours on a short story about the gym, and then on a full year of comments.

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-word-counter, 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-word-counter.git

Git makes a folder, exercise-ds-word-counter, with the exercise code inside.

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

  • 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 counts the words of a short story about the gym.

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

What to do

splitWords (SplitWords in C#, split_words in Python) is already written: it turns a text into its words, in lowercase, so "The" and "the" count as one word. The other three functions return an empty answer for now. Here is the first one in Python, as the starter has it (the other languages say the same in their own syntax):

def count_words(words):
    """
    How many times each word appears: a dict from each different word to
    its count. Walk the words once.

    count_words(["the", "gym", "the"]) -> {"the": 2, "gym": 1}
    count_words([]) -> {}

    Growth rate: (write it here)
    """
    return {}
  1. Count the words. Finish countWords (CountWords in C#, count_words in Python): each different word with how many times it appears. Walk the words once.
  2. List the most common. Finish mostCommon (most_common): the howMany most common words, most common first. Words with the same count go from A to Z. Asked for more words than there are, it gives them all.
  3. Find the words used once. Finish usedOnce (used_once): every word whose count is 1, from A to Z.
  4. Name the growth rates. On each function's Growth rate: line, write its Big-O and a few words on why. For mostCommon and usedOnce, call the number of different words k.

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 WordCount
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 9 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: maya, pool and track all appear twice, so they come from A to Z. The last test is the full year: 300,000 words, 30,000 of them different, in under 2 seconds.

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

  • countWords is the frequency count from When a Loop Inside a Loop Is Too Slow: Hash Tables at Work: keep a dictionary from each word to its count. For each word, read its count, or 0 if there's none yet, and add 1. The safe read is GetValueOrDefault (C#), getOrDefault (Java), get(word, 0) (Python) or get(word) ?? 0 (JavaScript and TypeScript).
  • The year of comments is too slow? Look for a search inside the loop: a list of words you look through, or a call that counts one word through all the comments. Each word's count has to be found in one step.
  • mostCommon sorts the different words, not the comments. Sort by count, biggest first; when two counts are equal, by the word. Python can sort by both at once with key=lambda word: (-counts[word], word). The other languages take a compare function that checks the counts first and the words second.
  • Keep the first howMany, or all of them if there are fewer: GetRange with Math.Min (C#), subList with Math.min (Java), a slice [:how_many] (Python), slice(0, howMany) (JavaScript and TypeScript).
  • usedOnce is a filter, then a sort. Go through the counts, keep the words whose count is 1, and sort what you kept.
  • Stuck on a growth rate? countWords touches each of the n words once. The other two work on the k different words, and sorting k things is O(k log k), as in Sorting a Million Songs, and the Playlist You Can't Compute: O(n log n) and O(2ⁿ).

</details>

When you're done

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

Words: 98
Different words: 50
Ten most common: the 13, morning 5, and 4, maya 4, on 4, priya 4, was 4, gym 3, swam 3, closed 2
Used only once: 28 words, starting a, at, before, bench, but

Four words tie at 4, and they come out from A to Z. Now think about the full year: 300,000 words and 30,000 different ones. Counting is one pass, 300,000 steps. But to pick the top ten, your mostCommon sorts all 30,000 words, just to keep ten of them. Is there a way to find the top ten without putting the other 29,990 in order?

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

The year of comments is 300,000 words, 30,000 of them different. Here's what each way of counting them cost when it was measured on the test.

  • A list of words with their counts, searched for every word (the manager's first version): each word read means looking through the words found so far, about 15,000 of them once the list fills up. That's O(n × k), over 4 billion comparisons: 10 seconds in C#, 15 in Java, 25 to 27 in JavaScript and TypeScript, and 139 in Python.
  • Taking each different word and counting it through all the comments: the same loop inside a loop, turned around, and just as slow.
  • Sorting the words first, then counting each run of equal words: O(n log n), about 5.5 million steps. Fast enough here, but more code, and it sorts all 300,000 words when only 30,000 different ones matter.
  • A dictionary from word to count: finding a word's count is O(1) on average, so counting is one pass, O(n), and only the 30,000 different words are sorted, O(k log k). The whole report: 0.03 seconds in Python, 0.05 in C#, 0.06 in JavaScript and TypeScript, and 0.08 in Java.

What it costs is memory, one entry per different word, and order: a dictionary keeps none you can count on, which is why mostCommon and usedOnce still sort.

</details>

Where else does this shape show up?

This chapter's three shapes were "count each thing in one pass", "have I seen this before?" and "write the answer down once". Before you open the answers, think of one place for each, in an app you use or at work, where a program does exactly that.

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

  • Counting in one pass: an election's vote count per candidate; a shop's "best sellers this week"; the error log's "which error happened most?"; the likes on each post.
  • Have I seen this before? A sign-up form's "that email already has an account"; a payment system that never charges the same order twice; a web crawler that skips pages it has already visited; a music app that doesn't shuffle the same song twice in a row.
  • Write the answer down once: a browser that keeps pictures it has already downloaded; a weather app that shows the last forecast for a few minutes before asking again; a currency converter that remembers today's rate.

</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-word-counter), 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-word-counter.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-word-counter, 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 6 unlocks

There is a faster way to the top ten, and it's a tree. Module 6, Trees and Heaps, starts with the trees all around you (folders, org charts, the page you're reading) and builds up to two you'll use for exactly this kind of job: a heap, which keeps the most important item on top, so the top ten come out without sorting everything, and a trie, which stores words letter by letter, the way a phone suggests the next word as you type.

So what

You've counted a year of comments in one pass, the job a hash table does best, and proved it with a stopwatch. Counting, top-ten lists and "used only once" are everyday tasks in reports, search and data work, and you now have all three in your language.

Key terms

Related