Sling Blade Runner IV

I've been doing some more work on my kōan, Sling Blade Runner. I've given up on the beam-stack search approach. I doubt it will improve results much. If any at all.

Instead I have spent some time on improving the extend method so that it can find more extensions. And it is becoming quite efficient in exploring the neighbourhood of any given pair of titles. Previously it was only looking for extensions between two adjacent titles in the chain but now it searches for extensions between end-points in a whole sequence of titles instead. Consider the chain [A,B,C,D,...]. Now, if there's an extension between A and C, other than, and that is longer than [B], the chain is extended with it.

This, simple, tweak makes the search slower (of course) but it also improves the lengths of almost all chains that are explored. It rarely ends up with a chain that is shorter than 235 titles and most end up longer than 250 (246 was the previous best) titles.

The longest chain found is now 265 titles:

1 THE GOSPEL
2 THE GOSPEL OF JOHN
3 JOHN Q
4 Q AND A
5 A RIVER RUNS THROUGH IT
6 IT HAPPENED AT THE WORLDS FAIR
7 FAIR GAME
8 GAME OF DEATH
9 DEATH BECOMES HER
10 HER MAJESTY MRS BROWN
11 BROWN SUGAR
12 SUGAR AND SPICE
13 SPICE WORLD
14 WORLD TRADE CENTER
15 CENTER STAGE
16 STAGE FRIGHT
17 FRIGHT NIGHT
18 NIGHT OF THE LIVING DEAD
19 DEAD BANG
20 BANG BANG YOURE DEAD
21 DEAD MAN WALKING
22 WALKING AND TALKING
23 TALKING ABOUT SEX
24 SEX AND THE OTHER MAN
25 MAN OF THE HOUSE
26 HOUSE OF DRACULA
27 DRACULA DEAD AND LOVING IT
28 IT HAPPENED ONE NIGHT
29 ONE NIGHT STAND
30 STAND IN
31 IN GODS HANDS
32 HANDS ON A HARD BODY
33 BODY AND SOUL
34 SOUL FOOD
35 FOOD OF LOVE
36 LOVE IS THE DEVIL
37 THE DEVIL RIDES OUT
38 OUT COLD
39 COLD FEVER
40 FEVER PITCH
41 PITCH BLACK
42 BLACK LIKE ME
43 ME WITHOUT YOU
44 YOU LIGHT UP MY LIFE
45 MY LIFE SO FAR
46 FAR FROM HOME THE ADVENTURES OF YELLOW DOG
47 DOG RUN
48 RUN SILENT RUN DEEP
49 DEEP BLUE
50 DEEP BLUE SEA
51 SEA OF LOVE
52 LOVE WALKED IN
53 IN OLD CALIFORNIA
54 CALIFORNIA SPLIT
55 SPLIT SECOND
56 SECOND BEST
57 BEST MEN
58 MEN WITH GUNS
59 GUNS OF THE MAGNIFICENT SEVEN
60 THE MAGNIFICENT SEVEN
61 SEVEN YEARS IN TIBET
62 TIBET CRY OF THE SNOW LION
63 LION OF THE DESERT
64 DESERT HEARTS
65 HEARTS OF DARKNESS A FILMMAKERS APOCALYPSE
66 APOCALYPSE NOW
67 NOW YOU SEE HIM NOW YOU DONT
68 DONT BOTHER TO KNOCK
69 KNOCK OFF
70 OFF THE BLACK
71 THE BLACK ANGEL
72 ANGEL EYES
73 EYES OF AN ANGEL
74 ANGEL BABY
75 BABY SECRET OF THE LOST LEGEND
76 LEGEND OF THE LOST
77 THE LOST BOYS
78 BOYS LIFE
79 LIFE OR SOMETHING LIKE IT
80 IT TAKES TWO
81 TWO MEN WENT TO WAR
82 WAR OF THE WORLDS
83 THE WORLDS FASTEST INDIAN
84 INDIAN SUMMER
85 SUMMER CATCH
86 CATCH ME IF YOU CAN
87 YOU CAN COUNT ON ME
88 ME MYSELF I
89 I WANT TO LIVE
90 LIVE FOREVER
91 FOREVER YOUNG
92 YOUNG SHERLOCK HOLMES
93 SHERLOCK HOLMES IN WASHINGTON
94 WASHINGTON SQUARE
95 SQUARE DANCE
96 DANCE WITH A STRANGER
97 STRANGER IN THE HOUSE
98 THE HOUSE OF THE DEAD
99 DEAD OF NIGHT
100 NIGHT AND THE CITY
101 THE CITY
102 CITY OF ANGELS
103 ANGELS WITH DIRTY FACES
104 FACES OF DEATH
105 DEATH WISH
106 WISH UPON A STAR
107 A STAR IS BORN
108 BORN TO BE WILD
109 WILD THINGS
110 THINGS TO COME
111 COME AND GET IT
112 IT RUNS IN THE FAMILY
113 THE FAMILY MAN
114 MAN ON FIRE
115 FIRE ON THE MOUNTAIN
116 THE MOUNTAIN MEN
117 MEN IN BLACK
118 BLACK HAWK DOWN
119 DOWN WITH LOVE
120 LOVE AND DEATH
121 DEATH WISH V THE FACE OF DEATH
122 DEATH SHIP
123 SHIP OF FOOLS
124 FOOLS RUSH IN
125 IN THE WINTER DARK
126 DARK STAR
127 STAR TREK IV THE VOYAGE HOME
128 HOME ALONE
129 ALONE IN THE DARK
130 DARK BLUE
131 BLUE CAR
132 CAR 54 WHERE ARE YOU
133 YOU CANT TAKE IT WITH YOU
134 YOU ONLY LIVE ONCE
135 ONCE IN THE LIFE
136 LIFE AS A HOUSE
137 HOUSE PARTY
138 HOUSE PARTY 3
139 3 NINJAS
140 3 NINJAS KNUCKLE UP
141 UP CLOSE AND PERSONAL
142 PERSONAL BEST
143 BEST OF THE BEST
144 BEST OF THE BEST 3 NO TURNING BACK
145 NO TURNING BACK
146 BACK TO SCHOOL
147 SCHOOL OF ROCK
148 ROCK STAR
149 STAR TREK THE MOTION PICTURE
150 PICTURE BRIDE
151 BRIDE OF THE MONSTER
152 MONSTER HOUSE
153 HOUSE OF FRANKENSTEIN
154 FRANKENSTEIN AND THE MONSTER FROM HELL
155 FROM HELL
156 HELL UP IN HARLEM
157 HARLEM RIVER DRIVE
158 DRIVE ME CRAZY
159 CRAZY AS HELL
160 HELL NIGHT
161 NIGHT FALLS ON MANHATTAN
162 MANHATTAN MURDER MYSTERY
163 MYSTERY ALASKA
164 ALASKA SPIRIT OF THE WILD
165 THE WILD
166 THE WILD ONE
167 ONE NIGHT WITH THE KING
168 THE KING AND I
169 I SPY
170 SPY HARD
171 HARD EIGHT
172 EIGHT MEN OUT
173 OUT OF THE BLUE
174 BLUE SKY
175 SKY HIGH
176 HIGH CRIMES
177 CRIMES OF PASSION
178 PASSION IN THE DESERT
179 DESERT BLUE
180 BLUE STEEL
181 STEEL DAWN
182 DAWN OF THE DEAD
183 THE DEAD
184 DEAD MAN ON CAMPUS
185 CAMPUS MAN
186 MAN TROUBLE
187 TROUBLE EVERY DAY
188 DAY OF THE WOMAN
189 THE WOMAN IN RED
190 RED EYE
191 EYE FOR AN EYE
192 EYE OF GOD
193 GOD TOLD ME TO
194 TO DIE FOR
195 FOR THE BOYS
196 THE BOYS
197 BOYS AND GIRLS
198 GIRLS WILL BE GIRLS
199 GIRLS GIRLS GIRLS
200 GIRLS OF SUMMER
201 SUMMER LOVERS
202 LOVERS AND OTHER STRANGERS
203 STRANGERS WHEN WE MEET
204 MEET JOE BLACK
205 BLACK AND WHITE
206 WHITE HUNTER BLACK HEART
207 HEART CONDITION
208 CONDITION RED
209 RED RIVER
210 RIVER OF NO RETURN
211 RETURN OF THE FLY
212 FLY AWAY HOME
213 HOME ALONE 2 LOST IN NEW YORK
214 NEW YORK NEW YORK
215 NEW YORK COP
216 COP LAND
217 LAND OF THE DEAD
218 DEAD END
219 END OF DAYS
220 DAYS OF HEAVEN
221 HEAVEN CAN WAIT
222 WAIT UNTIL DARK
223 DARK CITY
224 CITY OF JOY
225 JOY RIDE
226 RIDE THE HIGH COUNTRY
227 COUNTRY LIFE
228 LIFE WITH FATHER
229 FATHER OF THE BRIDE
230 BRIDE OF THE WIND
231 THE WIND AND THE LION
232 THE LION KING
233 KING OF THE JUNGLE
234 THE JUNGLE BOOK
235 JUNGLE BOOK
236 BOOK OF LOVE
237 LOVE LIFE
238 LIFE IS BEAUTIFUL
239 BEAUTIFUL PEOPLE
240 PEOPLE I KNOW
241 I KNOW WHERE IM GOING
242 IM GOING HOME
243 HOME ALONE 3
244 3 NINJAS KICK BACK
245 BACK TO THE BEACH
246 BEACH PARTY
247 PARTY MONSTER
248 MONSTER IN A BOX
249 BOX OF MOON LIGHT
250 LIGHT OF DAY
251 DAY FOR NIGHT
252 NIGHT MOTHER
253 MOTHER NIGHT
254 NIGHT ON EARTH
255 EARTH GIRLS ARE EASY
256 EASY MONEY
257 MONEY FOR NOTHING
258 NOTHING BUT TROUBLE
259 TROUBLE IN PARADISE
260 PARADISE ROAD
261 ROAD HOUSE
262 HOUSE PARTY 2
263 2 DAYS IN THE VALLEY
264 VALLEY GIRL
265 GIRL WITH A PEARL EARRING

