(Regex Crosswords) Here is a very cool game based on regular expressions.^1 You
ID: 3869570 • Letter: #
Question
(Regex Crosswords) Here is a very cool game based on regular expressions.^1 You are given a grid A[, .. m][1 .. n] (m rows, n columns) as well as m regular expressions R_1, .., R_m corresponding to each row, and n more regular expressions C_1, .., C_n corresponding to each column. The alphabet of all regexes is sigma. Your task is to determine if there is a way of assigning a character in Ipound in each of the cells of A such that the concatenation of the cells in row 1 (from left to right) is a string in L(R_1), row 2's concatenation is a string in L(R_2), as well as for all the other row and column regexes (columns concatenate from top to bottom) We say that this input has a solution if there is such an assignment. Let the language RegexCrossword be the set of all instances (A, R_1, .., R_m, C_1, .., C_n) where A is an m times n grid, R_1, .., R_m, C_1, .., C_n are regexes, and there is a solution to A as described above. Show that RegexCrossword is decidable.Explanation / Answer
We have an algorithm! Now we just need to figure out how to write the function satisfiesAtPos. In Go, it’s frighteningly easy if you understand some regular expression theory and have the patience to scratch around in the source code. For understanding regular expression theory, this article by Russ Cox is an excellent introduction on the subject. And since the author is also one of the core contributors to Go, the algorithm described in this article is also the one implemented in the Go regexp package. Convenient!
I’m not going to re-iterate everything said in that article, and I highly recommend reading it. But as long as you know that regular expressions can be expressed as state machines, you should be able to follow the rest of this discussion.
Normally when you use regular expressions in Go, you call the regexppackage. Specifically, you might call regexp.Compile, like this:
which gives you re, a *Regexp you can use to call Match, Find, or Replace. But what does Go do internally to get you that Regexp struct? It’s very interesting.
When you call regexp.Compile, a number of things happen:
Here’s a simple program that performs the steps described above, and prints out the resulting program (state machine):
(Go Playground)
Running this gives us the following output:
This may seem cryptic at first, but it’s actually not hard to understand. The output describes a state machine. The first number on each line is the ID of the node. The next word describes the type of node. It could be cap, which is short for capture, and corresponds to the start and end of match groups in the regex. rune1 describes a node that exactly matches a specific rune. alt describes a node that merely exists to create a fork in the road: one path leads to the first argument, and the other to the second argument. And so on for different types of nodes. Every node has an output, described by the final number, which tells us the ID of the next node after this one. All in all, the above gives us a state machine diagram that looks more or less
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.