Kolejna rewolucja w pisaniu na laptopach została wydana pierwszego kwietnia 2014 roku przez SwiftKey . Chcę jednak być pierwszą osobą, która napisała przesuwającego się nano-klona, ​​ale ponieważ nie mogę znaleźć dobrego tekstu przesuwanego do biblioteki tekstu rzeczywistego i nie mogę się doczekać, pytam tutaj.

Zadanie

Napisz program, który pobiera tekst machnięcia i generuje odpowiednik tekstu rzeczywistego. Przykład:

Input: hgrerhjklo
Output: hello

Gdy użytkownik:

Inne przykłady:

Input: wertyuioiuytrtjklkjhgfd
Output: world

Input: poiuytrtyuioiugrewsasdfgbhnmkijnbg
Output: programming

Input: poiuygfdzxcvhjklkjhgres
Output: puzzles

Input: cvhjioiugfde
Output: code

Input: ghiolkjhgf
Output: golf

Zasady

• Program pobierze jedno przeciągnięte „słowo” na stdin lub argv
• Pierwsza i ostatnia litera wprowadzonego tekstu będzie równa pierwszej i ostatniej literze prawdziwego słowa
• Możesz założyć, że użytkownik wykona rozsądnie proste linie, ale możesz użyć przykładowych danych, aby to zweryfikować (stworzyłem przykładowe dane i zrobię końcowe dane testowe)
• W przypadku niejednoznacznych danych wejściowych możesz wybrać jedno z danych wyjściowych, ale spróbuję usunąć wszelkie niejednoznaczności z danych testowych
• To słowo będzie w tym liście słów (ale przeciągnął). Lista słów będzie w bieżącym katalogu i będzie można ją odczytać (oddzielony nowy wiersz, zostanie nazwany wordlist, bez rozszerzenia).
• Przeciągnięcie będzie zawierać tylko małe litery
• Przesunięcie może zawierać zduplikowane znaki, jeśli użytkownik pauzuje na klawiszu
• Program musi wyprowadzać na standardowe wyjście (wielkość liter nie ma znaczenia)
• Program musi zostać zwrócony 0jako kod powrotu
• Musisz podać polecenie uruchomienia, polecenie kompilacji (w razie potrzeby), nazwę i ścieżkę wejściową do użycia
• Obowiązują standardowe luki (mogą jednak nie pomóc)
• Niedozwolone są wbudowane biblioteki
• Preferowane są deterministyczne, nie golfowe / zaciemnione rozwiązania
• Bez pisania plików, pracy w sieci itp.
• Twój kod musi działać w ciągu jednej sekundy lub krócej (kod jest uruchamiany raz na słowo)
• Przebiegi oceniania są uruchamiane na procesorze Intel i7 Haswell z 4 wirtualnymi kodami (2 prawdziwe), więc możesz użyć wątków, jeśli musisz
• Maksymalna długość kodu 5000 bajtów
• Język, którego używasz, musi mieć bezpłatną (próbną) wersję dla Linuksa (Arch Linux, jeśli to ma znaczenie)

Zwycięskie kryterium

• Zwycięzca jest najdokładniejszym rozwiązaniem (ocenionym przez program kontroli , na podstawie dostarczonej listy testów)
• Popularność jest czynnikiem rozstrzygającym
• Tabela punktacji będzie aktualizowana co kilka dni
• Przerwy i awarie liczą się jako niepowodzenia
• To wyzwanie potrwa dwa tygodnie lub dłużej, w zależności od popularności
• W końcowej punktacji zostanie użyta inna, losowo wybrana lista słów (ta sama długość, z tej samej listy słów)

Inny

