Convertidor de tipo de deslizamiento

27

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:

ingrese la descripción de la imagen aquí

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 0como 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

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

testlist2 ( registros ):

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!

matsjoyce
fuente
¿Qué es "una solución"? ¿Dónde está su código?
Pomo de la puerta
Continuemos esta discusión en el chat .
Optimizador
8
Algo relacionado.
wchargin
@Optimizer No estoy seguro sobre los otros casos, pero " p oiuytres unr es un s d fghui o iugfd x CGU i ug c XS un sdfghjk l ku y " contiene todas las letras del "paradójicamente", en orden, a excepción de la l, que no se duplica
es1024
1
@Optimiser Bueno, pensé que su presentación lo superaría, pero estaba justo debajo (un pequeño ajuste habría cambiado eso, estoy seguro). Parece que puedo aceptarlo, así que ... ¿debería (parece que no obtengo un representante de aceptarlo)? Me gustaría aceptar las de otra persona, pero eso no sigue las reglas (a menos que tenga una buena idea).
matsjoyce

Respuestas:

12

JavaScript, ES6, Optimizador de tres pasos , 112 187 235 240 241 243 y 231 234 pases

Un 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:

  1. Un RegEx formado libremente a partir de las claves críticas y claves de ayuda. Esto da el resultado correcto para la mayoría de las claves (alrededor de 150)
  2. Un estricto RegEx hecho de solo claves críticas. Esto da el resultado correcto para 85 secuencias adicionales
  3. Un tercer filtro para descubrir la ambigüedad entre las respuestas cercanas. Esto funciona para 40% de casos ambiguos.

Código

keyboard = {
  x: {},
  y: ['  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'],
};
for (var i in keyboard.y)
  for (var y of keyboard.y[i])
    keyboard.x[y] = +i*7;
p = C => (x=keyboard.x[C],{x, y: keyboard.y[x/7].indexOf(C)})
angle = (L, C, R) => (
  p0 = p(L), p1 = p(C), p2 = p(R),
  a = Math.pow(p1.x-p0.x,2) + Math.pow(p1.y-p0.y,2),
  b = Math.pow(p1.x-p2.x,2) + Math.pow(p1.y-p2.y,2),
  c = Math.pow(p2.x-p0.x,2) + Math.pow(p2.y-p0.y,2),
  Math.acos((a+b-c) / Math.sqrt(4*a*b))/Math.PI*180
)
corner = (L, C, R, N, W) => {
  if (skip) {
    skip = false;
    return [];
  } 
  ngl = angle(L, C, R);
  if (ngl < 80) return [C + "{1,3}"]
  if (ngl < 115 && p(L).x != p(R).x && p(L).x != p(C) && p(R).x != p(C).x && Math.abs(p(L).y - p(R).y) < 5) return [C + "{0,3}"]
  if (ngl < 138) {
    if (N && Math.abs(ngl - angle(C, R, N)) < 6) {
      skip = true;
      return [L + "{0,3}", "([" + C + "]{0,3}|[" + R + "]{0,3})?", N + "{0,3}"]
    }
    return [C + "{0,3}"]
  }
  return ["([" + L + "]{0,3}|[" + C + "]{0,3}|[" + R + "]{0,3})?"]
}
f = S => {
  for (W = [S[0] + "{1,2}"],i = 1; i < S.length - 1; i++)
    W.push(...corner(S[i - 1], S[i], S[i + 1], S[i + 2], W))
  return [
    new RegExp("^" + W.join("") + S[S.length - 1] + "{1,3}$"),
    new RegExp("^" + W.filter(C=>!~C.indexOf("[")).join("") + S[S.length - 1] + "{1,3}$")
  ]
}
thirdPass = (F, C) => {
  if (!F[0]) return null
  F = F.filter((s,i)=>!F[i - 1] || F[i - 1] != s)
  FF = F.map(T=>[...T].filter((c,i)=>!T[i - 1] || T[i - 1] != c).join(""))
  if (FF.length == 1) return F[0];
  if (FF.length < 6 && FF[0][2] && FF[1][2] && FF[0][0] == FF[1][0] && FF[0][1] == FF[1][1])
    if (Math.abs(F[0].length - F[1].length) < 1)
      for (i=0;i<Math.min(F[0].length, FF[1].length);i++) {
        if (C.indexOf(FF[0][i]) < C.indexOf(FF[1][i])) return F[0]
        else if (C.indexOf(FF[0][i]) > C.indexOf(FF[1][i])) return F[1]
      }
  return F[0]
}
var skip = false;
SwiftKey = C => (
  C = [...C].filter((c,i)=>!C[i - 1] || C[i - 1] != c).join(""),
  skip = false, matched = [], secondPass = [], L = C.length, reg = f(C),
  words.forEach(W=>W.match(reg[0])&&matched.push(W)),
  words.forEach(W=>W.match(reg[1])&&secondPass.push(W)),
  matched = matched.sort((a,b)=>Math.abs(L-a.length)>Math.abs(L-b.length)),
  secondPass = secondPass.sort((a,b)=>Math.abs(L-a.length)>Math.abs(L-b.length)),
  first = matched[0], second = secondPass[0], third = thirdPass(secondPass.length? secondPass: matched, C),
  second && second.length >= first.length - 1? first != third ? third: second: third.length >= first.length ? third: first
)

