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.

• Consecutive characters are easier to type if they use different hands. Therefore, we say that each pair of consecutive characters that uses the same typing hand contributes 1 unit to the typing cost. For example, typing d followed by a adds 1 to the this component of the typing cost because d and a are both typed using the left hand. On the other hand, typing n followed by e does not contribute anything to this component of the typing cost because n and e are typed using different hands. An exception to this rule is when the two consecutive characters are identical; such a pair of characters does not contribute anything to this component of the typing cost (e.g., the consecutive ns in cnn.com).
• We assume that the typist begins in the neutral touch typing position, with the fingers of the left hand over the keys a, s, d, and f, and the fingers of the right hand over the keys j, k, l, and ;. In order to type characters that are not in this middle row of keys, the hands are moved to the top and bottom rows. For example, to type r, the left hand is moved to the top row. Similarly, to type . (dot), the right hand is moved to the bottom row. Each such movement costs twice the number of rows moved. We assume that after typing a character, the hand remains over that character's row. For example, after typing r, the left hand stays over the top row until we need to move it in order to type another character with the left hand. Thus, if the r is followed by characters l and o, which are typed using the right hand, the left hand remains on the top row. For example, in order to type x after typing r and u, the left hand must move from the top row (used to type r) to the bottom row (for x); at a cost of 4 units (twice the distance of two rows).
• Typing the characters t, g, b, y, h, and n requires stretching the index finger. Therefore, each occurrence of any of these characters adds 3 units to the typing cost. An exception to this rule is when any of these characters is repeated in succession; in such a case, only the first occurrence of the character is charged the cost of 3 units. For example, typing bgth incurs a cost of 12 units (3 times 4) due to stretching. However, typing bbbbbhhhhh incurs a cost of only 6 units (3 times 2) due to stretching (once for the bs and once for the hs). Each of the characters in bhbhbh incurs a stretching cost of 3 units (for a total of 18) because the bs and hs are not contiguous.

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.

  
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: Web Browser Window Placement Up: No Title Previous: Web Server Cache