Suppose I have three integers. I want to get a list of all possible values obtained by performing all 16 (4x4 of *, /, +, - ) operations among between them.
Like if I have 3 4 1, we should get values 1, 2, 6, 7, 8, 9, 11, 12,
13, 15 and 16. That is,
res = num1 (op1) num2 (op2) num3 where operators are:
["**", "*/", "*+", "*-", "/*", "//", "/+", "/-", "+*", "+/", "++", "+-", "-*", "-/", "-+", "--"]
However, the catch is that division can only be possible if
x%y==0i.e. divisor is factor of dividend.
So, far I've been able to brute force every operation but am missing some answers. I also defined a custom divide operation to take the catch into account.
I'm required to return a list containing unique values that are all positive.
My current code is a mess but here it is for the sake of it. This is missing out some values too.
def div(x, y):
if x!=0 and y!=0:
if x%y==0:return x/y
else:return None
ops_lis = ["**", "*/", "*+", "*-", "/*", "//", "/+", "/-", "+*", "+/", "++", "+-", "-*", "-/", "-+", "--"]
d1, d2, d3 = map(int, input().split())
cal_lis, res_lis = [], []
for op in ops_lis:
if op[0] == "*" and op[1] == "*":cal_lis.append(d1*d2*d3)
if op[0] == "*" and op[1] == "/":
if div(d1*d2, d3) != None:cal_lis.append(div(d1*d2, d3))
cal_lis.append(div(d1*d2, d3))
if op[0] == "*" and op[1] == "+":
cal_lis.append(d1*(d2+d3))
cal_lis.append((d1*d2)+d3)
if op[0] == "*" and op[1] == "-":
cal_lis.append(d1*d2-d3)
cal_lis.append(d1*(d2-d3))
cal_lis.append((d1*d3)-d2)
if op[0] == "/" and op[1] == "*":cal_lis.append(div(d1, d2*d3))
if op[0] == "/" and op[1] == "/":
if div(d1, d2) == None or div(d2, d3) == None:
cal_lis.append(None)
else:
cal_lis.append(div(div(d1, d2), d3))
if op[0] == "/" and op[1] == "+":
if div(d1, d2) == None:
cal_lis.append(None)
else:
cal_lis.append(div(d1, d2)+d3)
if op[0] == "/" and op[1] == "-":
if div(d1, d2) == None:
cal_lis.append(None)
else:
cal_lis.append(div(d1, d2)-d3)
if op[0] == "+" and op[1] == "*":
cal_lis.append(d1+d2*d3)
cal_lis.append((d1+d2)*d3)
cal_lis.append((d1+d3)*d2)
if op[0] == "+" and op[1] == "/":
if div(d2, d3) == None:
cal_lis.append(None)
else:
cal_lis.append(d1+div(d2, d3))
if op[0] == "+" and op[1] == "+":cal_lis.append(d1+d2+d3)
if op[0] == "+" and op[1] == "-":cal_lis.append(d1+d2-d3)
if op[0] == "-" and op[1] == "*":
cal_lis.append(d1-d2*d3)
cal_lis.append((d1-d2)*d3)
cal_lis.append((d1-d3)*d2)
if op[0] == "-" and op[1] == "/":
if div(d2, d3) == None:cal_lis.append(None)
else: cal_lis.append(d1-div(d2, d3))
if div(d1-d2, d3) == None:cal_lis.append(None)
else: cal_lis.append(div(d1-d2, d3))
if op[0] == "-" and op[1] == "+":cal_lis.append(d1-d2+d3)
if op[0] == "-" and op[1] == "-":cal_lis.append(d1-d2-d3)
# print(cal_lis)
cal_lis = [int(cal) for cal in cal_lis if cal!=None]
for res in cal_lis:
if (res > 0 and res not in res_lis):
res_lis.append(int(res))
for a in sorted(res_lis):
print(a, end=" ")
print()
Is there an efficient way to perform this task (using trees maybe ?) given that the division condition is also true ?
Any help would be appreciated...
EDIT: Added Constraints
The calculation must conform to the following format: number = dice1 op1 dice2 op2 dice3
where:
To get all possible results, you will need to include grouping of operations in you combinations. I would suggest a recursive function for this:
def calcAll(*values,seen=None):
seen = seen or set()
if len(values) == 2:
a,b = values
a,sa = (a[0],f"({a[1]})") if isinstance(a,tuple) else (a,str(a))
b,sb = (b[0],f"({b[1]})") if isinstance(b,tuple) else (b,str(b))
if a>b : a,sa, b,sb = b,sb, a,sa
if (a,b) in seen or seen.add((a,b)) :return
yield a+b, f"{sa}+{sb}"
yield a*b, f"{sa}*{sb}"
yield a-b, f"{sa}-{sb}"
yield b-a, f"{sb}-{sa}"
if b != 0 and a%b==0: yield a//b, f"{sa}/{sb}"
if a != 0 and b%a==0: yield b//a, f"{sb}/{sa}"
return
pairs = ((i,j) for i in range(len(values)-1) for j in range(i+1,len(values)))
for i,j in pairs:
rest = [*values]
a,b = rest.pop(j),rest.pop(i)
for paired in calcAll(a,b,seen=seen):
for result in calcAll(paired,*rest):
if result in seen or seen.add(result): continue
yield result
output:
# distinct positive solutions sorted by result
for r,sr in sorted(calcAll(3,4,1)):
if r>0: print(sr,"=",r)
(1*4)-3 = 1
4-(3/1) = 1
(4/1)-3 = 1
(4-3)*1 = 1
4/(1+3) = 1
4-(1*3) = 1
(4-3)/1 = 1
1/(4-3) = 1
3/(4-1) = 1
(1+3)/4 = 1
(4-1)/3 = 1
1-(3-4) = 2
4-(3-1) = 2
(1+4)-3 = 2
(1-3)+4 = 2
(4-3)+1 = 2
4/(3-1) = 2
(4-1)+3 = 6
(3-1)+4 = 6
3-(1-4) = 6
4-(1-3) = 6
(4+3)-1 = 6
(1*4)+3 = 7
(3/1)+4 = 7
(4/1)+3 = 7
(1*3)+4 = 7
(4+3)/1 = 7
(4+3)*1 = 7
(1+4)+3 = 8
(1+3)+4 = 8
(3-1)*4 = 8
(4+3)+1 = 8
(4-1)*3 = 9
(4*3)-1 = 11
(1*4)*3 = 12
(4*3)*1 = 12
(4*3)/1 = 12
(1*3)*4 = 12
(3/1)*4 = 12
(4/1)*3 = 12
(4*3)+1 = 13
(1+4)*3 = 15
(1+3)*4 = 16
If you only want the distinct positive results:
print( set(r for r,_ in calcAll(3,4,1) if r>0) )
{1, 2, 6, 7, 8, 9, 11, 12, 13, 15, 16}
The function also works for larger lists of numbers:
# one solution for each positive result of operations between 4 numbers
for r,sr in sorted(dict(calcAll(1,2,3,4)).items()):
if r>0: print(sr,"=",r)
(2/1)+(3-4) = 1
(2-1)-(3-4) = 2
(2/1)-(3-4) = 3
(4*3)/(2+1) = 4
((4*3)/2)-1 = 5
(4*3)/(2/1) = 6
((4*3)/2)+1 = 7
(4+3)-(1-2) = 8
(4*3)-(2+1) = 9
(4*3)-(2/1) = 10
(1-2)+(4*3) = 11
(4*3)/(2-1) = 12
(4*3)-(1-2) = 13
(2/1)+(4*3) = 14
(2+1)+(4*3) = 15
(1+(4+3))*2 = 16
(3*(4+2))-1 = 17
(3/1)*(4+2) = 18
(3*(4+2))+1 = 19
((3*2)-1)*4 = 20
(2+1)*(4+3) = 21
((4*3)-1)*2 = 22
(2*(4*3))-1 = 23
(2/1)*(4*3) = 24
(2*(4*3))+1 = 25
(1+(4*3))*2 = 26
(1+(4*2))*3 = 27
(1+(3*2))*4 = 28
(4+1)*(3*2) = 30
(3+1)*(4*2) = 32
(2+1)*(4*3) = 36
And also for duplicate numbers:
for r,sr in sorted(dict(calcAll(3,3,3)).items()):
if r>0: print(sr,"=",r)
3-(3/3) = 2
3/(3/3) = 3
(3/3)+3 = 4
(3*3)-3 = 6
(3+3)+3 = 9
(3*3)+3 = 12
(3+3)*3 = 18
(3*3)*3 = 27