The original problem is here: [Five programming problems every Software Engineer should be able to solve in less than 1 hour](https://blog.svpino.com/2015/05/07/five-programming-problems-every- software-engineer-should-be-able-to-solve-in-less-than-1-hour) Japanese translation: 5 problems that will disqualify a programmer if not solved within 1 hour
I tried to challenge problem 5 of these with Python.
Define the function f (n, M) as a function that returns all the ways the calculation results in M using numbers from 1 to n (return values are a list). Then the answer you want is f (9, 100). First, if the calculation works as it is (example: n = 3, M = 123), one of the answers is M as a character string. In addition, f (n, M) can be decomposed into smaller n. By repeating the decomposition recursively, you can find all the calculation methods.
First, the formula does not hold as it is (123 ≠ 9). f (3, 9) can be decomposed in the following four ways (generally, there are (n-1) * 2 ways of decomposition). f(2, 6) "+3" f(2, 12) "-3" f(1, -14) "+23" f(1, 32) "-23"
Of these, f (1, -14) and f (1, 32) are unsuitable because they cannot be decomposed any further and the equation does not hold as they are. f (2, 6) can be further decomposed into f (1, 5) "+1" and f (1, 7) "-1", but neither formula holds. Since f (2, 12) is a pattern in which the equation holds as it is, "12" is one solution. Also, it can be decomposed into f (1, 11) "+1" and f (1, 13) "-1", but neither is suitable. Therefore, "12-3" is sought as the only solution.
When f (9, 100) is calculated, 11 patterns presented by the questioner (Solution to Problem 5 -some-other-thoughts-about-this-type-of-questions)) has the same solution.
However, using such a recursive function is a little unpleasant, and in the case of Python, an execution error will occur if the depth of recursion exceeds 1000 (Reference. % 20script /% E3% 82% A2% E3% 82% A4% E3% 83% 87% E3% 83% B3% E3% 83% 86% E3% 82% A3% E3% 83% 86% E3% 82% A3)). In this example, the depth does not exceed 9, so it's okay. Also, in the answer example, it was a mechanism that can handle numbers other than 1 to 9, but it is weak that I can not do it with my method.
def fun5(n, M):
digits = "123456789"[0:n]
out = []
if int(digits) == M:
out += [ digits ]
for i in xrange(1, n):
out += map(lambda z: z + "+" + digits[-i:n], fun5(n - i, M - int(digits[-i:n])) )
out += map(lambda z: z + "-" + digits[-i:n], fun5(n - i, M + int(digits[-i:n])) )
return out
print fun5(2, 3)
print fun5(5, 168)
print fun5(9, 100)
#['1+2']
#['123+45']
#['1+23-4+56+7+8+9', '12+3-4+5+67+8+9', '1+2+34-5+67-8+9', '1+2+3-4+5+6+78+9', '123-4-5-6-7+8-9', '123+45-67+8-9', '1+23-4+5+6+78-9', '12-3-4+5-6+7+89', '12+3+4+5-6-7+89', '123-45-67+89', '123+4-5+67-89']