patternpythonMinor
Compose valid subtractions using all digits from a set
Viewed 0 times
alldigitssubtractionsusingcomposevalidfromset
Problem
I have created a brainteaser, which I called the "impossible problem" (see this video I made). The aim is to create a valid 3-digit subtraction which uses every digit from 1 to 9 once. Here is an example of one of the solutions: 873-254=619.
After finding it hard to come up with answers I created this program. What it basically does is iterate through every possible 3-digit subtraction and if it finds one which fits the criteria, it prints it.
My program worked quite well but then I decided could you
After finding it hard to come up with answers I created this program. What it basically does is iterate through every possible 3-digit subtraction and if it finds one which fits the criteria, it prints it.
from math import trunc
def solver(number,number2, numberofdigits):
seq = str(number),str(number2), str(number - number2)
digits = "".join(seq)
goodChecks = 0
count= numberofdigits/3
for i in range(1,10):
if digits.count(str(i)) == count:
goodChecks += 1
if goodChecks == 9:
return digits
else:
return False
middlenumber =[]
successes = 0
num_of_digits = int(input("please enter a number of digits, which is a multiple of 3"))
if num_of_digits == 3:
minY = 381
maxY = 987
if num_of_digits == 6:
minY =246912
maxY = 998877
if num_of_digits == 3:
minX = 123
if num_of_digits == 6:
minX =123123
for y in range(minY, maxY+1):
numberlist = []
if y%100 == 0:
print(y)
for x in range(minX,trunc(y/2)):
digits = solver(y,x,num_of_digits)
if digits is not False:
successes += 2
print(digits)
numberlist.extend([x,y-x])
middlenumber.extend([x, y-x])
print("")
print("I found: ", successes, " successful solution to your brainteaser")
if successes < 20:
print("there were almost no solutions")
elif successes < 100:
print("there were not many solutions")
elif successes < 1000:
print("there were more than a hundred solutions it is definitely not impossible :)")
else:
print("that's a lot of successes")
print("There were ", len(middlenumber) - len(set(middlenumber)) , " duplicates, by the way :)")My program worked quite well but then I decided could you
Solution
-
first of all try use middlenumber as set. Than adding numbers no by
first of all try use middlenumber as set. Than adding numbers no by
extends but something as middlenumber.add(x
-
naive brute force algorithm use 9^6 checking as you mentioned
-
something better when you change to permutations (9!/3! checking). There example for simpler 3-digit version
from itertools import permutations
def permutations_solver():
digits = set('987654321')
numbers = (''.join(x) for x in permutations(digits, 6))
for x in numbers:
a = int(x[0 : 3])
b = int(x[3 : 6])
c = a - b
if b > c and c > 0 and set(str(c) + x) == digits:
yield a, b, c
print(len(list(permutations_solver())))
-
checking b > c and c > 0 and set(str(c) + x) == digits above still is very ineffective
-
you can try write iterator on digits, something as
""" set('abcdefgh') == set('123456789') and set('zxyr') == set('01')
zxyr abc < def (enough a < d)
abc z == 0
+def x + a + d == g + 10 * z
---- y + b + e == h + 10 * x
ghi r + c + f == i + 10 * y
zxy r == 0 // it looks like logic programming problem
"""
from itertools import product
def digits_solver():
column = [(x, a, d, (x + a + d) % 10, (x + a + d) // 10)
for x, a, d in product(range(2), range(1, 10), range(1, 10))
if len(set([a, d, (x + a + d) % 10])) == 3 and (x + a + d) % 10 != 0]
first_column = [(x, a, d, g) for x, a, d, g, z in column if z == 0 and a < d]
for x, a, d, g in first_column:
second_column = [(y, b, e, h) for y, b, e, h, xx in column if xx == x and not set([a,d,g]) & set([b,e,h])]
for y, b, e, h in second_column:
third_column = [(r, c, f, i) for r, c, f, i, yy in column
if yy == y and not set([a,d,g,b,e,h]) & set([c,f,i]) and r == 0 ]
for _, c, f, i in third_column:
yield (100 * g + 10 * h + i, 100 * d + 10 * e + f, 100 * a + 10 * b + c)
-
in above example for by for by for is bad idea, you can remove it by recursion. The code will be much less messy
-
if you want try 6-digits number, you can change check unique digits (using set at examples) to multiset (at python you can use Counter` class from collections library to emulate it)Code Snippets
from itertools import permutations
def permutations_solver():
digits = set('987654321')
numbers = (''.join(x) for x in permutations(digits, 6))
for x in numbers:
a = int(x[0 : 3])
b = int(x[3 : 6])
c = a - b
if b > c and c > 0 and set(str(c) + x) == digits:
yield a, b, c
print(len(list(permutations_solver())))""" set('abcdefgh') == set('123456789') and set('zxyr') == set('01')
zxyr abc < def (enough a < d)
abc z == 0
+def x + a + d == g + 10 * z
---- y + b + e == h + 10 * x
ghi r + c + f == i + 10 * y
zxy r == 0 // it looks like logic programming problem
"""
from itertools import product
def digits_solver():
column = [(x, a, d, (x + a + d) % 10, (x + a + d) // 10)
for x, a, d in product(range(2), range(1, 10), range(1, 10))
if len(set([a, d, (x + a + d) % 10])) == 3 and (x + a + d) % 10 != 0]
first_column = [(x, a, d, g) for x, a, d, g, z in column if z == 0 and a < d]
for x, a, d, g in first_column:
second_column = [(y, b, e, h) for y, b, e, h, xx in column if xx == x and not set([a,d,g]) & set([b,e,h])]
for y, b, e, h in second_column:
third_column = [(r, c, f, i) for r, c, f, i, yy in column
if yy == y and not set([a,d,g,b,e,h]) & set([c,f,i]) and r == 0 ]
for _, c, f, i in third_column:
yield (100 * g + 10 * h + i, 100 * d + 10 * e + f, 100 * a + 10 * b + c)Context
StackExchange Code Review Q#123800, answer score: 3
Revisions (0)
No revisions yet.