Imagine an alphabet of words.
Example:
a ==> 1
b ==> 2
c ==> 3
z ==> 26
ab ==> 27
ac ==> 28
az ==> 51
bc ==> 52
and so on.
Such that the sequence of characters need to be in ascending order only (ab is valid but ba is not). Given any word print its index if valid and 0 if not.
Input Output
ab 27
ba 0
aez 441
In this question, I can do math easily but I am not getting any algorithm.
What i did in math is
one letter 26
two letter 325
.
.
.
so on
Now for the magic formula:
Coded with examples and demonstration of speed even in worse case scenario:
def comb(n,k): #returns combinations
p = 1 #product
for i in range(k):
p *= (n-i)/(i+1)
return p
def solve(string):
x = []
for letter in string:
x.append(ord(letter)-96) #convert string to list of integers
x = list(reversed(x)) #reverse the order of string
#Next, the magic formula
return x[0]+sum(comb(26,i)-comb(26-x[i-1]+1,i)*(1-i/(26-x[i-1]+1)) for i in range(2,len(x)+1))
solve('bhp')
764.0
>>> solve('afkp')
3996.0
>>> solve('abcdefghijklmnopqrstuvwxyz')
67108863.0
>>> solve('hpz')
2090.0
>>> solve('aez')
441.0
>>> if 1:
s = ''
for a in range(97,97+26):
s += chr(a)
t = time.time()
for v in range(1000):
temp = solve(s)
print (time.time()-t)
0.1650087833404541
In order to understand my explanation to this formula, I need to go over a mathematical occurrence in pascal's triangle and the binomial theorem:
Here is pascal's triangle:
Going from top right to bottom left, first there is a sequence of 1s. Then a sequence of the counting numbers. The next sequence is the sum of the counting numbers. These are known as the triangular numbers. The next sequence is the sum of the triangular numbers, known as the tetrahedral numbers and this pattern goes on and on.
Now for the binomial theorem:
By combining the binomial theorem and pascals triangle, it can be seen that the nth triangular number is:
and nth tetrahedral number is:
the sum of the first n tetrahedral numbers is:
and on ...
Now for the explanation. For this explanation, I will only use 6 letters, a-f, and will replace these with the numbers 1-6. The procedure is the same with more letters
If the length is 1, then the possible sequences are:
1
2
3
4
5
6
In this the answer is simply the value
Now for a length of 2:
12 13 14 15 16
23 24 25 26
34 35 36
45 46
56
To solve this we split it into 3 parts:
Next we will repeat for sequences of length 3:
123 124 125 126
134 135 136
145 146
156
234 235 236
245 246
256
345 346
356
456
Once again we split this problem into steps:
This
234 235 236
245 246
256
becomes
12 13 14
23 24
34
Combining these our total formula for length 3 becomes:
We can follow this pattern of reduction for higher length sequences
Now we will right out our formulas to look for patterns:
Length 1: y1
Length 2:
Length 3:
Note: I also used length 4 to make sure the patterns held
With a bit of math, grouping of terms, and the change from 6 to 26 our formula becomes:
In order to simplify this further, more math must be done.
This identity holds true for all a and b. For a quick fun exercise, prove it (not really difficult):
This identity allows as to further group and negate terms to reach our much oversimplified formula:
This is a combination of two problems: parsing a number in a base that isn't 10 and determining if input is sorted.
Note that, since this is probably homework, you probably can't just use existing methods to do the hard work.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With