6 ms·
Regular Expression Crossword Puzzle
- overlordalex 11y agoHere's a nice site for these: https://regexcrossword.com/ https://regexcrossword.com/ The default puzzles are a bit basic, but there's a large amount of player-created puzzles that are great.
- padolsey 11y agoI love these! I tried automating the creation of them a while ago[1] (refreshing the page creates a new one). I should probably revisit it though as the generated puzzles aren't tricky enough.. [1] http://padolsey.github.io/redoku/ http://padolsey.github.io/redoku/
- diziet 11y agoThere's also an extension for this: https://github.com/wolfascu/regex-crossword-goodies https://github.com/wolfascu/regex-crossword-goodies
- jgeralnik 11y agoThe original source for this puzzle was the 2013 MIT Mystery Hunt: http://www.mit.edu/~puzzle/2013/coinheist.com/rubik/a_regular_crossword/index.html http://www.mit.edu/~puzzle/2013/coinheist.com/rubik/a_regula...
- schoen 11y agoand it is credited to "Dan Gulotta, based on an idea by Palmer Mebane". (It's too bad when people republish puzzles without explaining where they're from or linking to the original.)
- gregable 11y agoAwesome, thanks! I've added attributions on both the blog post and the puzzle page. It's a really fun puzzle, the author of it definitely deserves credit.
- schoen 11y agoThanks for updating your post with the attributions!
- pan69 11y agoHow about that for a CAPTCHA. :)
- kaoD 11y agoCAPTCHAs should be easy to solve for humans and hard for computers, not the other way around :P
- anon4 11y agoOne note about the interface - the rotation arrows are very confusing. You should always put the curve on top, rather than on bottom, since most people think of rotation directions based on the movement of a point on the top of the arc. Additionally, the left arrow rotates right, while the right arrow rotates left.
- jcoffland 11y agoWhen the top moves left the bottom moves right.
- gregable 11y agoI reversed the order of the arrows, but I'm not sure about flipping the glyphs. Those are the standard unicode glyphs for rotation arrows, I didn't want to use any images on the page. I suppose I could use CSS to invert them.
- beerbajay 11y agoI solved this a while back. It's a bit challenging, but mostly due to the fact that the clues aren't really completely determining the solution, so you can't deduce each square like you can in e.g. sudoku. You have to make some guesses and then backtrack if they're wrong.
- scr4ve 11y agoFWIW, I found that you can either deterministically deduce a cell or prove that the choice is irrelevant for at least two of the conditions. In this case, you can fill it with the solution that gives you the most flexibility for the third.
- Apanatshka 11y agoIt took me a while, but I solved it without any guessing+backtracking.
- shimo5037 11y agoSame. Definitely doable. It did take me a guesstimated 1.5h though.
- mijoharas 11y agoAgreed, you can definitely arrive at a deterministic answer. (takes a lot longer though.)
- aurbano 11y agoAfter spending most of the morning solving it manually I was thinking about how an algorithm might work for this. Perhaps converting each regex into a DFA, but there are too many dependencies with all the other regexes. Any ideas on how to avoid brute forcing it?
- nly 11y agoMy thought was to try ragel with the intersection operator, but for most of them it just result in something that'll match any character... maybe I'm doing something wrong.
- chpatrick 11y agoYou can turn it into an SMT problem and solve it with a standard solver. In Haskell it's quite beautiful as you can write code that's basically identical to writing a parser, and then generate inputs that satisfy the parser magically. https://github.com/ekmett/ersatz/tree/master/examples/regexp-grid https://github.com/ekmett/ersatz/tree/master/examples/regexp...
- WildUtah 11y agoThese regexes aren't really regular expressions. They're PERL regexes with backreferences so a DFA won't do.
- malisper 11y agoThis kind of puzzle falls under a general class of problems called Constraint Satisfaction Problems. Sudoku puzzles, map coloring, and cryptarithms are all examples of CSPs. A CSP is defined by a bunch of variables, each of which can take on some values in their domain (In this case each cell is a variable, and initially their domain is all 26 letters.) and a group of arbitrary constraints over the variables (the regexes). One method of solving a CSP is to keep a set that initially contains all of the variables. On each iteration you choose a variable from the set and remove all values in its domain that are impossible given the constraints containing the variable and the domains of the other variables in those constraints. Then you add all of those other variables to the set because they are now restricted more than before. You keep doing the above until you get stuck (which may or may not happen). You then start guessing. There are a bunch of heuristics about how you should choose which variable to guess (eg the variable with the smallest domain). Once you have made your guess, you then add all of the variables back to the set. If you find out the puzzle is impossible, you backtrack to the last guess you made. I believe there are ways you can determine which guess was the problem and immediately backtrack to there.
- osoba 11y agoCould you move the puzzle on amazon a few (20?) pixels to the right, the.(.)(.)(.)(.)\4\3\2\1. regex gets cut off on the left when you rotate http://i.imgur.com/qcG1kav.png http://i.imgur.com/qcG1kav.png
- mrcactu5 11y agoSites like http://regexper.com/#.*OXR.* http://regexper.com/#.*OXR.* help interpret the clues without solving the puzzles
- rileymat2 11y agoAssuming a puzzle had a single solution: How computationally hard would it be to prove that one solution was the only solution?
- almost 11y agoI had a lot of fun writing a program to solve this puzzle last year. I wrote about it here: http://almostobsolete.net/regex-crossword/part1.html http://almostobsolete.net/regex-crossword/part1.html The Haskell code is also on GitHub
- phamilton 11y agoI did this puzzle with a coworker and regular "commits" ( photocopy and add a version number ) was pretty useful. We botched it more than once and it was nice being able to revert.
- Drdrdrq 11y agoGreat puzzle, too bad it doesn't have a single solution...
- gregable 11y agoI'm fairly sure there is only one solution.