Algorithm: Printing the correct index for the character sequence

Question

I came across the following problem while preparing for an exam:

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.

The sequence of characters needs to be in ascending order only (i.e. 'ab' is valid but 'ba' is not).

Question: Given any word, print its index if valid and 0 if not.

Input Output
ab 27
ba 0
aez 441 

Any pointers on how to solve this would be appreciated.

Answer 1

Let me give you a few hints:

• Can you find a formula for the number of such words of a given length k ?
• Now fix a length k, and a letter l. How many word of length k starting with l are they ?

Hint: Pascal triangle. If you need some more hint, http://en.wikipedia.org/wiki/Combinadic can help. If you need some implementation, you can get inspiration from the rank function defined in (Python language) https://github.com/sagemath/sagelib/blob/master/sage/combinat/choose_nk.py

Answer 2

1. make sure the input is letters only. Fail if not.
2. Setup a loop based on the string length minus 1.
3. "Subtract" the value of the first letter in the string from the next. If the value is zero or positive, you are done as the string is non-ascending so return 0.
4. Repeat by moving up the string one letter at a time checking the next letter.
5. If you get to the end, it is an ascending order string.

To be fair, I have not mentioned an algorithm on how to calculate the index value, just the exit case. But it gives you a start in the right direction and calculating the index will follow the same framework.

More Info:

Start counting upwards on first letter. When you hit 'z', reset to next valid string and keep counting -> "aa" fails don't count it. Add to next which here is "ab". Once you hit "az", try "ba" - fail, keep adding letters until you get a valid string "bc" and start counting again. It's like an odometer that counts upwards.

Dang slow, but it should work as it is what you do manually to get the answer.

BTW, there is a much more elegant solution hinted at by @hivert that would be nearly instant to calculate...