Na nowoczesnych konsolach do gier i innych urządzeniach bez tradycyjnych klawiatur próba wprowadzania tekstu jest koszmarem. Konieczność pisania za pomocą kilku przycisków i joysticka na wirtualnej klawiaturze jest denerwująca i lubię wykonywać jak najmniej ruchów / naciskania przycisków.

Klawiatura, której będziesz używać, wygląda następująco:

+---+---+---+---+---+---+---+---+---+---+
| 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 | _ | @ | . |
+---+---+---+---+---+---+---+---+---+---+

Można użyć następujących operacji:

• L: przesuń o jeden kwadrat w lewo na klawiaturze (zawija się)
• R: przesuń o jeden kwadrat w prawo na klawiaturze (zawija się)
• U: przesuń o jeden kwadrat w górę na klawiaturze (zawija się)
• D: przesuń o jeden kwadrat w dół na klawiaturze (zawija się)
• Y: wstaw spację
• B: przesuń wskaźnik wstawiania o jedną spację w lewo (nic nie robi, jeśli wskaźnik znajduje się na początku)
• F: przesuń wskaźnik wstawiania o jedną spację w prawo (nic nie robi, jeśli wskaźnik znajduje się na końcu)
• C: przełącz Caps Lock
• A: wstaw wybrany znak w miejscu wskaźnika wstawiania

Biorąc pod uwagę ciąg wejściowy zawierający tylko znaki ASCII, które można wpisać za pomocą powyższej klawiatury i poleceń (dopasowań [a-zA-Z0-9 _@.-]*), wypisz sekwencję poleceń, które spowodują powstanie ciągu wyjściowego. Początkowa pozycja kursora znajduje się na1 klawiszu (lewy górny róg), a Caps Lock jest początkowo wyłączony.

Punktacja

W przypadku każdego ciągu znaków naiwnym podejściem byłoby, aby dla każdego znaku w ciągu przejść do znaku na klawiaturze najkrótszą ścieżką, w razie potrzeby przełączać Caps Lock i wybrać znak. Takie naiwne podejście generowałoby nakaz długości (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). Na przykład podejście naiwne dla 101skutkowałoby ALARAwydaniem polecenia o długości 5 i Noob 5skutkowałoby DDDRRRRRCAUURRRCAADDLLLLAYUUUAwydaniem polecenia o długości 30.

Wasze poddanie się ma jednak na celu lepsze wyniki niż naiwne podejście. Za każdy ciąg wejściowy twoje zgłoszenie otrzyma punkty równe liczbie poleceń, których używa naiwne podejście, minus liczba poleceń, które wyprowadza twoje podanie. Twój ogólny wynik będzie sumą poszczególnych wyników.

Zasady

• Zgłoszenia będą realizowane w wirtualnym obszarze roboczym Cloud9 . Obszar roboczy ma 512 MB pamięci RAM, 2 GB miejsca na dysku, 8 procesorów Intel (R) Xeon (R) @ 2,50 GHz (pełne informacje o procesorze, które cat /proc/cpuinfomożna znaleźć po uruchomieniu , można znaleźć tutaj ) i działa 64-bitowy Ubuntu 14.04 Wierny. Możesz poprosić o dostęp do testowego obszaru roboczego w celu uruchomienia i oceny twojego zgłoszenia lub też mogę go dla ciebie ocenić.
• Zgłoszenia będą uruchamiane raz na przypadek testowy. Przechowywanie stanu między przebiegami jest zabronione. Zgłoszenia nie mogą zapisywać ani odczytywać plików innych niż plik źródłowy (których nie można modyfikować między uruchomieniami), z możliwym wyjątkiem odczytywania pliku wejściowego, jeśli jest to wymagane.
• Zgłoszenia są ograniczone do 1 minuty czasu wykonywania dla każdego przypadku testowego. Zgłoszenia mogą generować wiele rozwiązań, ale do oceny zostanie użyte tylko ostatnie prawidłowe rozwiązanie w wyznaczonym czasie. Brak wydrukowania jakichkolwiek poprawnych rozwiązań w wyznaczonym czasie spowoduje wynik 0 dla tego przypadku testowego.
• Podaj wskazówki, jak wywołać zgłoszenie, a także wszelkie narzędzia / biblioteki, które należy zainstalować, które nie są zawarte w standardowej instalacji Ubuntu 14.04.
• Zwycięzcą zostanie zgłoszenie z największą liczbą punktów. W przypadku remisu wygrywa zgłoszenie o lepszej złożoności algorytmicznej. Jeśli remis nadal nie zostanie rozstrzygnięty, wygrana zostanie pierwsza próba osiągnięcia wyniku i złożoności algorytmu.
• Zgłoszenia mogą nie zostać zoptymalizowane pod kątem przypadków testowych. Zastrzegam sobie prawo do zmiany przypadków testowych, jeśli uważam, że jest taka potrzeba.

Przypadki testowe

Format: input string => naive score

