A próxima revolução na digitação em laptops foi lançada no dia primeiro de abril de 2014 pela SwiftKey . No entanto, quero ser a primeira pessoa a escrever um nano clone deslizante, mas como não consigo encontrar um bom texto de furto na biblioteca de texto real e não posso esperar por eles, pergunto aqui.
Tarefa
Escreva um programa que receba texto de furto e produza o equivalente em texto real. Exemplo:
Input: hgrerhjklo
Output: hello
Quando o usuário faz:
Outros exemplos:
Input: wertyuioiuytrtjklkjhgfd
Output: world
Input: poiuytrtyuioiugrewsasdfgbhnmkijnbg
Output: programming
Input: poiuygfdzxcvhjklkjhgres
Output: puzzles
Input: cvhjioiugfde
Output: code
Input: ghiolkjhgf
Output: golf
Regras
- O programa incluirá uma palavra 'swiped' em stdin ou argv
- A primeira e a última letra da entrada swiped serão iguais à primeira e à última letra da palavra real
- Você pode assumir que o usuário fará linhas razoavelmente retas, mas você pode usar os dados da amostra para verificar isso (eu fiz os dados da amostra e os dados finais do teste)
- Para entrada ambígua, você pode selecionar qualquer saída, mas tentarei erradicar toda ambiguidade dos dados de teste
- Esta palavra estará nesta lista de palavras (mas passou o dedo). A lista de palavras estará no diretório atual e pode ser lida (nova linha separada, será nomeada
wordlist
, sem extensão). - O furto conterá apenas caracteres alfabéticos em minúsculas
- O furto pode conter caracteres duplicados, se o usuário pausar em uma tecla
- O programa deve produzir em stdout (caso não importe)
- O programa deve retornar
0
como o código de retorno - Você deve fornecer o comando de execução, comando de compilação (se necessário), nome e qual caminho de entrada usar
- Aplicam-se brechas padrão (embora possam não ajudar)
- Não são permitidas bibliotecas não integradas
- Soluções determinísticas, não-golfe / ofuscadas preferidas
- Sem gravação de arquivo, rede, etc.
- Seu código deve ser executado em um segundo ou menos (seu código é executado uma vez por palavra)
- As execuções de pontuação são executadas em um processador Intel i7 Haswell, com 4 códigos virtuais (2 reais), para que você possa usar threads se precisar
- Comprimento máximo do código de 5000 bytes
- O idioma usado deve ter uma versão gratuita (sem teste) disponível para Linux (Arch Linux, se isso importa)
Critério vencedor
- O vencedor é a solução mais precisa (pontuada pelo programa de controle , usando a lista de testes fornecida)
- A popularidade é o desempate
- A tabela de pontuação será atualizada a cada poucos dias
- Tempos limite e falhas contam como falhas
- Esse desafio dura duas semanas ou mais, dependendo da popularidade
- A pontuação final usará uma lista de palavras diferente e selecionada aleatoriamente (mesmo tamanho, da mesma lista de palavras)
De outros
- Você pode usar o programa de controle para testar seu programa
- Se você é impaciente e deseja que seu programa seja atualizado / adicionado rapidamente, inicie um problema ou solicite a solicitação em https://github.com/matsjoyce/codegolf-swipe-type/blob/master
- As entradas são mantidas em https://github.com/matsjoyce/codegolf-swipe-type/blob/master/entries
- Os logs de cada execução do programa são mantidos em https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs
- Registro principal em https://github.com/matsjoyce/codegolf-swipe-type/blob/master/log.log
- A posição de cada chave será fornecida como um arquivo csv no diretório atual chamado
keypos.csv
, com os valores x e y dados em relação aQ
(consulte https://github.com/matsjoyce/codegolf-swipe-type/blob/master/ keypos.csv ) - Cada tecla mede 1,5 x 1,5 cm (mesma unidade do keypos.csv)
Current Score Boards
lista de teste ( logs ):
Three Pass Optimizer:Errors: 0/250 Fails: 7/250 Passes: 243/250 Timeouts: 0/250
Corner Sim: Errors: 0/250 Fails: 9/250 Passes: 241/250 Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250 Fails: 17/250 Passes: 233/250 Timeouts: 0/250
Turnaround: Errors: 0/250 Fails: 18/250 Passes: 232/250 Timeouts: 0/250
Direction Checker: Errors: 0/250 Fails: 19/250 Passes: 231/250 Timeouts: 0/250
Regex Solver: Errors: 0/250 Fails: 63/250 Passes: 187/250 Timeouts: 0/250
Corner Sim: Errors: 0/250 Fails: 10/250 Passes: 240/250 Timeouts: 0/250
Three Pass Optimizer:Errors: 2/250 Fails: 14/250 Passes: 234/250 Timeouts: 0/250
Turnaround: Errors: 0/250 Fails: 16/250 Passes: 234/250 Timeouts: 0/250
Direction Checker: Errors: 0/250 Fails: 17/250 Passes: 233/250 Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250 Fails: 18/250 Passes: 232/250 Timeouts: 0/250
Regex Solver: Errors: 0/250 Fails: 67/250 Passes: 183/250 Timeouts: 0/250
Final Run
lista de teste ( logs ):
Corner Sim: Errors: 0/250 Fails: 14/250 Passes: 236/250 Timeouts: 0/250
Three Pass Optimizer:Errors: 0/250 Fails: 18/250 Passes: 232/250 Timeouts: 0/250
Direction Checker: Errors: 0/250 Fails: 20/250 Passes: 230/250 Timeouts: 0/250
Turnaround: Errors: 0/250 Fails: 23/250 Passes: 227/250 Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250 Fails: 30/250 Passes: 220/250 Timeouts: 0/250
Regex Solver: Errors: 0/250 Fails: 55/250 Passes: 195/250 Timeouts: 0/250
Bem feito a todos e hgfdsasdertyuiopoiuy swertyuiopoijnhg!
code-challenge
keyboard
matsjoyce
fonte
fonte
l
, que não é dobrado.Respostas:
JavaScript, ES6, Three Pass Optimizer,
112 187 235 240 241243 e231234 passesUm filtro de três passagens que primeiro descobre chaves críticas na sequência de pressionamento de tecla e depois passa a sequência pelos três filtros:
Código
O código assume que uma variável chamada
words
está presente, que é uma matriz de todas as palavras desta páginaVeja o código em ação aqui
Veja os casos de teste em ação aqui
O link acima funciona apenas em um Firefox mais recente (33 e superior) (devido ao ES6).
fonte
keypos.csv
arquivo apropriado agora. As funções IO Avalible estão listados no developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/...Ruby, Regex Solver -
30 140 176 180 182187 e179183 passesEu vou descobrir a pontuação mais tarde. Aqui está uma solução muito ingênua que não leva em conta o layout do teclado:
Ele recebe a entrada do ARGV e imprime o resultado. Estou apenas filtrando a lista de palavras pela primeira e pela última letra, e elas estou tentando todas as palavras restantes contra a entrada (eliminando letras duplicadas e usando um regex como
^g.*u.*e.*s$
para "palpite") e retornando a primeira delas, se houver são várias soluções.Execute como
Qualquer outra pessoa, sinta-se à vontade para reutilizar esta etapa como primeiro filtro - acredito que ela não emitirá nenhuma palavra correta, portanto, essa verificação preliminar pode reduzir bastante o espaço de pesquisa para obter melhores algoritmos.
Edit: Seguindo a sugestão dos OPs, agora estou selecionando o mais longo dos candidatos, o que parece ser uma heurística decente.
Também obrigado a es1024 por me lembrar sobre letras duplicadas.
fonte
paradoxically
, pois asl
apareceriam apenas uma vez na entrada, em vez de duas vezes o exigido pelo regex.C ++, distância discreta de Fréchet -
201220222232 e 232 passesPara mim, o problema exigia muito a Distância Fréchet, que infelizmente é muito difícil de calcular.
Apenas por diversão, tentei abordar o problema implementando uma aproximação discreta descrita por Thomas Eiter e Heikki Mannila em Computing Discrete Fréchet Distance (1994).
No começo, estou usando a mesma abordagem que as outras para filtrar todas as palavras na lista que são subsequências da entrada (também são responsáveis por várias ocorrências sequenciais do mesmo caractere). Então, estou preenchendo a curva de polígono de letra a letra de cada palavra com pontos intermediários e comparando-a com a curva de entrada. Finalmente, divido cada distância pelo comprimento da palavra e obtenho a pontuação mínima.
Até agora, o método não funciona tão bem quanto eu esperava (ele reconhece o exemplo de código como "chide"), mas isso poderia ser apenas o resultado de bugs que ainda não encontrei. Senão, outra idéia seria usar outras variações da distância do fréchet ("média" em vez de "comprimento máximo da trela do cão").
Edit: Agora, eu estou usando uma aproximação para o "comprimento médio da trela do cão". Isso significa que estou encontrando um mapeamento ordenado entre os dois caminhos, o que minimiza a soma de todas as distâncias e depois o dividimos pelo número de distâncias.
Se o mesmo caractere aparecer duas ou mais vezes na palavra do dicionário, colocarei apenas um nó no caminho.
Eu compilei o código com clang, mas
g++ ./thiscode.cpp -o ./thiscode
também deve funcionar bem.fonte
programmijng
- isso me dápang
.programming
como deveria. Você poderia descomentar a linha// cout << thispair->first << ": " << score << endl;
e colar as pontuações resultantes?Python 2, Turnarounds,
224 226 230232 e230234 passesEssa é uma abordagem bastante direta:
Correr como
A solução não é muito robusta. Um único pressionamento de tecla errado faria com que falhasse. No entanto, como o conjunto de casos de teste tem
muito poucoerro de ortografia, ele executa muito bem, ficando confuso em alguns casos em que escolhe palavras muito longas.Edit: Eu mudei um pouco para não usar o arquivo de posição-chave fornecido, mas um layout simplificado. Isso facilita o meu algoritmo, porque no arquivo as chaves não são espaçadas igualmente. Posso obter resultados ainda um pouco melhores incluindo alguns desempatadores ad-hoc para casos ambíguos, mas isso seria otimizador demais para esse conjunto de testes em particular. Permanecem algumas falhas que não são realmente ambíguas, mas que eu não entendo com meu algoritmo simples porque ele considera apenas mudanças de direção superiores a 90 graus.
fonte
brats
poderia ser o'bgrdsasdrtrds'
que não pode ser confundidobreasts
. No entanto, eu também não me importaria se você deixasse como está.PHP, Checker Checker,
203 213 216 229231 e229233 passesIsso começa com uma simples passagem pelo dicionário para obter uma lista de palavras cujas letras estão presentes na entrada (o que Martin fez aqui ), e também apenas procurando em
l.*
vez del.*l.*
quandol
é duplicada.A palavra mais longa aqui é salva em uma variável.
Outra verificação é feita, com base nas teclas nos pontos em que o furto muda de direção (+ / 0 a - ou - / 0 a +, em x ou y). A lista de palavras possíveis é verificada nessa lista de caracteres e as palavras que não correspondem são eliminadas. Essa abordagem depende de curvas acentuadas no deslize para ser precisa.
A palavra restante mais longa é emitida ou, se nenhuma palavra for deixada, a palavra mais longa anterior é emitida.
Editar: Adicionado todos os caracteres em uma linha horizontal que leva a uma mudança de direção como possíveis valores a serem verificados.
É necessário o PHP 5.4 (ou substitua todos
[..]
porarray(..)
).fonte
keypos.csv
sss
) - não acho que sua eliminação duplicada as capturasse.Python 3, Corner Simulator, 241 e 240 passes
Algoritmo:
significant_letter
função) (terceira passagem)Código:
Correr com
python3 entries/corner_sim.py
fonte