// For use by js shell of latest firefox
print(SwiftKey(readline()));

El código asume que wordsestá presente una variable llamada que es una matriz de todas las palabras de esta página

Mira 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).

Optimizador
fuente
¡Sip! Estoy bombardeando con conchas. También puede usar el keypos.csvarchivo adecuado ahora. Las funciones IO disponibles están listadas en developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/…
matsjoyce
Está bien, pero los golpes se hacen con los ángulos de mi teclado, por lo que es su elección (¡aunque no parece haber afectado su puntaje!)
matsjoyce
¡240 pases son excepcionales! Pensé que las ambigüedades evitarían tan buenos resultados. Tendré curiosidad sobre cómo funcionará esto en el conjunto de prueba final.
Emil
@Emil - Sí, estoy esperando ver eso también.
Optimizador
9

Ruby, Regex Solver - 30 140 176 180 182 187 y 179 183 pases

Descubriré el puntaje más tarde. Aquí hay una solución muy ingenua que no tiene en cuenta la distribución del teclado:

words = File.readlines('wordlist').map(&:chomp)

swipe = ARGV.shift
puts words.select {|word| word[0] == swipe[0] &&
                          word[-1] == swipe[-1]}
          .select {|word|
              chars = [word[0]]
              (1..word.size-1).each {|i| chars << word[i] if word[i] != word[i-1]}
              swipe[Regexp.new('^'+chars.join('.*')+'$')]
          }.sort_by {|word| word.size}[-1]

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

ruby regex-solver.rb cvhjioiugfde

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.

Martin Ender
fuente
Hecho. Su registro está en github.com/matsjoyce/codegolf-swipe-type/blob/master/logs/… Creo que el problema es que selecciona aleatoriamente las posibles soluciones, que podrían mejorarse seleccionando la más larga u otra cosa.
matsjoyce
Creo que esto podría arrojar todas las palabras correctas con dos letras idénticas una al lado de la otra, como paradoxically, ya lque solo aparecerían una vez en la entrada, en lugar de dos veces como lo exige la expresión regular.
es1024
@ es1024, ah, gracias, cuando propuse este algoritmo por primera vez en la caja de arena, estaba consciente de eso, pero ayer lo olvidé. Se arreglará más tarde.
Martin Ender
7

C ++, distancia discreta de Fréchet - 201 220 222 232 y 232 pases

Para 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.

#include<iostream>
#include<fstream>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
#include<cmath>

using namespace std;

const double RESOLUTION = 3.2;