The results vary a bit depending on search depth (not that surprising really) so there may still be some possible improvements by just modifying parameters.

[Update 2008-07-20] The longest chain found is now 268 titles long.

Sling Blade Runner III

Continuing work on my Sling Blade Runner solution has led me to improve the search algorithm a bit further. Instead of looking for good starting-points for a search, it now looks for good mid-points and searches both forwards and backwards. This should, in theory, be a better way to do it and it does improve the average length of chains. But it turns out that it doesn't make *that* big a difference on the longest one (roughly 10 titles). The longest chain found is now 246 titles long.

1 THE PRICE OF MILK
2 MILK AND HONEY
3 HONEY I BLEW UP THE KID
4 THE KID
5 THE KID AND I
6 I WENT DOWN
7 DOWN TO YOU
8 YOU ONLY LIVE ONCE
9 ONCE AROUND
10 AROUND THE BEND
11 BEND OF THE RIVER
12 THE RIVER
13 THE RIVER WILD
14 WILD THINGS
15 THINGS TO COME
16 COME AND GET IT
17 IT TAKES TWO
18 TWO EVIL EYES
19 EYES OF AN ANGEL
20 ANGEL HEART
21 HEART CONDITION
22 CONDITION RED
23 RED RIVER
24 RIVER OF NO RETURN
25 RETURN TO HORROR HIGH
26 HIGH SCHOOL HIGH
27 HIGH CRIMES
28 CRIMES OF PASSION
29 PASSION IN THE DESERT
30 DESERT HEARTS
31 HEARTS OF DARKNESS A FILMMAKERS APOCALYPSE
32 APOCALYPSE NOW
33 NOW YOU SEE HIM NOW YOU DONT
34 DONT BOTHER TO KNOCK
35 KNOCK OFF
36 OFF THE BLACK
37 THE BLACK ANGEL
38 ANGEL BABY
39 BABY SECRET OF THE LOST LEGEND
40 LEGEND OF THE LOST
41 THE LOST BOYS
42 BOYS AND GIRLS
43 GIRLS JUST WANT TO HAVE FUN
44 FUN AND FANCY FREE
45 FREE WILLY
46 FREE WILLY 2 THE ADVENTURE HOME
47 HOME ALONE 3
48 3 NINJAS
49 3 NINJAS KNUCKLE UP
50 UP CLOSE AND PERSONAL
51 PERSONAL BEST
52 BEST OF THE BEST
53 BEST OF THE BEST 3 NO TURNING BACK
54 NO TURNING BACK
55 BACK STAGE
56 STAGE FRIGHT
57 FRIGHT NIGHT
58 NIGHT MOTHER
59 MOTHER NIGHT
60 NIGHT FALLS ON MANHATTAN
61 MANHATTAN MURDER MYSTERY
62 MYSTERY ALASKA
63 ALASKA SPIRIT OF THE WILD
64 THE WILD
65 THE WILD ONE
66 ONE NIGHT WITH THE KING
67 THE KING AND I
68 I NEVER PROMISED YOU A ROSE GARDEN
69 GARDEN STATE
70 STATE FAIR
71 FAIR GAME
72 GAME OF DEATH
73 DEATH WISH V THE FACE OF DEATH
74 DEATH SHIP
75 SHIP OF FOOLS
76 FOOLS RUSH IN
77 IN PRAISE OF OLDER WOMEN
78 WOMEN IN LOVE
79 IN LOVE AND WAR
80 WAR OF THE WORLDS
81 THE WORLDS FASTEST INDIAN
82 INDIAN SUMMER
83 SUMMER CATCH
84 CATCH A FIRE
85 FIRE ON THE MOUNTAIN
86 THE MOUNTAIN MEN
87 MEN WITH GUNS
88 GUNS OF THE MAGNIFICENT SEVEN
89 THE MAGNIFICENT SEVEN RIDE
90 RIDE WITH THE DEVIL
91 THE DEVIL RIDES OUT
92 OUT COLD
93 COLD FEVER
94 FEVER PITCH
95 PITCH BLACK
96 BLACK AND WHITE
97 WHITE WATER SUMMER
98 SUMMER LOVERS
99 LOVERS AND OTHER STRANGERS
100 STRANGERS WHEN WE MEET
101 MEET JOE BLACK
102 BLACK HAWK DOWN
103 DOWN WITH LOVE
104 LOVE LIFE
105 LIFE IS BEAUTIFUL
106 BEAUTIFUL GIRLS
107 GIRLS GIRLS GIRLS
108 GIRLS WILL BE GIRLS
109 GIRLS TOWN
110 TOWN AND COUNTRY
111 COUNTRY LIFE
112 LIFE WITH FATHER
113 FATHER OF THE BRIDE
114 BRIDE OF THE WIND
115 THE WIND AND THE LION
116 THE LION KING
117 KING OF THE JUNGLE
118 THE JUNGLE BOOK
119 JUNGLE BOOK
120 BOOK OF LOVE
121 LOVE CRAZY
122 CRAZY AS HELL
123 HELL NIGHT
124 NIGHT ON EARTH
125 EARTH GIRLS ARE EASY
126 EASY MONEY
127 MONEY FOR NOTHING
128 NOTHING BUT TROUBLE
129 TROUBLE EVERY DAY
130 DAY FOR NIGHT
131 NIGHT OF THE LIVING DEAD
132 DEAD MAN
133 DEAD MAN WALKING
134 WALKING AND TALKING
135 TALKING ABOUT SEX
136 SEX AND THE OTHER MAN
137 MAN OF THE HOUSE
138 THE HOUSE OF THE DEAD
139 DEAD END
140 END OF DAYS
141 DAYS OF HEAVEN
142 HEAVEN CAN WAIT
143 WAIT UNTIL DARK
144 DARK STAR
145 STAR WARS EPISODE V THE EMPIRE STRIKES BACK
146 BACK TO THE BEACH
147 THE BEACH
148 BEACH PARTY
149 PARTY MONSTER
150 MONSTER HOUSE
151 HOUSE OF DRACULA
152 DRACULA DEAD AND LOVING IT
153 IT HAD TO BE YOU
154 YOU LIGHT UP MY LIFE
155 MY LIFE
156 LIFE OR SOMETHING LIKE IT
157 IT HAPPENED ONE NIGHT
158 ONE NIGHT STAND
159 STAND IN
160 IN THE HEAT OF THE NIGHT
161 NIGHT AND THE CITY
162 THE CITY
163 CITY BY THE SEA
164 SEA OF LOVE
165 LOVE WALKED IN
166 IN THE COMPANY OF MEN
167 MEN IN BLACK
168 BLACK LIKE ME
169 ME MYSELF I
170 I WANT TO LIVE
171 LIVE AND LET DIE
172 DIE MONSTER DIE
173 DIE MOMMIE DIE
174 DIE ANOTHER DAY
175 DAY OF THE DEAD
176 THE DEAD
177 DEAD OF NIGHT
178 NIGHT AND DAY
179 DAY OF THE WOMAN
180 THE WOMAN IN RED
181 RED EYE
182 EYE FOR AN EYE
183 AN EYE FOR AN EYE
184 EYE OF GOD
185 GOD TOLD ME TO
186 TO DIE FOR
187 FOR THE BOYS
188 THE BOYS
189 BOYS LIFE
190 LIFE AS A HOUSE
191 HOUSE OF FRANKENSTEIN
192 FRANKENSTEIN MEETS THE WOLF MAN
193 THE WOLF MAN
194 MAN TROUBLE
195 TROUBLE IN PARADISE
196 PARADISE ROAD
197 ROAD HOUSE
198 HOUSE PARTY
199 HOUSE PARTY 3
200 3 NINJAS KICK BACK
201 BACK TO SCHOOL
202 SCHOOL OF ROCK
203 ROCK STAR
204 STAR TREK IV THE VOYAGE HOME
205 HOME ALONE
206 ALONE IN THE DARK
207 DARK BLUE
208 BLUE CAR
209 CAR 54 WHERE ARE YOU
210 YOU CANT TAKE IT WITH YOU
211 YOU CAN COUNT ON ME
212 ME WITHOUT YOU
213 YOU SO CRAZY
214 CRAZY PEOPLE
215 PEOPLE WILL TALK
216 TALK OF ANGELS
217 ANGELS WITH DIRTY FACES
218 FACES OF DEATH
219 DEATH WISH
220 WISH UPON A STAR
221 A STAR IS BORN
222 BORN AMERICAN
223 AMERICAN DREAM
224 DREAM A LITTLE DREAM
225 DREAM MAN
226 MAN ON FIRE
227 FIRE IN THE SKY
228 SKY HIGH
229 HIGH SPIRITS
230 SPIRITS OF THE DEAD
231 DEAD BANG
232 BANG BANG YOURE DEAD
233 DEAD HEAT
234 HEAT AND DUST
235 DUST TO GLORY
236 GLORY ROAD
237 ROAD GAMES
238 GAMES PEOPLE PLAY NEW YORK
239 NEW YORK NEW YORK
240 NEW YORK COP
241 COP LAND
242 LAND OF THE DEAD
243 DEAD MAN ON CAMPUS
244 CAMPUS MAN
245 MAN ON THE MOON
246 MOON OVER PARADOR
Time: 00:49:32

