Solving the KAYAK crossword puzzle with code

Solving the KAYAK crossword puzzle with code(github.com)

34 points by stepanbujnak 11 years ago | 21 comments

nhstanley 11 years ago |

Was the use of ANN necessary, or simply done because it was cool to do? Because at least in my mind it looks like extracting the text and running a brute force program on it would be faster, no?

biot 11 years ago | |

If my reading is correct, the neural network was used to OCR the image, extracting the text. From there, it is indeed a simple brute-force string search.

quadrature 11 years ago | | |

Yeah, but the type is pretty regular and and the alphabet is small. I bet you could just use convolution.

stepanbujnak 11 years ago | |

The use of ANN was completely unnecessary, as there are only 3 characters in the crossword puzzle. I wanted to try out the OpenCV ANN implementation though and since it's not a real world application it doesn't really matter.

yen223 11 years ago |

FWIW that's not a crossword puzzle. As a crossword enthusiast, I would be very interested in the implementation of an AI-backed crossword puzzle solver!

skellystudios 11 years ago | |

For my masters thesis I wrote some software to solve UK-style cryptic crosswords[1].

We're cleaning up the code now for release as an AI paper, so as soon as we're done I'll release the code on Github.

[1] http://en.wikipedia.org/wiki/Cryptic_crossword

bvm 11 years ago | | |

What a great idea. What's your success rate like?

Cryptic crosswords (at least good ones) play with conventions so much, I imagine it must be quite a challenge.

gjm11 11 years ago | | |

Excellent! How does its performance compare with Crossword Maestro (http://www.crosswordtools.com/cm/) which I think is the current state of the art?

splike 11 years ago | |

Just a thought, but I bet word2vec would be a pretty good starting point for a crossword solver

https://code.google.com/p/word2vec/

column 11 years ago |

How I did it:

0. Download and install Tesseract https://code.google.com/p/tesseract-ocr/

1. Crop and adjust curves of the image in Paint.Net (= get a better contrast) to ease OCR

2. Save as PNG in the folder of Tesseract

3. Open cmd in Tesseract folder, type tesseract kayak.png kayak (produces kayak.txt)

4. Open kayak.txt in Notepad++, remove empty lines (to have correct indexes), CTRL+F "KAYAK"

jjnoakes 11 years ago | |

Doesn't this only work if the word is west-to-east? Seems like it'd fail for any other orientation (there are 7 others).

(Well, for a palindrome, it works for east-to-west too - so I guess you missed 6).

column 11 years ago | | |

You are correct. However, it is stated that 'KAYAK' appears only once and it seems to me that CTRL+Fing should be the first thing to do when searching for a string in a relatively small text. The next step, had the CTRL+F failed, would have been to search for "KAYAK" vertically/diagonally programmatically.

(on a sidenote, you're counting is incorrect, as it is a palindrome there really is only 4 directions for the word to appear: W-E, N-S, NW-SE, NE-SW)

column 11 years ago | |

This is the output of Tesseract (once empty lines are removed):

    AAYKAKAYKAYYKKAAKAYAAAYKYKYAYK
    KYYAKYAAAYKAAKKYAKKKAAAKAAYKAA
    KKKYAKAKAYKKYKKYKKAKYAAAAKAAKK
    YKAAKYAAKKKKKAYAYYYYYAAKAAKKKK
    KKAYYAAKKYYAYAAKAAKKAAYKAKKAAK
    KKAAAKAAAKKAKKKYAAAYKYAYAKYKAA
    KKYKAAAAAAAAAAKKAAAKYYAKAKAKKY
    KKKKKKAKYYKYYKKAAYAKAAAKYAKKAA
    KAKKAKAYKAAYAKYYKKAYKKKAAAAAKA
    KKAKAKAKAAAKAYAYKAKAYYAYKKAKYY
    AAAYAKKKAKKAKYKAYKKAKKYKAAKKYY
    YKKKYKKYAAAKKKKAKAYKKKKKAAKKKY
    KKAKAYKAAKAKKYYAKAYAAKYAAAAAAA
    AAAAKKYAAKKAAYKKAAAYAYAKYAKAYK
    AKKAKKAYKAAYKYKAKYAAKKYKKKKKKA
    KYKAAKKYAYKAKKKYKAKAYAYKYAAAKK
    KAYYKKAKYKAYAAKAYAAYYYAKKYKYKK
    KKKKAKAYAAAKKAYAYKKYAKAAAAYKAY
    AYKAKKKAAKAKAYAAAKKYKKAYKAYAYY
    KYAYKAYAKAKYYKYKAKAAYKYKKAYKAK
    AKAKKAKKAKKKKAAAKYYYYKAKAAAAAK
    KAKYYKAKKYKYAKYAAAAAKAKAYAAKKA
    KKAAAKKAKAKKAAKAYAAYAAAKKAAYYA
    KAKKYYKKAYAYKKAKKYYKYKYKKAAAKA

brusch64 11 years ago | |

How do you do OCR in Paint.Net ?

column 11 years ago | | |

In Paint.Net I only adjusted the curves (CTRL+SHIFT+M) to get a better contrast. The OCR is done by Tesseract. This solution is all about using the right tool for the job.

garethadams 11 years ago |

This seems like a good place to link to the UsVsTh3m one-word-wordsearch generator:

http://games.usvsth3m.com/one-word-wordsearch/#MTAsS0FZQUssN...

column 11 years ago | |

In the source: "bastardTouchMoveWhatTheHellIsWrongWithMobileBrowsersSeriously"

xigency 11 years ago |

Found it in a couple minutes by hand. I started from the position (3,3) and circled the board looking for "Y" surrounded by two A's, and checking for the phrase. Working inward it's only a matter of time before you find it. There are also the borders to check then.

gokhan 11 years ago |

Similar:

https://projecteuler.net/problem=11

AAYKAKAYKAYYKKAAKAYAAAYKYKYAYK KYYAKYAAAYKAAKKYAKKKAAAKAAYKAA KKKYAKAKAYKKYKKYKKAKYAAAAKAAKK YKAAKYAAKKKKKAYAYYYYYAAKAAKKKK KKAYYAAKKYYAYAAKAAKKAAYKAKKAAK KKAAAKAAAKKAKKKYAAAYKYAYAKYKAA KKYKAAAAAAAAAAKKAAAKYYAKAKAKKY KKKKKKAKYYKYYKKAAYAKAAAKYAKKAA KAKKAKAYKAAYAKYYKKAYKKKAAAAAKA KKAKAKAKAAAKAYAYKAKAYYAYKKAKYY AAAYAKKKAKKAKYKAYKKAKKYKAAKKYY YKKKYKKYAAAKKKKAKAYKKKKKAAKKKY KKAKAYKAAKAKKYYAKAYAAKYAAAAAAA AAAAKKYAAKKAAYKKAAAYAYAKYAKAYK AKKAKKAYKAAYKYKAKYAAKKYKKKKKKA KYKAAKKYAYKAKKKYKAKAYAYKYAAAKK KAYYKKAKYKAYAAKAYAAYYYAKKYKYKK KKKKAKAYAAAKKAYAYKKYAKAAAAYKAY AYKAKKKAAKAKAYAAAKKYKKAYKAYAYY KYAYKAYAKAKYYKYKAKAAYKYKKAYKAK AKAKKAKKAKKKKAAAKYYYYKAKAAAAAK KAKYYKAKKYKYAKYAAAAAKAKAYAAKKA KKAAAKKAKAKKAAKAYAAYAAAKKAAYYA KAKKYYKKAYAYKKAKKYYKYKYKKAAAKA