This page contains an exercise and details on reporting encounters in Tolkien's classic `The Two Towers' (`Sagan Om De Två Tornen'), part 2 of the `Lord of the Rings' trilogy.
The longest path problem is to find the longest (weighted, simple) path in a graph. The exercise is to find a long path in Book("tolkien") -- the longer the better!
It is quite possible that we'll find the optimum easily (who knows? -- I haven't tried it). So in case of a tie, the first group to hand in the winning solution wins.
Hand in a print-out of your feasible solution, together with its cost. Also, please tell me how you found the solution (by hand? by a local search algorithm? by branch-and-bound? by something completely different?). Note that you cannot cheat in this exercise, since there are no rules. Any solution will do, no matter how you found it. I'm just curious, so I'd be happy to see the algorithm as well.
Note:The tolkien graph contains all encounters in The Hobbit, and (as of Dec 9) the first two volumes of the Lord of the Rings.
Please report data as you find it, especially on character names and abbreviations. Send me e-mail with the header
[LotR] Chapter 3.5or similar and I will update this page quickly.
Your must document your chapter by 1 December.
We'll enumerate the Chapters as follows. Book 1 will have numbers from 1.1 to 1.12. Book 2 has numbers 2.1 to 2.10. The preface has number 1.0. The chapters in the Hobbit are numbered 0.1 to 0.19.
The two books (Book 3 and 4) that constitute the volume The Two Towers are thus numbered 3.1, 3.2, etc. and 4.1, 4.2, etc.
This section contains the two-letter abbreviations used with all the characters. If you cannot find your character on the list, invent a meaningful abbreviation for it. I will merge these and update the list.
The notion of a `character' in a novel is usually straightforward, but in some cases we want to generalise the idea so that a group of people can collectively act as an individual. Thus, for example, one of the characters in Huckleberry Finn is TF, `townfolk.' In the Iliad, OG stands for Olympian Gods, collectively; GS and TS are arrays of Greek soldiers and Trojan soldiers.
Swedish translations of character names etc. are no problem, I will anglify the data as neccessary. We hope that the Swedish text follows the plot of the original.
Many of the minor characters will receive numeric and almost meaningless abbreviations. For example, here are some characters from the Iliad, with 561 characters,
1J Amphius, fighter from Paesus, killed by AJ 1K Laomedon, king of Troy, father of PR, killed by HR 1L Hesione, daughter of 1K, rescued by HR 1M Coeranus, Lycian speared by OD
Please refer to the
tolkien data filefor the current list of character codes. The file also includes data for the first volume of the Lord of the Rings (which was reported by the course's students last year) and the Hobbit which I compiled myself. If you find any errors or omissions please tell me. Note that some of the chapters are missing because of lazy students.
This section contains information about the chapters as they are reported. There is one line for each chapter, containing `cliques of encounters.' For example, the line
means that, in chapter 22 of book 3, there were encounters between the pairs3.22:AA,BB,CC,DD;CC,DD,EE;AA,FF
AA-BB, AA-CC, AA-DD, BB-CC, BB-DD, CC-DD, CC-EE, DD-EE, AA-FF.(The encounter CC-DD is specified twice, once in the clique AA, BB, CC, DD, and once in CC, DD, EE; this does not imply anything about the actual number of encounters between CC and DD in the chapter.)
A clique might involve one character only, when the character is featured in sort of a soliloquy. For example, the line
indicates that only Vronsky made a substantial appearance in chapter 16.1.16:VR
Sometimes a person who has prepared the data files has chosen to follow the plot of the novel closely so that one can easily match the data file with the book itself. But at other times the data might be `optimized' so as to be brief yet mathematically equivalent to the book. For example, the clique AA, BB, CC, DD might be listed even if the four characters were never present simultaneously in any scene, provided that each character did happen to meet the others at least once.
Jugdement calls occasionally need to be made about whether encounters are significant enough to be recorded. What should be done when AA tells BB that CC once met DD? Let's decide that this gives an encounter between AA and BB, and another between CC and DD, so the correct line would be
AA,BB;CC,DD
What should be done when EE sees FF, but FF cannot see EE? What should be done if EE and FF fight in the same battle? Attend the same birthday party?
In all such cases, arbitrary decisions must be made and the resulting data files are correct by definition.
A chapter might contain no references to characters at all. In such a case the `:' following the chapter number is omitted.
There might be more encounters than will fit on a single line. In such cases, continuation lines begin with `&:'.
Here's what you do: Buy, borrow, or steal a copy of J.R.R. Tolkiens classic `The Two Towers', in Swedish (Sagan om de två tornen) or English or any other language you like. This volume consists of two parts (confusingly called Book 3 and Book 4), with 11 and 10 chapters, respectively. Find your chapter on this list, read the relevant chapter, and mail me the data by December 1.