Skip to content

Instantly share code, notes, and snippets.

@les-peters les-peters/N-from-D.py
Last active Mar 6, 2020

Embed
What would you like to do?
Cassidoo 2020-03-02
# Write a function that when given a positive integer n and a digit d (which is not 0),
# outputs a way to represent n using only addition, subtraction, multiplication,
# exponentiation, division, concatenation, parenthesis and the digit d.
# Example:
# n = 6, d = 1 => 1 + 1 + 1 + 1 + 1 + 1
# n = 10, d = 1 => 1 | 1 - 1
# n = 12, d = 1 => 1 | (1 + 1)
# n = 64, d = 2 => 2 ^ (2 + 2 + 2)
# n = 1, d = 9 => 9 / 9
# (In this example, | represents concatenation)
import math
import re
def concatAddition(n, d):
add_str = " + "
a = []
for i in range(0, int(n/d)):
a.append(str(d))
return "(" + add_str.join(a) + ")"
def zeroN(n,d):
squence = "(" + str(d) + " - " + str(d) + ")"
return squence
def oneN(n,d):
squence = "(" + str(d) + " / " + str(d) + ")"
return squence
def NequalsD(n,d):
if n == d:
return str(d)
else:
return None
def concatenatedDigits(n,d):
if len(str(n)) >= 2:
digits_p = re.compile('(^\d)(\d+$)')
digits_m = digits_p.search(str(n))
return createFormula(int(digits_m.group(1)),d) + " | " + createFormula(int(digits_m.group(2)),d)
def createFormula(n, d):
# print("n = " + str(n) + ", d = " + str(d))
squence = 'No answer'
leading_digit_p = re.compile('^' + str(d) + '(.*$)')
leading_digit_m = leading_digit_p.search(str(n))
# test for n == d
if n == d:
return NequalsD(n,d)
# test for d as the leading digit of n
if leading_digit_m:
remainder = int(leading_digit_m.group(1))
remainder_value = createFormula(remainder, d)
squence = str(d) + " | " + remainder_value
return squence
# test for n == 0
if n == 0:
return zeroN(n,d)
# test for n == 1
if n == 1:
return oneN(n,d)
# test for power function
if d != 1:
ex = math.log(n, d)
if math.floor(ex) == ex:
ex_str = createFormula(int(ex), d)
squence = "(" + str(d) + " ^ " + "(" + ex_str + ")" + ")"
return squence
# test for n divisible by d
if ((n % d) == 0):
return concatAddition(n, d)
if (d > n):
first = int(math.floor(n / d) * d)
second = n - first
first_answer = createFormula(n * d, d)
squence = "(" + createFormula(n * d, d) + " / " + str(d) + ")"
return squence
else:
first = int(math.floor(n / d) * d)
first_answer = createFormula(first, d)
second = math.floor(n % d)
second_answer = createFormula(second, d)
squence = first_answer + " + " + second_answer
return squence
print("Original ask:")
print("n = 6, d = 1 =>", createFormula(6, 1))
print("n = 10, d = 1 =>", createFormula(10, 1))
print("n = 12, d = 1 =>", createFormula(12, 1))
print("n = 64, d = 2 =>", createFormula(64, 2))
print("n = 1, d = 9 =>", createFormula(1, 9))
print("Extended test:")
for n in range(1, 100):
for d in range(1, 10):
answers = []
a = zeroN(n,d)
if eval(a) == n:
answers.append(a)
a = oneN(n,d)
if eval(a) == n:
answers.append(a)
a = concatAddition(n,d)
if eval(a) == n:
answers.append(a)
a = NequalsD(n,d)
if a:
if eval(a) == n:
answers.append(a)
a = concatenatedDigits(n,d)
if a:
answers.append(a)
answers.append(createFormula(n,d))
sorted_answers = sorted(answers, key=len)
print("n =", str(n), ", d =", str(d), "=>", sorted_answers[0])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.