Em consoles de jogos modernos e outros dispositivos sem teclados tradicionais, tentar inserir texto é um pesadelo. Ter que digitar com alguns botões e um joystick em um teclado virtual é irritante, e eu gosto de fazer o mínimo de movimentos / pressionamentos de botão possível.
O teclado que você usará se parece com isso:
+---+---+---+---+---+---+---+---+---+---+
| 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 | _ | @ | . |
+---+---+---+---+---+---+---+---+---+---+
As seguintes operações podem ser usadas:
L
: mova um quadrado para a esquerda no teclado (envolvimentos)R
: mova um quadrado para a direita no teclado (envolvimentos)U
: move um quadrado para cima no teclado (envolvimentos)D
: mova um quadrado para baixo no teclado (envolvimentos)Y
: insira um espaçoB
: move o ponteiro de inserção um espaço para a esquerda (não faz nada se o ponteiro estiver no início)F
: move o ponteiro de inserção um espaço para a direita (não faz nada se o ponteiro estiver no final)C
: alternar as tampas de bloqueioA
: insira o caractere selecionado na posição do ponteiro de inserção
Dada uma sequência de entrada que contém apenas caracteres ASCII que podem ser digitados usando o teclado e os comandos (correspondências [a-zA-Z0-9 [email protected]]*
) acima, produz uma sequência de comandos que resultará na sequência de saída. A posição inicial do cursor está na 1
tecla (no canto superior esquerdo) e o caps lock está desativado inicialmente.
Pontuação
Para qualquer sequência dada, uma abordagem ingênua seria, para cada caractere na sequência, navegar até o caractere no teclado pelo caminho mais curto, alternar entre maiúsculas e minúsculas, se necessário, e selecionar o caractere. Uma abordagem tão ingênua geraria um comando de comprimento (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 exemplo, a abordagem ingênua para 101
resultaria em ALARA
um comando de comprimento 5 e Noob 5
resultaria em DDDRRRRRCAUURRRCAADDLLLLAYUUUA
um comando de comprimento 30.
Sua submissão, no entanto, busca fazer melhor do que a abordagem ingênua. Para cada sequência de entrada, seu envio receberá pontos iguais ao número de comandos que a abordagem ingênua usa menos o número de comandos que seu envio gera. Sua pontuação geral será a soma das pontuações individuais.
Regras
- Os envios serão executados em um espaço de trabalho virtual gratuito Cloud9 . O espaço de trabalho possui 512 MB de RAM, 2 GB de espaço em disco, 8 CPUs Intel (R) Xeon (R) a 2,50 GHz (informações completas da CPU, encontradas em execução
cat /proc/cpuinfo
, podem ser encontradas aqui ) e estão executando o Ubuntu 14.04 de 64 bits Fiel. Você pode solicitar acesso ao espaço de trabalho de teste para executar e classificar seu envio, ou posso classificá-lo para você. - Os envios serão executados uma vez por caso de teste. O estado de armazenamento entre execuções é proibido. Os envios não podem gravar ou ler nenhum arquivo que não seja o arquivo de origem (que não pode ser modificado entre as execuções), com a possível exceção de ler um arquivo de entrada, se necessário.
- Os envios são limitados a 1 minuto de tempo de execução para cada caso de teste. Os envios podem gerar várias soluções, mas apenas a última solução válida dentro do tempo alocado será usada para a pontuação. A falha na saída de qualquer solução válida dentro do tempo alocado resultará em uma pontuação de 0 para esse caso de teste.
- Por favor, inclua instruções sobre como chamar sua submissão, bem como quaisquer ferramentas / bibliotecas que precisam ser instaladas que não estão incluídas em uma instalação padrão do Ubuntu 14.04.
- O vencedor será a finalização com a maior pontuação. Em caso de empate, a finalização com a melhor complexidade algorítmica vencerá. Se o empate ainda não for resolvido, a primeira submissão a atingir a pontuação e a complexidade algorítmica vencerá.
- Os envios podem não otimizar para os casos de teste. Reservo-me o direito de alterar os casos de teste, se achar necessário.
Casos de teste
Formato: input string => naive score
(se houver algum erro nestes, deixe um comentário com a correção)
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
Respostas:
C
A pontuação é 193.
Compile com como "gcc virtualKeyboard.c". Execute-o sem argumentos "./a.out". Ele lê a entrada de stdin e grava a saída em stdout.
fonte
C99
Aqui está minha tentativa de solução. Obteve uma pontuação de 62.
Parecia funcionar corretamente para as palavras menores e presumi que as maiores também funcionam corretamente porque são grandes demais para eu testar manualmente.
Compilar com "gcc -std = gnu99" O
uso é "virtualKeyboard" string ""
fonte
Noob 5
éRRRRRUCALCAYRRRRARRRRDBBBAA
, que produzN33b @
, e sua segunda saída éLLDAAYRRRRAUBBARBBBCA
, que produz4oo3 e
. Como está, sua pontuação atual é 5, porque seu programa imprime apenas seqüências de comandos válidas para os 3 primeiros casos de teste.