Skip to content

Instantly share code, notes, and snippets.

@JosephCatrambone
Created February 8, 2019 15:43
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save JosephCatrambone/2edda2038ec5c08b54cc355bb999d172 to your computer and use it in GitHub Desktop.
Searching for a solution to the 10958 problem.
# -*- 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