On modern game consoles and other devices without traditional keyboards, trying to input text is a nightmare. Having to type with a few buttons and a joystick on a virtual keyboard is annoying, and I like to make as few movements/button presses as possible.
The keyboard you will be using looks like this:
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
+---+---+---+---+---+---+---+---+---+---+
| q | w | e | r | t | y | u | i | o | p |
+---+---+---+---+---+---+---+---+---+---+
| a | s | d | f | g | h | j | k | l | - |
+---+---+---+---+---+---+---+---+---+---+
| z | x | c | v | b | n | m | _ | @ | . |
+---+---+---+---+---+---+---+---+---+---+
The following operations can be used:
L: move one square to the left on the keyboard (wraps)R: move one square to the right on the keyboard (wraps)U: move one square up on the keyboard (wraps)D: move one square down on the keyboard (wraps)Y: insert a spaceB: move the insertion pointer one space to the left (does nothing if pointer is at the beginning)F: move the insertion pointer one space to the right (does nothing if pointer is at the end)C: toggle caps lockA: insert the selected character at the position of the insertion pointer
Given an input string containing only ASCII characters that can be typed using the above keyboard and commands (matches [a-zA-Z0-9 [email protected]]*), output a sequence of commands that will result in the output string. The initial position of the cursor is on the 1 key (the top-left), and caps lock is initially off.
Scoring
For any given string, a naive approach would be, for each character in the string, navigate to the character on the keyboard by the shortest path, toggle caps lock if necessary, and select the character. Such a naive approach would generate a command of length (length of input string) + (sum of Manhattan distances on keyboard between consecutive non-space characters) + (number of times the string alternates between lowercase and uppercase characters) + (1 if string starts with an uppercase letter else 0). For example, the naive approach for 101 would result in ALARA, a length 5 command, and Noob 5 would result in DDDRRRRRCAUURRRCAADDLLLLAYUUUA, a length 30 command.
Your submission, however, seeks to do better than the naive approach. For each input string, your submission will receive points equal to the number of commands the naive approach uses minus the number of commands your submission outputs. Your overall score will be the sum of the individual scores.
Rules
- Submissions will be run on a Cloud9 free virtual workspace. The workspace has 512 MB of RAM, 2 GB of disk space, 8 Intel(R) Xeon(R) CPUs @ 2.50 GHz (full CPU info, found by running
cat /proc/cpuinfo, can be found here), and is running 64-bit Ubuntu 14.04 Trusty. You may request access to the testing workspace in order to run and score your submission, or I can score it for you. - Submissions will be run once per test case. Storing state between runs is forbidden. Submissions may not write to or read from any files other than the source file (which may not be modified between runs), with the possible exception of reading an input file if required.
- Submissions are limited to 1 minute of runtime for each test case. Submissions may output multiple solutions, but only the last valid solution within the allotted time will be used for scoring. Failure to output any valid solutions within the allotted time will result in a score of 0 for that test case.
- Please include directions on how to invoke your submission, as well as any tools/libraries that need to be installed that aren't included with a standard Ubuntu 14.04 install.
- The winner will be the submission with the largest score. In the event of a tie, the submission with the better algorithmic complexity will win. If the tie is still not resolved, the first submission to reach the score and algorithmic complexity will win.
- Submissions may not optimize for the test cases. I reserve the right to change the test cases if I feel there is a need.
Test cases
Format: input string => naive score
(if you see any errors in these, please leave a comment with the correction)
101 => 5
quip => 12
PPCG => 15
Mego => 25
Noob 5 => 26
penguin => 27
867-5309 => 32
2_sPoOkY_4_mE => 60
The Nineteenth Byte => 76
[email protected] => 95
8xM3R__5ltZgrkJ.-W b => 98
correcthorsebatterystaple => 104
verylongRUNSOFCAPSandnocaps => 118
This is an English sentence. => 122
WNtza.akjzSP2GI0V9X .0epmUQ-mo => 131
Programming Puzzles and Code Golf => 140
