Saturday Night Geekery

by on September 23, 2007 · 21 comments

What did you do with your Saturday night? I spent mine solving this programming puzzle. (Via PJ) I’m guessing most TLF readers don’t care, but if any do, details are below the fold.


The puzzle is as follows:

“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.

I found the reference to “heuristic solutions” puzzling until I took a first stab at implementing it and found out how slow it ran. My perl script starts by building a digraph in which each node represents a movie and each edge indicates that one movie can follow another. Then it does a straightforward depth-first search on the graph. This worked great on a test set of a few hundred movies. But when I applied it to the full 6500-movie dataset, it never produced any output.

After some further thinking, it became obvious why they mentioned “heuristic solutions.” The number of possible paths through the graph grows much faster than the number of nodes. Apparently with the full 6500-movie dataset, there are so many paths to explore that an exhaustive search won’t finish in our lifetimes.

I don’t know if there’s a general solution to the problem of finding the longest (non-repeating) path through a digraph. A quick web search didn’t turn up any good ideas, and to my untrained eye the problem appears to have some similarities with the Traveling Salesman Problem, suggesting that it might not have a general polynomial-time solution.

So I took the easy way out and just put a ceiling to the number of nodes the search function would traverse before returning a result. With the limit set at 20,000, I got results like this:

20 MILLION MILES TO EARTH GIRLS ARE EASY COME EASY GO NOW YOU SEE HIM NOW YOU DONT BOTHER TO KNOCK OFF THE BLACK AND WHITE DOG RUN SILENT RUN DEEP BLUE CAR 54 WHERE ARE YOU CAN COUNT ON ME MYSELF I AM TRYING TO BREAK YOUR HEART CONDITION RED DAWN OF THE DEAD BANG BANG YOURE DEAD END OF DAYS OF HEAVEN CAN WAIT UNTIL DARK BLUE SKY HIGH CRIMES OF THE HEART OF ME WITHOUT YOU CANT TAKE IT WITH YOU LIGHT UP MY LIFE AS A HOUSE OF DRACULA DEAD AND LOVING IT CAME FROM BENEATH THE SEA OF LOVE AND DEATH BECOMES HER MAJESTY MRS BROWN SUGAR AND SPICE WORLD TRADE CENTER STAGE FRIGHT NIGHT AND DAY FOR NIGHT AND THE CITY HEAT AND DUST TO GLORY ROAD GAMES PEOPLE PLAY NEW YORK COP LAND OF THE DEAD MAN ON CAMPUS MAN OF THE HOUSE OF FRANKENSTEIN AND THE MONSTER FROM HELL NIGHT FALLS ON MANHATTAN MURDER MYSTERY ALASKA SPIRIT OF THE WILD ANGELS WITH DIRTY FACES OF DEATH SHIP OF FOOLS RUSH IN COLD BLOOD BEACH PARTY GIRL IN THE CADILLAC MAN ON FIRE ON THE MOUNTAIN MEN CRY BULLETS OVER BROADWAY DANNY ROSE RED EYE FOR AN EYE FOR AN EYE OF GOD TOLD ME TO DIE FOR LOVE OF THE GAME OF DEATH WISH 3 NINJAS KICK BACK TO SCHOOL OF ROCK N ROLL HIGH SCHOOL HIGH SPIRITS OF THE DEAD MAN WALKING AND TALKING ABOUT SEX AND THE OTHER MAN TROUBLE EVERY DAY OF THE DEAD OF NIGHT MOTHER JUGS AND SPEED 2 CRUISE CONTROL ROOM AT THE TOP GUN CRAZY AS HELL UP IN HARLEM RIVER DRIVE ME CRAZY PEOPLE I KNOW WHAT YOU DID LAST SUMMER LOVERS AND OTHER STRANGERS WHEN WE MEET JOE BLACK HAWK DOWN TO YOU ONLY LIVE ONCE AROUND THE BEND OF THE RIVER OF NO RETURN OF THE FLY AWAY HOME ALONE IN THE DARK CITY OF JOY RIDE THE HIGH COUNTRY LIFE IS BEAUTIFUL GIRLS GIRLS GIRLS JUST WANT TO HAVE FUN AND FANCY FREE WILLY 2 THE ADVENTURE HOME ALONE 3 NINJAS KNUCKLE UP CLOSE AND PERSONAL BEST OF THE BEST OF EVERYTHING RELATIVE FEAR X THE MAN WITH THE X RAY EYES OF AN ANGEL BABY SECRET OF THE LOST LEGEND OF THE LOST BOYS LIFE OR SOMETHING LIKE IT HAPPENED ONE NIGHT STAND IN GODS HANDS ON A HARD BODY AND SOUL FOOD OF LOVE LIFE WITH FATHER OF THE BRIDE OF THE WIND AND THE LION KING OF THE JUNGLE 2 JUNGLE BOOK OF LOVE WALKED IN OLD CALIFORNIA SPLIT SECOND BEST MEN WITH GUNS OF THE MAGNIFICENT SEVEN BRIDES FOR SEVEN BROTHERS IN TROUBLE IN PARADISE ROAD HOUSE PARTY MONSTER IN A BOX OF MOON LIGHT OF DAY OF THE WOMAN ON TOP SECRET AGENT CODY BANKS 2 DESTINATION LONDON.