double dist(const pair<double, double>& a, const pair<double, double>& b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

double helper(const vector<pair<double, double> >& a,
        const vector<pair<double, double> >& b,
        vector<vector<double> >& dp,
        int i,
        int j) {
    if (dp[i][j] > -1)
        return dp[i][j];
    else if (i == 0 && j == 0)
        dp[i][j] = dist(a[0], b[0]);
    else if (i > 0 && j == 0)
        dp[i][j] = helper(a, b, dp, i - 1, 0) +
                   dist(a[i], b[0]);
    else if (i == 0 && j > 0)
        dp[i][j] = helper(a, b, dp, 0, j - 1) +
                   dist(a[0], b[j]);
    else if (i > 0 && j > 0)
        dp[i][j] = min(min(helper(a, b, dp, i - 1, j),
                           helper(a, b, dp, i - 1, j - 1)),
                       helper(a, b, dp, i, j - 1)) +
                   dist(a[i], b[j]);
    return dp[i][j];
}

double discretefrechet(const vector<pair<double, double> >& a, const vector<pair<double, double> >& b) {
    vector<vector<double> > dp = vector<vector<double> >(a.size(), vector<double>(b.size(), -1.));
    return helper(a, b, dp, a.size() - 1, b.size() - 1);
}

bool issubsequence(string& a, string& b) {
    // Accounts for repetitions of the same character: hallo subsequence of halo
    int i = 0, j = 0;
    while (i != a.size() && j != b.size()) {
        while (a[i] == b[j])
            ++i;
        ++j;
    }
    return (i == a.size());
}

int main() {
    string swipedword;
    cin >> swipedword;

    ifstream fin;
    fin.open("wordlist");
    map<string, double> candidatedistance = map<string, double>();
    string readword;
    while (fin >> readword) {
        if (issubsequence(readword, swipedword) && readword[0] == swipedword[0] && readword[readword.size() - 1] == swipedword[swipedword.size() - 1]) {
            candidatedistance[readword] = -1.;
        }
    }
    fin.close();

    ifstream fin2;
    fin2.open("keypos.csv");
    map<char, pair<double, double> > keypositions = map<char, pair<double, double> >();
    char rc, comma;
    double rx, ry;
    while (fin2 >> rc >> comma >> rx >> comma >> ry) {
        keypositions[rc] = pair<double, double>(rx, ry);
    }
    fin2.close();

    vector<pair<double, double> > swipedpath = vector<pair<double, double> >();
    for (int i = 0; i != swipedword.size(); ++i) {
        swipedpath.push_back(keypositions[swipedword[i]]);
    }

    for (map<string, double>::iterator thispair = candidatedistance.begin(); thispair != candidatedistance.end(); ++thispair) {
        string thisword = thispair->first;
        vector<pair<double, double> > thispath = vector<pair<double, double> >();
        for (int i = 0; i != thisword.size() - 1; ++i) {
            pair<double, double> linestart = keypositions[thisword[i]];
            pair<double, double> lineend = keypositions[thisword[i + 1]];
            double linelength = dist(linestart, lineend);
            if (thispath.empty() || linestart.first != thispath[thispath.size() - 1].first || linestart.second != thispath[thispath.size() - 1].second)
                thispath.push_back(linestart);
            int segmentnumber = linelength / RESOLUTION;
            for (int j = 1; j < segmentnumber; ++j) {
                thispath.push_back(pair<double, double>(linestart.first + (lineend.first - linestart.first) * ((double)j) / ((double)segmentnumber),
                                    linestart.second + (lineend.second - lineend.second) * ((double)j) / ((double)segmentnumber)));
            }
        }
        pair<double, double> lastpoint = keypositions[thisword[thisword.size() - 1]];
        if (thispath.empty() || lastpoint.first != thispath[thispath.size() - 1].first || lastpoint.second != thispath[thispath.size() - 1].second)
        thispath.push_back(lastpoint);

        thispair->second = discretefrechet(thispath, swipedpath) / (double)(thispath.size());
    }

    double bestscore = 1e9;
    string bestword = "";
    for (map<string, double>::iterator thispair = candidatedistance.begin(); thispair != candidatedistance.end(); ++thispair) {
        double score = thispair->second;
        if (score < bestscore) {
            bestscore = score;
            bestword = thispair->first;
        }
        // cout << thispair->first << ": " << score << endl;
    }
    cout << bestword << endl;

    return 0;
}

He compilado el código con clang, pero g++ ./thiscode.cpp -o ./thiscodetambién debería funcionar bien.

camello
fuente
1
¡Sí! ¡Alguien finalmente ha agregado una solución con un nombre de algoritmo grande y gordo! Su registro está en github.com/matsjoyce/codegolf-swipe-type/blob/master/logs/…
matsjoyce
1
Llamémoslo un algoritmo de programación dinámico simple para un gran problema informático.
camelNeck
Por alguna razón, esto parece fallar por la entrada de programmijng- me da pang.
Riking
Eso es extraño. Me estoy poniendo programmingcomo debería. ¿Podría por favor descomentar la línea // cout << thispair->first << ": " << score << endl;y pegar las puntuaciones resultantes?
camelNeck
6

Python 2, Turnarounds, 224 226 230 232 y 230 234 pases

Este es un enfoque bastante directo:

  • Encuentre los puntos donde el flujo de letras cambia de dirección (más el inicio y el final).
  • Salida de la palabra más larga que incluye todos estos puntos de inflexión.
import sys, csv, re

wordlistfile = open('wordlist', 'r')
wordlist = wordlistfile.read().split('\n')

layout = 'qwertyuiop asdfghjkl  zxcvbnm'
keypos = dict((l, (2*(i%11)+i/11, i/11)) for i,l in enumerate(layout))

#read input from command line argument
input = sys.argv[1]

#remove repeated letters
input = ''.join(x for i,x in enumerate(input) if i==0 or x!=input[i-1])

#find positions of letters on keyboard
xpos = map(lambda l: keypos[l][0], input)
ypos = map(lambda l: keypos[l][1], input)

#check where the direction changes (neglect slight changes in x, e.g. 'edx')
xpivot = [(t-p)*(n-t)<-1.1 for p,t,n in zip(xpos[:-2], xpos[1:-1], xpos[2:])]
ypivot = [(t-p)*(n-t)<0 for p,t,n in zip(ypos[:-2], ypos[1:-1], ypos[2:])]
pivot = [xp or yp for xp,yp in zip(xpivot, ypivot)]

#the first and last letters are always pivots
pivot = [True] + pivot + [True]

#build regex
regex = ''.join(x + ('+' if p else '*') for x,p in zip(input, pivot))
regexobj = re.compile(regex + '$')

#find all words that match the regex and output the longest one
words = [w for w in wordlist if regexobj.match(w)]
output = max(words, key=len) if words else input
print output

Correr como

python turnarounds.py tyuytrghn

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 pocos errores 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.

Emil
fuente
¡Bien hecho! ¡Líder actual! Si desea ver el registro, vaya a github.com/matsjoyce/codegolf-swipe-type/blob/master/logs/…
matsjoyce
@matsjoyce: agregué un comentario a la pregunta señalando los dos errores ortográficos que creo haber encontrado. :)
Emil
Sí, gracias, solo le doy otro cheque. Sin embargo, no estoy muy seguro de qué hacer con los casos ambiguos.
matsjoyce
@matsjoyce: algunas ambigüedades podrían resolverse eligiendo otro de los posibles caminos a través del teclado. Por ejemplo, bratspodría ser lo 'bgrdsasdrtrds'que no se puede confundir con breasts. Sin embargo, tampoco me importaría si lo dejaras como está.
Emil
Es cierto, eso funcionaría. Solo me preocupa que si este conjunto se hace demasiado 'óptimo', y el conjunto de puntuación final no se somete a mucho escrutinio, algunas soluciones pueden no funcionar tan bien
matsjoyce
6

