Revolusi berikutnya dalam mengetik di laptop dirilis pada tanggal 1 April 2014 oleh SwiftKey . Namun, saya ingin menjadi orang pertama yang menulis klon nano swiping, tetapi, karena saya tidak dapat menemukan teks gesek yang baik ke perpustakaan teks asli, dan saya tidak bisa menunggu mereka, saya bertanya di sini.

Tugas

Tulis program yang menerima teks gesek dan mengeluarkan teks-nyata yang setara. Contoh:

Input: hgrerhjklo
Output: hello

Ketika pengguna melakukannya:

Contoh lain:

Input: wertyuioiuytrtjklkjhgfd
Output: world

Input: poiuytrtyuioiugrewsasdfgbhnmkijnbg
Output: programming

Input: poiuygfdzxcvhjklkjhgres
Output: puzzles

Input: cvhjioiugfde
Output: code

Input: ghiolkjhgf
Output: golf

Aturan

• Program akan mengambil satu 'kata' yang digesek di atas stdin atau argv
• Huruf pertama dan terakhir dari input yang digesek akan sama dengan huruf pertama dan terakhir dari kata asli
• Anda dapat mengasumsikan pengguna akan membuat garis lurus yang wajar, tetapi Anda dapat menggunakan data sampel untuk memverifikasi ini (saya membuat data sampel, dan saya akan membuat data uji akhir)
• Untuk input yang ambigu, Anda dapat membuat pilih salah satu output, tetapi saya akan mencoba untuk menghapus semua ambiguitas dari data uji
• Kata ini akan ada dalam daftar kata ini (tetapi digesek). Daftar kata akan berada di direktori saat ini, dan dapat dibaca (baris baru dipisahkan, akan dinamai wordlist, tidak ada ekstensi).
• Babatan hanya akan berisi karakter alfabet huruf kecil
• Gesek dapat berisi karakter yang digandakan, jika pengguna berhenti sebentar pada kunci
• Program harus menampilkan pada stdout (kasus tidak masalah)
• Program harus kembali 0sebagai kode pengembalian
• Anda harus memberikan perintah jalankan, kompilasi perintah (jika perlu), nama dan jalur input mana yang digunakan
• Namun, celah standar berlaku (mereka mungkin tidak membantu)
• Tidak ada perpustakaan non-builtin yang diizinkan
• Lebih disukai solusi deterministik, non-golf / tidak jelas
• Tidak ada penulisan file, jaringan, dll.
• Kode Anda harus berjalan dalam satu detik atau kurang (kode Anda dijalankan sekali per kata)
• Proses penilaian dijalankan pada prosesor Intel i7 Haswell, dengan 4 kode virtual (2 yang nyata), sehingga Anda dapat menggunakan utas jika Anda harus
• Panjang kode maksimum 5000 byte
• Bahasa yang Anda gunakan harus memiliki versi gratis (tidak percobaan) yang tersedia untuk Linux (Arch Linux, jika itu penting)

Kriteria Kemenangan

• Pemenangnya adalah solusi yang paling akurat (diberi skor oleh program kontrol , menggunakan daftar tes yang disediakan)
• Popularitas adalah tie breaker
• Tabel penilaian akan diperbarui setiap beberapa hari
• Time-out dan crash dihitung sebagai gagal
• Tantangan ini akan berjalan selama dua minggu atau lebih, tergantung pada popularitas
• Skor akhir akan menggunakan daftar kata yang berbeda, yang dipilih secara acak (panjang yang sama, dari daftar kata yang sama)

Lain

