# Check consistency of statements, with fuzzy rhyme matching (Kattis "Mårten's Theorem" challenge)

I wrote a review for Check consistency of a list of statements, with fuzzy rhyme matching, which basically required me to try writing my own solution to fully understand the challenge. So, I thought that I should put my solution up for review.

I'll paraphrase the "Mårten's Theorem" challenge on Kattis:

Given up to 100000 statements of the form X is Y or X not Y, determine whether the statements are consistent (in which case output yes) or inconsistent (in which case output wait what?). X and Y are words, up to 20 characters long. For example, the two statements ulf is lukas and ulf not lukas contradict each other. The three statements ulf is lukas and lukas is ulf and ulf is bjorn, however, could be consistent.

The catch is that every word that rhymes with X in any provided statement is said to be equivalent to X. Here, two words X and Y are said to "rhyme" if the last min(3, |X|, |Y|) characters are the same.

Some examples:

4
herp is derp
derp is herp
herp is herp
derp is derp


Output to the input above should be yes.

3
oskar not lukas
oskar is poptart
lukas is smart


… should output wait what?, because:

• you could infer that lukas is poptart (due to rhyming equivalence between poptart and smart)
• you could also infer that lukas is oskar (since lukas is poptart and oskar is poptart)
• that contradicts oskar not lukas.

1
moo not foo


… should output yes

2
moo not foo
oo is blah


… should output wait what?, because the appearance of the word oo anywhere means that the first statement moo not foo could be equivalent to oo not oo, which is a self-contradiction.

I wrote a solution in Python 3, but I believe it also works in Python 2. I've attempted to address all of the issues I pointed out in this review.

import fileinput
from itertools import chain
import re

r"""
Read the rules into a dictionary of two sets.  Only the last
word_suffix_len letters of each word are considered.

... oskar not lukas
... oskar is poptart
... lukas is smart'''.split('\n'))
>>> rules == {
...     'is': set([('kar', 'art'), ('kas', 'art')]),
...     'not': set([('kar', 'kas')]),
... }
True
"""
rules = {'is': set(), 'not': set()}
regex = re.compile(r'.*?(\S{1,%d}) (is|not) .*?(\S{1,%d})\$' % (word_suffix_len, word_suffix_len))
line_iter = iter(line_iter)
for _ in range(int(next(line_iter))):
line = next(line_iter)
match = regex.match(line)
if match is None:
raise Exception('Invalid input: ' + line)
return rules

def subst_rule_words(rules, word_map={}):
"""
Make a copy of the rules with the word substitutions applied.

>>> rules = {
...     'is': set([('one', 'won'), ('two', 'too'), ('foo', 'bar')]),
...     'not': set([('one', 'wun'), ('six', 'sex')]),
... }
>>> r = subst_rule_words(rules, {'one': 'un', 'two': 'deux', 'wun': 'baz'})
>>> r == {
...     'is': set([('un', 'won'), ('deux', 'too'), ('foo', 'bar')]),
...     'not': set([('un', 'baz'), ('six', 'sex')]),
... }
True
"""
simplified_rules = {}
for rule_type, statements in rules.items():
simplified_rules[rule_type] = set(
tuple(word_map.get(word, word) for word in words)
for words in statements
)
return simplified_rules

def rhyme_map(rules, word_suffix_len=3):
"""
Make a map of word substitutions based on shared word endings.

>>> rules = {'not': [('moo', 'foo')], 'is': [('oo', 'blah')]}
>>> rhyme_map(rules) == {'foo': 'oo', 'moo': 'oo'}
True
"""
words = set(chain.from_iterable(chain.from_iterable(rules.values())))
abbreviations = {}
short_words = set()
for word_len in range(1, word_suffix_len + 1):
for word in (w for w in words if len(w) == word_len):
for short_word in short_words:
if word.endswith(short_word):
abbreviations[word] = short_word
if word_len < word_suffix_len:
return abbreviations

def union_map(rules):
"""
Make a map of word substitutions based on the "is" rules.
This is an implementation of union-find.
"""
uf = UnionFind()
for x, y in rules['is']:
uf.union(x, y)
equivs = {x: uf[x] for x, y in rules['is']}
equivs.update({y: uf[y] for x, y in rules['is']})
return equivs

def main(fileinput):
r"""
>>> main('''4
... herp is derp
... derp is herp
... herp is herp
... derp is derp'''.split('\n'))
yes

>>> main('''3
... oskar not lukas
... oskar is poptart
... lukas is smart'''.split('\n'))
wait what?

>>> main('''1
... moo not foo'''.split('\n'))
yes

>>> main('''2
... moo not foo
... oo is blah'''.split('\n'))
wait what?
"""
if rules['not']:    # Ruleset without "not" rules must be self-consistent
rules = subst_rule_words(rules, rhyme_map(rules))
rules = subst_rule_words(rules, union_map(rules))
print('wait what?' if any(x == y for x, y in rules['not']) else 'yes')

if __name__ == '__main__':
main(fileinput.input())


In the union_map function, I am making use of an MIT-licensed implementation of the union-find data structure by David Eppstein. I have included it below for reference, but it is not subject to review here.

"""UnionFind.py

Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""

class UnionFind:
"""Union-find data structure.

Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:

- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.

- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set.  If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""

def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}

def __getitem__(self, object):
"""Find and return the name of the set containing the object."""

# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object

# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]

# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root

def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)

def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest


The Kattis online judge reports that this solution runs in 1.67 seconds, which is under the 2-second time limit.

There's a bug if I understood the rules. This is now a "yes" even though it should be a "wait what?":

2
aaa not aa
a is aa


This happens because rhyme_map does not necessarily map each word to the shortest possible rhyme. The fix is simply to change short_words from set to list and add a break to the loop that iterates over it. There is no reason for it to be a set anyway as it is only accessed by iteration.

Also, rhyme_map would seem simpler to me if, instead of testing different short words with ends_with, we would look up every suffix of every word:

def rhyme_map(rules, word_suffix_len=3):
words = set(chain.from_iterable(chain.from_iterable(rules.values())))
abbreviations = {}
for word in words:
for suffix_len in range(1, len(word)):
suffix = word[-suffix_len:]
if suffix in words:
abbreviations[word] = suffix
break
return abbreviations