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