• Anda dapat menggunakan program kontrol untuk menguji program Anda
• Jika Anda tidak sabar, dan ingin program Anda diperbarui / ditambahkan dengan cepat, mulai masalah atau tarik permintaan di https://github.com/matsjoyce/codegolf-swipe-type/blob/master
• Entri dikelola di https://github.com/matsjoyce/codegolf-swipe-type/blob/master/entries
• Log dari setiap program dijalankan di https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs
• Log utama di https://github.com/matsjoyce/codegolf-swipe-type/blob/master/log.log
• Posisi setiap kunci akan diberikan sebagai file csv di direktori saat ini disebut keypos.csv, dengan nilai x dan y diberikan relatif terhadap Q(lihat https://github.com/matsjoyce/codegolf-swipe-tipe/blob/master/ keypos.csv )
• Setiap kunci 1,5 x 1,5 cm (unit yang sama seperti di keypos.csv)

Papan Skor Saat Ini

daftar tes ( log ):

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

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

daftar tes ( log ):

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

Dilakukan dengan baik untuk semua orang dan hgfdsasdertyuiopoiuy swertyuiopoijnhg!

JavaScript, ES6, Three Pass Optimizer, 112 187 235 240 241 243 dan 231 234 berlalu

Filter tiga lintasan yang pertama kali mengetahui kunci-kunci penting dalam urutan penekanan tombol dan kemudian melewati urutan tersebut melalui tiga filter:

1. RegEx yang longgar dibentuk dari kunci kritis dan kunci bantuan. Ini memberikan hasil yang benar untuk sebagian besar kunci (sekitar 150)
2. RegEx yang ketat hanya terbuat dari kunci-kunci penting. Ini memberikan hasil yang benar untuk 85 urutan tambahan
3. Filter ketiga untuk mengetahui ambiguitas di antara jawaban dekat. Ini berfungsi untuk 40% kasus ambigu.

Kode

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

Kode mengasumsikan variabel yang dipanggil wordshadir yang merupakan array dari semua kata dari halaman ini

Lihat kode ini di sini

Lihat kasus uji yang sedang beraksi di sini

Kedua tautan di atas hanya berfungsi pada Firefox terbaru (33 dan lebih tinggi) (karena ES6).

Ruby, Regex Solver - 30 140 176 180 182 187 dan 179 183 berlalu

Saya akan mencari tahu skornya nanti. Berikut ini adalah solusi yang sangat naif yang tidak memperhitungkan tata letak keyboard:

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]

Dibutuhkan input dari ARGV dan mencetak hasilnya. Saya hanya memfilter daftar kata dengan huruf pertama dan terakhir, dan mereka saya mencoba semua kata yang tersisa terhadap input (menghilangkan surat duplikat dan menggunakan regex seperti ^g.*u.*e.*s$untuk "tebak") dan kembalikan yang pertama jika ada adalah beberapa solusi.

Jalankan seperti

ruby regex-solver.rb cvhjioiugfde

Orang lain, silakan gunakan kembali langkah ini sebagai filter pertama - Saya percaya ini tidak akan membuang kata-kata yang benar, sehingga pemeriksaan pendahuluan ini dapat sangat mengurangi ruang pencarian untuk algoritma yang lebih baik.

Sunting: Mengikuti saran OP, saya sekarang memilih kandidat terpanjang, yang tampaknya menjadi heuristik yang layak.

Juga terima kasih kepada es1024 untuk mengingatkan saya tentang surat duplikat.

C ++, Discret Fréchet Distance - 201 220 222 232 dan 232 berlalu

Bagi saya, masalah ini sangat membutuhkan Fréchet Distance yang sayangnya sangat sulit untuk dihitung.

Hanya untuk bersenang-senang, saya sudah mencoba untuk mendekati masalah dengan menerapkan pendekatan diskrit yang dijelaskan oleh Thomas Eiter dan Heikki Mannila dalam Computing Discrete Fréchet Distance (1994).

Pada awalnya, saya menggunakan pendekatan yang sama dengan yang lain untuk memfilter semua kata dalam daftar yang merupakan input berikutnya (juga akuntansi untuk beberapa kejadian berurutan dengan karakter yang sama). Lalu, saya mengisi kurva poligon dari huruf ke huruf setiap kata dengan titik tengah dan mencocokkannya dengan kurva input. Akhirnya, saya membagi setiap jarak dengan panjang kata dan mengambil skor minimum.

Sejauh ini, metode ini tidak berfungsi dengan baik seperti yang saya harapkan (Ia mengenali contoh kode sebagai "chide"), tetapi ini bisa saja hasil dari bug yang belum saya temukan. Selain itu, ide lain adalah menggunakan variasi lain dari jarak fréchet ("rata-rata" dan bukan "panjang tali anjing maksimum").

Sunting: Sekarang, saya menggunakan perkiraan untuk "panjang tali anjing rata-rata". Ini berarti bahwa saya menemukan pemetaan terurut antara kedua jalur yang meminimalkan jumlah semua jarak dan kemudian membaginya dengan jumlah jarak.

