The Special Services Group within CompuCo specializes in the development of products to meet the needs of physically disabled individuals. The engineering staff within this division has recently completed the construction of their latest prototype: an input device with just a single pushbutton that will hopefully prove to be useful in making the power of the personal computer more readily available to people with certain physical disabilities. This device has been dubbed "The Clicker" by those associated with it in house.
The Special Services Project Leader has assigned your software development team the task of devising a way to use the Clicker to perform text input. After considering several other options, your team has decided to initially explore the idea of using the Clicker in conjunction with a scrolling menu of 128 possible selections, each corresponding to one of th 128 ASCII characters in the range 0 to 127 (the menu must of necessity be long and narrow since it will need to appear on the same screen as whatever application it is working with). The first (topmost) character presented in the menu will be highlighted initially. If the user makes a fast click (holding the button down for less than half of a second), the menu highlight will move down one position, highlighting the next character. For a user to actually "type" the highlighted character, they must hold the button down for more than half of a second (a selection click). The menu will wrap around to the beginning should the user accidentally bypass a desired character when moving the highlight.
To produce a character, the user will either make a selection click immediately (indicating that the character initially presented at the top of the menu is to be typed), or they will make a series of fast clicks to move to the desired character first and then make a selection click (if the desired character is presented in the fifth position, the user must make four fast clicks and one selection click to cause it to be typed). The four fast clicks are considered overhead clicks necessary to ensure that the proper character is typed.
Your team quickly realized that if the menu selections are always presented in the standard ASCII code sequence (or any fixed sequence), users of the Clicker are going to be become involved in an extremely time-consuming and tedious task. It would be better if the menu could be presented more dynamically, with each click causing the characters presented in the menu to be re-arranged into an order of decreasing likelihood for the subsequent click. With an accurate projection of the likelihood of each character, this scheme would help to significantly reduce the total number of overhead clicks required to enter text. Your team has decided to construct a transition matrix based upon some sample text from a user and then use it to reorganize the menu for that person, working under the assumption that a user's typing pattern will follow similar transition probabilities in the future. In the transition matrix, the (i, j) entry will reflect the number of times that the character with ASCII value i was immediately followed by the character with ASCII value j in the sample text. Once the transition matrix has been built, the order of the characters displayed in the menu will depend upon the most recently typed character. If that character has ASCII value x, then the order of the characters presented in the menu will be based upon row x of the matrix. If the (x, y) entry exceeds the (x, z) entry, then the character with ASCII value y will be presented in the menu ahead of the character with ASCII value z. When the (x, y) entry and the (x, z) entry are equal, the character which corresponds to the lesser of y and z will appear earlier in the menu. The first menu displayed (prior to any character being "typed") is to be based upon row 0 of the transition matrix.
Write a program that will construct such a transition matrix from a sample input text. Then, use it to determine the minimum number of overhead clicks that are required to enter a second passage of text with the Clicker, assuming that the user never makes an error in selecting a character from the menu. The program should also compute the average number of overhead clicks per character (under this assumption) as well as displaying the number of characters appearing in the passage of text entered with the Clicker.
a short piece of text a piece of short text
22 characters were "typed" with 13 overhead clicks. This is an average rate of 0.59 overhead clicks per character.
The ACM Scholastic Programming Contest is a contest consisting of Regional Contests from which teams are selected to advance to the Contest Finals. Competition is among teams of students representing institutions of higher education. The ACM Scholastic Programming Contest is an activity of the Contest Steering Committee and, consequently, of the Local Activities Board. The "Contest Director," who serves as chairman of the steering committee, coordinates these contests, oversees budgetary matters, and assures conformance with ACM policies and procedures. Rules for the Scholastic Programming Contest are determined by the Contest Steering Committee. The Contest Director is solely responsible for interpreting the rules and for ruling on any unforeseen situations. 6.Contestants may report claims of rule violations or misconduct of the contest within 7 days of the Regional Contest to the Director of Regional Contests. The Director of Regional Contests will make a recommendation within the next 7 days to the Contest Steering Committee. The Contest Steering Committee may, by a 2/3 vote, overturn the results of the Regional Contest no later than December 6. Should circumstances disqualify finalists, the Contest Steering Committee shall designate the teams to advance to the Contest Finals.
534 characters were "typed" with 7944 overhead clicks. This is an average rate of 14.88 overhead clicks per character.