3 ms·
After 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
by aurbano 11y ago
After 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.
- sizzzzlerz 11y agoSeems like this puzzle might be a candidate for solving using Donald Knuth's Dancing Links algorithm. Setting it up, however, might be as much work as solving it manually.
- sah2ed 11y agoWhat books come highly recommended for learning CSP?
- beerbajay 11y agoI wrote my master's thesis in Constraint Programming. The textbook for my CP course was Apt's "Principles of Constraint Programming"[1], but I have to admit to barely using it. Most of the books and "introductions" to CP which I've read have been lacking in either rigor or clarity; many important details are glossed over, partly I think, because of CP's development from other kinds of optimization/satisfaction programming. When learning, I mostly used lecture notes from Christian Schulte (from KTH in Sweden) and Pierre Flener (from Uppsala University, also in Sweden). I can unfortunately not find these accessible online at the moment. [1] http://www.amazon.com/Principles-Constraint-Programming-Krzysztof-Apt/dp/0521125499 http://www.amazon.com/Principles-Constraint-Programming-Krzy...
- malisper 11y agoI've actually learned everything I know about CSP from chapter six of Artificial Intelligence a Modern Approach.