I agree the transitive closure is sufficient, but I suspect it is hardly
necessary. My own internal sketch of the solution matches yours except
for the closure thing. I wonder if I'm having a repeat of a five years
ago event :-)
A real mathematician wouldn't use no steenkin' computer, Charles Epps
notwithstanding, so some elegance is necessary.
Roger Hui wrote:
http://www.itasoftware.com/careers/puzzles07.html
The specs say:
How long a chain of overlapping movie titles,
like Sling Blade Runner, can you find?
I interpret "x overlap y" as "a suffix of x is
a prefix of y" and so my program counts
DEATH WITH -> DEATH WISH V THE FACE OF DEATH
as an overlap.
A tougher problem than I at first thought, and obviously needs more
analysis.
Oh, the solution is easy to describe: Find the
edges in the overlap relation. Compute its
transitive closure. Read off a longest path.
At this point, if you are a real mathematician,
you say, problem solved, and go on to the next
problem. :-)
----- Original Message -----
From: John Randall <[EMAIL PROTECTED]>
Date: Tuesday, May 22, 2007 2:02 pm
Subject: Re: [Jprogramming] Sling Blade Runner
Roger Hui wrote:
My current champion has length 278 (titles).
A few key insights made possible several orders
of magnitude improvements in the processing speed.
Also, beware that the input file has some subtle
flaws which may make a difference (some lines
terminate in CR instead of CRLF; duplicate lines).
I will have to recheck the input file.
On a point not explained by the rules, I am assuming that a title
being a prefix of another counts as a legitimate transition, e.g.
DEATH WITH -> DEATH WISH V THE FACE OF DEATH
Assuming that the graph is roughly the same with the input file
corrections, I believe my current algorithm will correctly yield a
longest solution, but it will take a very long time. Even though
I am
up to 201 titles, I have no guarantee that I am anywhere near a
solution. I can generate lists of around 180 titles in a couple of
seconds using depth-first search, but the problem is the cycles.
A tougher problem than I at first thought, and obviously needs more
analysis.
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
--
later ...
<pre>------------------------------------------------------------------------
|\/| Randy A MacDonald | APL: If you can say it, it's done.. (ram)
|/\| [EMAIL PROTECTED] |
|\ | | The only real problem with APL is that
BSc(Math) UNBF'83 | it is "still ahead of its time."
Sapere Aude | - Morten Kromberg
Natural Born APL'er | Looking for a whip-smart APL developer <a href="mailto:[EMAIL
PROTECTED]">Send me a note</a>
-----------------------------------------------------(INTP)----{ gnat }-</pre>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
