The Puzzle by ITA Software:
How long a chain of overlapping movie titles, like Sling Blade Runner, can you find?
And the date is a list of movie titles provided by movielens. And here is my solution with the resulting output:
import collections, time
starttime = time.time()
titles = [x.strip() for x in open('MOVIES.LST.txt') if x.strip()]
# Add titles to beginnings such that, beginnings[T] = list of titles
# that start with some suffix of title T.
beginnings = collections.defaultdict(list)
ends = collections.defaultdict(list)
begs = collections.defaultdict(list)
for t in titles:
s = t.split()
for i in range(len(s) - 1):
end = ' '.join(s[-i-1:])
ends[end].append(t)
beg = ' '.join(s[:i+1])
begs[beg].append(t)
for k in [k for k in ends if k in begs]:
for t in ends[k]:
beginnings[t].extend( begs[k] )
titles.sort(key=lambda t: len(beginnings[t]), reverse=True)
for t in beginnings.keys():
# if reverse is set to False, then the longer results don't
# show up that quickly.
beginnings[t].sort(key=lambda t: len(beginnings[t]), reverse=True)
best = []
try:
for t in titles:
states = collections.deque()
states.append( (set([t]), [t]) )
while states:
seen, state = states.popleft()
last = state[-1]
for x in beginnings[last]: # remember beginnings is a defaultdict
if x in seen:
continue
seen2 = seen.copy()
seen2.add(x)
newstate = (seen2, state + [x])
states.appendleft(newstate) # KEY!!
if len(newstate[1]) > len(best):
best = newstate[1]
except KeyboardInterrupt:
print
print '\n'.join(best)
print '--'
print len(best)
print 'elapsed secs', time.time()-starttime
Q AND AA KISS BEFORE DYING
DYING YOUNG
YOUNG GUNS
GUNS OF THE MAGNIFICENT SEVEN
SEVEN YEARS IN TIBET
TIBET CRY OF THE SNOW LION
LION OF THE DESERT
DESERT HEARTS
HEARTS OF DARKNESS A FILMMAKERS APOCALYPSE
APOCALYPSE NOW
NOW YOU SEE HIM NOW YOU DONT
DONT BOTHER TO KNOCK
KNOCK OFF
OFF THE MAP
MAP OF THE HUMAN HEART
HEART CONDITION
CONDITION RED
RED RIVER
RIVER OF NO RETURN
RETURN OF THE FLY
FLY AWAY HOME
HOME ALONE
ALONE IN THE DARK
DARK BLUE WORLD
WORLD TRADE CENTER
CENTER STAGE
STAGE FRIGHT
FRIGHT NIGHT
NIGHT FALLS ON MANHATTAN
MANHATTAN MURDER MYSTERY
MYSTERY ALASKA
ALASKA SPIRIT OF THE WILD
WILD IN THE STREETS
STREETS OF FIRE
FIRE ON THE MOUNTAIN
THE MOUNTAIN MEN
MEN CRY BULLETS
BULLETS OVER BROADWAY
BROADWAY DANNY ROSE
ROSE RED
RED HEAT
HEAT AND DUST
DUST TO GLORY
GLORY ROAD
ROAD GAMES
GAMES PEOPLE PLAY NEW YORK
NEW YORK COP
COP LAND
LAND OF THE DEAD
DEAD MAN ON CAMPUS
CAMPUS MAN
MAN TROUBLE
TROUBLE EVERY DAY
DAY OF THE WOMAN
WOMAN ON TOP
TOP GUN
GUN CRAZY
CRAZY PEOPLE
PEOPLE WILL TALK
TALK RADIO
RADIO DAYS
DAYS OF HEAVEN
HEAVEN CAN WAIT
WAIT UNTIL DARK
DARK CITY
CITY OF JOY
JOY RIDE
RIDE THE HIGH COUNTRY
COUNTRY LIFE
LIFE WITH FATHER
FATHER OF THE BRIDE
BRIDE OF THE WIND
THE WIND AND THE LION
THE LION KING
KING RAT
RAT RACE
RACE WITH THE DEVIL
THE DEVIL RIDES OUT
OUT TO SEA
SEA OF LOVE
LOVE AND SEX
SEX AND THE OTHER MAN
MAN ON FIRE
FIRE IN THE SKY
SKY HIGH
HIGH SPIRITS
SPIRITS OF THE DEAD
DEAD BANG
BANG BANG YOURE DEAD
DEAD MAN
MAN OF THE HOUSE
HOUSE PARTY
PARTY MONSTER
MONSTER IN A BOX
BOX OF MOON LIGHT
LIGHT OF DAY
DAY FOR NIGHT
NIGHT ON EARTH
EARTH GIRLS ARE EASY
EASY MONEY
MONEY FOR NOTHING
NOTHING PERSONAL
PERSONAL BEST
BEST FRIENDS
FRIENDS AND LOVERS
LOVERS AND OTHER STRANGERS
STRANGERS WHEN WE MEET
MEET JOE BLACK
BLACK DOG
DOG RUN
RUN SILENT RUN DEEP
DEEP BLUE
BLUE STEEL
STEEL DAWN
DAWN OF THE DEAD
DEAD OF NIGHT
NIGHT MOTHER
MOTHER NIGHT
NIGHT AND THE CITY
CITY OF ANGELS
ANGELS WITH DIRTY FACES
FACES OF DEATH 4
4 LITTLE GIRLS
GIRLS JUST WANT TO HAVE FUN
FUN AND FANCY FREE
FREE WILLY 2 THE ADVENTURE HOME
HOME ALONE 3
3 NINJAS KICK BACK
BACK TO SCHOOL
SCHOOL OF ROCK
ROCK N ROLL HIGH SCHOOL
HIGH SCHOOL HIGH
HIGH CRIMES
CRIMES OF PASSION
PASSION IN THE DESERT
DESERT BLUE
BLUE CAR
CAR 54 WHERE ARE YOU
YOU CAN COUNT ON ME
ME WITHOUT YOU
YOU CANT TAKE IT WITH YOU
YOU LIGHT UP MY LIFE
MY LIFE WITHOUT ME
ME MYSELF I
I NEVER PROMISED YOU A ROSE GARDEN
GARDEN STATE
STATE FAIR
FAIR GAME
GAME OF DEATH
DEATH SHIP
SHIP OF FOOLS
FOOLS RUSH IN
IN PRAISE OF OLDER WOMEN
WOMEN IN LOVE
LOVE LIFE
LIFE OR SOMETHING LIKE IT
IT HAD TO BE YOU
YOU ONLY LIVE ONCE
ONCE AROUND
AROUND THE BEND
BEND OF THE RIVER
THE RIVER WILD
WILD THINGS
THINGS TO COME
COME AND GET IT
IT HAPPENED ONE NIGHT
ONE NIGHT STAND
STAND IN
IN GODS HANDS
HANDS ON A HARD BODY
BODY AND SOUL
SOUL FOOD
FOOD OF LOVE
LOVE WALKED IN
IN OLD CALIFORNIA
CALIFORNIA SPLIT
SPLIT SECOND
SECOND BEST
BEST OF THE BEST
THE BEST OF EVERYTHING
EVERYTHING RELATIVE
RELATIVE FEAR
FEAR X
X THE MAN WITH THE X RAY EYES
EYES OF AN ANGEL
ANGEL BABY
BABY SECRET OF THE LOST LEGEND
LEGEND OF THE LOST
THE LOST BOYS
BOYS ON THE SIDE
SIDE OUT
OUT COLD
COLD FEVER
FEVER PITCH
PITCH BLACK
BLACK HAWK DOWN
DOWN WITH LOVE
LOVE AND DEATH
DEATH WISH V THE FACE OF DEATH
DEATH WISH
WISH UPON A STAR
STAR TREK THE MOTION PICTURE
PICTURE BRIDE
BRIDE OF THE MONSTER
MONSTER HOUSE
HOUSE OF DRACULA
DRACULA DEAD AND LOVING IT
IT TAKES TWO
TWO MUCH
MUCH ADO ABOUT NOTHING
NOTHING BUT TROUBLE
TROUBLE IN PARADISE
PARADISE ROAD
ROAD HOUSE
HOUSE OF FRANKENSTEIN
FRANKENSTEIN AND THE MONSTER FROM HELL
HELL UP IN HARLEM
HARLEM RIVER DRIVE
DRIVE ME CRAZY
CRAZY AS HELL
HELL NIGHT
NIGHT AND DAY
DAY OF THE DEAD
THE DEAD GIRL
GIRL IN THE CADILLAC
CADILLAC MAN
MAN OF THE YEAR
YEAR OF THE DRAGON
DRAGON SEED
SEED OF CHUCKY
----
231
elapsed secs 101.631449938