• Możesz użyć programu sterującego do przetestowania swojego programu
• Jeśli jesteś niecierpliwy i chcesz, aby Twój program był szybko aktualizowany / dodawany, rozpocznij problem lub ściągnij żądanie na https://github.com/matsjoyce/codegolf-swipe-type/blob/master
• Wpisy są utrzymywane na https://github.com/matsjoyce/codegolf-swipe-type/blob/master/entries
• Dzienniki każdego uruchomienia programu są przechowywane na stronie https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs
• Główny dziennik na https://github.com/matsjoyce/codegolf-swipe-type/blob/master/log.log
• Pozycja każdego klucza zostanie podana jako plik csv w bieżącym katalogu o nazwie keypos.csv, z wartościami x i y podanymi w stosunku do Q(patrz https://github.com/matsjoyce/codegolf-swipe-type/blob/master/ keypos.csv )
• Każdy klucz ma wymiary 1,5 x 1,5 cm (ta sama jednostka, co w keypos.csv)

Aktualne tablice wyników

lista testów ( logi ):

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

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 testów ( logi ):

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

Dobra robota dla wszystkich i hgfdsasdertyuiopoiuy swertyuiopoijnhg!

JavaScript, ES6, Three Pass Optimizer, 112 187 235 240 241 243 i 231 234 przebiegów

Trzyprzepustowy filtr, który najpierw rozpoznaje klawisze krytyczne w sekwencji naciśnięć klawiszy, a następnie przepuszcza sekwencję przez trzy filtry:

1. Luźno utworzony RegEx z kluczowych kluczy i kluczy pomocniczych. To daje poprawny wynik dla większości klawiszy (około 150)
2. Surowy RegEx złożony z kluczowych kluczy. To daje poprawny wynik dla dodatkowych 85 sekwencji
3. Trzeci filtr, aby ustalić niejednoznaczność wśród bliskich odpowiedzi. Działa to w przypadku 40% niejednoznacznych przypadków.

Kod

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

Kod zakłada, że wordsobecna jest zmienna o nazwie, która jest tablicą wszystkich słów z tej strony

Zobacz kod w akcji tutaj

Zobacz przypadki testowe w akcji tutaj

Oba powyższe łącza działają tylko w najnowszym Firefoksie (33 i nowszym) (z powodu ES6).

Ruby, Regex Solver - 30 140 176 180 182 187 i 179 183 podań

Ustalę wynik później. Oto bardzo naiwne rozwiązanie, które nie uwzględnia układu klawiatury:

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]

Pobiera dane wejściowe z ARGV i drukuje wynik. Po prostu filtruję listę słów według pierwszej i ostatniej litery i wypróbowuję wszystkie pozostałe słowa pod ^g.*u.*e.*s$kątem wejściowym (eliminując duplikaty liter i używając wyrażenia regularnego typu „zgadnij”) i zwracam pierwszą z nich, jeśli istnieje to wiele rozwiązań.

Uruchom to jak

ruby regex-solver.rb cvhjioiugfde

Każdemu innemu możesz użyć tego kroku jako pierwszego filtru - uważam, że nie wyrzuci on żadnych poprawnych słów, więc ta wstępna kontrola może znacznie zmniejszyć przestrzeń wyszukiwania lepszych algorytmów.

Edycja: Zgodnie z sugestią PO wybieram teraz najdłuższego z kandydatów, co wydaje się być porządną heurystą.

Również dzięki es1024 za przypomnienie mi o zduplikowanych literach.

C ++, dyskretna odległość Frécheta - 201 220 222 232 i 232 przebiegi

Dla mnie problem bardzo wymagał odległości Frécheta, która niestety jest bardzo trudna do obliczenia.

Dla zabawy próbowałem podejść do tego problemu, wdrażając dyskretne przybliżenie opisane przez Thomasa Eitera i Heikki Mannilę w Computing Discrete Fréchet Distance (1994).

Najpierw używam tego samego podejścia, co inne, do filtrowania wszystkich słów na liście, które są podsekwencjami danych wejściowych (również uwzględniając wiele kolejnych wystąpień tego samego znaku). Następnie wypełniam krzywą wielokąta od litery do litery każdego słowa punktami pośrednimi i dopasowuję ją do krzywej wejściowej. Na koniec dzielę każdy dystans przez długość słowa i uzyskuję minimalny wynik.

Jak dotąd metoda nie działa tak dobrze, jak się spodziewałem (rozpoznaje przykład kodu jako „chide”), ale może to wynikać z błędów, których jeszcze nie znalazłem. W innym przypadku innym pomysłem byłoby użycie innych wariantów odległości fréchet („średnia” zamiast „maksymalnej długości smyczy dla psa”).

Edycja: Teraz używam przybliżenia do „średniej długości smyczy dla psa”. Oznacza to, że znajduję uporządkowane mapowanie między obiema ścieżkami, które minimalizuje sumę wszystkich odległości, a następnie dzielę je przez liczbę odległości.

