puzzle-solvers

  1#!/bin/env python3
  2
  3from collections import defaultdict
  4import sys
  5import itertools
  6from typing import Sequence
  7
  8
  9class Add:
 10    def __init__(self, one, two):
 11        self.one = one
 12        self.two = two
 13        self.res = self.one + self.two
 14
 15    def __str__(self):
 16        return f"{self.one} + {self.two} = {self.res}"
 17
 18    def __repr__(self):
 19        return self.__str__()
 20
 21    def operate(self):
 22        return self.res
 23
 24
 25class Mul:
 26    def __init__(self, one, two):
 27        self.one = one
 28        self.two = two
 29        self.res = self.one * self.two
 30
 31    def __str__(self):
 32        return f"{self.one} * {self.two} = {self.res}"
 33
 34    def __repr__(self):
 35        return self.__str__()
 36
 37    def operate(self):
 38        return self.res
 39
 40
 41class Sub:
 42    def __init__(self, one, two):
 43        self.one = one
 44        self.two = two
 45        if self.two > self.one:
 46            self.one, self.two = self.two, self.one
 47
 48        self.res = self.one - self.two
 49
 50    def __str__(self):
 51        return f"{self.one} - {self.two} = {self.res}"
 52
 53    def __repr__(self):
 54        return self.__str__()
 55
 56    def operate(self):
 57        return self.res
 58
 59
 60class Div:
 61    def __init__(self, one, two):
 62        self.one = max(one, two)
 63        self.two = min(one, two)
 64        self.res = None
 65
 66        try:
 67            d = self.one / self.two
 68            if int(d) == d:
 69                self.res = int(d)
 70        except ZeroDivisionError:
 71            pass
 72
 73    def __str__(self):
 74        return f"{self.one} / {self.two} = {self.res}"
 75
 76    def __repr__(self):
 77        return self.__str__()
 78
 79
 80ops = [Add, Sub, Mul, Div]
 81paths = []
 82unique = {}
 83
 84
 85def solve(digits: Sequence[int], target: int, path: list):
 86    if target in digits:
 87        paths.append(path)
 88
 89    for combo in itertools.combinations(range(0, len(digits)), 2):
 90        for op in ops:
 91            o = op(digits[combo[0]], digits[combo[1]])
 92            res = o.res
 93            if res is None:
 94                continue
 95
 96            path_new = path.copy()
 97            path_new.append(o)
 98            digits_new = [d[1] for d in enumerate(digits) if d[0] not in combo]
 99            digits_new.append(res)
100
101            # We prefer shorter paths because that seems like the right
102            # heuristic to use.
103            if res not in unique or len(unique[res]) > len(path_new):
104                unique[res] = path_new
105
106            solve(digits_new, target, path_new)
107
108
109def main(argv: Sequence[str]) -> int:
110    if len(argv) <= 2:
111        print("usage: solver.py <DIGITS> <TARGET>")
112        return 1
113
114    digits = [int(x) for x in argv[1:-1]]
115    target = int(argv[-1])
116    solve(digits, target, [])
117
118    for d in digits:
119        global unique
120        unique[d] = "given"
121
122    print("Correct paths")
123    for path in paths:
124        for op in path:
125            print(op)
126        print()
127
128    print(f"Total possible paths: {len(paths)}")
129    print(f"Unique numbers encountered: {len(unique)}")
130
131    print("Ops used:")
132    op_use_count = defaultdict(int)
133    for path in paths:
134        for op in path:
135            op_use_count[op.__class__.__name__] += 1
136    for op in ops:
137        print(f"\t{op.__name__}\t{op_use_count[op.__name__]}")
138    print()
139
140    print("Contiguous constructable numbers")
141    for i in range(0, max(unique.keys())):
142        if i in unique:
143            print(f"{i}\t{unique[i]}")
144        else:
145            break
146
147    # A possible method of sorting, suggested by dad.  Just count the number of
148    # multiplications.
149    # sorted_paths = sorted(paths, key=lambda path: max((r.res for r in path if isinstance(r, Mul))))
150    # for path in sorted_paths:
151    #    for op in path:
152    #        print(op)
153    #    print()
154
155    return 0
156
157
158if __name__ == "__main__":
159    sys.exit(main(sys.argv))