Qat Equation Solver

Question

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 the regular expression [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. The RHS is a simple pattern, which matches any word that fits that pattern [which is then output as a result].

Qat will try to assign strings of characters to the variables so that the whole LHS matches the RHS.

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 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. You do not need to handle recursive inputs.

Test cases

Dictionary	Pattern	Output
[one two onetwo onesix]	A=o..	one
[one two onetwo onesix]	A=o..;A=..e	one one
[one two onetwo onesix]	A=...	one; two
[one two onetwo onesix]	A=oneB;B=...	onetwo two
[one two onetwo onesix]	o..A=ones..	onesix
[one two onetwo onesix]	A=...;B=...;C=AB	one two onetwo

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

Answer 1

Python 3.8 (pre-release), 298 bytes

from itertools import*
import re
P=product
def F(W,E):
 V={ord(i)for i in E if'@'<i<'['};E=E.split(';')
 for t in P(set().union(*[sum((l:=[i]+[x+i for x in l]for i in s),l:=[])for s in W]),repeat=len(V)):yield from P(*[[c for c in W if re.fullmatch(e.translate(dict(zip(V,t))),c+'='+c)]for e in E])

Try it online!

Brute force. Tries assigning every substring from every word to each variable.

Answer 2

Vyxal, 45 bytes

₄↔ƛ⁰kAfnvvV₅¹↔$vZ'ƛ÷Mƛ÷εnh=;A;A;vvh;ÞfUvṄ‛; j

Try it Online! (times out) or try a version with only three variables.

Tries all possible substitutions and all possible equation results so it's extremely slow.

Answer 3

Python3, 776 bytes

Long, but fast.

from itertools import*
U=str.isupper
E=enumerate
def f(W,p):
 q=[({},{},p)]
 for d,D,p in q:
  if[]==p:return d,D
  for i,a in E(p):
   if all(not U(j)or j in d for j in a[1]):
    H,K={},{}
    for k in product(*[d[j]if U(j)else[j]for j in a[1]]):
     for w in W:
      if all(A=='.'or A==B for A,B in zip_longest(''.join(k),w)):
       H[a[0]]=H.get(a[0],[])+[w]
       for A,B in zip_longest(a[1],k):
        if U(A):K[A]=K.get(A,[])+[B]
       Q=[(a[0],w,{})]
       for u,o,z in Q:
        if''==u and''==o:K={**K,**{i:K.get(i,[])+z[i]for i in z}};continue
        if u and o:
         if U(u[0]):
          for I,_ in E(o):Q+=[(u[1:],o[I+1:],{**z,u[0]:z.get(u[0],[])+[o[:I+1]]})]
         else:Q+=[(u[1:],o[1:],z)]
    q+=[({**d,**K},{**D,**H},p[:i]+p[i+1:])]
    break

Try it online!