Capstone: a word index

The back of a book lists every word and the pages it appears on. Build the same for lines of text and you have used most of this course at once: patterns to find the words, a table of tables to hold them, pairs and ipairs to walk it, table.sort to make the output stable, and pcall to survive input that is not what you were promised.

Nothing below is a new feature. It is the wiring. The examples index a different thing, ingredients by recipe number, so you can see the shape without seeing the answer.

One table, two shapes

The index is a dictionary whose keys are names and whose values are arrays of numbers: the two table roles you already know, nested.

local pantry = {}
pantry["salt"] = {1, 3}
pantry["rice"] = {2}
print("salt: " .. table.concat(pantry["salt"], " "))

--> salt: 1 3

table.concat takes numbers as happily as strings, so the lists need no conversion on the way out.

The fiddly step is appending to a list that may not exist yet: the create-on-first-use move from Tables as Dictionaries, one level deeper.

local used = pantry[item]
if used == nil then
    used = {}
    pantry[item] = used
end
used[#used + 1] = recipe

used is a reference to the table now sitting in the pantry, so appending to used appends to the pantry. There is nothing to write back.

Finding the words

%a+ matches a run of letters, which throws away digits and punctuation for free, and :lower() folds case so Salt and salt land on one entry.

local found = {}
for token in ("Salt, rice; SALT!"):lower():gmatch("%a+") do
    found[#found + 1] = token
end
print(table.concat(found, "|"))

--> salt|rice|salt

That output also shows the problem you have to solve: salt occurs twice in the same recipe, and an index that appends blindly reports salt: 1 1. Because recipes arrive in order, the last number already recorded is the only one worth comparing against.

if used[#used] ~= recipe then
    used[#used + 1] = recipe
end

Ascending order then comes free: the numbers went in ascending, so the inner lists never need sorting. The outer table does.

Making the output stable

pairs promises no order at all, so the keys get collected into an array, sorted, and walked with ipairs.

local shelf = {oil = {2}, beans = {1, 3}, flour = {3}}
local names = {}
for key in pairs(shelf) do names[#names + 1] = key end
table.sort(names)
for _, key in ipairs(names) do
    print(key .. " -> " .. table.concat(shelf[key], ","))
end

--> beans -> 1,3
--> flour -> 3
--> oil -> 2

Skip the sort and every line is still individually correct; only their order is a coin flip, which is exactly what a byte-exact test cannot tolerate.

Failing on purpose

A program that reads a count should check that it got one. Raise where you detect the problem, handle it once at the top:

local function read_limit(header)
    local limit = tonumber(header)
    if limit == nil or limit > 9 then
        error("limit out of range", 0)
    end
    return limit
end

print(pcall(read_limit, "3"))
print(pcall(read_limit, "x"))

--> true	3
--> false	limit out of range

The 0 is not decoration. Drop it and the message arrives as script.lua:4: limit out of range, carrying a line number that depends on where you happened to put the call.

Common mistakes

• Printing straight out of pairs. Every line is correct, the order is a coin flip, and a one-word test case hides it completely.
• Recording the same line twice. A word repeated on one line gives the: 1 1 unless you compare against the last number already stored.
• Splitting on %S+ instead of %a+. cat, and cat become two different words, comma and all.
• Forgetting :lower(). The and the get separate entries, which is right for a case-sensitive search and wrong here.
• Dropping the 0 from error. The message picks up a script.lua:N: prefix and the comparison fails on a line number you do not control.

Your exercise

Word Index reads a count and that many lines, then prints one line per distinct word: the word, a colon and a space, then the line numbers it appeared on.

Everything you need is above; the part that is easy to skip is the header. When the first line is not a number, or is below 1, the program prints exactly error: bad line count and nothing else. The starter's build function does the reading and a pcall below it does the catching, so your part is to raise the error inside build. Words are runs of letters, lower-cased; a line with no letters in it contributes nothing at all.