Qat Equation Solver

code-golf

Qat is a tool that lets you search for words matching a given pattern, often used by crossword and other word puzzle writers and solvers.

In this challenge, you will have to implement a specific part of Qat, namely a subset of the "equation solver".

Equations

The output of a Qat query depends on the dictionary you use (i.e. the list of words you are pattern matching against) and the pattern you input.

The most basic thing you can do in Qat is define simple patterns, which are sequences of symbols which should match some words (similar to regular expressions). In this problem, we will only include two different types of symbols:

• A lowercase letter, which just matches that letter
• A period ., which can match any letter (equivalent to [a-z]).

For example, using the base Qat dictionary, the simple pattern l.......v matches leitmotiv and lermontov, so the output is leitmotiv lermontov.

(There are many more complicated patterns you can also define, but we'll ignore them for this challenge.)

In Qat, you can also describe equations. From the website (description simplified and modified to only use our simple patterns):

Qat's equation solver is based around variables, represented by capital letters from A to Z.

An equation consists of a left-hand side (LHS) followed by an equals sign = and a right-hand side (RHS).

The LHS consists of a sequence of variables and simple patterns. Qat will try to assign strings of characters to the variables so that the whole LHS matches the RHS.

The RHS can be:

• a simple pattern, which matches any word that fits that pattern [which is then output as a result], or
• a simple pattern enclosed by round brackets, which matches any sequence of letters that fits that pattern. In this case the equation in question is not included in the table of results.

Multiple equations are separated by semicolons, in which case all of the equations must be satisfied, the solution to each of the equations is shown in sequence. If there are multiple valid solutions, each of them is output in sequence.

Examples

It's probably easiest to understand with some examples.

Suppose we are using the dictionary [one two onetwo onesix]. Then:

• The pattern A=o.. is an equation which says "A must match a three letter word starting with 'o'"; the only option here is one, so the output is one.
• The pattern A=o..;A=..e is an equation which says "A must match a three letter word starting with 'o' and also a three letter word ending with 'e'"; the only option here is one, so the output is one one (because there are two equations).
• The pattern A=... says "A must match a three letter word"; there are two options here (one and two), so the output is one; two.
• The pattern A=oneB;B=... says "A must one prepended to B, where B is a three-letter word"; the only option here is that B is two, making A equal to onetwo. Thus, the output is onetwo two. (Note the solutions to the equations are output in order.)
• The pattern A=oneB;B=(...) says "A must one prepended to B, where B is a three-letter string of characters"; in this case, this is equivalent to saying A=one..., which means the output is onetwo; onesix. (Note that the solution to the second equation is not output because of the parentheses.)
• The pattern o..A=ones.. says "look for a sequence of characters A where the pattern o..A can match ones...". The only option in this case is that A equals six, in which case we find a word in the dictionary which matches both o..six and ones..; the only solution here is onesix, so this produces the output onesix.
• The pattern A=...;B=...;C=AB says "C must be the combination of two three-letter words"; the output is thus one two onetwo.

Challenge

Given a dictionary (i.e. a list of valid words) and a pattern, produce the sequence of solutions to the equations matching the pattern. You can take in the input pattern in any format you want as long as it is reasonable and has a direct mapping to the format described above, and output in any reasonable format.

You can assume that the dictionary contains only strings of lowercase letters and the pattern only contains a sequence of valid equations which has at least one solution.

Test cases

Standard loopholes are forbidden. Since this is code-golf, the shortest program wins.

Questions

Should I even include . in the simple patterns? Would it be better to just have a simple pattern be a sequence of lowercase alphabetic characters?

Should I include the optional brackets indicating the result is not a word in the dictionary?

Qat Equation Solver

Should I include the bracket

Should I include the optional brackets indicating the result is not a word in the dictionary?