Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving the KAYAK crossword puzzle with code

github.com

Post reply on HN
Print view View original

11–20 of 22 posts

Re: Solving the KAYAK crossword puzzle with code

#11

Post by column »

brusch64 wrote: post #10
column wrote: post #9

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"

How do you do OCR in Paint.Net ?

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.

Re: Solving the KAYAK crossword puzzle with code

#12

Post by column »

column wrote: post #9

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"

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

Re: Solving the KAYAK crossword puzzle with code

#13

Post by bvm »

skellystudios wrote: post #8
yen223 wrote: post #6

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!

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

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.

Re: Solving the KAYAK crossword puzzle with code

#14

Post by jjnoakes »

column wrote: post #9

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"

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

Re: Solving the KAYAK crossword puzzle with code

#15

Post by column »

jjnoakes wrote: post #14
column wrote: post #9

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"

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

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)

Re: Solving the KAYAK crossword puzzle with code

#16

Post by brusch64 »

column wrote: post #11
brusch64 wrote: post #10

Earlier quoted context omitted.

How do you do OCR in Paint.Net ?

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.

Sorry I misunderstood your comment. Was just wondering how you are doing OCR in Paint.Net. Thank you for your clarification.

Re: Solving the KAYAK crossword puzzle with code

#18

Post by gjm11 »

skellystudios wrote: post #8
yen223 wrote: post #6

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!

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

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

Re: Solving the KAYAK crossword puzzle with code

#19

Post by xigency »

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.

Re: Solving the KAYAK crossword puzzle with code

#20

Post by pacofvf »

column wrote: post #15
jjnoakes wrote: post #14

Earlier quoted context omitted.

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

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 wo…

for vertical, you could transpose the crossword then Ctrl+F, just being aware that the result has its columns and rows switched.
Post reply on HN