I have a triangle with four integer values at the top between 1 to 256. The values below it are all determined by the "distance" between the two values immediately above them. That distance is the subtraction of the left-hand "parent" from the right-hand parent, plus 1. It this result would be 0 or negative, then 256 is added to the result, so it is guaranteed to be between 1 and 256.
49 52 158 201
\ / \ / \ /
4 107 44
\ / \ /
104 194
\ /
91
The top row is the input. The other rows are derived:
The second row starts with 52 - 49 + 1 = 4, then follows 158 - 52 + 1 = 107, ...etc.
The second value in the third row needs the additional 256: it is 44 - 107 + 1 + 256 = 194
For the actual challenge, we don't have the third input value, but instead the final value at the bottom, and we need to find out what the third value should be. Also, the range of the values is not always 1..256, but 1..VariableNo_In_1_Group, where these are inputs too. In the above example, Variable = 2 and No_In_1_Group = 8
So we have this pattern:
c1 c2 c3 c4
\ / \ / \ /
f1 f2 f3 (f: first level distance)
\ / \ /
s1 s2 (s: second level distance)
\ /
t1 (t: third level distance)
Given input: Variable, No_In_1_Group, c1, c2, c4, t1
Required output: c3
Input: c1 = 49, c2 = 52, c4 = 201, t1 = 91, Variable = 2, No_In_1_Group = 8
Output: c3 = 158
49 52 ? 201
\ / \ / \ /
. . .
\ / \ /
. .
\ /
91
I have a function Distance_Calculation:
def Distance_Calculation(Variable, No_In_1_Group, Comb_1, Comb_2):
"""This function gives the value of "*Direct_Distance*" if Comb_1 & Comb_2 are known."""
if (Comb_2 >= Comb_1):
return Comb_2 - Comb_1 + 1
else:
return pow(Variable, No_In_1_Group) - Comb_1 + Comb_2 + 1
So I could call it like this, provided I already gave the values of the arguments:
f1 = Distance_Calculation(Variable, No_In_1_Group, c1, c2) or
s2 = Distance_Calculation(Variable, No_In_1_Group, f2, f3) or
t1 = Distance_Calculation(Variable, No_In_1_Group, s1, s2)
But I would need sometimes to derive a sibling value from a child value. For that I have this function:
"""If Comb_1 & Direct_Distance are known, then Comb_2 will be calculated using this function"""
def Reverse_Distance_Calculation(Variable, No_In_1_Group, Comb_1, Direct_Distance):
if (Comb_1+Direct_Distance-pow(Variable, No_In_1_Group)-1 <= 0 and Direct_Distance-1 >= 0):
return Comb_1 + Direct_Distance - 1
else:
return Comb_1 + Direct_Distance - pow(Variable, No_In_1_Group) - 1
In a similar fashion, all f and s values are calculated with the following code:
def get_unknown_element(c1, c2, c4_final, t1_final):
c4 = c4_final
base_reminder_index = Variable**No_In_1_Group
for i in range(1,base_reminder_index+1):
c3 = i
f1 = Distance_Calculation(Variable, No_In_1_Group, c1, c2)
f2 = Distance_Calculation(Variable, No_In_1_Group, c2, c3)
f3 = Distance_Calculation(Variable, No_In_1_Group, c3, c4)
s1 = Distance_Calculation(Variable, No_In_1_Group, fld1, fld2)
s2 = Distance_Calculation(Variable, No_In_1_Group, fld2, fld3)
t1 = Distance_Calculation(Variable, No_In_1_Group, sld1, sld2)
if (t1 == t1_final):
return i
return -1
The above method is not very efficient as it takes a max of 256 iterations in every single run and I have run this code more than 1000 times to get my desired result. Is there an efficient method where iterations can be reduced drastically?
I would first consider Variable and No_In_1_Group as one input m, like m=256 in your example.
The calculation adds 256 (ie. the value m) when a result would become negative. This corresponds to modular arithmetic. When c2 would be less than c1 or equal), we should get m + (c2 - c1 + 1), but that is c2 - c1 (mod m) + 1, which in Python you get with the modulo operator: (c2 - c1) % m + 1. The + 1 is left out of the modulo operation as you don't values in the range 0..m-1, but 1..m
The calculation can be expanded from top to bottom as follows, always considering that the expressions are to be considered modulo m (as explained above):
c1 c2 c3 c4
\ / \ / \ /
(c2-c1+1) (c3-c2+1) (c4-c3+1)
\ / \ /
(c3-2c2+c1) (c4-2c3+c2)
\ /
(c4-3c3+3c2-c1+1)
The bottom expression must equal t1 - 1 (mod m) + 1, so to rewrite that in terms of c3 (the unknown):
3c3 = c4 + 3c2 - c1 - t1 (mod m) + 1
Because of the coefficient 3 at the left side we actually have 3 candidates to solve this equation:
c3 = [c4 + 3c2 - c1 - t1 (mod m) + 1] / 3
or [c4 + 3c2 - c1 - t1 (mod m) + 1 + m] / 3
or [c4 + 3c2 - c1 - t1 (mod m) + 1 + 2m] / 3
To rewrite this in Python:
def solve (c1, c2, c4, t1, m):
triple_c3 = (c4 + 3*c2 - c1 - t1) % m + 1
if triple_c3 % 3:
triple_c3 += m
if triple_c3 % 3:
triple_c3 += m
if triple_c3 % 3:
return None # No solution
return (triple_c3 // 3 - 1) % m + 1 # map to 1..m range
c3 = solve(49, 52, 201, 91, 256)
print(c3) # 158