First, read and try implementing a solution to the original question below. Remember that on the qual, students had an hour.
Now, assess your answer based on these critiques.
Finally, look at the answer I generated. It's more than what can be done in an hour, but it's also complete and more polished than I would expect.
Congratulations! One-Hour Software ("ready in 60 or you don't pay!") has hired you to implement Fitzgerald's Indexed Concept Parser (ICP). ICP takes an input text and returns a list of target concepts, sorted by how strongly the text indexes the targets. ICP uses a memory containing:
Here are some examples of target concepts for a robot gardener and their indices:
|
Target |
Index set |
|---|---|
|
|
|
|
|
|
|
|
|
A target can have more than one index set linked to it.
Given an input text, ICP maps the words and phrases to a pool of input concepts, P, and sorts the index sets in memory based on how well each index set S matches P, combining these positive and negative metrics:
(As usual, a concept is trivially an abstraction of itself.) Another programmer has defined score-match(p+s, p-s, s-p) to combine these numbers into a single score. ICP then sorts the target concepts based on the score of their best matching index set.
Working top-down, starting with parse(input-list-of-words), implement as much of the code as you can. Don't worry about implementing the links between concepts and words and index sets. Focus on the parsing and matching. Clarity and brevity of code count more than efficiency, but, since the obvious algorithms are combinatoric, notes that would help later programmers improve the efficiency of your code are important too.