# Virtual Keyboard Text Input

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 space
• B: 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 lock
• A: 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 _@.-]*), 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
penguins@SouthPole.org => 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

• I got -27 ... never mind Apr 10 '16 at 11:13
• @Mego: I think he's saying that his solution did worse than naive. :P Apr 10 '16 at 19:11
• I agree, gaming console keyboards suck. Apr 11 '16 at 16:46
• What happens if the program does not terminate within one minute but prints out one or more solutions within that time? Is there any penalty for not terminating? May 13 '16 at 12:25
• @mIllIbyte The last valid (i.e. results in the correct text) command printed out within the time limit is used. If no valid command is printed out, then the score is 0.
– user45941
May 13 '16 at 20:33

# C

The score is 193.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define LEFT 'L'
#define RIGHT 'R'
#define CAPS 'C'
#define UP 'U'
#define DOWN 'D'
#define SPACE 'Y'
#define CURSORLEFT 'B'
#define CURSORRIGHT 'F'
#define APPLY 'A'
#define TABLEX 10
#define TABLEY 4
#define casediff(A,B) (isupper(A)*islower(B)+islower(A)*isupper(B))
typedef struct {int x; int y;} coord;
coord letters[300];
#define initLetter(letter, X, Y) \
letters[letter].x=X, letters[letter].y=Y
#define initAllLetters(); \
initLetter('1',0,0);\
initLetter('1',0,0);\
initLetter('2',1,0);\
initLetter('2',1,0);\
initLetter('3',2,0);\
initLetter('3',2,0);\
initLetter('4',3,0);\
initLetter('4',3,0);\
initLetter('5',4,0);\
initLetter('5',4,0);\
initLetter('6',5,0);\
initLetter('6',5,0);\
initLetter('7',6,0);\
initLetter('7',6,0);\
initLetter('8',7,0);\
initLetter('8',7,0);\
initLetter('9',8,0);\
initLetter('9',8,0);\
initLetter('0',9,0);\
initLetter('0',9,0);\
initLetter('Q',0,1);\
initLetter('q',0,1);\
initLetter('W',1,1);\
initLetter('w',1,1);\
initLetter('E',2,1);\
initLetter('e',2,1);\
initLetter('R',3,1);\
initLetter('r',3,1);\
initLetter('T',4,1);\
initLetter('t',4,1);\
initLetter('Y',5,1);\
initLetter('y',5,1);\
initLetter('U',6,1);\
initLetter('u',6,1);\
initLetter('I',7,1);\
initLetter('i',7,1);\
initLetter('O',8,1);\
initLetter('o',8,1);\
initLetter('P',9,1);\
initLetter('p',9,1);\
initLetter('A',0,2);\
initLetter('a',0,2);\
initLetter('S',1,2);\
initLetter('s',1,2);\
initLetter('D',2,2);\
initLetter('d',2,2);\
initLetter('F',3,2);\
initLetter('f',3,2);\
initLetter('G',4,2);\
initLetter('g',4,2);\
initLetter('H',5,2);\
initLetter('h',5,2);\
initLetter('J',6,2);\
initLetter('j',6,2);\
initLetter('K',7,2);\
initLetter('k',7,2);\
initLetter('L',8,2);\
initLetter('l',8,2);\
initLetter('-',9,2);\
initLetter('-',9,2);\
initLetter('Z',0,3);\
initLetter('z',0,3);\
initLetter('X',1,3);\
initLetter('x',1,3);\
initLetter('C',2,3);\
initLetter('c',2,3);\
initLetter('V',3,3);\
initLetter('v',3,3);\
initLetter('B',4,3);\
initLetter('b',4,3);\
initLetter('N',5,3);\
initLetter('n',5,3);\
initLetter('M',6,3);\
initLetter('m',6,3);\
initLetter('_',7,3);\
initLetter('_',7,3);\
initLetter('@',8,3);\
initLetter('@',8,3);\
initLetter('.',9,3);\
initLetter('.',9,3);
typedef struct {int length; char instr[300];} movement;
movecasefold(char*instr,coord A, coord B){
register int i=0;int j;
if(A.x<B.x)
if(B.x-A.x<=TABLEX/2)
for(;B.x-A.x!=i;)instr[i++]=RIGHT;
else
for(;TABLEX-B.x+A.x!=i;)instr[i++]=LEFT;
else if(A.x>B.x)
if(A.x-B.x<=TABLEX/2)
for(;A.x-B.x!=i;)instr[i++]=LEFT;
else
for(;TABLEX-A.x+B.x!=i;)instr[i++]=RIGHT;
j=i;
if(A.y<B.y)
if(B.y-A.y<=TABLEY/2)
for(;B.y-A.y!=i-j;)instr[i++]=DOWN;
else
for(;TABLEY-B.y+A.y!=i-j;)instr[i++]=UP;
else if(A.y>B.y)
if(A.y-B.y<=TABLEY/2)
for(;A.y-B.y!=i-j;)instr[i++]=UP;
else
for(;TABLEY-A.y+B.y!=i-j;)instr[i++]=DOWN;
instr[i]='\0';
return i;
}
char sentence[50], oldcase, oldletter;
int sentencelength;
typedef struct {
int sentencetoorder[50];
int ordertosentence[50];
int length;
} order;
ordercopy(order*a, order b){
register int i;
for(i=0;++i<sentencelength;) a->sentencetoorder[i]=b.sentencetoorder[i], a->ordertosentence[i]=b.ordertosentence[i];
a->length=b.length;
}
order currentOrder;
movetwo(char*instr,int A, int B){
register int j; int i=0;
if(A<B)
{ for(j=A+1;j<B;j++)
if(currentOrder.sentencetoorder[j]<currentOrder.sentencetoorder[B])
instr[i++]=CURSORRIGHT;
}
else
{ for(j=A;j>B;j--)
if(currentOrder.sentencetoorder[j]<currentOrder.sentencetoorder[B])
instr[i++]=CURSORLEFT;
}
if(sentence[B]==' '){
instr[i++]=SPACE;
instr[i]='\0';
return i;
}
i+=movecasefold(instr+i,letters[oldletter],letters[sentence[B]]);
oldletter=sentence[B];
if(casediff(oldcase,sentence[B]))oldcase=sentence[B],instr[i++]=CAPS;
instr[i++]=APPLY;
instr[i]='\0';
return i;
}
moveall(char*instr){
int j;int i = 0;
oldcase='a';
oldletter='1';
for(j=0;++j<sentencelength;)
i+=movetwo(instr+i,currentOrder.ordertosentence[j-1],currentOrder.ordertosentence[j]);
return i;
}
iteration();
main(){
initAllLetters();
gets(sentence+1);*sentence='1';sentencelength=strlen(sentence);
int i;
for(i=0;++i<sentencelength;)currentOrder.sentencetoorder[i]=currentOrder.ordertosentence[i]=i;
char instr[300];
currentOrder.length=moveall(instr);
puts(instr);
while(iteration());
}
#define inside(item, start, stop) (((start)<=(item))&((item)<(stop)))
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
iteration(){
char instr[300];
register int i;
int newstart, start, l;
static order oldorder, neworder;
ordercopy(&oldorder,currentOrder);
ordercopy(&neworder,currentOrder);
for(l=0;++l<sentencelength-1;)
for(start=0;++start<sentencelength-l;)
for(newstart=0;++newstart<sentencelength-l;)
if(start!=newstart){
for(i=0;++i<sentencelength;)
if(inside(i,start,start+l))currentOrder.ordertosentence[i-start+newstart]=oldorder.ordertosentence[i];
else if(inside(i,min(start,newstart),max(start+l,newstart+l)))currentOrder.ordertosentence[newstart<start?i+l:(i-l)]=oldorder.ordertosentence[i];
else currentOrder.ordertosentence[i]=oldorder.ordertosentence[i];
for(i=0;++i<sentencelength;) currentOrder.sentencetoorder[currentOrder.ordertosentence[i]]=i;
currentOrder.length=moveall(instr);
if(currentOrder.length<neworder.length){
puts(instr);
ordercopy(&neworder, currentOrder);
}
}
ordercopy(&currentOrder, neworder);
return neworder.length<oldorder.length;
}


Compile with as "gcc virtualKeyboard.c". Run it without arguments "./a.out". It reads the input from stdin and writes the output to stdout.

• Sorry for the delay - your score is 193.
– user45941
May 24 '16 at 5:19