(jeśli zauważysz w nich jakieś błędy, zostaw komentarz z poprawką)

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

do

Wynik to 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;
}

Skompiluj jako „gcc virtualKeyboard.c”. Uruchom go bez argumentów „./a.out”. Odczytuje dane wejściowe ze standardowego wejścia i zapisuje dane wyjściowe na standardowe wyjście.

C99

Oto moja próba rozwiązania. Uzyskał 62 punkty.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define COORDINATES_ARRAY_SIZE 256
#define MOVEMENT_ARRAY_LEN 1024

#define KEYBOARD_WIDTH 10
#define KEYBOARD_HEIGHT 4

#define DIRECTION_BIT 0x40

#define INITIAL_CHAR '1'

#define SPACE_WEIGHT_INCREMENT 2
#define SPACE_WEIGHT_MAX 10
#define CURSOR_WEIGHT_INCREMENT 2
#define CURSOR_WEIGHT_MAX 10

const char keyboard[KEYBOARD_HEIGHT][KEYBOARD_WIDTH] = {
    {'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','_','@','.'}
};

typedef enum {
    right,
    left,
    up,
    down
} dir;

//iirc it is an omptimization to use int over byte or short despite only using values <10
typedef struct {
    int x;
    int y;
} coordinates;

typedef struct {
    int xmove;
    int ymove;
    dir xdir;
    dir ydir;
} movedata;

void generateCoords(coordinates*);
unsigned int nearestNeighbor(coordinates*, char*, char*, char*, char*, int, int, int, int, int, int, int);
int calcDistance(coordinates*, char, char, movedata*);

int main(int argc, char **argv){
    coordinates coords[COORDINATES_ARRAY_SIZE];
    char moves[MOVEMENT_ARRAY_LEN];
    unsigned int temp, min = 0;
    min--; //largest possible int

    if(argc != 2){
        printf("Invalid Arguments. Usage: virtualKeyboard <string>\n");

    }else{
        int len = strlen(argv[1]);
        int moveCursor, capsLock;
        char *workingString =  malloc(len * sizeof(char));
        generateCoords(coords);
        movedata data;
        for(int spaceWeight = 1; spaceWeight < SPACE_WEIGHT_MAX; spaceWeight += SPACE_WEIGHT_INCREMENT){
            for(int cursorWeight = 1; cursorWeight < CURSOR_WEIGHT_MAX; cursorWeight+= CURSOR_WEIGHT_INCREMENT){
                for(int i = 0; i<len; i++){
                    //zero out arrays
                    moveCursor = 0;
                    capsLock = 0;
                    memset(moves, 0, MOVEMENT_ARRAY_LEN);
                    memset(workingString, 0, len);
                    workingString[0] = argv[1][i];
                    //add initial moves
                    temp = calcDistance(coords, INITIAL_CHAR, argv[1][i], &data);

                    for(int j = 0; j < data.xmove; j++){
                        moves[moveCursor] = data.xdir == right ? 'R' : 'L';
                        moveCursor++;
                    }
                    for(int j = 0; j < data.ymove; j++){
                        moves[moveCursor] = data.ydir == up ? 'U' : 'D';
                        moveCursor++;
                    }
                    if((capsLock==0) != (isupper(argv[1][i])==0)){
                        moves[moveCursor] = 'C';
                        capsLock = capsLock == 0 ? 1 : 0;
                        moveCursor++;
                        temp++;
                    }
                    moves[moveCursor] = 'A';
                    temp++;
                    temp += nearestNeighbor(coords, moves, argv[1], argv[1], workingString, i ,len, len, 1, capsLock, cursorWeight, spaceWeight);
                    if(temp < min){
                        printf("%s\t%s\t%i\n", moves, workingString, temp);
                        min = temp;
                    }

                }
            }
        }
        free(workingString);
    }
    return 0;
}

//optimization so it only searches through the matrix once
void generateCoords(coordinates* coords){
    for(int i = 0; i < KEYBOARD_HEIGHT; i++){
        for(int j = 0; j < KEYBOARD_WIDTH; j++){
            coords[(int)keyboard[i][j]].y = i;
            coords[(int)keyboard[i][j]].x = j;
        }
    }
}

int calcCursorMoves(char* og, char* workingString, char added, int cursor, int len){
    char* inUseWS = calloc(len, sizeof(char));
    char* inUseOG = calloc(len, sizeof(char));
    int indexToAdd = 0, newCursor = cursor;
    for(int i = 0; i < len; i++){
        for(int j = 0; j < len; j++){
            if(workingString[j] != -1 && og[i] == workingString[j] 
                    && inUseOG[i] == 0 && inUseWS[j] == 0){
                inUseOG[i] = 1;
                inUseWS[j] = i+1; // set in use to corresponding working string
                break;
            }
            if(workingString[j] == 0){
                inUseWS[j] = -1; //append -1 to end
                break; //nothing more to see here   
            }
        }
    }
    for(int i = 0; i < len; i++){
        if(og[i] == added && inUseOG[i] == 0){
            indexToAdd = i;
            break;
        }
    }
    for(int i = 0; i < len; i++){
        if(i==0 && indexToAdd < inUseWS[i]-1){
            newCursor = i;
            break;

        }
        if(inUseWS[i]-1 < indexToAdd && (indexToAdd < inUseWS[i+1]-1 || inUseWS[i+1] == -1)){
            newCursor = i+1;
            break;
        }
        if(workingString[i+1] == 0){
            newCursor = i+1;
            break;
        }

    }
    free(inUseWS);
    free(inUseOG);
    return newCursor - cursor;  
}

