UVa 417

From Algorithmist
Jump to navigation Jump to search

417 - Word Index[edit]

Summary[edit]

Consider the English alphabet {a,b,c,...,z}. Using this alphabet, a set of valid words are to be formed that are in a strict lexicographic order. In this set of valid words, the successive letters of a word are in a strictly ascending order; that is, later letters in a valid word are always after previous letters with respect to their positions in the alphabet list {a,b,c,...,z}. For example,

abc aep gwz

are all valid three-letter words, whereas

aab are cat

are not.

For each valid word associate an integer which gives the position of the word in the alphabetized list of words. That is:

   a -> 1
   b -> 2
   .
   .
   z -> 26
   ab -> 27
   ac -> 28
   .
   .
   az -> 51
   bc -> 52
   .
   .
   vwxyz -> 83681

Your program is to read a series of input lines. Each input line will have a single word on it, that will be from one to five letters long. For each word read, if the word is invalid give the number 0. If the word read is valid, give the word's position index in the above alphabetical list.

Explanation[edit]

The most easy way to solve this problem is generate all the strings valid in an ordered way, and then look for the string from the input. You can do this generating the strings and saving them into a vector or a map.

Gotchas[edit]

  • It could be tricky generate all the strings with a short and generic code. Don't give up!

Notes[edit]

  • There is many different ways to solve this problem. If you solve it, try to re-think with a different "frame", for example, if you do it using a map, can you do it with graph concepts...?

Implementations[edit]

- Version 1: (soon)

Optimizations[edit]

With multiple lines in the input, is better precalculate and store the 83681 string-value pairs.

Input[edit]

z
a
cat
vwxyz

Output[edit]

26
1
0
83681

Solutions[edit]

References[edit]

  1. Reference 1

Categories here, use the form [[Category: Category Name]], see Categories for a list