Solve the Spelling Bee with kanren

The constraints are:

  1. Only 7 letters are allowed to write words of arbitrary lengths;
  2. One those letters is compulsory membero(compulsory_letter, word)
  3. The word must be in the dictionary dictionary(word)

TODO Download simple dictionary and add constraint

We can find lists of english words online. The file linked before is only 4Mb.

from kanren import fact, run, var

# Populate a dictionary (start with short words)
dictionary = Relation("dictionary")
for word in dictionary:
    fact(dictionary, word)

q = var()
res = run(1, q, dictionary(q))
print(res)

TODO Constraint that one letter is compulory

from kanren import membero, var

compulsory_letter = "a"
word = var()
goal = membero(compulsory_letter, word)

TODO Constraint on the only allowed letters

The `letterconstraints` goal is actually not enough; it will not guarantee that other letters won't be present in the word. We need a goal that states that a set is a subset of another?

from kanren import membero, fact, Relation

lall(*(not(membero(forbidden, word)) for forbidden in forbidden_letters)))