int calcDistance(coordinates* coords, char from, char to, movedata* data){
    if(to == ' ')
        return 0;
    from = tolower(from);
    to = tolower(to);
    data->xmove = coords[(int)from].x - coords[(int)to].x;
    data->ymove = coords[(int)from].y - coords[(int)to].y;  
    data->xdir = data->xmove >= 0 ? left : right;
    data->ydir = data->ymove >= 0 ? up : down;
    data->xmove = abs(data->xmove);
    data->ymove = abs(data->ymove);
    //wraparound
    if(data->xmove > 5){
        data->xmove = 10 - data->xmove;
        data->xdir = data->xdir == right ? left : right;
    }   
    if(data->ymove > 2){
        data->ymove = 4 - data->ymove;
        data->ydir = data->ydir == up ? down : up;
    }
    return data->xmove + data->ymove;
}

//assumes array is longer than current string
void insertAt(char* str, char toIns, int index){
    char* temp = malloc(strlen(str) + 1);
    strncpy(temp, str, index);
    temp[index] = toIns;
    strcpy(temp+index+1, str+index);
    strcpy(str, temp);  
    free(temp);
}

unsigned int nearestNeighbor(coordinates* coords, char* moves, char* og, 
        char* input, char* workingString, int index, int lenOG, int len,  
        int cursor, int capsLock, int cursorWeight, int spaceWeight){
    if(len  == 1){
        return 0;
    }
    movedata data, bestData;
    char bestChar = '\0';
    unsigned int bestCursor = -1, bestIndex = -1, bestDist = -1;
    unsigned int dist = -1, cursorDist = -1, best = -1;
    char newString[len-1] ;
    memset(newString, 0, len-1);
    strncpy(newString, input, index);
    strcpy(newString+index, input+index+1);
//  printf("%s\t", newString);
    for(int i = 0; i < len-1; i++){
        dist = calcDistance(coords, input[index], newString[i], &data);
        cursorDist = calcCursorMoves(og, workingString, newString[i], cursor, lenOG);
        if(dist + cursorWeight * abs(cursorDist) + spaceWeight * (newString[i] == ' ') + ((capsLock==0) != (isupper(newString[i])==0)) < best){
    //      printf("%c %c %i %i\n", workingString[cursor], newString[i], cursorDist, cursor);
            bestDist = cursorDist;
            bestCursor = cursor + cursorDist;
            best = dist + cursorWeight * abs(cursorDist) + spaceWeight * (newString[i] == ' ') + ((capsLock==0) != (isupper(newString[i])==0));
            bestChar = newString[i];
            bestIndex = i;
            memcpy(&bestData, &data, sizeof(data));
        }
    }
    //append moves
    int i;
    for(i = 0; i < MOVEMENT_ARRAY_LEN && moves[i]!=0; i++);
    if(bestChar != ' '){
        for(int j = 0; j < bestData.xmove; j++){
            moves[i] = bestData.xdir == right ? 'R' : 'L';
            i++;
        }
        for(int j = 0; j < bestData.ymove; j++){
            moves[i] = bestData.ydir == up ? 'U' : 'D';
            i++;
        }
        for(int j = 0; j < abs(bestDist); j++){
            moves[i] = bestDist > 0 ? 'B' : 'F'; 
            i++;
        }
        if((capsLock==0) != (isupper(bestChar)==0)){
            moves[i] = 'C';
            capsLock = capsLock == 0 ? 1 : 0;
            i++;
        }
        moves[i] = 'A';
    } else {
        moves[i] = 'Y';
    }
    //remove weight
    best -= cursorWeight * abs(bestDist);
    best -= spaceWeight * (bestChar==' ');
    insertAt(workingString, bestChar, bestCursor);
    int max = nearestNeighbor(coords, moves, og, newString, workingString, 
             bestIndex, lenOG, len-1, bestCursor+1, capsLock, cursorWeight, spaceWeight);
    //the 1 is for the actual click
    return max + best + 1 + abs(bestDist);
}

Wydawało się, że działa poprawnie dla mniejszych słów, a ja po prostu założyłem, że te większe również działają poprawnie, ponieważ są one zbyt duże, aby przetestować je ręcznie.

Skompiluj z „gcc -std = gnu99”
Użycie to „virtualKeyboard” string ”„