next up previous
Next: Web Browser Window Placement Up: No Title Previous: Web Server Cache

Finger-Friendly Domain Names

Your Internet startup needs a domain name. Your market research guru tells you that users tend to avoid sites with names that are hard to type. Thus, you must pick a name that is easy to type. For your research, you decide to use the idealized keyboard model suggested by Figure 1. Note that the keys are perfectly aligned both horizontally and vertically, unlike the skewed positioning of keys in typical keyboards. You decide to assign a typing cost to each domain name (or any word, in general) based on the following rules.

Your goal is to write a program that takes a list of words (presumably candidate domain names) as input and outputs their typing costs. If the word contains a character that is absent from the idealized keyboard suggested by Figure 1, you should replace that character with the , (comma) character for the purpose of calculating the typing cost. For example, the typing cost of foo-bar_baz is calculated by applying the above rules to foo,bar,baz (obtained by replacing the - and _ characters with ,). Similarly, if the input contains uppercase characters (e.g., DiScO.oRG), you should replace them with the corresponding lowercase characters (disco.org) for calculating the typing cost. You may assume a maximum word length of 256 characters.

   figure108
Figure: The idealized keyboard

Input Format

The input consists of a sequence of words (e.g., foo, bar, barney.com, abra.cadabra.gov.jp) separated by white space (space, tab, or newline). The end of the sequence is denoted using the reserved word ``.'' (a single period). A sample input is displayed below:

 UMD.edu  TheNextBigThing.com  abra.cadabra.gov.jp
 database.org www.linux.org .

Output Format

Your program should output the typing costs of the input words (in the same order as the input words). It should print each cost on a separate line. The required output on the above input is displayed below:

16
81
56
36
46

Example

Consider the first domain name in our sample input: UMD.edu. First, we convert the uppercase letters to lowercase, yielding umd.edu. The pairs (u,m) and (e,d) are consecutive characters that must be typed using the same hand. Therefore, each pair contributes 1 unit to the typing cost, for a total of 2. Further, typing u requires moving the right hand from the middle row to the top row, at a cost of twice the distance (1 row): 2 units. Next, typing m requires moving the right hand from the top row to the bottom row, at a cost of twice the distance (2 rows): 4 units. Typing the next d does not require moving the left hand since it is over the middle row initially. Typing . does not require moving the right hand since it is already over the bottom row (from typing m earlier). Typing e requires moving the left hand from the middle row to the top row, at a cost of 2 units (twice the distance moved). Similarly, typing d requires moving the left hand back to the middle row, at a cost of 2 units. Typing the final u requires moving the right hand from the bottom row to the top row, at a cost of 4 units. Thus, the total cost of hand movements between rows is 2 + 4 + 2 + 2 + 4 = 14 units. Since umd.edu does not contain any of the characters that require stretching the index finger for typing, there is no additional cost, and the final typing cost of umd.edu is 16 units (2 units due to pairs of characters and 14 units due to hand movements between rows).

Test data used in judging

Input 1 Output 1
Input 2 Output 2
Input 3 Output 3
Input 4 Output 4
Input 5 Output 5

Our Solution


next up previous
Next: Web Browser Window Placement Up: No Title Previous: Web Server Cache

Chau-Wen Tseng
Tue Mar 14 18:48:15 EST 2000