La prochaine révolution dans la dactylographie sur les ordinateurs portables a été lancée le 1er avril 2014 par SwiftKey . Cependant, je veux être la première personne à écrire un nano clone de balayage, mais, comme je ne trouve pas un bon texte de balayage vers une bibliothèque de texte réel, et je ne peux pas attendre pour eux, je demande ici.

Tâche

Écrivez un programme qui accepte le texte glissé et génère l'équivalent en texte réel. Exemple:

Input: hgrerhjklo
Output: hello

Lorsque l'utilisateur:

Autres exemples:

Input: wertyuioiuytrtjklkjhgfd
Output: world

Input: poiuytrtyuioiugrewsasdfgbhnmkijnbg
Output: programming

Input: poiuygfdzxcvhjklkjhgres
Output: puzzles

Input: cvhjioiugfde
Output: code

Input: ghiolkjhgf
Output: golf

Règles

• Le programme prendra un «mot» glissé sur stdin ou argv
• La première et la dernière lettre de l'entrée balayée correspondront à la première et à la dernière lettre du mot réel
• Vous pouvez supposer que l'utilisateur fera des lignes raisonnablement droites, mais vous pouvez utiliser les données d'exemple pour le vérifier (j'ai créé les données d'exemple et je ferai les données de test finales)
• Pour une entrée ambiguë, vous pouvez faire sélectionner l'une ou l'autre sortie, mais j'essaierai d'éliminer toute ambiguïté des données de test
• Ce mot sera dans cette liste de mots (mais glissé). La liste de mots sera dans le répertoire courant, et peut être lue (nouvelle ligne séparée, sera nommée wordlist, sans extension).
• Le balayage ne contiendra que des caractères alphabétiques en minuscules
• Le balayage peut contenir des caractères en double, si l'utilisateur marque une pause sur une touche
• Le programme doit sortir sur stdout (le cas n'a pas d'importance)
• Le programme doit retourner 0comme code retour
• Vous devez fournir la commande d'exécution, la commande de compilation (si nécessaire), le nom et le chemin d'entrée à utiliser
• Des failles standard s'appliquent (cependant, elles pourraient ne pas aider)
• Aucune bibliothèque non intégrée autorisée
• Solutions déterministes, non golfées / obscurcies préférées
• Pas d'écriture de fichiers, de mise en réseau, etc.
• Votre code doit être exécuté en une seconde ou moins (votre code est exécuté une fois par mot)
• Les scores sont exécutés sur un processeur Intel i7 Haswell, avec 4 codes virtuels (2 réels), vous pouvez donc utiliser des threads si vous devez
• Longueur maximale du code de 5000 octets
• La langue que vous utilisez doit avoir une version gratuite (non d'essai) disponible pour Linux (Arch Linux, si cela est important)

Critère gagnant

• Le gagnant est la solution la plus précise (notée par le programme de contrôle , en utilisant la liste de tests fournie)
• La popularité est le bris d'égalité
• Le tableau des scores sera mis à jour tous les quelques jours
• Les temps morts et les accidents comptent comme des échecs
• Ce défi durera deux semaines ou plus, selon la popularité
• La notation finale utilisera une liste de mots différente, choisie au hasard (même longueur, à partir de la même liste de mots)

Autre

• Vous pouvez utiliser le programme de contrôle pour tester votre programme
• Si vous êtes impatient et souhaitez que votre programme soit mis à jour / ajouté rapidement, lancez un problème ou envoyez une demande à https://github.com/matsjoyce/codegolf-swipe-type/blob/master
• Les inscriptions sont conservées sur https://github.com/matsjoyce/codegolf-swipe-type/blob/master/entries
• Les journaux de chaque exécution de programme sont conservés sur https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs
• Journal principal sur https://github.com/matsjoyce/codegolf-swipe-type/blob/master/log.log
• La position de chaque clé sera fournie sous forme de fichier csv dans le répertoire courant appelé keypos.csv, avec les valeurs x et y données par rapport à Q(voir https://github.com/matsjoyce/codegolf-swipe-type/blob/master/ keypos.csv )
• Chaque clé mesure 1,5 x 1,5 cm (même unité que dans keypos.csv)

Tableaux de score actuels

liste de tests ( journaux ):

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 ( journaux ):

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

Course finale

liste de tests ( journaux ):

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

Bravo à tout le monde et hgfdsasdertyuiopoiuy swertyuiopoijnhg!

JavaScript, ES6, trois passages Optimizer, 112 187 235 240 241 243 et 231 234 passes

Un filtre à trois passes qui comprend d'abord les touches critiques dans la séquence de touches, puis passe la séquence à travers les trois filtres:

1. Un RegEx vaguement formé à partir des clés critiques et des clés d'aide. Cela donne un résultat correct pour la majorité des touches (environ 150)
2. Un RegEx strict composé uniquement de clés critiques. Cela donne un résultat correct pour 85 séquences supplémentaires
3. Un troisième filtre pour comprendre l'ambiguïté parmi les réponses proches. Cela fonctionne pour 40% des cas ambigus.

Code

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()));

