Cassidoo 2020-03-02

N-from-D.py

# 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])