Created
February 8, 2019 15:43
Star
You must be signed in to star a gist
Searching for a solution to the 10958 problem.
This file contains 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
# -*- coding: utf-8 -*- | |
""" | |
(c) 2019 Joseph Catrambone, Xoana LTD. Releasewd under MIT License. | |
""" | |
# Create 10958 using, in order, 1, 2, 3, 4, 5, 6, 7, 8, 9. | |
# Let's phrase this as a search problem. | |
# Concat only applies if the underlying operands are digits, not products. I.e, one could go concat(1, 2) -> 12, but not concat(1+2, 3) -> 33. | |
# Iterative deepening DFS. | |
def search(digits): | |
# Move the division point across the digits, left to right. | |
# For example: [1, 2, | 3, 4, 5, 6, 7, 8, 9] -> [1, 2, 3, | 4, 5, 6, 7, 8, 9] | |
# Yields a tuple of ((operation, left, right), result) or ('noop', result) | |
if len(digits) == 1: | |
yield (('noop', digits[0]), digits[0][1]) | |
yield (('neg', digits[0]), -digits[0][1]) | |
elif len(digits) == 2: | |
left = digits[0] | |
right = digits[1] | |
a = left[1] | |
b = right[1] | |
yield (('+', left, right), a+b) | |
yield (('-', left, right), a-b) | |
yield (('*', left, right), a*b) | |
if b != 0: | |
yield (('/', left, right), a/b) | |
if b >= 0 and isinstance(a, int) and isinstance(b, int): | |
yield (('c', left, right), int(str(a) + str(b))) | |
if a != 0 or b >= 0: | |
yield (("^", left, right), a**b) | |
else: | |
for split_point in range(len(digits)): | |
for left, right in zip(search(digits[:split_point]), search(digits[split_point:])): | |
yield (('+', left[0], right[0]), left[1]+right[1]) | |
yield (('-', left[0], right[0]), left[1]-right[1]) | |
yield (('*', left[0], right[0]), left[1]*right[1]) | |
if right[1] != 0: | |
yield (('/', left[0], right[0]), left[1]/right[1]) | |
if right[1] >= 0 and isinstance(left[1], int) and isinstance(right[1], int): | |
yield (('c', left[0], right[0]), int(str(left[1]) + str(right[1]))) | |
if (left[1] != 0 or right[1] >= 0) and right[1] < 1000000: # NOTE: We're capping right for computation reasons. | |
yield (("^", left[0], right[0]), left[1]**right[1]) | |
def run(): | |
i = 0 | |
for result in search([('base', 1), ('base', 2), ('base', 3), ('base', 4), ('base', 6), ('base', 6), ('base', 7), ('base', 8), ('base', 9)]): | |
i += 1 | |
if i%10 == 0: | |
print("{}, {}".format(i, result)) | |
if abs(result[1] - 10958) < 2: | |
print("Possible solution:") | |
print(result) | |
print("Search complete after {} steps.".format(i)) | |
run() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment