{"id":184,"date":"2012-04-09T04:23:26","date_gmt":"2012-04-09T04:23:26","guid":{"rendered":"http:\/\/alexboisvert.com\/musings\/?p=184"},"modified":"2012-04-13T15:22:18","modified_gmt":"2012-04-13T15:22:18","slug":"fillbot-jr-initial-results","status":"publish","type":"post","link":"https:\/\/alexboisvert.com\/musings\/2012\/04\/09\/fillbot-jr-initial-results\/","title":{"rendered":"FillBot Jr.: Initial Results"},"content":{"rendered":"

If you’re a regular on this blog, you may remember that I floated the idea of making a crossword-filling algorithm<\/a> just to see how hard it would be. I wasn’t sure I’d ever get around to making it but today I was sick and bedridden and bored (yay?) so I spent a few hours coding something up. If you’d like to see more or less what I’ve done and how it performs on a sample themeless puzzle<\/a>, follow me to the rest of this post.<\/p>\n

<\/p>\n

Here’s the basics of it: MySQL has a terrific full-text match based on the tf*idf algorithm<\/a> which I’m using to find good fits for clue\/entry pairs. For instance, if I have a four-letter word for “Fried Cajun side” you can run the MySQL query
\n[SQL]
\nSELECT Entry,
\nMATCH (
\nClue
\n)
\nAGAINST (
\n‘Fried Cajun Side’
\n) AS Score
\nFROM `Clues`
\nWHERE MATCH (
\nClue
\n)
\nAGAINST (
\n‘Fried Cajun Side’
\n)
\nAND Entry LIKE ‘____’
\nLIMIT 0 , 10
\n[\/SQL]
\nand get the following results:<\/p>\n

\r\nEntry \tScore\r\nSLAW \t15.20439338684082\r\nOKRA \t14.877264976501465\r\nOKRA \t9.801589965820312\r\nOKRA \t9.801589965820312\r\nOKRA \t9.801589965820312\r\nOKRA \t9.801589965820312\r\nOKRA \t9.801589965820312\r\nOKRA \t9.801589965820312\r\nROUX \t9.69262981414795\r\nOKRA \t9.69262981414795\r\n<\/pre>\n
(OKRA appears several times because it has matched with several different clues.)  Of course, if you knew even one of the letters, this process would immediately give you the correct answer (OKRA).<\/p>\n
At each step of the algorithm, I’m taking these results and adding the “Score” to the difference between the top entry and the second-ranked entry.  The entry with the highest sum gets added to the grid and the process is restarted.  For now I’m not doing any backtracking; I just want to see how this algorithm will do simply marching ahead and filling in entries.<\/p>\n
Ready?  Let’s step through with it on Brendan’s grid<\/a> and see how it does.<\/p>\n
Step 1: 49 ACROSS: Electrical resistance symbol — OMEGA<\/i><\/strong>
\nWe’re off to a good start.  This clue was an exact match for one I had in my database, and was a much better match than the second-best possibility (which turned out to be SAILS, for whatever reason).<\/p>\n
Step 2: 10 DOWN: 1961 Charlton Heston epic — ELCID
\nStep 3: 39 DOWN: Renault vehicle marketed to the U.S. — LECAR
\nStep 4: 33 DOWN: North Carolina town or college — ELON<\/i><\/strong>
\nThese are all stone-cold gimmes for anyone who does a lot of crosswords, so it’s nice to see the algorithm doing well on them too.  Nice to see it reject DUKE for 33-Down; the database’s clue of “North Carolina college town” was a great match.<\/p>\n
Step 5: 57 ACROSS: ___ Center (home of the Nets and Devils) — IZOD
\nStep 6: 1 ACROSS: Model airplane material — BALSA<\/i><\/strong>
\nI was shocked that the algorithm got the IZOD Center so quickly, I guess because I didn’t know this little bit of trivia.  And now that I’ve learned it, it’s already out of date, since those teams have moved to the Prudential Center.  Oh well.<\/p>\n
Step 7: 6 DOWN: Immune system stuff — SHREDBLOODCELLS<\/i><\/strong>
\nWell, we had to mess up eventually.  A human would never ever have entered this into the grid, but the bot sees the clue in its database that reads [Attack the immune system?] and thinks it’s got a good match.  Maybe I need some logic for when the clue in the database has a question mark?  This seems especially important for long entries.  (And incidentally, I don’t have WHITEBLOODCELLS in my database, which is shocking, considering it’s a totally legit 15-letter answer.  I’ll have to data-mine Brendan’s puzzle after I’m done here to add it.)<\/p>\n
Step 8: 59 ACROSS: Pummels — ROUTS<\/i><\/strong>
\nAh, shoot, we’ve messed up again even though this one doesn’t look quite so bad.  The intended answer was PELTS.  There’s only one five-letter entry in my database with the word “pummels” in it, so it gets the green light here.<\/p>\n
Step 9: 35 DOWN: Clothing joint? — SEAM
\nStep 10: 8 DOWN: Miso soup enhancer — MSG
\nStep 11: 60 ACROSS: Choosing word — EENY<\/i><\/strong>
\nYeah, it’s doing fine on these, but let me show the grid at this point:<\/p>\n
\r\nB A L S A . . S _ M . _ E _ _\r\n_ _ _ _ _ . _ H _ S . _ L _ _\r\n_ _ _ _ _ . _ R _ G _ _ C _ _\r\n_ _ _ _ _ _ _ E _ . _ _ I _ _\r\n. . . _ _ _ _ D _ _ _ _ D _ _\r\n_ _ _ _ _ _ _ B . _ _ _ . . .\r\n_ _ _ _ . . _ L _ _ _ _ _ _ E\r\n_ _ _ . . S _ O _ _ . . _ _ L\r\n_ _ _ _ L E _ O _ . . _ _ _ O\r\n. . . _ E A . D _ _ _ _ _ _ N\r\n_ _ _ _ C M _ C _ _ _ _ . . .\r\nO M E G A . _ E _ _ _ _ _ _ _\r\n_ _ _ _ R _ _ L _ . _ _ _ _ _\r\nI Z O D . _ _ L _ . R O U T S\r\nE E N Y . _ _ S . . _ _ _ _ _\r\n<\/pre>\n
Anything jump out at you? Something sure jumps out at me: we’re hardly crossing any words at all.  We absolutely HAVE to use the information we’ve got in terms of the crossing words or we’ll never get anywhere.  The algorithm isn’t doing that, and definitely needs a push in that direction.<\/p>\n
Okay, look at the above grid one more time.  What answer can you put in next, even without looking at the clues?  I see an obvious one: _M_ZE has to<\/b> be AMAZE, right?  Let’s see what the bot fills in next.<\/p>\n
Step 12: 27 ACROSS: Chicago-based insurance company that sponsors Manchester United’s uniforms — RIO<\/i><\/strong>
\nOkay … that’s wrong, first of all, and why didn’t you fill in AMAZE?<\/p>\n
So … this needs work.  Any thoughts on how to make this better?<\/p>\n","protected":false},"excerpt":{"rendered":"
If you’re a regular on this blog, you may remember that I floated the idea of making a crossword-filling algorithm just to see how hard it would be. I wasn’t sure I’d ever get around to making it but today … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,11,5],"tags":[],"class_list":["post-184","post","type-post","status-publish","format-standard","hentry","category-coding","category-fillbot-jr","category-puzzles"],"_links":{"self":[{"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/posts\/184","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/comments?post=184"}],"version-history":[{"count":11,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/posts\/184\/revisions"}],"predecessor-version":[{"id":196,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/posts\/184\/revisions\/196"}],"wp:attachment":[{"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/media?parent=184"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/categories?post=184"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/tags?post=184"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}