Tuesday, May 21, 2013

A partial crossword solver in Python

A Cryptic Crossword Clue Solver ←

Saw this via Twitter.

It is a partial crossword solver, because it only helps solve a particular category of crossword clues - those in which the clue (which is usually a sentence or phrase) contains both a "definition" of the answer as well a hint of some kind that leads to the same answer. This solver tries to compute the answer using both the definition and the hint, and checks whether the results match. Ingenious.

I found it interesting because this is a somewhat difficult problem, and yet the author managed to create a solution (involving NLTK and parsing) that works in many, if not all cases.

Also, long ago, in college days, I had written another kind of partial crossword solver (in BASIC); it was much simpler, using a brute force method - what it did was help solve the kind of crossword clues in which the answer is a permutation of a substring of the characters comprising the clue sentence or phrase. The program would generate and display on the screen, all possible permutations of all possible substrings of the sentence, that were of the same length as the answer. Then you had to view those permutations and guess whether any of them was the right answer, based on the clue.

I wrote the permutation-generation code by hand, but saw recently that the Python itertools module has methods to generate permutations (as well as combinations) from sequences:




- Vasudev Ram

No comments: