La próxima revolución en escribir en computadoras portátiles fue lanzada el 1 de abril de 2014 por SwiftKey . Sin embargo, quiero ser la primera persona en escribir un nano clon deslizante, pero, como no puedo encontrar una buena biblioteca de texto deslizable a texto real, y no puedo esperar, les pregunto aquí.
Tarea
Escriba un programa que tome texto deslizante y genere el equivalente de texto real. Ejemplo:
Input: hgrerhjklo
Output: hello
Cuando el usuario hace:
Otros ejemplos:
Input: wertyuioiuytrtjklkjhgfd
Output: world
Input: poiuytrtyuioiugrewsasdfgbhnmkijnbg
Output: programming
Input: poiuygfdzxcvhjklkjhgres
Output: puzzles
Input: cvhjioiugfde
Output: code
Input: ghiolkjhgf
Output: golf
Reglas
- El programa tomará una 'palabra' deslizada en stdin o argv
- La primera y última letra de la entrada deslizada será igual a la primera y última letra de la palabra real
- Puede suponer que el usuario formará líneas rectas razonables, pero puede usar los datos de la muestra para verificar esto (hice los datos de la muestra y haré los datos finales de la prueba)
- Para entradas ambiguas, puede seleccionar seleccionar cualquiera de las salidas, pero intentaré erradicar toda ambigüedad de los datos de prueba
- Esta palabra estará en esta lista de palabras (pero deslizada). La lista de palabras estará en el directorio actual y puede leerse (nueva línea separada, se nombrará
wordlist
, sin extensión). - El deslizamiento solo contendrá caracteres alfabéticos en minúsculas
- El deslizamiento puede contener caracteres duplicados, si el usuario hace una pausa en una tecla
- El programa debe salir en stdout (el caso no importa)
- El programa debe regresar
0
como el código de retorno - Debe proporcionar el comando de ejecución, el comando de compilación (si es necesario), el nombre y qué ruta de entrada usar
- Se aplican las lagunas estándar (aunque podrían no ayudar)
- No se permiten bibliotecas no integradas
- Se prefieren soluciones deterministas, no golfizadas / ofuscadas
- Sin escritura de archivos, redes, etc.
- Su código debe ejecutarse en un segundo o menos (su código se ejecuta una vez por palabra)
- Las ejecuciones de puntuación se ejecutan en un procesador Intel i7 Haswell, con 4 códigos virtuales (2 reales), por lo que puede usar hilos si tiene que
- Longitud máxima de código de 5000 bytes
- El idioma que use debe tener una versión gratuita (no de prueba) disponible para Linux (Arch Linux, si eso es importante)
Criterio ganador
- El ganador es la solución más precisa (puntuada por el programa de control , utilizando la lista de pruebas proporcionada)
- La popularidad es el factor decisivo
- La tabla de puntuación se actualizará cada pocos días.
- Los tiempos de espera y los accidentes cuentan como fallidos
- Este desafío durará dos semanas o más, dependiendo de la popularidad.
- La puntuación final usará una lista de palabras diferente, seleccionada al azar (misma longitud, de la misma lista de palabras)
Otro
- Puede usar el programa de control para probar su programa
- Si eres impaciente y quieres que tu programa se actualice / agregue rápidamente, inicia un problema o solicita una solicitud en https://github.com/matsjoyce/codegolf-swipe-type/blob/master
- Las entradas se mantienen en https://github.com/matsjoyce/codegolf-swipe-type/blob/master/entries
- Los registros de cada ejecución del programa se mantienen en https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs
- Registro principal en https://github.com/matsjoyce/codegolf-swipe-type/blob/master/log.log
- La posición de cada clave se proporcionará como un archivo csv en el directorio actual llamado
keypos.csv
, con los valores x e y en relación conQ
(consulte https://github.com/matsjoyce/codegolf-swipe-type/blob/master/ keypos.csv ) - Cada llave mide 1,5 x 1,5 cm (la misma unidad que en keypos.csv)
Tablas de puntuación actual
lista de prueba ( registros ):
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
Carrera final
lista de prueba ( registros ):
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
Enhorabuena a todos y hgfdsasdertyuiopoiuy swertyuiopoijnhg!
code-challenge
keyboard
matsjoyce
fuente
fuente
l
, que no se duplicaRespuestas:
JavaScript, ES6, Optimizador de tres pasos ,
112 187 235 240 241243 y231234 pasesUn filtro de tres pasos que primero descubre las claves críticas en la secuencia de pulsación de teclas y luego pasa la secuencia a través de los tres filtros:
Código
El código asume que
words
está presente una variable llamada que es una matriz de todas las palabras de esta páginaMira el código en acción aquí
Vea los casos de prueba en acción aquí
Tanto el enlace anterior solo funciona en un Firefox más reciente (33 y superior) (debido a ES6).
fuente
keypos.csv
archivo adecuado ahora. Las funciones IO disponibles están listadas en developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/…Ruby, Regex Solver -
30 140 176 180 182187 y179183 pasesDescubriré el puntaje más tarde. Aquí hay una solución muy ingenua que no tiene en cuenta la distribución del teclado:
Toma información de ARGV e imprime el resultado. Solo estoy filtrando la lista de palabras por la primera y la última letra, y luego estoy probando todas las palabras restantes contra la entrada (eliminando letras duplicadas y usando una expresión regular como
^g.*u.*e.*s$
"adivinar") y devuelvo la primera de ellas si existe Son múltiples soluciones.Ejecútalo como
Cualquier otra persona, siéntase libre de reutilizar este paso como primer filtro: creo que no arrojará ninguna palabra correcta, por lo que esta verificación preliminar puede reducir en gran medida el espacio de búsqueda para mejores algoritmos.
Editar: Siguiendo la sugerencia de OP, ahora selecciono al candidato más largo, lo que parece ser una heurística decente.
También gracias a es1024 por recordarme sobre letras duplicadas.
fuente
paradoxically
, yal
que solo aparecerían una vez en la entrada, en lugar de dos veces como lo exige la expresión regular.C ++, distancia discreta de Fréchet -
201220222232 y 232 pasesPara mí, el problema requería mucho la distancia de Fréchet, que desafortunadamente es muy difícil de calcular.
Solo por diversión, he tratado de abordar el problema implementando una aproximación discreta descrita por Thomas Eiter y Heikki Mannila en Computing Discrete Fréchet Distance (1994).
Al principio, estoy usando el mismo enfoque que los demás para filtrar todas las palabras de la lista que son subsecuencias de la entrada (que también representan múltiples ocurrencias secuenciales del mismo carácter). Luego, estoy llenando la curva de polígono de letra a letra de cada palabra con puntos intermedios y la comparo con la curva de entrada. Finalmente, divido cada distancia por la longitud de la palabra y tomo el puntaje mínimo.
Hasta ahora, el método no funciona tan bien como esperaba (reconoce el ejemplo de código como "chide"), pero esto podría ser el resultado de errores que aún no he encontrado. De lo contrario, otra idea sería utilizar otras variaciones de la distancia de fréchet ("promedio" en lugar de "longitud máxima de la correa del perro").
Editar: Ahora, estoy usando una aproximación a la "longitud promedio de la correa del perro". Esto significa que estoy encontrando un mapeo ordenado entre ambas rutas que minimiza la suma de todas las distancias y luego lo divido por el número de distancias.
Si el mismo carácter aparece dos veces o más a menudo en la palabra del diccionario, solo pongo un nodo en la ruta.
He compilado el código con clang, pero
g++ ./thiscode.cpp -o ./thiscode
también debería funcionar bien.fuente
programmijng
- me dapang
.programming
como debería. ¿Podría por favor descomentar la línea// cout << thispair->first << ": " << score << endl;
y pegar las puntuaciones resultantes?Python 2, Turnarounds,
224 226 230232 y230234 pasesEste es un enfoque bastante directo:
Correr como
La solución no es muy robusta. Una sola pulsación incorrecta haría que fallara. Sin embargo, dado que el conjunto de casos de prueba tiene
muy pocoserrores ortográficos, funciona bastante bien, solo se confunde en algunos casos donde elige palabras demasiado largas.Editar: lo cambié un poco para no usar el archivo de posición de clave proporcionado sino un diseño simplificado. Esto facilita mi algoritmo porque en el archivo las claves no están espaciadas de manera uniforme. Puedo lograr resultados incluso ligeramente mejores al incluir algunos desempates ad-hoc para casos ambiguos, pero eso sería una optimización excesiva para este conjunto de pruebas en particular. Quedan algunas fallas que no son realmente ambiguas pero que no entiendo con mi algoritmo simple porque solo considera cambios de dirección de más de 90 grados.
fuente
brats
podría ser lo'bgrdsasdrtrds'
que no se puede confundir conbreasts
. Sin embargo, tampoco me importaría si lo dejaras como está.PHP, Direction Checker,
203 213 216 229231 y229233 pasesEsto comienza con un simple paso por el diccionario para obtener una lista de palabras cuyas letras están todas presentes en la entrada (lo que Martin hizo aquí ), y también solo verificando en
l.*
lugar del.*l.*
cuandol
está duplicado.La palabra más larga aquí se guarda en una variable.
Luego se realiza otra verificación, basada en las teclas en los puntos donde el deslizamiento cambia de dirección (+ / 0 a - o - / 0 a +, ya sea en x o y). La lista de palabras posibles se compara con esta lista de caracteres y se eliminan las palabras que no coinciden. Este enfoque se basa en giros bruscos al deslizar para ser preciso.
Se emite la palabra restante más larga, o si no quedan palabras, se emite la palabra más larga de antes.
Editar: se agregaron todos los caracteres en una línea horizontal que conducen a un cambio de dirección como posibles valores para verificar.
Se requiere PHP 5.4 (o reemplazar todo
[..]
conarray(..)
).fuente
keypos.csv
sss
): no creo que su eliminación duplicada las atrape.Python 3, Corner Simulator, 241 y 240 pases
Algoritmo:
significant_letter
función) (tercer paso)Código:
Corre con
python3 entries/corner_sim.py
fuente