Algorithm: print the correct index for a sequence of characters

Question

In preparation for the exam, I encountered the following problem:

Imagine the 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 should only be in ascending order (i.e., "ab" is valid, but "ba" is not).

Question For any word, type its index if it is valid and 0 if not.

 Input Output ab 27 ba 0 aez 441 

Any pointers on how to solve this problem would be appreciated.

Answer 1

Let me give you some tips:

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

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

Answer 2

• make sure that only letters are entered. Fail if not.
• Set up a loop based on line length minus 1.
• Subtract the value of the first letter in the string from the following. If the value is zero or positive, you are executed as the line does not rise, so return 0.
• Repeat by moving the line one letter at a time, checking the next letter.
• If you get to the end, this is an ascending line.

In fairness, I did not mention the algorithm for calculating the index value, namely in the case of exit. But it gives you a start in the right direction, and index calculation will follow the same structure.

Additional Information:

Start counting up the first letter. When you press "z", reset to the next valid line and continue to count → "aa" are not counted. Add to the next that here is "ab". As soon as you press “az”, try “ba” - crash, keep adding letters until you get a valid string “bc” and start counting again. It is like an odometer that counts up.

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

By the way, there is a much more elegant solution outlined by @hivert that will calculate almost instantly ...