PHP, Direction Checker, 203 213 216 229 231 y 229 233 pases

Esto 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 de l.*l.*cuando lestá 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 [..]con array(..)).

<?php
function get_dir($a, $b){
    $c = [0, 0];
    if($a[0] - $b[0] < -1.4) $c[0] = 1;
    else if($a[0] - $b[0] > 1.4) $c[0] = -1;
    if($a[1] < $b[1]) $c[1] = 1;
    else if($a[1] > $b[1]) $c[1] = -1;
    return $c;
}
function load_dict(){
    return explode(PHP_EOL, file_get_contents('wordlist'));
}

$coord = [];
$f = fopen('keypos.csv', 'r');
while(fscanf($f, "%c, %f, %f", $c, $x, $y)){
    $coord[$c] = [$x, $y];  
}
fclose($f);

$dict = load_dict();
$in = $argv[1];
$possib = [];

foreach($dict as $c){
    if($c[0] == $in[0]){
        $q = strlen($c);
        $r = strlen($in);
        $last = '';
        $fail = false;
        $i = $j = 0;
        for($i = 0; $i < $q; ++$i){
            if($last == $c[$i]) continue;
            if($j >= $r){
                $fail = true;
                break;
            }
            while($c[$i] != $in[$j++])
                if($j >= $r){
                    $fail = true; 
                    break;
                }
            if($fail) break;
            $last = $c[$i];
        }
        if(!$fail) 
            $possib[] = $c;
    }
}

$longest = '';
foreach($possib as $p){
    if(strlen($p) > strlen($longest))
        $longest = $p;
}

$dir = [[0, 0]];
$cdir = [0, 0];
$check = '/^' . $in[0] . '.*?';
$olst = []; $p = 1;

$len = strlen($in);
for($i = 1; $i < $len; ++$i){
    $dir[$i] = get_dir($coord[$in[$i - 1]], $coord[$in[$i]]);
    $olddir = $cdir;
    $newdir = $dir[$i];
    $xc = $olddir[0] && $newdir[0] && $newdir[0] != $olddir[0];
    $yc = $olddir[1] && $newdir[1] && $newdir[1] != $olddir[1];
    if($xc || $yc){ // separate dir from current dir
        if($yc && !$xc && $dir[$i - 1][1] == 0){
            $tmp = '';
            for($j = $i - 1; $j >= 0 && $dir[$j][1] == 0; --$j){
                $tmp = '(' . $in[$j-1] . '.*?)?' . $tmp;
            }
            $olst[] = range($p, $p + (($i - 1) - $j));
            $p += ($i - 1) - $j + 1;
            $check .= $tmp . '(' . $in[$i - 1] . '.*?)?';
        }else{
            $check .= $in[$i - 1] . '.*?';
        }
        $cdir = $dir[$i];
    }else{
        if(!$cdir[0]) $cdir[0] = $dir[$i][0]; 
        if(!$cdir[1]) $cdir[1] = $dir[$i][1]; 
    }
}
$check .= substr($in, -1) . '$/';
$olstc = count($olst);
$res = [];
foreach($possib as $p){
    if(preg_match($check, $p, $match)){
        if($olstc){
            $chk = array_fill(0, $olstc, 0);
            for($i = 0; $i < $olstc; ++$i){
                foreach($olst[$i] as $j){
                    if(isset($match[$j]) && $match[$j]){
                        ++$chk[$i];
                    }
                }
                // give extra weight to the last element of a horizontal run
                if(@$match[$olst[$i][count($olst[$i])-1]])
                    $chk[$i] += 0.5;
            }
            if(!in_array(0, $chk)){
                $res[$p] = array_sum($chk);
            }
        }else{
            $res[$p] = 1;
        }
    }
}
$possib = array_keys($res, @max($res));
$newlong = '';
foreach($possib as $p){
    if(strlen($p) > strlen($newlong))
        $newlong = $p;
}
if(strlen($newlong) == 0) echo $longest;
else echo $newlong;
es1024
fuente
@matsjoyce Se perdió esa viñeta mientras leía la pregunta. El código ahora usa las posiciones dekeypos.csv
es1024
@ es1024 Si bien no es parte de los 250 casos de prueba, la lista de palabras contiene 238 palabras con tres letras consecutivas (hasta ahora, todo lo que he verificado son palabras que terminan en sss): no creo que su eliminación duplicada las atrape.
Martin Ender
Si lo necesita, sus registros en github.com/matsjoyce/codegolf-swipe-type/blob/master/logs/…
matsjoyce
3

Python 3, Corner Simulator, 241 y 240 pases

Algoritmo:

  • Deduplicar (eliminar ejecuciones consecutivas del mismo carácter) la entrada y todas las palabras en la lista de palabras (usando un diccionario para recuperar las palabras originales)
  • Elimine todas las palabras que no comienzan y terminan con el inicio y el final del deslizamiento (primer paso)
  • Haga una expresión regular de todas las esquinas mayores de 80 grados, luego elimine todas las palabras que no coinciden con esto (segunda pasada)
  • Regex cada palabra (como Regex Solver) contra el deslizamiento, luego divida el deslizamiento en una serie de líneas teóricamente rectas, y verifique si son rectas y podrían haber sido producidas por un dedo moviéndose a lo largo de esa línea ( significant_letterfunción) (tercer paso)
  • Ordenar las palabras por cercanía a las líneas rectas
  • Luego use la longitud como un desempate (más largo es mejor)
  • Luego use la distancia de Levenshtein como el desempate final
  • Palabra de salida!

Código:

# Corner Sim

from math import atan, degrees, pi, factorial, cos, radians
import csv
import re
import sys

keys = {}
key_size = 1.5
for line in open("keypos.csv"):
    k, x, y = map(str.strip, line.split(","))
    keys[k] = float(x), float(y)


def deduplicate(s):
    return s[0] + "".join(s[i + 1] for i in range(len(s) - 1) if s[i + 1] != s[i])


def angle(coord1, coord2):
    x1, y1, x2, y2 = coord1 + coord2
    dx, dy = x2 - x1, y1 - y2
    t = abs(atan(dx/dy)) if dy else pi / 2
    if dx >= 0 and dy >= 0: a = t
    elif dx >= 0 and dy < 0: a = pi - t
    elif dx < 0 and dy >= 0: a = 2 * pi - t
    else: a = t + pi
    return degrees(a)


def significant_letter(swipe):
    if len(swipe) <= 2: return 0
    x1, y1, x2, y2 = keys[swipe[0]] + keys[swipe[-1]]
    m = 0 if x2 == x1 else (y2 - y1) / (x2 - x1)
    y = lambda x: m * (x - x1) + y1
    def sim_fun(x2, y2):
        try: return (x2 / m + y2 - y1 + x1 * m) / (m + 1 / m)
        except ZeroDivisionError: return x2
    dists = []
    for i, key in enumerate(swipe[1:-1]):
        sx, bx = min(x1, x2), max(x1, x2)
        pos_x = max(min(sim_fun(*keys[key]), bx), sx)
        sy, by = min(y1, y2), max(y1, y2)
        pos_y = max(min(y(pos_x), by), sy)
        keyx, keyy = keys[key]
        dist = ((keyx - pos_x) ** 2 + (keyy - pos_y) ** 2) ** 0.5
        a = angle((keyx, keyy), (pos_x, pos_y))
        if 90 <= a <= 180: a = 180 - a
        elif 180 <= a <= 270: a = a - 180
        elif 270 <= a <= 360: a = 360 - a
        if a > 45: a = 90 - a
        h = key_size / 2 / cos(radians(a))
        dists.append((max(dist - h, 0), i + 1, key))
    return sorted(dists, reverse=True)[0][0]