I’m not sure how close that is to the maximum length. I plan to let it run overnight with a cap of 100,000 nodes to see how much that improves the result.

I have no idea how to solve ITA’s other puzzle, “word numbers.” The only approach I can think of is “wait until 256 GB DRAM gets cheaper.” But that’s probably not the approach they’re looking for.

  • satoria

    For the word numbers it seems that one need only come up with a way to calculate the number of characters used up until the 51′st billionth. The pattern is a predictable one, so you needn’t use brute force.

  • satoria

    For the word numbers it seems that one need only come up with a way to calculate the number of characters used up until the 51′st billionth. The pattern is a predictable one, so you needn’t use brute force.

  • http://www.techliberation.com/ Tim Lee

    New record, after letting it run longer and randomizing the next nodes:

    THE WATERMELON MAN ON FIRE ON THE MOUNTAIN MEN CRY BULLETS OVER BROADWAY DANNY ROSE RED DAWN OF THE DEAD MAN WALKING AND TALKING ABOUT SEX AND THE OTHER MAN TROUBLE IN PARADISE ROAD GAMES PEOPLE PLAY NEW YORK NEW YORK COP LAND OF THE DEAD GIRL IN THE CADILLAC MAN OF THE HOUSE PARTY 3 NINJAS KNUCKLE UP CLOSE AND PERSONAL BEST MEN DONT LEAVE HER TO HEAVEN AND EARTH GIRLS ARE EASY COME EASY GO NOW YOU SEE HIM NOW YOU DONT TELL MOM THE BABYSITTERS DEAD BANG BANG YOURE DEAD HEAT AND DUST TO GLORY ROAD HOUSE OF FRANKENSTEIN AND THE MONSTER FROM HELL NIGHT AND DAY OF THE DEAD OF NIGHT MOTHER JUGS AND SPEED 2 CRUISE CONTROL ROOM AT THE TOP GUN CRAZY AS HELL UP IN HARLEM RIVER DRIVE ME CRAZY PEOPLE I KNOW WHERE IM GOING HOME ALONE 3 NINJAS KICK BACK TO SCHOOL OF ROCK N ROLL HIGH SCHOOL HIGH CRIMES OF PASSION IN THE DESERT BLUE SKY HIGH SPIRITS OF THE DEAD END OF DAYS OF HEAVEN CAN WAIT UNTIL DARK CITY BY THE SEA OF LOVE HAPPY BIRTHDAY TO ME MYSELF I WAS A MALE WAR BRIDE OF THE MONSTER IN A BOX OF MOON LIGHT OF DAY OF THE WOMAN IN RED RIVER OF NO RETURN TO ME WITHOUT YOU LIGHT UP MY LIFE SO FAR FROM HOME THE ADVENTURES OF YELLOW DOG RUN SILENT RUN DEEP BLUE CAR 54 WHERE ARE YOU CANT TAKE IT WITH YOU ONLY LIVE ONCE IN THE LIFE OR SOMETHING LIKE IT HAPPENED AT THE WORLDS FAIR GAME OF DEATH BECOMES HER MAJESTY MRS BROWN SUGAR TOWN AND COUNTRY LIFE IS BEAUTIFUL PEOPLE WILL TALK OF ANGELS WITH DIRTY FACES OF DEATH 4 LITTLE GIRLS WILL BE GIRLS JUST WANT TO HAVE FUN AND FANCY FREE WILLY 2 THE ADVENTURE HOME ALONE IN THE DARK BLUE WORLD TRADE CENTER STAGE FRIGHT NIGHT FALLS ON MANHATTAN MURDER MYSTERY MEN WITH GUNS OF THE MAGNIFICENT SEVEN BRIDES FOR SEVEN BROTHERS IN TROUBLE EVERY DAY FOR NIGHT AND THE CITY OF JOY RIDE WITH THE DEVIL RIDES OUT COLD FEVER PITCH BLACK HAWK DOWN WITH LOVE AND DEATH WISH V THE FACE OF DEATH WISH UPON A STAR WARS EPISODE V THE EMPIRE STRIKES BACK TO THE BEACH PARTY MONSTER HOUSE OF DRACULA DEAD AND LOVING IT TAKES TWO MEN WENT TO WAR OF THE WORLDS FASTEST INDIAN SUMMER LOVERS AND OTHER STRANGERS WHEN WE MEET JOE BLACK AND WHITE HUNTER BLACK HEART CONDITION RED EYE FOR AN EYE FOR AN EYE OF GOD TOLD ME TO DIE FOR THE BOYS IN THE BAND OF THE HAND THAT ROCKS THE CRADLE WILL ROCK STAR TREK THE MOTION PICTURE BRIDE OF THE WIND AND THE LION KING OF THE JUNGLE 2 JUNGLE BOOK OF LOVE WALKED IN GODS HANDS ON A HARD BODY DOUBLE TAKE THIS JOB AND SHOVE IT HAPPENED ONE NIGHT WITH THE KING AND I WANT TO LIVE FOREVER YOUNG SHERLOCK HOLMES FACES DEATH SHIP OF FOOLS RUSH IN OLD CALIFORNIA SPLIT SECOND BEST OF THE BEST OF EVERYTHING RELATIVE FEAR X THE MAN WITH THE X RAY EYES OF AN ANGEL BABY SECRET OF THE LOST LEGEND OF THE LOST BOYS LIFE WITH FATHER OF THE BRIDE OF FRANKENSTEIN MEETS THE WOLF MAN OF THE YEAR OF THE HORSE IN THE GRAY FLANNEL SUIT” (561 words)

  • http://www.techliberation.com/ Tim Lee

    New record, after letting it run longer and randomizing the next nodes:

    THE WATERMELON MAN ON FIRE ON THE MOUNTAIN MEN CRY BULLETS OVER BROADWAY DANNY ROSE RED DAWN OF THE DEAD MAN WALKING AND TALKING ABOUT SEX AND THE OTHER MAN TROUBLE IN PARADISE ROAD GAMES PEOPLE PLAY NEW YORK NEW YORK COP LAND OF THE DEAD GIRL IN THE CADILLAC MAN OF THE HOUSE PARTY 3 NINJAS KNUCKLE UP CLOSE AND PERSONAL BEST MEN DONT LEAVE HER TO HEAVEN AND EARTH GIRLS ARE EASY COME EASY GO NOW YOU SEE HIM NOW YOU DONT TELL MOM THE BABYSITTERS DEAD BANG BANG YOURE DEAD HEAT AND DUST TO GLORY ROAD HOUSE OF FRANKENSTEIN AND THE MONSTER FROM HELL NIGHT AND DAY OF THE DEAD OF NIGHT MOTHER JUGS AND SPEED 2 CRUISE CONTROL ROOM AT THE TOP GUN CRAZY AS HELL UP IN HARLEM RIVER DRIVE ME CRAZY PEOPLE I KNOW WHERE IM GOING HOME ALONE 3 NINJAS KICK BACK TO SCHOOL OF ROCK N ROLL HIGH SCHOOL HIGH CRIMES OF PASSION IN THE DESERT BLUE SKY HIGH SPIRITS OF THE DEAD END OF DAYS OF HEAVEN CAN WAIT UNTIL DARK CITY BY THE SEA OF LOVE HAPPY BIRTHDAY TO ME MYSELF I WAS A MALE WAR BRIDE OF THE MONSTER IN A BOX OF MOON LIGHT OF DAY OF THE WOMAN IN RED RIVER OF NO RETURN TO ME WITHOUT YOU LIGHT UP MY LIFE SO FAR FROM HOME THE ADVENTURES OF YELLOW DOG RUN SILENT RUN DEEP BLUE CAR 54 WHERE ARE YOU CANT TAKE IT WITH YOU ONLY LIVE ONCE IN THE LIFE OR SOMETHING LIKE IT HAPPENED AT THE WORLDS FAIR GAME OF DEATH BECOMES HER MAJESTY MRS BROWN SUGAR TOWN AND COUNTRY LIFE IS BEAUTIFUL PEOPLE WILL TALK OF ANGELS WITH DIRTY FACES OF DEATH 4 LITTLE GIRLS WILL BE GIRLS JUST WANT TO HAVE FUN AND FANCY FREE WILLY 2 THE ADVENTURE HOME ALONE IN THE DARK BLUE WORLD TRADE CENTER STAGE FRIGHT NIGHT FALLS ON MANHATTAN MURDER MYSTERY MEN WITH GUNS OF THE MAGNIFICENT SEVEN BRIDES FOR SEVEN BROTHERS IN TROUBLE EVERY DAY FOR NIGHT AND THE CITY OF JOY RIDE WITH THE DEVIL RIDES OUT COLD FEVER PITCH BLACK HAWK DOWN WITH LOVE AND DEATH WISH V THE FACE OF DEATH WISH UPON A STAR WARS EPISODE V THE EMPIRE STRIKES BACK TO THE BEACH PARTY MONSTER HOUSE OF DRACULA DEAD AND LOVING IT TAKES TWO MEN WENT TO WAR OF THE WORLDS FASTEST INDIAN SUMMER LOVERS AND OTHER STRANGERS WHEN WE MEET JOE BLACK AND WHITE HUNTER BLACK HEART CONDITION RED EYE FOR AN EYE FOR AN EYE OF GOD TOLD ME TO DIE FOR THE BOYS IN THE BAND OF THE HAND THAT ROCKS THE CRADLE WILL ROCK STAR TREK THE MOTION PICTURE BRIDE OF THE WIND AND THE LION KING OF THE JUNGLE 2 JUNGLE BOOK OF LOVE WALKED IN GODS HANDS ON A HARD BODY DOUBLE TAKE THIS JOB AND SHOVE IT HAPPENED ONE NIGHT WITH THE KING AND I WANT TO LIVE FOREVER YOUNG SHERLOCK HOLMES FACES DEATH SHIP OF FOOLS RUSH IN OLD CALIFORNIA SPLIT SECOND BEST OF THE BEST OF EVERYTHING RELATIVE FEAR X THE MAN WITH THE X RAY EYES OF AN ANGEL BABY SECRET OF THE LOST LEGEND OF THE LOST BOYS LIFE WITH FATHER OF THE BRIDE OF FRANKENSTEIN MEETS THE WOLF MAN OF THE YEAR OF THE HORSE IN THE GRAY FLANNEL SUIT” (561 words)

  • Jim Ganon

    Since the same name can be used more than once, how about the trivial solution:

    Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run…
    :)
    Jim

  • http://enigmafoundry.wordpress.com/ enigma_foundry

    Tim:

    I think that you are right about this problem being related to the traveling salesman problem–in fact I think this problem maps directly on to the traveling salesman problem, meaning it requires brute force approach…

    EF

  • Jim Ganon

    Since the same name can be used more than once, how about the trivial solution:

    Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run Lola Run…

    :)
    Jim

  • http://enigmafoundry.wordpress.com eee_eff

    Tim:

    I think that you are right about this problem being related to the traveling salesman problem–in fact I think this problem maps directly on to the traveling salesman problem, meaning it requires brute force approach…

    EF

  • http://www.manifestdensity.net Tom

    It shouldn’t be too hard to brute-force the word numbers problem. You’d just have to segment your sorting algorithm so that it shuttles data to and from your disk smartly. In practice you could probably just allocate a ton of memory and count on your OS to make a swap disk half-cleverly.

    Better still, just shove everything into MySQL and then ask it to sort it. Hey, it might work! Of course, I doubt that’s the sort of approach ITA is looking for.

    I suspect that the Right Way to tackle the problem is to break the spelled-out numbers into the word-tokens that will comprise them (e.g. “eight”, “forty”, “million”, etc). Those’ll be easy to alphabetize — you’ll know what the first column of a properly-sorted list would look like.

    If you can develop an algorithm that can fully explore the space underneath a given token (not simple, but not mind-bendingly difficult I don’t think), then proceed through that space while counting letters (and ignoring order) you can eliminate chunks of the problem’s space, token by token. Narrow it down to the left-most token that contains the 51 billionth letter — the order of the elements belonging to the tokens before it doesn’t matter, thanks to the commutative property. This lets you simply keep a count of total letters instead of keeping each word in memory. Once you hit the target letter, you’ll know the left-most token in whose neighborhood the answer resides. You can repeat the process with the next-to-left-most token; then do it with the next-to-next-to-left-most token; etc. Eventually you’ll have a set of possible answers that’s small enough to sort easily.

    In practice this would be pretty tedious to code (and I’d hate to risk missing a token while defining the first step), so I can’t say I’m champing at the bit to try implementing it. I bet there’s a more elegant solution.

  • http://www.manifestdensity.net Tom

    It shouldn’t be too hard to brute-force the word numbers problem. You’d just have to segment your sorting algorithm so that it shuttles data to and from your disk smartly. In practice you could probably just allocate a ton of memory and count on your OS to make a swap disk half-cleverly.

    Better still, just shove everything into MySQL and then ask it to sort it. Hey, it might work! Of course, I doubt that’s the sort of approach ITA is looking for.

    I suspect that the Right Way to tackle the problem is to break the spelled-out numbers into the word-tokens that will comprise them (e.g. “eight”, “forty”, “million”, etc). Those’ll be easy to alphabetize — you’ll know what the first column of a properly-sorted list would look like.

    If you can develop an algorithm that can fully explore the space underneath a given token (not simple, but not mind-bendingly difficult I don’t think), then proceed through that space while counting letters (and ignoring order) you can eliminate chunks of the problem’s space, token by token. Narrow it down to the left-most token that contains the 51 billionth letter — the order of the elements belonging to the tokens before it doesn’t matter, thanks to the commutative property. This lets you simply keep a count of total letters instead of keeping each word in memory. Once you hit the target letter, you’ll know the left-most token in whose neighborhood the answer resides. You can repeat the process with the next-to-left-most token; then do it with the next-to-next-to-left-most token; etc. Eventually you’ll have a set of possible answers that’s small enough to sort easily.

    In practice this would be pretty tedious to code (and I’d hate to risk missing a token while defining the first step), so I can’t say I’m champing at the bit to try implementing it. I bet there’s a more elegant solution.

  • Brooke

    If you read it out loud and pretend you’re William Shatner, it sounds like some very angsty beat poetry.

  • Brooke

    If you read it out loud and pretend you’re William Shatner, it sounds like some very angsty beat poetry.

  • http://cooly3series1.info/ Jane
  • http://cooly3series1.info/ Jane
  • http://therecool.info/ Hero
  • http://therecool.info/ Hero
  • http://therecool.info/ Hero
  • http://therecool.info/ Hero
  • http://benjamin-meyer.blogspot.com/ Benjamin Meyer

    Rather then words try to find the longest number of movies titles (sling blade runner being a length of 2). I don't know what the longest number of words is, but for movies you can find a chain that is over 320 in length.

  • http://benjamin-meyer.blogspot.com/ Benjamin Meyer

    Rather then words try to find the longest number of movies titles (sling blade runner being a length of 2). I don't know what the longest number of words is, but for movies you can find a chain that is over 320 in length.

  • http://benjamin-meyer.blogspot.com/ Benjamin Meyer

    Rather then words try to find the longest number of movies titles (sling blade runner being a length of 2). I don't know what the longest number of words is, but for movies you can find a chain that is over 320 in length.

Previous post:

Next post: