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.

One table, two shapes

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

local index = {}
index["cat"] = {1, 3}
index["dog"] = {2}
print("cat: " .. table.concat(index["cat"], " "))

--> cat: 1 3

table.concat takes numbers as happily as strings, so the line 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 hits = index[word]
if hits == nil then
    hits = {}
    index[word] = hits
end
hits[#hits + 1] = lineno

hits is a reference to the table now sitting in the index, so appending to hits appends to the index. 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 The and the land on one entry.

local out = {}
for word in ("The cat, the CAT!"):lower():gmatch("%a+") do
    out[#out + 1] = word
end
print(table.concat(out, "|"))

--> the|cat|the|cat

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

if hits[#hits] ~= lineno then
    hits[#hits + 1] = lineno
end

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

Making the output stable

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

local index = {the = {1, 2}, a = {3}, cat = {1, 3}}
local words = {}
for w in pairs(index) do words[#words + 1] = w end
table.sort(words)
for _, w in ipairs(words) do
    print(w .. ": " .. table.concat(index[w], " "))
end

--> a: 3
--> cat: 1 3
--> the: 1 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 build(header)
    local n = tonumber(header)
    if n == nil or n < 1 then
        error("bad line count", 0)
    end
    return n
end

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

--> true	3
--> false	bad line count

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

Common mistakes

• Printing straight out of pairs — every line correct, the order 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 hits[#hits].
• 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 separated by single spaces.

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 — raise it with error("bad line count", 0) inside the build function the starter gives you and let the pcall already sitting below it do the catching. Words are runs of letters, lower-cased; a line with no letters in it contributes nothing at all.