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.
The Technology Liberation Front is the tech policy blog dedicated to keeping politicians' hands off the 'net and everything else related to technology.