def closeness2(s, t):
    # https://en.wikipedia.org/wiki/Levenshtein_distance
    if s == t: return 0
    if not len(s): return len(t)
    if not len(t): return len(s)
    v0 = list(range(len(t) + 1))
    v1 = list(range(len(t) + 1))
    for i in range(len(s)):
        v1[0] = i + 1
        for j in range(len(t)):
            cost = 0 if s[i] == t[j] else 1
            v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost)
        for j in range(len(v0)):
            v0[j] = v1[j]
    return v1[len(t)] / len(t)


def possible(swipe, w, s=False):
    m = re.match("^" + "(.*)".join("({})".format(i) for i in w) + "$", swipe)
    if not m or s:
        return bool(m)
    return closeness1(swipe, w) < 0.8


def closeness1(swipe, w):
    m = re.match("^" + "(.*)".join("({})".format(i) for i in w) + "$", swipe)
    unsigpatches = []
    groups = m.groups()
    for i in range(1, len(groups), 2):
        unsigpatches.append(groups[i - 1] + groups[i] + groups[i + 1])
    if debug: print(unsigpatches)
    sig = max(map(significant_letter, unsigpatches))
    if debug: print(sig)
    return sig


def find_closest(swipes):
    level1, level2, level3, level4 = swipes
    if debug: print("Loading words...")
    words = {deduplicate(i.lower()): i.lower() for i in open("wordlist").read().split("\n") if i[0] == level1[0] and i[-1] == level1[-1]}
    if debug: print("Done first filter (start and end):", words)
    r = re.compile("^" + ".*".join(level4) + "$")
    pos_words2 = list(filter(lambda x: bool(r.match(x)), words))
    if debug: print("Done second filter (sharpest points):", pos_words2)
    pos_words = pos_words2 or words
    pos_words = list(filter(lambda x: possible(level1, x), pos_words)) or list(filter(lambda x: possible(level1, x, s=True), pos_words))
    if debug: print("Done third filter (word regex):", pos_words)
    sorted_pos_words = sorted((closeness1(level1, x), -len(x), closeness2(level1, x), x)
                              for x in pos_words)
    if debug: print("Closeness matching (to", level2 + "):", sorted_pos_words)
    return words[sorted_pos_words[0][3]]


def get_corners(swipe):
    corners = [[swipe[0]] for i in range(4)]
    last_dir = last_char = None
    for i in range(len(swipe) - 1):
        dir = angle(keys[swipe[i]], keys[swipe[i + 1]])
        if last_dir is not None:
            d = abs(last_dir - dir)
            a_diff = min(360 - d, d)
            corners[0].append(last_char)
            if debug: print(swipe[i], dir, last_dir, a_diff, end=" ")
            if a_diff >= 55:
                if debug: print("C", end=" ")
                corners[1].append(last_char)
            if a_diff >= 65:
                if debug: print("M", end=" ")
                corners[2].append(last_char)
            if a_diff >= 80:
                if debug: print("S", end=" ")
                corners[3].append(last_char)
            if debug: print()
        last_dir, last_char = dir, swipe[i + 1]
    tostr = lambda x: deduplicate("".join(x + [swipe[-1]]).lower())
    return list(map(tostr, corners))


if __name__ == "__main__":
    debug = "-d" in sys.argv
    if debug: sys.argv.remove("-d")
    swipe = deduplicate(sys.argv[1] if len(sys.argv) > 1 else input()).lower()
    corners = get_corners(swipe)
    if debug: print(corners)
    print(find_closest(corners))

Corre con python3 entries/corner_sim.py

matsjoyce
fuente
Esta fue una respuesta válida. No es necesario que la respuesta sea mía.
Optimizador
@Optimizer Bueno, la meta discusión parece favorecer la aceptación de su respuesta, así que está bien para mí.
matsjoyce
Después de leer solo esa meta discusión, estaba de acuerdo con su decisión, pero esto también es bueno (mejor) :)
Optimizer