TMSolver/Solver.py at master · fdamhaut/TMSolver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
from itertools import combinations, groupby, permutations
from Conditions import ConditionCard
from Value import generateValueSet

def one_of_each(items):
    if len(items) < 2:
        yield from ((i,) for i in items[0])
        return
    for q in one_of_each(items[1:]):
        for i in items[0]:
            yield (i,) + q

def make_combination_dict(cs):
    res = {}
    for i in range(len(cs)):
        for c in combinations(cs, i + 1):
            for co in one_of_each(c):
                res[co] = Solution(co, res)
    return res


class Solution:
    def __init__(self, cs, combi_dict):
        self.conditions = cs
        self.child = []
        self.parent = [combi_dict[c] for c in combinations(cs, len(cs)-1) if c]
        for p in self.parent:
            p.child += [self]
        self.banned, self.evaled, self.success = False, False, False
        if not self.parent:
            self.eval_one()

    def ban(self):
        if self.banned:
            return
        self.banned = True
        for c in self.child:
            c.ban()

    def eval_one(self):
        self.vset = self.conditions[0].vset
        self.evaled = True

    def eval(self, explain=False):
        if self.evaled or self.banned:
            return
        a, b = self.parent[:2]
        self.vset = a.vset.intersection(b.vset)
        if not self.vset:
            self.ban()
            self.explain(explain, f'{self} has no valid combination')
        for p in self.parent:
            if len(p.vset) == len(self.vset):
                self.ban()
                self.explain(explain, f'{p} implies {self}')
                break
        if not self.child:
            if len(self.vset) != 1:
                self.ban()
                self.explain(explain, f'{self} has too many valid combinations')
            else:
                self.success = True
        if len(self.vset) == 1:
            self.ban()
            self.explain(explain, f'{self} has only one valid combination and is not terminal')

    def explain(self, explain, msg):
        if explain:
            print(msg)

    def __repr__(self):
        return ' & '.join(map(repr, self.conditions)) + ('' if len(self.vset) != 1 else ' - ' + str(list(self.vset)[0]))

    def __lt__(self, other):
        return self.conditions < other.conditions

    def __getitem__(self, item):
        return self.conditions[item]

    def __len__(self):
        return len(self.conditions)

class Solver:

    def __init__(self, conditions_cards, card_double=list()):
        self.extra = set.union(*[set(cc[1]) for cc in conditions_cards + card_double if cc])
        self.vset = generateValueSet(self.extra)
        if len(card_double) < len(conditions_cards):    # Pad with empty list for zip
            card_double = card_double + [False] * (len(conditions_cards) - len(card_double))
        self.conditions_cards = [ConditionCard(cc[0], self.vset, overlap=len(cc) > 2 and cc[2]) +
                                 (cd and ConditionCard(cd[0], self.vset, overlap=len(cd) > 2 and cd[2] )) for cc, cd in zip(conditions_cards, card_double)]
        self.combination = make_combination_dict(self.conditions_cards)
        self.solution = []

    def solve(self, explain=False):
        for key in sorted(self.combination, key=lambda x: len(x)):
            sol = self.combination[key]
            sol.eval(explain=explain)
            if sol.success:
                self.solution += [sol]

    def get_best_tree(self):
        if not self.solution:
            return None
        # TODO improve perf with information theory (reduce entropy)
        # Make all choice binary
        best = ({}, (9999, 9999))
        for perm in permutations(list(range(len(self.solution[0])))):
            best = min(best, self.make_solution_tree(perm, info=True), key=lambda x: x[1])
        return best[0]

    def get_one_tree(self):
        if not self.solution:
            return None
        return self.make_solution_tree()

    def make_solution_tree(self, combi=None, info=False):
        if not combi:
            combi = list(range(len(self.solution[0])))
        def recursive(solutions, combi, depth=0):
            if depth == len(solutions[0]):
                return solutions
            if len(solutions) == 1:
                return solutions
            level = list(map(lambda group: (group[0], recursive(tuple(group[1]), combi, depth+1)), groupby(solutions, lambda sol:sol[combi[depth]])))
            if len(level) == 1:
                return level[0][1]
            return level
        key = [tuple(sol[key] for key in combi) for sol in self.solution]
        sols = [res for _, res in sorted(zip(key, self.solution))]
        res = recursive(sols, combi)
        if not info:
            return res
        def get_depth(tree):
            if not isinstance(tree, list):
                yield 0
                return
            for leaf in tree:
                for depth in get_depth(leaf[1]):
                    yield depth + 1
        depths = list(get_depth(res))
        return res, (max(depths), sum(depths)/len(depths))