Le code suppose qu'une variable appelée wordsest présente qui est un tableau de tous les mots de cette page

Voir le code en action ici

Voir les cas de test en action ici

Le lien ci-dessus ne fonctionne que sur un dernier Firefox (33 et supérieur) (en raison de ES6).

Ruby, Regex Solver - 30 140 176 180 182 187 et 179 183 passes

Je trouverai le score plus tard. Voici une solution très naïve qui ne prend pas en compte la disposition du clavier:

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]

Il prend l'entrée de l'ARGV et imprime le résultat. Je filtre simplement la liste de mots par première et dernière lettre, et eux, j'essaie tous les mots restants par rapport à l'entrée (en éliminant les lettres en double et en utilisant une expression régulière comme ^g.*u.*e.*s$pour "suppose") et je renvoie la première de celles-ci s'il y a sont de multiples solutions.

Exécutez-le comme

ruby regex-solver.rb cvhjioiugfde

N'importe qui d'autre, n'hésitez pas à réutiliser cette étape comme premier filtre - je pense que cela ne jettera pas de mots corrects, donc cette vérification préliminaire peut considérablement réduire l'espace de recherche pour de meilleurs algorithmes.

Edit: Suite à la suggestion des PO, je sélectionne maintenant le plus long des candidats, ce qui semble être une heuristique décente.

Merci également à es1024 de m'avoir rappelé les lettres en double.

C ++, Distance Fréchet discrète - 201 220 222 232 et 232 passes

Pour moi, le problème appelait beaucoup la distance de Fréchet qui est malheureusement très difficile à calculer.

Pour le plaisir, j'ai essayé d'aborder le problème en mettant en œuvre une approximation discrète décrite par Thomas Eiter et Heikki Mannila dans Computing Discrete Fréchet Distance (1994).

Au début, j'utilise la même approche que les autres pour filtrer tous les mots de la liste qui sont des sous-séquences de l'entrée (ce qui représente également plusieurs occurrences séquentielles du même caractère). Ensuite, je remplis la courbe polygonale de lettre en lettre de chaque mot avec des points intermédiaires et la compare à la courbe d'entrée. Enfin, je divise chaque distance par la longueur du mot et je prends le score minimum.

Jusqu'à présent, la méthode ne fonctionne pas aussi bien que je l'espérais (elle reconnaît l'exemple de code comme "chide"), mais cela pourrait simplement être le résultat de bugs que je n'ai pas encore trouvés. Sinon, une autre idée serait d'utiliser d'autres variations de la distance de fréchet ("moyenne" au lieu de "longueur maximale de laisse de chien").

Edit: Maintenant, j'utilise une approximation de la "longueur moyenne de la laisse de chien". Cela signifie que je trouve une cartographie ordonnée entre les deux chemins qui minimise la somme de toutes les distances et la divise plus tard par le nombre de distances.

Si le même caractère apparaît deux fois ou plus souvent dans le mot du dictionnaire, je ne mets qu'un seul nœud dans le chemin.

#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;
}