Jika karakter yang sama muncul dua kali atau lebih sering dalam kata kamus, saya hanya meletakkan satu simpul di jalur.

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

Saya telah mengkompilasi kode dengan dentang, tetapi g++ ./thiscode.cpp -o ./thiscodejuga harus berfungsi dengan baik.

Python 2, Turnarounds, 224 226 230 232 dan 230 234 berlalu

Ini adalah pendekatan yang sangat mudah:

• Temukan titik-titik di mana aliran huruf berubah arah (plus awal dan akhir).
• Keluarkan kata terpanjang yang mencakup semua titik balik ini.

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

Jalankan sebagai

python turnarounds.py tyuytrghn

Solusinya tidak terlalu kuat. Satu penekanan tombol yang salah akan membuatnya gagal. Namun, karena serangkaian kasus uji memiliki sangat sedikit kesalahan ejaan, kinerjanya cukup baik, hanya menjadi bingung dalam beberapa kasus di mana ia mengambil kata-kata yang terlalu panjang.

Sunting: Saya mengubahnya sedikit untuk tidak menggunakan file posisi kunci yang disediakan tetapi tata letak yang disederhanakan. Ini membuatnya lebih mudah untuk algoritma saya karena dalam file kunci tidak spasi secara merata. Saya dapat mencapai hasil yang sedikit lebih baik dengan memasukkan beberapa penghambat ad-hoc untuk kasus-kasus yang ambigu, tetapi itu akan terlalu mengoptimalkan untuk set tes khusus ini. Beberapa gagal tetap yang sebenarnya tidak ambigu tetapi saya tidak menangkap dengan algoritma sederhana saya karena hanya mempertimbangkan perubahan arah lebih dari 90 derajat.

PHP, Direction Checker, 203 213 216 229 231 dan 229 233 lolos

Ini dimulai dengan melewati kamus untuk mendapatkan daftar kata-kata yang semua suratnya ada di input (apa yang Martin lakukan di sini ), dan juga hanya memeriksa l.*alih - alih l.*l.*kapan ldigandakan.

Kata terpanjang di sini kemudian disimpan dalam variabel.

Pemeriksaan lain kemudian dilakukan, berdasarkan pada tombol di titik-titik di mana gesekan mengubah arah (+ / 0 ke - atau - / 0 ke +, dalam x atau y). Daftar kata-kata yang mungkin diperiksa terhadap daftar karakter ini, dan kata-kata yang tidak cocok dihilangkan. Pendekatan ini bergantung pada tikungan tajam dalam menggesek untuk menjadi akurat.

Kata terpanjang yang tersisa dikeluarkan, atau jika tidak ada kata yang tersisa, kata terpanjang dari sebelumnya dihasilkan.

Sunting: Menambahkan semua karakter dalam garis horizontal yang mengarah ke perubahan arah sebagai nilai yang mungkin untuk diperiksa.

Diperlukan PHP 5.4 (atau ganti semua [..]dengan 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 dan 240 lintasan

Algoritma:

• Deduplicate (menghapus berturut-turut berjalan dari karakter yang sama) input dan semua kata dalam daftar kata (menggunakan kamus untuk mendapatkan kata-kata asli kembali)
• Hapus semua kata yang tidak dimulai dan diakhiri dengan awal dan akhir gesekan (pass pertama)
• Buat regex dari semua sudut lebih dari 80 derajat, lalu singkirkan semua kata yang tidak cocok dengan ini (pass kedua)
• Regex setiap kata (seperti Regex Solver) terhadap swipe, lalu bagi swipe ke dalam serangkaian garis lurus secara teoritis, dan periksa apakah itu lurus dan bisa dihasilkan oleh jari yang bergerak di sepanjang garis itu ( significant_letterfungsi) (pass ketiga)
• Urutkan kata berdasarkan kedekatan dengan garis lurus
• Kemudian gunakan panjang sebagai tie breaker (lebih lama lebih baik)
• Kemudian gunakan jarak Levenshtein sebagai pemutus dasi akhir
• Kata keluaran!

Kode:

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

Jalankan dengan python3 entries/corner_sim.py