6 ms·
The Berkeley Crossword Solver
- _eigenfoo 4y agoI wrote some of my thoughts on the BCS here. tldr: I don’t think BCS outperforms humans. https://twitter.com/_eigenfoo/status/1528427650187943941 https://twitter.com/_eigenfoo/status/1528427650187943941
- sblom 4y agoIs this a totally different thing than Dr. Fill [1]? [1]: https://slate.com/technology/2021/04/american-crossword-puzzle-tournament-dr-fill-artificial-intelligence.html https://slate.com/technology/2021/04/american-crossword-puzz...
- mjlawson 4y agoIt is. The results section indicate that BCS performs better than Dr. Fill by a significant amount. I'm curious how well this performs on the New York Times Thursday puzzles, and specifically whether or not it can handle rebus answers where multiple letters can exist in a single square.
- banana_giraffe 4y agoOr something like November 26, 2020, with what is kind of an anti-rebus and letters that span more than one cell, or January 27, 2022 with musical notation for repeated letters in a word, or February 7, 2019 which involved writing outside the puzzle grid. Thursdays can sometimes hurt my head.
- texaslonghorn5 4y agoAre there any nontrivial connections to term rewriting in this work?
- msla 4y agoIs there much new work being done on automatic crossword puzzle generation? I could only find one paper in a very brief Google search: > AUTOMATIC GENERATION OF CROSSWORD PUZZLES > LEONARDO RIGUTINI, MICHELANGELO DILIGENTI, MARCO MAGGINI and MARCO GORI https://doi.org/10.1142/S0218213012500145 https://doi.org/10.1142/S0218213012500145
- saulpw 4y agoThere are plenty of automatically generated puzzles. Most of the crossword puzzle books in the supermarket (without an editor or bylines) are completely auto-generated. They are like verbal Sudoku with trivia. They have no soul. "Real" crosswords have a fresh theme (the 3-5 longest entries that usually stretch across the entire puzzle) and fresh clues if not answers for the fill. Maybe GPT-x could come up with fresh clues (though you would still need an editor), but coming up with a fresh theme would be the truly challenging part.
- dalke 4y agoI am neither good at crossword puzzles nor at making them. I am curious about how hard it is to make a simple one. I'm planning to put together a sort of activity book for a user group meeting this fall, for the open source package "RDKit", which is used in cheminformatics and related fields. I thought it might be fun to have a cheminformatics crossword puzzle, with words and ideas from my field. For example, "Ran for US President" with the answer "[Au].O"; those being a way to denote "Gold" and "water" in the SMILES notation. Saying with SMILES, there are some interesting permutation possibilities, like O=S or S=O for sulfur monoxide. With a theme around, say, edible chemicals (caffeine = "Cn1c(=O)c2c(ncn2C)n(C)c1=O" and permutations thereof, vanillin = "c1(C=O)cc(OC)c(O)cc1", etc). So I've got an esoteric theme, and am looking for pointers on how to put them together.
- candlemas 4y agoI'd like to see its performance on New York Times crosswords split into decades. I suspect they've been getting dumbed down.
- anothernewdude 4y agoI'm looking for a good online cryptic crossword. Something harder than Lovatt's Cryptic. The Guardian is no good, I can look at their solutions and still have no idea why those are the answers.
- billfruit 4y agoMay be the Guardian one needs a Chambers dictionary to solve it? But still, is there a good guide to get into Cryptics?
- tominous 4y agoCracking the Cryptic, e.g.: https://youtu.be/ecytVCusIeY https://youtu.be/ecytVCusIeY It's mostly a variant sudoku channel but Mark Goodliffe is an insanely good cryptic crossword solver, and both Simon and Mark are good teachers. Beyond the intro the key skills are: parsing the clues into definition and wordplay, knowing signifiers for different types of wordplay, recognising common abbreviations (there are lists a web search away), recalling short synonyms, and anagramming. If you want to get your mind blown I highly recommend spending the $2 for Cracking the Cryptic's Patreon to watch Mark solve the Monthly Club Special using almost pure wordplay and whatever string manipulation coprocessor he has in his head (which also seems to work for sudoku too).
- caminante 4y agoHow does the "competition" work? Is it "live"? Is it online? Is there an accuracy component? I'm intrigued how the NYT ran a crossword competition with thousands of competitors. > Proverb and Dr. Fill. Proverb is a 1998 system that ranked 213th out of 252 competitors in the tournament. > Dr. Fill’s first competition was in ACPT 2012, and it ranked 141st out of 650 competitors. > We teamed up with Dr. Fill’s creator Matt Ginsberg and combined an early version of our QA system with Dr. Fill’s search procedure to win first place in the 2021 ACPT against over a thousand competitors.
- dekhn 4y agoIf I remember correctly my dad would go to New York City to compete in person. If you make mistakes you're not going to win.
- dataflow 4y agoSo if I had to come up with a crossword solver, the first (dumb) approach I would try is the following: - Come up with guesses for each clue (somehow—let's ignore the "how" for now) - Prune all guesses whose letters mismatch with all the guesses for overlapping words - Hopefully, you now have only one consistent solution set Could someone explain why this approach doesn't work, and why you need probabilistic approaches?
- atwood22 4y agoHow do you decide which guess to prune? Likely almost every guess would have a conflict, so if the space of possibly changes would be combinatorially large.
- dataflow 4y agoIf your guesses for 1-across are AAA and BBB, and your guesses for 1-down are ABC and DEF, and they share their first letters in common, then you necessarily have to prune DEF and BBB. I don't think there's a combinatorial explosion anywhere here right?
- atwood22 4y agoIn your contrived example, you only know the right answer after considering all four possible combinations. That is a combinatorial explosion when there are only two choices to make.
- dataflow 4y agoNo, you don't need to do it with such a slow algorithm like that. There are only 26 possibilities for a given square. All you need is to track the set of possible letters for each square in each direction (52 bits of information—you can even literally fit it into a 64-bit integer). Then for each guess going across, cross it off your list if its corresponding letter isn't in the set of letters going down, and vice-versa. It should be pretty darn quick without any exponential growth.
- tokamak-teapot 4y agoFor those who do cryptic crosswords, CrosswordGenius [1] on iOS (Android coming apparently) will solve clues for you - and explain the logic it used! This is extremely helpful when you aren’t familiar with a particular setter’s style. If you’ve guessed an answer (and if you’re on a mobile app you might have already been able to verify that it’s correct) you may not be sure how the clue maps to it. Example: Digital projection tempered elation (7) I believe the answer is: TOENAIL 'digital projection' is the definition. (protection on a digit of the foot) 'tempered elation' is the wordplay. 'tempered' indicates an anagram (temper can mean to adjust or modify). 'elation' is an anagram of 'TOENAIL'. [1] https://www.crosswordgenius.com/ https://www.crosswordgenius.com/
- thom 4y agoUsually my approach is: 1) try to answer straight away, 2) try to answer once I have some letters from other clues, 3) use a thesaurus, 4) use an anagram solver, 5) wait for tomorrow's paper. I already feel wretched about 3/4, I'm not sure I want to cheat more than that. But sometimes this completely falls down and I have no idea where something comes from, e.g.: "Theatre of war where activity was uncovered (8)" is WINDMILL which still baffles me.
- mechanical_berk 4y agofifteensquared.net is great for explained answers, see eg http://www.fifteensquared.net/2018/03/09/independent-9798-phi/ http://www.fifteensquared.net/2018/03/09/independent-9798-ph... for the WINDMILL explanation.
- thom 4y agoOh, lovely, thank you. I figured it had to be the theatre and still didn't get it. This hobby regularly makes me feel dumb. :)
- 2143 4y agobtw, do you happen to be British? The reason I ask is that only British people seem to add "lovely" in their sentences. Also, I now learnt that the WINDMILL answer refers to something in London. I don't know how outsiders — say a random person from Argentina — is supposed to know that.