Last active
August 12, 2022 01:44
-
-
Save PatrickChildersIT/ab72a7172b9bcfefab6de8591efebb43 to your computer and use it in GitHub Desktop.
solves Numble since I'm better at python than arithmetic
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from operator import add, sub, mul, truediv | |
| import itertools | |
| from typing import Generator | |
| TARGET = 755 | |
| NUMBERS = [3, 4, 25, 50, 75, 100] | |
| OPERATIONS = {add: "+", sub: "-", mul: "*", truediv: "/"} | |
| def series_to_string(series: list) -> str: | |
| """ | |
| turns a jagged array of numbers and operators into | |
| a more pleasing-looking set of parenthesis and math symbols | |
| """ | |
| result = "( " | |
| for item in series: | |
| if item in NUMBERS: | |
| result += f"{item} " | |
| elif callable(item): | |
| result += f"{OPERATIONS[item]} " | |
| else: | |
| result += f"{series_to_string(item)} " | |
| result += ")" | |
| return result | |
| def numbers_in_problem(problem: list) -> Generator: | |
| """ | |
| iterates recursively through a "problem" yielding up any numbers | |
| """ | |
| for item in problem: | |
| if item in NUMBERS: | |
| yield item | |
| elif callable(item): | |
| continue | |
| else: | |
| yield from numbers_in_problem(item) | |
| def sides_share_number(combinations, lside, rside) -> bool: | |
| """ | |
| the left and right sides of a problem could be numbers or sub-problems | |
| we check for numbers first to short-circuit, but if there are sub-problems | |
| we check their contents with our number-generator | |
| the "in" keyword, i believe, will short circuit the generator soon as a match is yielded | |
| """ | |
| lside = combinations[lside] or lside | |
| rside = combinations[rside] or rside | |
| if lside in NUMBERS: | |
| if rside in NUMBERS: | |
| return False | |
| else: | |
| # lside is constant, rside is problem | |
| return lside in numbers_in_problem(rside) | |
| else: | |
| if rside in NUMBERS: | |
| # rside is constant, lside is problem | |
| return rside in numbers_in_problem(lside) | |
| else: | |
| # both are problems, pick one arbitrarily and check each number and sub-problem | |
| for number in numbers_in_problem(lside): | |
| return number in numbers_in_problem(rside) | |
| def main(): | |
| combinations = {k: None for k in NUMBERS} | |
| # it might be possible to compute how many iterations this should take | |
| # but if i good enough at math to figure that out i wouldn't have made this program | |
| while True: | |
| for lside, rside in itertools.combinations(combinations.keys(), 2): | |
| if lside == 0 or rside == 0: # zeroes add nothing of value | |
| continue | |
| if sides_share_number( | |
| combinations, lside, rside | |
| ): # skip over any combinations that use the same base number | |
| continue | |
| for op in OPERATIONS: | |
| answer = op(lside, rside) | |
| if answer in combinations: | |
| continue | |
| lside_for_answer = combinations[lside] or lside | |
| rside_for_answer = combinations[rside] or rside | |
| combinations[answer] = [lside_for_answer, op, rside_for_answer] | |
| if answer == TARGET: | |
| print(f"{series_to_string(combinations[answer])} = {answer}") | |
| return combinations[answer] | |
| if __name__ == "__main__": | |
| main() |
Author
Author
I changed it pretty completely, it'll now output parenthesis and though the first test case takes longer now, the solution is cleaner and it's more capable of finding other solutions that might've been missed before
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
There's 2 copies of each operator so that the
combinations_with_replacementfunction is at least 5-long and is still evenly distributed.The printout at the end is made by doing each operation from left to right in order, evaluating each time, so for numble you should add parenthesis around everything.
If this prints out
50 - 3 * 100 * 4 + 75 / 25 = 755then enter in( ( ( ( 50 - 3 ) * 100 ) * 4 ) + 75 ) / 25