Следующая революция в наборе текста на ноутбуках была выпущена SwiftKey первого апреля 2014 года . Тем не менее, я хочу быть первым, кто напишет наноклон для просмотра, но, так как я не могу найти хороший текст в библиотеке реального текста и не могу их ждать, я спрашиваю здесь.
задача
Напишите программу, которая принимает текст свайпом и выводит эквивалент реального текста. Пример:
Input: hgrerhjklo
Output: hello
Когда пользователь делает:
Другие примеры:
Input: wertyuioiuytrtjklkjhgfd
Output: world
Input: poiuytrtyuioiugrewsasdfgbhnmkijnbg
Output: programming
Input: poiuygfdzxcvhjklkjhgres
Output: puzzles
Input: cvhjioiugfde
Output: code
Input: ghiolkjhgf
Output: golf
правила
- Программа возьмет одно слово «слово» на стандартный ввод или argv
- Первая и последняя буква введенного пальца будет соответствовать первой и последней букве реального слова.
- Вы можете предположить, что пользователь будет делать достаточно прямые линии, но вы можете использовать данные образца для проверки этого (я сделал данные образца, и я сделаю окончательные данные теста)
- Для неоднозначного ввода, вы можете сделать выбор любого выхода, но я постараюсь устранить всю неоднозначность из тестовых данных
- Это слово будет в этом списке слов (но сильно ударил). Список слов будет находиться в текущем каталоге и может быть прочитан (разделены новой строкой, будет иметь имя
wordlist
, без расширения). - Размах будет содержать только строчные буквенные символы
- Размах может содержать дублированные символы, если пользователь делает паузу на клавише
- Программа должна выводить на стандартный вывод (регистр не имеет значения)
- Программа должна вернуться
0
как код возврата - Вы должны указать команду запуска, команду компиляции (если необходимо), имя и какой входной путь использовать
- Применяются стандартные лазейки (хотя они могут не помочь)
- Не допускаются не встроенные библиотеки
- Предпочтительны детерминированные, не гольфовые / запутанные решения
- Нет записи файла, сети и т. Д.
- Ваш код должен выполняться за одну секунду или меньше (ваш код запускается один раз за слово)
- Оценки выполняются на процессоре Intel i7 Haswell с 4 виртуальными кодами (2 реальных), поэтому вы можете использовать потоки, если вам нужно
- Максимальная длина кода 5000 байтов
- Используемый язык должен иметь бесплатную (не пробную) версию для Linux (Arch Linux, если это имеет значение)
Критерий победы
- Победителем является наиболее точное решение (оценивается контрольной программой с использованием предоставленного списка тестов)
- Популярность это разрыв связи
- Таблица очков будет обновляться каждые несколько дней
- Тайм-ауты и сбои считаются сбоями
- Это испытание будет выполняться в течение двух или более недель, в зависимости от популярности.
- В окончательной оценке будет использоваться другой, случайно выбранный список слов (той же длины, из того же списка слов)
Другие
- Вы можете использовать управляющую программу для проверки вашей программы
- Если вы нетерпеливы и хотите, чтобы ваша программа обновлялась / добавлялась быстро, начните выпуск или запрос по запросу по адресу https://github.com/matsjoyce/codegolf-swipe-type/blob/master.
- Записи поддерживаются на https://github.com/matsjoyce/codegolf-swipe-type/blob/master/entries
- Журналы каждого запуска программы ведутся по адресу https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs.
- Основной журнал по адресу https://github.com/matsjoyce/codegolf-swipe-type/blob/master/log.log
- Положение каждого ключа будет указано в виде csv-файла в текущем каталоге
keypos.csv
, где значения x и y указаны относительноQ
(см. Https://github.com/matsjoyce/codegolf-swipe-type/blob/master/. keypos.csv ) - Каждая клавиша имеет размер 1,5 х 1,5 см (такая же единица, как в keypos.csv)
Текущие табло
список тестов ( логи ):
Three Pass Optimizer:Errors: 0/250 Fails: 7/250 Passes: 243/250 Timeouts: 0/250
Corner Sim: Errors: 0/250 Fails: 9/250 Passes: 241/250 Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250 Fails: 17/250 Passes: 233/250 Timeouts: 0/250
Turnaround: Errors: 0/250 Fails: 18/250 Passes: 232/250 Timeouts: 0/250
Direction Checker: Errors: 0/250 Fails: 19/250 Passes: 231/250 Timeouts: 0/250
Regex Solver: Errors: 0/250 Fails: 63/250 Passes: 187/250 Timeouts: 0/250
Corner Sim: Errors: 0/250 Fails: 10/250 Passes: 240/250 Timeouts: 0/250
Three Pass Optimizer:Errors: 2/250 Fails: 14/250 Passes: 234/250 Timeouts: 0/250
Turnaround: Errors: 0/250 Fails: 16/250 Passes: 234/250 Timeouts: 0/250
Direction Checker: Errors: 0/250 Fails: 17/250 Passes: 233/250 Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250 Fails: 18/250 Passes: 232/250 Timeouts: 0/250
Regex Solver: Errors: 0/250 Fails: 67/250 Passes: 183/250 Timeouts: 0/250
Финальный забег
список тестов ( логи ):
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
Молодцы всем и hgfdsasdertyuiopoiuy swertyuiopoijnhg!
code-challenge
keyboard
matsjoyce
источник
источник
l
Ответы:
JavaScript, ES6, Three Pass Optimizer,
112 187 235 240 241243 и231234 проходаТрехпроходный фильтр, который сначала определяет критические ключи в последовательности нажатий клавиш, а затем пропускает последовательность через три фильтра:
Код
Код предполагает наличие переменной с именем,
words
которая представляет собой массив всех слов с этой страницыСмотрите код в действии здесь
Смотрите тестовые примеры в действии здесь
Обе вышеуказанные ссылки работают только на последнем Firefox (33 и выше) (благодаря ES6).
источник
keypos.csv
файл сейчас. Функции ввода - вывода avalible перечислены в developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/...Ruby, Regex Solver -
30 140 176 180 182187 и179183 проходаЯ выясню счет позже. Вот очень наивное решение, которое не учитывает раскладку клавиатуры:
Он принимает входные данные от ARGV и печатает результат. Я просто фильтрую список слов по первой и последней букве, а затем я пробую все оставшиеся слова по отношению к вводу (исключая повторяющиеся буквы и используя регулярное выражение, как
^g.*u.*e.*s$
для «угадай») и возвращаю первое из них, если есть Есть несколько решений.Запустите это как
Любой другой, не стесняйтесь повторно использовать этот шаг в качестве первого фильтра - я полагаю, что он не выбрасывает правильные слова, поэтому эта предварительная проверка может значительно сократить пространство поиска для лучших алгоритмов.
Изменить: Следуя предложению ОП, я сейчас выбираю самого длинного из кандидатов, что кажется неплохой эвристикой.
Также спасибо es1024 за напоминание о дубликатах писем.
источник
paradoxically
, так как ониl
будут отображаться только один раз на входе, а не в два раза, как того требует регулярное выражениеC ++, Дискретное расстояние Фреше -
201220222232 и 232 проходаДля меня проблема очень требовала расстояния Фреше, которое, к сожалению, очень сложно вычислить.
Ради интереса я попытался подойти к этой проблеме, применив дискретное приближение, описанное Томасом Эйтером и Хейкки Маннилой в « Вычисление дискретного расстояния Фреше» (1994).
Сначала я использую тот же подход, что и другие, для фильтрации всех слов в списке, которые являются подпоследовательностями входных данных (также учитывающих множественные последовательные вхождения одного и того же символа). Затем я заполняю кривую многоугольника от буквы к букве каждого слова промежуточными точками и сопоставляю ее с входной кривой. Наконец, я делю каждое расстояние на длину слова и беру минимальный балл.
Пока что метод работает не так хорошо, как я надеялся (он распознает пример кода как «chide»), но это может быть просто результатом ошибок, которые я еще не обнаружил. Иначе, другой идеей было бы использовать другие вариации расстояния fréchet («среднее» вместо «максимальная длина поводка»).
Редактировать: Теперь я использую приближение к "средней длине поводка собаки". Это означает, что я нахожу упорядоченное отображение между двумя путями, которое минимизирует сумму всех расстояний, а затем делит ее на количество расстояний.
Если один и тот же символ встречается в словарном слове дважды или чаще, я ставлю только один узел в пути.
Я скомпилировал код с помощью Clang, но он
g++ ./thiscode.cpp -o ./thiscode
также должен работать нормально.источник
programmijng
- это дает мнеpang
.programming
как должно. Не могли бы вы раскомментировать строку// cout << thispair->first << ": " << score << endl;
и вставить полученные результаты?Python 2, Turnarounds,
224 226 230232 и230234 проходовЭто довольно прямой подход:
Беги как
Решение не очень надежное. Единственное неправильное нажатие клавиши может привести к сбою. Однако, поскольку в наборе тестовых примеров
очень малоошибок, он работает довольно хорошо, запутываясь только в некоторых случаях, когда выбирает слишком длинные слова.Редактировать: я немного изменил его, чтобы не использовать предоставленный файл положения ключа, а упрощенный макет. Это облегчает мой алгоритм, потому что в файле ключи не расположены равномерно. Я могу достичь даже чуть лучших результатов, включив некоторые специальные таймбрейкеры для неоднозначных случаев, но это будет чрезмерной оптимизацией для этого конкретного набора тестов. Остаются некоторые сбои, которые на самом деле не являются неоднозначными, но которые я не уловил с помощью моего простого алгоритма, потому что он учитывает только изменения направления более чем на 90 градусов.
источник
brats
может быть, с'bgrdsasdrtrds'
чем нельзя спутатьbreasts
. Впрочем, я бы тоже не возражал, если бы вы оставили все как есть.PHP, Direction Checker,
203 213 216 229231 и229233 проходовЭто начинается с простого прохода по словарю, чтобы получить список слов, чьи буквы присутствуют во входных данных (что сделал здесь Мартин ), а также только проверка
l.*
вместо того,l.*l.*
когдаl
дублируется.Самое длинное слово здесь сохраняется в переменной.
Затем выполняется еще одна проверка, основанная на клавишах в точках, где свайп меняет направление (от + / 0 до - или - / 0 до +, в x или y). Список возможных слов сверяется с этим списком символов, а слова, которые не совпадают, удаляются. Этот подход основан на резких поворотах при смахивании, чтобы быть точным.
Выводится самое длинное оставшееся слово, или, если не осталось слов, вместо него выводится самое длинное слово из предыдущего.
Редактировать: Добавлены все символы в горизонтальной линии, приводящие к изменению направления, в качестве возможных значений для проверки.
Требуется PHP 5.4 (или заменить все
[..]
наarray(..)
).источник
keypos.csv
sss
) - я не думаю, что ваше дублирование исключит их.Python 3, Corner Simulator, 241 и 240 проходов
Алгоритм:
significant_letter
функция) (третий проход)Код:
Бежать с
python3 entries/corner_sim.py
источник