OraQA

The following is an interesting puzzle posted by itasofware :

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.

——————————SQL Solution——————————-

The following SQL pattern can be used to solve this puzzle. In order to reduce the query execution time, a small table is used instead. This query also handles a maximum of three overlap words in the title. If the real MOVIES.LST file is used, the SQL should be modified based on the maximum possible multi-word overlaps in the file: maximum number of word in the title – 1.

create table movies_lst as
select 'Here are the movie list: one' as title from dual
union all
select 'one two' as title from dual
union all
select 'two three four' as title from dual
union all
select 'three four five six seven eight' as title from dual
union all
select 'six seven eight nine' as title from dual
union all
select 'nine ten' as title from dual
union all
select 'ten good movies!!!' as title from dual;

ALTER TABLE movies_lst ADD CONSTRAINT pk PRIMARY KEY (title)

SQL> select * from movies_lst;

TITLE
-------------------------------
Here are the movie list: one
one two
two three four
three four five six seven eight
six seven eight nine
nine ten
ten good movies!!!

7 rows selected.

SELECT  max_len AS num_of_title, Overlapping_titles
FROM
(SELECT Overlapping_titles, max(l)OVER () max_len, L
 FROM
 (SELECT LEVEL  L,
  replace(sys_connect_by_path(
  CASE WHEN PRIOR Last_one = First_one
     THEN CASE WHEN LEVEL =2
	       THEN PRIOR title||substr(title,instr(title,' '))
	       ELSE substr(title,instr(title,' '))
	  END
     WHEN PRIOR Last_two = First_two
     THEN CASE WHEN LEVEL =2
	       THEN PRIOR title||substr(title,instr(title,' ',1,2))
	       ELSE substr(title,instr(title,' ',1,2))
	  END
     WHEN PRIOR Last_three = First_three
     THEN CASE WHEN LEVEL =2
	       THEN PRIOR title||substr(title,instr(title,' ',1,3))
	        ELSE substr(title,instr(title,' ',1,3))
	  END
   END ,','),',') Overlapping_titles
   FROM
    (SELECT title,
            substr(title,instr(title,' ',-1)+1)    Last_one,
            substr(title,0,instr(title,' ')-1)     First_one,
	    substr(title,instr(title,' ',-1,2)+1)  Last_two,
	    substr(title,1,instr(title,' ',1,2)-1) First_two,
	    substr(title,instr(title,' ',-1,3)+1)  Last_three,
	    substr(title,1,instr(title,' ',1,3)-1) First_three
     FROM movies_lst)
     CONNECT BY NOCYCLE PRIOR Last_one = First_one
     OR PRIOR Last_two = First_two
     OR PRIOR Last_three = First_three
  )
)
WHERE max_len = L;

NUM_OF_TITLE   OVERLAPPING_TITLES

------------  ----------------------------------------------------------
7	      Here are the movie list: one two three four five six seven eight nine ten good movies!!!

Filed under SQL. Follow any responses to this entry through this RSS 2.0 feed.