Jeśli ten sam znak pojawia się dwa lub więcej razy w słowie słownikowym, umieszczam tylko jeden węzeł na ścieżce.

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

Skompilowałem kod z clang, ale g++ ./thiscode.cpp -o ./thiscodepowinien również działać dobrze.

Zalicza się pytanie Python 2, Turnarounds, 224 226 230 232 i 230 234

Jest to dość proste podejście:

• Znajdź punkty, w których przepływ liter zmienia kierunek (plus początek i koniec).
• Wypisz najdłuższe słowo, które obejmuje wszystkie te punkty zwrotne.

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

Uruchom jako

python turnarounds.py tyuytrghn

Rozwiązanie nie jest zbyt solidne. Pojedyncze nieprawidłowe naciśnięcie klawisza spowodowałoby błąd. Ponieważ jednak zestaw przypadków testowych nie ma bardzo mało błędów ortograficznych, działa całkiem dobrze, tylko myli się w niektórych przypadkach, w których wybiera zbyt długie słowa.

Edycja: Trochę go zmieniłem, aby nie używać dostarczonego pliku pozycji klucza, ale uproszczony układ. Ułatwia to mojemu algorytmowi, ponieważ w pliku klucze nie są równomiernie rozmieszczone. Mogę osiągnąć nawet nieco lepsze wyniki, włączając niektóre ad-hoc rozstrzygacze dla niejednoznacznych przypadków, ale byłoby to nadmierną optymalizację dla tego konkretnego zestawu testowego. Pozostają pewne błędy, które nie są tak naprawdę dwuznaczne, ale których nie rozumiem za pomocą mojego prostego algorytmu, ponieważ uwzględnia on jedynie zmiany kierunku większe niż 90 stopni.

PHP, Direction Checker, 203 213 216 229 231 i 229 233 przechodzi

Zaczyna się to od prostego przejścia przez słownik, aby uzyskać listę słów, których wszystkie litery są obecne na wejściu (co zrobił tutaj Martin ), a także tylko sprawdzanie l.*zamiast, l.*l.*kiedy ljest duplikowane.

Najdłuższe słowo tutaj jest następnie zapisywane w zmiennej.

Następnie przeprowadzana jest kolejna kontrola, oparta na klawiszach w punktach, w których przeciągnięcie zmienia kierunek (+ / 0 do - lub - / 0 do +, albo x, albo y). Lista możliwych słów jest porównywana z tą listą znaków, a słowa, które nie pasują, są eliminowane. To podejście polega na ostrych zakrętach podczas przesuwania, aby być dokładnym.

Zostaje wyprowadzone najdłuższe pozostające słowo, lub jeśli nie pozostały żadne słowa, zamiast tego wyprowadzane jest najdłuższe słowo z wcześniejszego.

Edycja: Dodano wszystkie znaki w linii poziomej prowadzącej do zmiany kierunku, jak to możliwe wartości do sprawdzenia.

PHP 5.4 jest wymagane (lub wymienić wszystkie [..]z 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 i 240 przechodzi

Algorytm:

• Deduplikuj (usuń kolejne serie tego samego znaku) dane wejściowe i wszystkie słowa z listy słów (używając słownika, aby odzyskać oryginalne słowa)
• Usuń wszystkie słowa, które nie zaczynają się i kończą wraz z początkiem i końcem przeciągnięcia (pierwsze przejście)
• Wykonaj regex ze wszystkich rogów większych niż 80 stopni, a następnie usuń wszystkie słowa, które nie pasują do tego (drugie przejście)
• Ponownie zlinkuj każde słowo (podobnie jak Regex Solver) względem przeciągnięcia, a następnie podziel przeciągnięcie na szereg teoretycznie prostych linii i sprawdź, czy są one proste i czy mogły zostać wytworzone przez palec przesuwający się wzdłuż tej linii ( significant_letterfunkcja) (trzecie przejście)
• Sortuj słowa według odległości od linii prostych
• Następnie użyj długości jako przerywacza remisu (im dłużej, tym lepiej)
• Następnie użyj dystansu Levenshteina jako ostatecznego przerywnika remisu
• Słowo wyjściowe!

Kod:

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

Biegnij z python3 entries/corner_sim.py