En consolas de juegos modernas y otros dispositivos sin teclados tradicionales, tratar de ingresar texto es una pesadilla. Tener que escribir con unos pocos botones y un joystick en un teclado virtual es molesto, y me gusta hacer la menor cantidad posible de movimientos / pulsaciones de botones.
El teclado que usará se ve así:
+---+---+---+---+---+---+---+---+---+---+
| 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 | _ | @ | . |
+---+---+---+---+---+---+---+---+---+---+
Se pueden utilizar las siguientes operaciones:
L
: mueve un cuadrado a la izquierda en el teclado (wraps)R
: mueve un cuadrado a la derecha en el teclado (wraps)U
: mueve un cuadrado hacia arriba en el teclado (wraps)D
: mueve un cuadro hacia abajo en el teclado (wraps)Y
: inserta un espacioB
: mueve el puntero de inserción un espacio hacia la izquierda (no hace nada si el puntero está al principio)F
: mueve el puntero de inserción un espacio hacia la derecha (no hace nada si el puntero está al final)C
: bloqueo de mayúsculasA
: inserta el carácter seleccionado en la posición del puntero de inserción
Dada una cadena de entrada que contiene solo caracteres ASCII que se pueden escribir usando el teclado y los comandos (coincidencias [a-zA-Z0-9 [email protected]]*
) anteriores, genera una secuencia de comandos que dará como resultado la cadena de salida. La posición inicial del cursor está en la 1
tecla (arriba a la izquierda) y el bloqueo de mayúsculas está inicialmente desactivado.
Tanteo
Para cualquier cadena dada, un enfoque ingenuo sería, para cada carácter en la cadena, navegar al carácter en el teclado por la ruta más corta, alternar el bloqueo de mayúsculas si es necesario y seleccionar el carácter. Un enfoque tan ingenuo generaría un comando de longitud (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)
. Por ejemplo, el enfoque ingenuo para 101
daría como resultado ALARA
un comando de longitud 5 y Noob 5
daría como resultado DDDRRRRRCAUURRRCAADDLLLLAYUUUA
un comando de longitud 30.
Su presentación, sin embargo, busca hacerlo mejor que el enfoque ingenuo. Para cada cadena de entrada, su envío recibirá puntos iguales al número de comandos que utiliza el enfoque ingenuo menos el número de comandos que genera su envío. Su puntaje general será la suma de los puntajes individuales.
Reglas
- Los envíos se ejecutarán en un espacio de trabajo virtual gratuito de Cloud9 . El espacio de trabajo tiene 512 MB de RAM, 2 GB de espacio en disco, 8 CPU Intel (R) Xeon (R) a 2.50 GHz (la información completa de la CPU, que se encuentra al ejecutar
cat /proc/cpuinfo
, se puede encontrar aquí ), y está ejecutando Ubuntu 14.04 de 64 bits Fiel. Puede solicitar acceso al espacio de trabajo de prueba para ejecutar y calificar su envío, o yo puedo calificarlo por usted. - Los envíos se realizarán una vez por caso de prueba. El estado de almacenamiento entre ejecuciones está prohibido. Los envíos no pueden escribir ni leer de ningún archivo que no sea el archivo fuente (que no puede modificarse entre ejecuciones), con la posible excepción de leer un archivo de entrada si es necesario.
- Los envíos están limitados a 1 minuto de tiempo de ejecución para cada caso de prueba. Los envíos pueden generar múltiples soluciones, pero solo la última solución válida dentro del tiempo asignado se utilizará para la puntuación. Si no se obtienen soluciones válidas dentro del tiempo asignado, se obtendrá una puntuación de 0 para ese caso de prueba.
- Incluya instrucciones sobre cómo invocar su envío, así como cualquier herramienta / biblioteca que deba instalarse que no esté incluida en una instalación estándar de Ubuntu 14.04.
- El ganador será la presentación con la mayor puntuación. En caso de empate, ganará la presentación con la mejor complejidad algorítmica. Si el empate aún no se resuelve, ganará la primera presentación que alcance el puntaje y la complejidad algorítmica.
- Los envíos pueden no optimizarse para los casos de prueba. Me reservo el derecho de cambiar los casos de prueba si siento que es necesario.
Casos de prueba
Formato: input string => naive score
(si ve algún error en estos, deje un comentario con la corrección)
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
Respuestas:
do
El puntaje es 193.
Compilar con "gcc virtualKeyboard.c". Ejecútelo sin argumentos "./a.out". Lee la entrada de stdin y escribe la salida en stdout.
fuente
C99
Aquí está mi intento de una solución. Obtuvo una puntuación de 62.
Parecía funcionar correctamente para las palabras más pequeñas y simplemente asumí que las más grandes también funcionan correctamente porque son demasiado grandes para que las pruebe manualmente.
Compilar con "gcc -std = gnu99" El
uso es "virtualKeyboard" string ""
fuente
Noob 5
esRRRRRUCALCAYRRRRARRRRDBBBAA
, que produceN33b @
, y su segunda salida esLLDAAYRRRRAUBBARBBBCA
, que produce4oo3 e
. Tal como está, su puntaje actual es 5, porque su programa solo imprime secuencias de comandos válidas para los primeros 3 casos de prueba.