This is still just a simple best-first search and I still have high hopes for a beam search beam-stack search to do a lot better.

[Correction 2008-07-02]: When I say beam search I mean beam-stack search.

Sling Blade Runner II

In an effort to understand my heuristic's performance better I've compared the chains created by icefox's (312 titles) and my program (225 titles). Interestingly enough I've found several "gaps" in my chain that really shouldn't be there. Below is a snippet of icefox's chain (the number specifies the title's position in my chain):

219 ROAD GAMES
220 GAMES PEOPLE PLAY NEW YORK
--- NEW YORK NEW YORK
221 NEW YORK COP
222 COP LAND

New York Cop has a subtree of size 7 and since New York New York's subtree is only 6 titles in size, New York Cop will always be selected by my heuristic function. But apparently there's a blind spot in my find/extend function that makes it skip New York New York even though it's not used in my chain (indicated by ---). Terribly annoying.

[Update 2008-06-25]: Now that I've "fixed" (I changed a constant from 2 to 1 ;-) the code, the longest chain found is 233 titles. A small improvement, but still. Here's the list with the titles that have been added (the number specifies the title's position in my 225-length chain):

...
036 IT HAD TO BE YOU
--- YOU CANT TAKE IT WITH YOU
037 YOU CAN COUNT ON ME
038 ME MYSELF I
039 I LOVE YOU TO DEATH
--- DEATH WISH V THE FACE OF DEATH
040 DEATH WISH
...
077 ALASKA SPIRIT OF THE WILD
--- THE WILD
078 THE WILD ONE
...
082 LIVE AND LET DIE
--- DIE MONSTER DIE
083 DIE MOMMIE DIE
...
089 DEATH WISH 3
--- 3 NINJAS
090 3 NINJAS KNUCKLE UP
...
101 EYE FOR AN EYE
--- AN EYE FOR AN EYE
102 EYE OF GOD
...
120 THE JUNGLE BOOK
--- JUNGLE BOOK
121 BOOK OF LOVE
...
220 GAMES PEOPLE PLAY NEW YORK
--- NEW YORK NEW YORK
221 NEW YORK COP
...

[Update 2008-06-26]: Modifying a few parameters creates a chain with 237 titles.

Sling Blade Runner

I found the ITA Software Hiring Puzzles almost a year ago and ever since I haven't really been able to stop thinking about one of the puzzles: Sling Blade Runner.

"How long a chain of overlapping movie titles, like Sling Blade Runner, can you find?"

Use the following listing of movie titles: MOVIES.LST. Multi-word overlaps, as in "License to Kill a Mockingbird," are allowed. The same title may not be used more than once in a solution. Heuristic solutions that may not always produce the greatest number of titles will be accepted: seek a reasonable tradeoff of efficiency and optimality.

The file MOVIES.LST contains 6561 movie titles in alphabetical order.

It *sounds* simple enough, but it's actually quite a challenging problem. In fact, if I'm not mistaken, it's one of those problems you really can't find an *optimal* solution to. Just better or worse approximations thereof.

I think I've made something like five or six, more or less serious, attempts at getting a decent solution during the year. But thinking about this problem has made me read several books, web pages and articles on various subjects like graph theory and clustering. I've written code in Lisp, CLIPS and Python to test ideas I've had. All in all; it's been a very rewarding, educational and fun year.

Last week I decided to give it another serious attempt. That resulted in (after two days and 6 hours worth of coding) a small (~200 LOC) Python program that finds a chain that is 225 titles long. I really have no idea if that is good or bad. I know that Eric Burke found a chain that is 245 titles long so I guess I could do better. But if that chain is optimal, or close to optimal, I'm quite pleased anyway.

My program uses a best-first search approach using the size of the successors tree as the heuristic. It's a rather crude approach but works surprisingly well. Since it doesn't backtrack or explore more than one path at a time it doesn't really require that much space. This also means that I can keep using my laptop while the program is running.

The program works as follows:

The first step is to build a dict containing all the successors for a title. I'm actually using the line number (from MOVIES.LST) as the identifier instead of the title itself, but this should give you an idea of what it looks like:

{ ..., 'SLING BLADE': ['BLADE II', 'BLADE RUNNER', 'BLADE TRINITY',], ... }

It takes about half a second to create the dict for this data set. It contains 6561 keys and the sum of the lengths of the values is 15157.

The second step is the search. It is done by selecting the title with the most successors (that isn't already in the list), adding it to the list and repeating until there are no more titles that can be added.

The dict is sorted by the length of the list of successors so we don't have to search using all of the 6561 titles as starting points. Since, at least in theory we'll get shorter and shorter chains the further down we go.

The gist of the search function looks like this:

>>> def best_first_search(xref, lookahead = 5, cutoff = -1):
...   [...]
...     for index in sorted(xref.keys(), key = lambda k: tree_size(xref, k, 0, [k,]), reverse = True):
...       [...]
...       while True:
...         [...]
...         for next in sorted(xref[curr], key = lambda k: tree_size(xref, k, lookahead, chain), reverse = True):
...           if next not in chain:
...             chain.append(next)
...             assigned = True
...             break
...         if not assigned:
...           if len(chain) > len(longest):
...             print len(chain), "(#%s)" % (i), "%02.2fs" % (time.time()-start)
...             longest = chain
...           break
...       [...]
...   return longest

The function that calculates the size of the successors tree (see below) does so by traversing it to a certain depth. The deeper you search, the longer it takes, but there seems to be diminishing returns when using a search-depth greater than six or seven.

>>> def tree_size(xref, curr, depth, chain = None):
...   if chain is None:
...     chain = []
...   result = 0
...   if depth > 0:
...     for next in xref[curr][1:]:
...       if next not in chain:
...         result += tree_size(xref, next, depth- 1, chain+ [next,])
...   else:
...     length = 0
...     for title in xref[curr][1:]:
...       if title not in chain:
...         length += 1
...     result = length
...   return result

Using the above we can get a chain that is 203 titles long. It takes about two and a half minutes and is found as the 17th title searched. A chain that is 200 titles long is found when expanding the third title and takes about 20 seconds to get to. The next best chain is 202 titles long and takes about 1 minute 15 seconds to find at the ninth title expanded. The total runtime for the program using a cutoff at 20 takes about three minutes to complete. Here is the output:

161 (#1) 7.98s
177 (#2) 14.72s
200 (#3) 20.57s
202 (#9) 72.25s
203 (#17) 146.46s

1 WOMEN IN LOVE
2 LOVE WALKED IN
3 IN THIS OUR LIFE
4 LIFE OR SOMETHING LIKE IT
5 IT HAPPENED ONE NIGHT
...
199 SEX AND THE OTHER MAN
200 MAN OF THE YEAR
201 YEAR OF THE DRAGON
202 DRAGON SEED
203 SEED OF CHUCKY
203 titles in chain 182.76s

To get a longer chain we need to do some tweaking. The problem is that by selecting the title with the largest successors tree we might get long chains, but we're missing all of those little detours that make it the "longest" chain. For example, if we have a title A with two successors, B and C, where B has several successors (D, E, F, ...) and C only has B as its successor. Even though A->C->B, clearly, is the better choice my program will *always* choose the direct route A->B.

To compensate for this blind spot, every chain is expanded by trying to find longer paths between each pair of nodes in the chain (see below). Unfortunately, by adding this extra step the program requires more memory and becomes noticeably slower.

>>> def expand(xref, chain, max_depth, longest):
...   [...]
...     for curr, next in zip(chain[:-1], chain[1:]):
...       expansions = None
...       for i in range(2, max_depth+ 1):
...         paths = find(xref, curr, next, i, chain)
...         if paths:
...           expansions = paths
...       if expansions is not None:
...         expansion = sorted(expansions, key = lambda k: len(k), reverse = True)[0]
...         [...]
...         chain[chain.index(next):chain.index(next)] = expansion
...   return chain

The find function looks like this:

>>> def find(xref, curr, end, depth, chain = None):
...   if chain is None:
...     chain = []
...   if depth > 0:
...     result = []
...     for next in xref[curr][1:]:
...       if next not in chain:
...         paths = find(xref, next, end, depth- 1, chain+ [next,])
...         if paths:
...           for path in paths:
...             result.append([next,]+ path)
...     return result
...   elif end in xref[curr][1:]:
...     return [[],]
...   return None

I've tried various values for max_depth and 25 seems to be a good-enough value. I have found several expansions that are longer than that but they don't seem to add to the overall result anyway.

If we change the block of code that checks for and assigns the longest chain in the best_first_search function to:

...         if not assigned:
...           chain = expand(xref, chain, max_depth, len(longest))
...           if len(chain) > len(longest):
...             print len(chain), "(#%s)" % (i), "%02.2fs" % (time.time()-start)
...             longest = chain
...           break

and run the program again we get the first result after about a minute and it is 205 titles long.

The longest chain is 225 titles and it is found at #134 but it takes almost 50 minutes to find. Running the whole search (500 "best" titles) takes about 4 hours. Running it with a cutoff of 150 takes about 55 minutes and produces the following output:

205 (#1) 52.72s
206 (#5) 176.38s
208 (#6) 199.54s
[10]
209 (#12) 338.63s
211 (#13) 360.17s
212 (#18) 471.40s
[20]
213 (#21) 538.34s
[30]
[40]
[50]
[60]
[70]
[80]
215 (#85) 1904.34s
[90]
[100]
[110]
218 (#116) 2592.82s
[120]
[130]
219 (#131) 2858.43s
225 (#134) 2900.19s
[140]
[150]
1 OFF THE BLACK
2 THE BLACK ANGEL
3 ANGEL EYES
4 EYES OF AN ANGEL
5 ANGEL BABY
6 BABY SECRET OF THE LOST LEGEND
7 LEGEND OF THE LOST
8 THE LOST BOYS
9 BOYS ON THE SIDE
10 SIDE OUT
11 OUT COLD
12 COLD FEVER
13 FEVER PITCH
14 PITCH BLACK
15 BLACK HAWK DOWN
16 DOWN WITH LOVE
17 LOVE WALKED IN
18 IN THIS OUR LIFE
19 LIFE OR SOMETHING LIKE IT
20 IT HAPPENED ONE NIGHT
21 ONE NIGHT STAND
22 STAND IN
23 IN THE HEAT OF THE NIGHT
24 THE NIGHT OF THE FOLLOWING DAY
25 DAY OF THE DEAD
26 THE DEAD
27 DEAD OF NIGHT
28 NIGHT OF THE LIVING DEAD
29 DEAD MAN
30 DEAD MAN WALKING
31 WALKING AND TALKING
32 TALKING ABOUT SEX
33 SEX AND THE OTHER MAN
34 MAN OF THE HOUSE
35 HOUSE OF DRACULA
36 DRACULA DEAD AND LOVING IT
37 IT HAD TO BE YOU
38 YOU CAN COUNT ON ME
39 ME MYSELF I
40 I LOVE YOU TO DEATH
41 DEATH WISH
42 WISH UPON A STAR
43 A STAR IS BORN
44 BORN AMERICAN
45 AMERICAN ME
46 ME WITHOUT YOU
47 YOU LIGHT UP MY LIFE
48 MY LIFE
49 LIFE AS A HOUSE
50 HOUSE OF FRANKENSTEIN
51 FRANKENSTEIN AND THE MONSTER FROM HELL
52 FROM HELL
53 HELL UP IN HARLEM
54 HARLEM RIVER DRIVE
55 DRIVE ME CRAZY
56 CRAZY AS HELL
57 HELL NIGHT
58 NIGHT AND THE CITY
59 THE CITY
60 CITY OF ANGELS
61 ANGELS WITH DIRTY FACES
62 FACES OF DEATH
63 DEATH SHIP
64 SHIP OF FOOLS
65 FOOLS RUSH IN
66 IN THE WINTER DARK
67 DARK STAR
68 STAR TREK IV THE VOYAGE HOME
69 HOME ALONE
70 ALONE IN THE DARK
71 THE DARK HALF
72 HALF LIGHT
73 LIGHT OF DAY
74 DAY FOR NIGHT
75 NIGHT FALLS ON MANHATTAN
76 MANHATTAN MURDER MYSTERY
77 MYSTERY ALASKA
78 ALASKA SPIRIT OF THE WILD
79 THE WILD ONE
80 ONE NIGHT WITH THE KING
81 THE KING AND I
82 I WANT TO LIVE
83 LIVE AND LET DIE
84 DIE MOMMIE DIE
85 DIE HARD
86 HARD EIGHT
87 EIGHT AND A HALF WOMEN
88 WOMEN IN LOVE
89 LOVE AND DEATH
90 DEATH WISH 3
91 3 NINJAS KNUCKLE UP
92 UP CLOSE AND PERSONAL
93 PERSONAL BEST
94 BEST OF THE BEST
95 BEST MEN
96 MEN IN BLACK
97 BLACK AND WHITE
98 WHITE HUNTER BLACK HEART
99 HEART CONDITION
100 CONDITION RED
101 RED EYE
102 EYE FOR AN EYE
103 EYE OF GOD
104 GOD TOLD ME TO
105 TO DIE FOR
106 FOR THE BOYS
107 THE BOYS
108 BOYS AND GIRLS
109 GIRLS WILL BE GIRLS
110 GIRLS GIRLS GIRLS
111 GIRLS OF SUMMER
112 SUMMER SCHOOL
113 SCHOOL OF ROCK
114 ROCK STAR
115 STAR TREK THE MOTION PICTURE
116 PICTURE BRIDE
117 BRIDE OF THE WIND
118 THE WIND AND THE LION
119 THE LION KING
120 KING OF THE JUNGLE
121 THE JUNGLE BOOK
122 BOOK OF LOVE
123 LOVE IS THE DEVIL
124 THE DEVIL RIDES OUT
125 OUT OF THE BLUE
126 BLUE CAR
127 CAR 54 WHERE ARE YOU
128 YOU ONLY LIVE ONCE
129 ONCE AROUND
130 AROUND THE BEND
131 BEND OF THE RIVER
132 THE RIVER
133 THE RIVER WILD
134 WILD THINGS
135 THINGS TO COME
136 COME AND GET IT
137 IT TAKES TWO
138 TWO FRIENDS
139 FRIENDS WITH MONEY
140 MONEY FOR NOTHING
141 NOTHING BUT TROUBLE
142 TROUBLE EVERY DAY
143 DAY OF THE WOMAN
144 THE WOMAN IN RED
145 RED RIVER
146 RIVER OF NO RETURN
147 RETURN TO HORROR HIGH
148 HIGH SPIRITS
149 SPIRITS OF THE DEAD
150 DEAD BANG
151 BANG BANG YOURE DEAD
152 DEAD MAN ON CAMPUS
153 CAMPUS MAN
154 MAN TROUBLE
155 TROUBLE IN PARADISE
156 PARADISE ROAD
157 ROAD HOUSE
158 HOUSE PARTY
159 HOUSE PARTY 3
160 3 NINJAS KICK BACK
161 BACK STAGE
162 STAGE FRIGHT
163 FRIGHT NIGHT
164 NIGHT MOTHER
165 MOTHER NIGHT
166 NIGHT ON EARTH
167 EARTH GIRLS ARE EASY
168 EASY COME EASY GO
169 GO NOW
170 NOW YOU SEE HIM NOW YOU DONT
171 DONT GO IN THE HOUSE
172 THE HOUSE OF THE DEAD
173 DEAD END
174 END OF DAYS
175 DAYS OF HEAVEN
176 HEAVEN CAN WAIT
177 WAIT UNTIL DARK
178 DARK CITY
179 CITY BY THE SEA
180 SEA OF LOVE
181 LOVE LIFE
182 LIFE IS BEAUTIFUL
183 BEAUTIFUL PEOPLE
184 PEOPLE I KNOW
185 I KNOW WHAT YOU DID LAST SUMMER
186 SUMMER CATCH
187 CATCH A FIRE
188 FIRE ON THE MOUNTAIN
189 THE MOUNTAIN MEN
190 MEN WITH GUNS
191 GUNS OF THE MAGNIFICENT SEVEN
192 THE MAGNIFICENT SEVEN
193 THE MAGNIFICENT SEVEN RIDE
194 RIDE THE HIGH COUNTRY
195 COUNTRY LIFE
196 LIFE WITH FATHER
197 FATHER OF THE BRIDE
198 BRIDE OF THE MONSTER
199 MONSTER HOUSE
200 HOUSE PARTY 2
201 2 DAYS IN THE VALLEY
202 VALLEY GIRL
203 GIRL IN THE CADILLAC
204 CADILLAC MAN
205 MAN ON FIRE
206 FIRE IN THE SKY
207 SKY HIGH
208 HIGH SCHOOL HIGH
209 HIGH CRIMES
210 CRIMES OF PASSION
211 PASSION IN THE DESERT
212 DESERT BLUE
213 BLUE STEEL
214 STEEL DAWN
215 DAWN OF THE DEAD
216 DEAD HEAT
217 HEAT AND DUST
218 DUST TO GLORY
219 GLORY ROAD
220 ROAD GAMES
221 GAMES PEOPLE PLAY NEW YORK
222 NEW YORK COP
223 COP LAND
224 LAND OF THE DEAD
225 THE DEAD POOL
225 titles in chain 3203.74s

I've got a few other ideas and strategies (beam search beam-stack search for instance) I'd like to try to see if I can get an even longer chain, but I should probably re-implement the code in Lisp to make it faster first. 50 minutes is a tad on the long side ;-)

[Update 2008-05-12] I just did some more extensive Googling and my results are not that good in comparison to the 312 titles long chain found by icefox. Back to work.

[Correction 2008-07-02]: When I say beam search I mean beam-stack search.