import random
import re

from collections import namedtuple

Rule = namedtuple('Rule', ['changes', 'environments'])

sonorization = Rule({'p': 'b', 't': 'd', 'ʈ': 'ɖ', 'c':'ɟ', 'k': 'g', 'q': 'ɢ'},
                    ['^.', 'V.V', '.$'])


rules = [sonorization]

words = ['otatop', 'tobado', 'xtabasco']

def choose_rule(words, rules):
    '''Returns a sound change rule from rules applicable to the given word list.'''
    filtered_rules = filter_rules_by_phonemes(words, rules)
    filtered_rules = filter_rules_by_environments(words, filtered_rules)

    return filtered_rules
    # selected_rule = random.choice(filtered_rules)

def intersecting(set_1, set_2):
    '''Return true if the intersection of the two sets isn't empty, false
otherwise.
    '''
    return (len(set_1.intersection(set_2)) != 0)

def filter_rules_by_phonemes(words, rules):
    '''Returns a list of rules which contain phonemes that are in the given word
list.
    '''
    word_phonemes = set(''.join(words))

    return [rule for rule in rules if intersecting(word_phonemes,
                                                   set(rule.changes.keys()))]


def rule_phonemes(rule):
    '''Returns a set of the target phonemes of the rule, i.e. the phonemes used as
keys in the changes dictionary.'''
    return set(rule.changes.keys())


def filter_rules_by_environments(words, rules):
    '''Returns a list of rules which apply to at least one word in the given word
list, taking into account the environments in which the rule applies. The rules
have all extraneous phoneme pairs removed, for maximum efficiency.
    '''
    filtered_rules = []

    # Combine the word list into one string, separated by newlines, to speed up
    # regex search.
    combined_words = '\n'.join(words)

    for rule in rules:
        phonemes = ''.join(rule_phonemes(rule))
        applicable_environments = []

        for environment in rule.environments:
            # Get a set of target phonemes which appear in the environment.
            regex = environment.replace('.', '([{0}])'.format(phonemes))
            targets = set(re.findall(regex, combined_words, re.MULTILINE))

            # If there are targets available, create a new rule with just those
            # targets and the current environment and add it to the filtered
            # list.
            if len(targets) != 0:
                changes = {target: replacement for target, replacement in
                           rule.changes.items() if target in targets}
                filtered_rules.append(Rule(changes, [environment]))

    return filtered_rules

if __name__ == '__main__':
    print(choose_rule(words, rules))

@@ -110,16 +110,17 @@
 nts'%5D)%0A%0A
+%0A
 sonoriza
@@ -166,16 +166,17 @@
 %C9%96', 'c':
+ 
 '%C9%9F', 'k'
@@ -302,16 +302,17 @@
 asco'%5D%0A%0A
+%0A
 def choo
@@ -408,22 +408,31 @@
 ven word
+%0A   
  list.
+%0A    
 '''%0A    
@@ -640,16 +640,17 @@
 rules)%0A%0A
+%0A
 def inte
@@ -747,16 +747,20 @@
 , false%0A
+    
 otherwis
@@ -762,16 +762,16 @@
 erwise.%0A
-
     '''%0A
@@ -820,16 +820,17 @@
  != 0)%0A%0A
+%0A
 def filt
@@ -874,32 +874,157 @@
    '''Returns a 
+If you want to customize the fill column value, use something like%0A    this inside the user-init function in your .spacemacs:
 list of rules wh
@@ -1026,16 +1026,20 @@
 es which
+%0A   
  contain
@@ -1070,25 +1070,25 @@
 e given word
-%0A
+ 
 list.%0A    ''
@@ -1384,16 +1384,20 @@
 used as%0A
+    
 keys in 
@@ -1419,16 +1419,21 @@
 tionary.
+%0A    
 '''%0A    
@@ -1596,16 +1596,20 @@
 en word%0A
+    
 list, ta
@@ -1677,15 +1677,19 @@
  The
+%0A   
  rules
-%0A
+ 
 have
@@ -1946,16 +1946,16 @@
  rules:%0A
+
         
@@ -1997,45 +1997,8 @@
 le))
-%0A        applicable_environments = %5B%5D
 %0A%0A  

Fix formatting errors