After solving Word Numbers, maybe I should solve ITA’s other current puzzle, Sling Blade Runner. I wasn’t sure how to solve it, so I made a pretty picture:
ITA provides you a list of over 6,500 movies, and the objective is to make as long a chain as possible of overlapping titles: Sling Blade Runner, License to kill a Mockingbird. Every dot in the graph is a movie, every arrow connecting them indicating their titles overlap. In comments on Reddit, a few people found solutions of around 230 titles.
Puzzles are useful to learn. Since I’m not an engineer, they force me to learn about computer science theory I never learned. Looking up graph problems of the sort, I found out that this class of problem is defined as a ‘hard’, and it is far too computationally intensive to try every possibility (’brute force’). The only way to solve it elegantly is to use shortcuts, and those depend on the type of graph in question - which is why I decided it might be interesting to have an actual picture.
Tools like graphviz are slow for very large graphs, so this picture doesn’t represent the whole graph. Still pretty, no?
2 comments ↓
If you solve them all ITA won’t be able to find any more candidates!! stop it!
How did you use graphviz? source code would be cool!
We should post the fullsize graph on our StandoutWall
A full-size graph would be pretty fun, but it might take a couple days of CPU. Maybe we could use an EC2 instance
Graphviz is open source and can be used via a command-line or a GUI. It is awesome, and the dot language is pretty straight-forward. Here’s an example .dot file:
digraph world {
“A CRY IN THE DARK” -> “THE DARK CRYSTAL”
“A CRY IN THE DARK” -> “THE DARK HALF”
}
Leave a Comment