J'ai compilé le code avec clang, mais g++ ./thiscode.cpp -o ./thiscodedevrait également fonctionner correctement .

Python 2, Turnarounds, 224 226 230 232 et 230 234 passes

Il s'agit d'une approche assez simple:

• Trouvez les points où le flux de lettres change de direction (plus le début et la fin).
• Sortez le mot le plus long qui inclut tous ces points tournants.

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

Courir comme

python turnarounds.py tyuytrghn

La solution n'est pas très robuste. Une seule mauvaise frappe entraînerait l'échec. Cependant, étant donné que l'ensemble des cas de test ne contient que très peu d'orthographe, il fonctionne assez bien, ne se confondant que dans certains cas où il choisit des mots trop longs.

Edit: je l'ai un peu changé pour ne pas utiliser le fichier de position clé fourni mais une mise en page simplifiée. Cela facilite la tâche de mon algorithme car dans le fichier, les clés ne sont pas espacées de manière égale. Je peux obtenir des résultats encore légèrement meilleurs en incluant des bris d'égalité ad hoc pour les cas ambigus, mais ce serait une optimisation excessive pour cet ensemble de tests particulier. Il reste quelques échecs qui ne sont pas réellement ambigus mais que je n'attrape pas avec mon algorithme simple car il ne considère que les changements de direction de plus de 90 degrés.

PHP, Direction Checker, 203 213 216 229 231 et 229 233 passes

Cela commence par un simple passage dans le dictionnaire pour obtenir une liste de mots dont les lettres sont toutes présentes dans l'entrée (ce que Martin a fait ici ), et aussi seulement pour vérifier au l.*lieu de l.*l.*quand lest dupliqué.

Le mot le plus long ici est ensuite enregistré dans une variable.

Une autre vérification est ensuite effectuée, basée sur les touches aux points où le balayage change de direction (+ / 0 à - ou - / 0 à +, en x ou y). La liste des mots possibles est vérifiée par rapport à cette liste de caractères et les mots qui ne correspondent pas sont éliminés. Cette approche repose sur des virages serrés dans le balayage pour être précis.

Le mot restant le plus long est sorti, ou s'il ne reste aucun mot, le mot le plus long du précédent est sorti à la place.

Modifier: ajout de tous les caractères sur une ligne horizontale menant à un changement de direction en tant que valeurs possibles à vérifier.

PHP 5.4 est requis (ou remplacez tout [..]par 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;

Python 3, Corner Simulator, 241 et 240 passes

Algorithme:

• Dédupliquer (supprimer les séquences consécutives du même caractère) l'entrée et tous les mots de la liste de mots (en utilisant un dictionnaire pour récupérer les mots d'origine)
• Supprimez tous les mots qui ne commencent et ne se terminent pas au début et à la fin du balayage (première passe)
• Faites une expression régulière de tous les coins supérieurs à 80 degrés, puis supprimez tous les mots qui ne correspondent pas à cela (deuxième passage)
• Regex chaque mot (comme Regex Solver) contre le glissement, puis divisez le glissement en une série de lignes théoriquement droites, et vérifiez si elles sont droites et pourraient avoir été produites par un doigt se déplaçant le long de cette ligne ( significant_letterfonction) (troisième passage)
• Trier les mots par proximité des lignes droites
• Utilisez ensuite la longueur comme bris d'égalité (plus c'est long, mieux c'est)
• Utilisez ensuite la distance de Levenshtein comme dernier bris d'égalité
• Mot de sortie!

Code:

# 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))

Courir avec python3 entries/corner_sim.py