I think that I have played to make 10 by looking at the number of the oncoming car, such as when I am in a car, adding, subtracting, multiplying, and dividing, but sometimes there is a difficult problem and it is moody. You must to do something before you go on. Also, I'm wondering how many combinations I can't solve. So, let's try all four 0-9 number pairs and operator combinations and write a program to display the results.
References:
-Ten Puzzle-Wikipedia -Search for solutions to ten puzzles --Mathematics free study: -Settlement on Ten Puzzle-Something to write down:
The third site for reference is in Python. However, since the formula is converted into a character string and passed to the eval function, the execution speed becomes extremely slow (Programming FAQ — Python 2.7ja1 documentation:. See programming.html # id20)). Therefore, as shown in the second reference site, the operators are six operators that distinguish the order for subtraction and division. That is,
from operator import add, sub, mul, div
def rsub(a, b):
return sub(b, a)
def rdiv(a, b):
return div(b, a)
o = [add, sub, rsub, mul, div, rdiv]
Create a list of operators as. The operator is used three times, assuming that a, b, c, d are numbers and o1, o2, o3 are operators.
((a o1 b) o2 c) o3 d ・ ・ ・ 1 (a o1 b) o3 (c o2 d) ・ ・ ・ 2
There are only two ways.
There are 4! = 24 ways to select a, b, c, d, but when it is 1, the ones with a and b replaced are duplicated, so there are 24/2 = 12 ways to choose. Specifically, if you write as follows, the list X will list all cases from the string q (such as '1337') except for duplicate numbers (such as '3' in '1337'). Can be stored in.
from itertools import combinations
q = [float(i) for i in list(q)]
X = []
for a, b in combinations([0, 1, 2, 3], 2):
t = [0, 1, 2, 3]
t.remove(a)
t.remove(b)
x = (q[a], q[b], q[t[0]], q[t[1]])
if not x in X:
X.append(x)
x = (q[a], q[b], q[t[1]], q[t[0]])
if not x in X:
X.append(x)
In the case of 2, it is not necessary to think about the combination of a, b, the combination of c, d, and the combination of (a, b) and (c, d), so if you think about the three combinations of numbers, I know it's good. Since the number is small, it may be easier to understand if you write solidly rather than thinking about combinations.
X = [
(q[0], q[1], q[2], q[3]),
(q[0], q[2], q[1], q[3]),
(q[0], q[3], q[1], q[2]),
]
As for how to select o1, 6 things are allocated to 3 places, so 6 3 = 216 ways to think about.
from itertools import product
O = [i for i in product(range(6), repeat=3)]
So you can make all the combinations.
After that, for all combinations of O, we can calculate for the two patterns using the contents of X, and record the one that becomes 10. At that time, ZeroDivisionError will be thrown, so you need to handle the exception. I converted the answer to a string to make it easier to see. Also, due to the nature of the computer, some errors may occur, so we decided to allow an error of a number (0.001) smaller than the number obtained by dividing 1 by 9 to the 3rd power (= 0.0013717421124828531 ...).
The one actually made is shown below. Since I was running it on IPython Notebook, I only have to define the function.
from itertools import permutations, combinations, product
from operator import add, sub, mul, div
from ipython_doctester import test
#@test
def make10(q='1337', verbose=True):
"""Make 10 from 4 numbers(0~9).
q : String, ex) 1337
verbose: Bool, print the results or not
doctest code:
>>> make10()
((7/3)+1)*3
True
"""
q = [float(i) for i in list(q)]
def rsub(a, b):
return sub(b, a)
def rdiv(a, b):
return div(b, a)
o = [add, sub, rsub, mul, div, rdiv]
o_k = ['+', '-', '-', '*', '/', '/']
O = [i for i in product(range(6), repeat=3)]
TOL = 0.001
res = []
for o1, o2, o3 in O:
# ((a o1 b) o2 c) o3 d
X = []
for a, b in combinations([0, 1, 2, 3], 2):
t = [0, 1, 2, 3]
t.remove(a)
t.remove(b)
x = (q[a], q[b], q[t[0]], q[t[1]])
if not x in X:
X.append(x)
x = (q[a], q[b], q[t[1]], q[t[0]])
if not x in X:
X.append(x)
for a, b, c, d in X:
try:
result = o[o3](o[o2](o[o1](a,b),c),d)
except ZeroDivisionError:
continue
if abs(result - 10) < TOL:
if o1 == 2 or o1 == 5:
a, b = b, a
p1 = "(%d%s%d)" % (a, o_k[o1], b)
if o2 == 2 or o2 == 5:
p2 = "%d%s" % (c, o_k[o2]) + p1
else:
p2 = p1 + "%s%d" % (o_k[o2], c)
if o3 == 2 or o3 == 5:
p = "%d%s" % (d, o_k[o3]) + "(" + p2 + ")"
else:
p = "(" + p2 + ")" + "%s%d" % (o_k[o3], d)
res.append(p)
# (a o1 b) o3 (c o2 d)
X = [
(q[0], q[1], q[2], q[3]),
(q[0], q[2], q[1], q[3]),
(q[0], q[3], q[1], q[2]),
]
for a, b, c, d in X:
try:
result = o[o3](o[o1](a,b),o[o2](c,d))
except ZeroDivisionError:
continue
if abs(result - 10) < TOL:
if o1 == 2 or o1 == 5:
a, b = b, a
p1 = "(%d%s%d)" % (a, o_k[o1], b)
if o2 == 2 or o2 == 5:
c, d = d, c
p2 = "(%d%s%d)" % (c, o_k[o2], d)
if o3 == 2 or o3 == 5:
p = p2 + o_k[o3] + p1
else:
p = p1 + o_k[o3] + p2
res.append(p)
if verbose:
for r in res:
print r
if len(res) > 0:
return True
else:
return False
Next, when I calculate this for all combinations of numbers,
import itertools
A = [''.join(i) for i in
itertools.combinations_with_replacement(
[str(x) for x in range(10)], 4)]
index_A = [make10(a, verbose=False) for a in A]
false = [a for i,a in enumerate(A) if not index_A[i]]
print len(false), false
Result is
163 ['0000', '0001', '0002', '0003', '0004', '0005', '0006', '0007', '0008', '0009', '0011', '0012', '0013', '0014', '0015', '0016', '0017', '0018', '0022', '0023', '0024', '0026', '0027', '0029', '0033', '0034', '0035', '0036', '0038', '0039', '0044', '0045', '0047', '0048', '0049', '0056', '0057', '0058', '0059', '0066', '0067', '0068', '0069', '0077', '0078', '0079', '0088', '0089', '0099', '0111', '0112', '0113', '0114', '0116', '0117', '0122', '0123', '0134', '0144', '0148', '0157', '0158', '0166', '0167', '0168', '0177', '0178', '0188', '0222', '0233', '0236', '0269', '0277', '0279', '0299', '0333', '0335', '0336', '0338', '0344', '0345', '0348', '0359', '0366', '0369', '0388', '0389', '0399', '0444', '0445', '0447', '0448', '0457', '0478', '0479', '0489', '0499', '0566', '0567', '0577', '0588', '0589', '0599', '0666', '0667', '0668', '0677', '0678', '0689', '0699', '0777', '0778', '0788', '0799', '0888', '1111', '1112', '1113', '1122', '1159', '1169', '1177', '1178', '1179', '1188', '1399', '1444', '1499', '1666', '1667', '1677', '1699', '1777', '2257', '3444', '3669', '3779', '3999', '4444', '4459', '4477', '4558', '4899', '4999', '5668', '5788', '5799', '5899', '6666', '6667', '6677', '6777', '6778', '6888', '6899', '6999', '7777', '7788', '7789', '7799', '7888', '7999', '8899']
And to Wikipedia The result is the same as what was listed.
Iterative calculation took about 10 seconds, but it took about 2.5 seconds (although it was slow), and I learned a lot about how to write combinations and comprehensions. You can increase the number of operators to put powers and logs, or you can put spaces and use 2- or 3-digit numbers instead of connected strings.
If you have any mistakes or if you would like to do more, please point out.
Recommended Posts