Эх, отписываются люди, потому что про парсеры не всем интересно читать, а я к сожалению ограничен форматом на время написания диплома :(

Подождите немного, скоро продолжу писать fopply и картинки красивые генерировать, всё будет.

Сегодня встретил такую "олимпиадную" задачку:
Выведите n-е по возрастанию натуральное число, сумма цифр которого, в десятичной системе счисления, равна двум.

Если интересно, можете для начала сами решить, ибо дальше спойлеры.

Очевидно, простейшая задача, но что-то я очень захотел её запрогать, и сделать это максимально красиво.

Анализ: имеется два возможных вида чисел, сумма цифр которых равна двум: 20*, 10*10*. Если написать эти числа по возрастанию:

2
11, 20
101, 110, 200
1001, 1010, 1100, 2000

то видно что для длины числа N, оно содержит N экземпляров числа, которые можно генерировать.

Это арифметическая прогрессия, можно легко посчитать размер числа из N, нужно только произвести обратную операцию. Ну и дальнейшее решение очевидно. Итоговая сложность - O(1).

Я начал с того, что сделал структуру арифметической прогрессии с такими методами:

new_canonical() -> ar
new(a1, d) -> ar
ar.nth(n) -> i64
ar.sum_to(n) -> sum
ar.from_sum(sum) -> n

Для подсчёта суммы использую формулу арифметической прогрессии S=(2a1+d(n-1))/2*n. Для обратной же операции from_sum нужно решать квадратное уравнение относительно n.

Кстати для решения квадратного уравнения я завёл такой enum:

pub enum SolvingResult {
  Two(f64, f64),
  One(f64),
  Zero,
}

(за это я и люблю АДТ)

Уже само выведение арифметической прогрессии в отдельный "класс" - это супер-удобно в решении, и не надо работать с этими дурацкими формулами.

Для итогового решения задачи я завёл такой enum:

pub enum Answer {
  Ones {
    size: i64,
    index: i64,
  },
  Two {
    size: i64,
  }
}

Функция, которая занимается основными вычислениями, возвращает именно его. Зачем? Чтобы код для отображения результата и его вычисления был различен.

Ведь отображать мы можем как в строку (чтобы тестировать), так и на экран (чтобы максимально быстро вывести ответ). А для отображения на экран аллоцировавть память как-то нехорошо.

Поэтому для этой структуры реализовал Display.

В общем самый главный код конкретно этой задачи занимает 12 строчек, а обслуживающий, ну, много...

И ещё ко всему добавил юнит-тестиков, на них же и дебажил, благодаря им я уверен, что код отработает правильно до отправки на тестовый сервер.

Итог:
https://github.com/optozorax/olymp/tree/master/nth-sum-equals-two

А теперь рассуждения по теме олимпиад, на основе этой задачи.

При решении этой задачки у меня было ОЧЕНЬ много off-by-one error (https://en.wikipedia.org/wiki/Off-by-one_error). Вот видите в основном коде кучу +1, -1, вот всё это подобрано опытным путём, а логика объяснена задним числом (когда всё заработало). Меня очень это напрягает, и мне кажется дальнейший путь совершенствования - это проектировать всё так, чтобы проблем с off-by-one вообще не возникало, чтобы все эти +1, -1 были закодированы в имя метода как-нибудь.

Во время олимпиад такие ошибки возникают постоянно, и на них тратится немало времени. Так что это актуальная тема. Если будут предложения, пишите!

В этой задаче:
* Класс для арифметической прогрессии
* Алгебраические типы данных для решения квадратного уравнения
* Разделение вычислений и отображения на экран
вот это всё мне прям понравилось. Не знаю, Растишка побуждает так хорошо писать код или я уже к нему стремлюсь, но Rust явно позволяет писать его намного проще, чем на C++, на котором я до этого решал все олимпиады.

Кстат, именно после последней олимпиады и настал тот переломный момент, когда я перешёл на Rust вместо C++. Ради примера, чтобы показать насколько ужасен C++, вот так там удаляются элементы в массиве по лямбде:

auto it = remove_if(a.begin(), a.end(), [] (auto i) { return ...; });
a.erase(it, a.end());

То есть remove_if не удаляет элементы, а просто помещает их в конец, и возвращает итератор конца. И чтобы уже на самом деле их удалить, надо вызвать дополнительный метод, который удаляет с одного конца до другого. Много же ног прострелено таким кодом. Отличная работа, C++ 💩👍. Этот язык не то что не побуждает писать в итераторном стиле, так он всеми силами пытается сказать не делать этого. Я ещё не говорю про std::move + &&, segfault и UB. Благо мне немного пришлось программировать на нём для продакшена. Ладно, возвращаясь к задаче...

Больше всего времени у меня ушло на написание метода from_sum для арифметической прогрессии, чем на, собственно, решение задачи. И если припомнить, арифметическая прогрессия встречается в олимпиадных задачах очень часто.

Мне хочется чтобы международная организация по олимпиадам ICPC наконец восприняли всерьёз Rust, и официально его добавила, ведь это шикарный язык, со всеми его итераторами и прочим. Kotlin же туда легко добавили.

И ещё я хочу, чтобы людям на олимпиадах больше не приходилось писать арифметические прогрессии и алгоритм дейкстры, я хочу чтобы у ICPC была open-source библиотека, которая подключается ко всем задачам. Чтобы люди занимались решением именно алгоритмических задач, и писали никогда не существовавшие алгоритмы, а не копипастили из головы 100500 решённую фигню, которую чтобы написать без ошибок и быстро, надо просто задрочить. Например в комментариях на codeforces.com люди говорят что умеют писать быструю сортировку на паскале за 10 минут (кто не знал, там нет сортировки в стандартной библиотеке, там вроде вообще нет стандартной библиотеки, лол). Мне кажется, чем заниматься таким безумием, им проще было уже научиться C++, где быстрая сортировка есть.

Сейчас я решил немного переделать ту часть моего парсера, которая считывает грамматику из строки. Назвал я этот модуль мета-парсинг, далее его буду его так называть, чтобы не возникало путаницы.

Итак, до этого у меня мета-парсинг работал так: берём строку из неё сразу получаем нужные структуры данных. Кстати, такой подход я лишь основывал на примерах (что говорит что примеры этой библиотеки нуждаются в переработке).

Сейчас же я переделал его под несколько этапов:
∙ токенизация
∙ построение абстрактного дерева
∙ проход по дереву и получение грамматики

## Токенизация

Для токенизации я решил взять код, лежащий в исходниках компилятора Rust! Это rustc_lexer, благодаря ему я смогу не думать насчёт сложных вещей, типо:
∙ идентификаторов на разных языках,
∙ считывания строчек со всеми возможными способами экранирования символов,
∙ рекурсивных комментариях.
И интерфейс у него относительно простой.

Но, как оказалось потом, он не используется в компиляторе, и это, похоже, задел на будущее. А использует этот крейт в основном rust-analyzer...

Ну и ладно, всё-равно решил заюзать. А интерфейс библиотеки для меня неудобный, поэтому я написал простенькую либку, которая делает всякую рутинную работу: simple_rustc_tokenizer.

Так же в процессе оказалось, что нельзя так просто скрестить использование токенов и мой любимый парсер rust-peg, из-за чего появилось это issue.

## Построение абстратного дерева

Напоминаю, что у меня может быть вложенное правило, например, такое:
S -> A (B | (C D | E) | F) | G;

Раньше я это как-то очень некрасиво обрабатывал через парсер, передавая ему мутабельную структуру данных, сейчас же с этим деревом всё очень красиво.

Структура данных дерева будет на следующем скриншоте.

Так же благодаря этому я решил такую проблему, что у меня на этапе парсинга раньше особым образом смотрелись токены Start, End, Any. Потому что в структурах они задаются особым образом, и приходилось парсить их костылём вида:
"Start" !ident()

Если бы не вот эта часть !ident(), то StartMy парсилось всегда как Start My.

Так же недавно я узнал что внутрь дерева можно вставить специальное ошибочное состояние, и по особому его парсить! Называется это "восставновление после ошибок".

Например, для всего что находится внутри скобок можно сделать такое правило:
S -> "{" Expr "}" | "{" AnythingExceptBrace "}";

Где первый вариант - это нормальный парсинг, а второй - вариант с ошибками. Это позволяет за один раз охватить как можно больше ошибок. Но я так не сделал, зато задел на будущее есть!

Ещё я благодаря дереву я улучшил нейминг анонимных правил. Раньше правило:
S -> A (B | C (D | F)) | H;

"рассахаривалось" в:

S.0 -> A λ0;
S.1 -> H;
λ0.0 -> B;
λ0.1 -> C λ1;
λ1.0 -> D;
λ1.1 -> F;

То есть лямбдам давались номера в соответствии с их глобальным появлением. А теперь же им даются имена на основе их родителя:

S.0 -> A S.0-λ0;
S.1 -> H;
S.0-λ0.0 -> B;
S.0-λ0.1 -> C S.0-λ0.1-λ0;
S.0-λ0.1-λ0.0 -> D;
S.0-λ0.1-λ0.1 -> F;

И это было сделать намного проще при новой схеме с абстрактным деревом, чем при старой (кстати это и стало причиной почему я решил использовать деревья).

А такие имена позволяют намного проще понимать что откуда взялось в процессе дебага. И в реальной грамматике у меня было что-то вроде λ47, по чему абсолютно невозможно понять откуда оно взялось :)

Структура данных абстрактного дерева для мета-парсинга.

Кстати, хочу немного прокомментировать статью:

https://habr.com/ru/post/498042/

Я тоже постепенно начинаю делать код так, чтобы сами типы данных помогали делать код надёжней к рефакторингу и ошибкам.

## Первый пример

У меня есть две структуры данных: ToParser, FromParser. Внутри они состоят абсолютно из одинаковых данных. Главная особенность, что для ToParser существуют конструкторы, а тип FromParser можно получить только вызвав у ToParser метод parse(). У структуры FromParser есть методы для получения деревьев парсинга, и вывода всего на экран. То есть нельзя распарсить что-то несколько раз, и нельзя не распарсить что-то. Типы и инкапсуляция защищают от этого :)

## Второй пример

Я уже об этом писал в /194, я оборачиваю почти все индексы для массивов в специальные типы данных, и пишу методы для индексирования этих массивов только нужным типом данных. Ну и в функции передаю только нужный тип, позволяет не запутаться в куче usize.

Подумываю над тем, чтобы сделать отдельную библиотеку контейнера, который индексируется только через такой тип-обёртку над usize, но пока получается не очень.

Я решил проблему с заданием "вероятностей", описанную в /184.

Постараюсь снова расписать и объяснить что это и зачем нужно.

В чём моя проблема? Я хочу иметь какие-то абстрактные чиселки рядом с правилами грамматики, которые будут преобразовываться по каким-то абстрактным правилам (не обязательно умножение или сложение), для достижения каких-то целей.

Что за цели? Я пишу парсер при помощи которого будет аппроксимироваться естественный язык через Контекстно-Свободные грамматики. Очевидно, так как это аппроксимация, не может быть чего-то абсолютно верного и точного. Значит какие-то правила могут лучше аппроксимировать некоторые фразы, а какие-то хуже. Для этого мне нужны чиселки, чтобы они как-то преобразовывались, и чтобы на выходе получалось примерно такое: вот для этой фразы такой-то факт с вероятностью 57% правильный, для такой-то фразы с вероятностью 98% правильный.

Почему чиселки абстрактные, что тебе нужно от них? Хотелось получить удобный интерфейс задания этих чиселок, который можно логически трактовать и который можно легко написать, будучи пользователем парсера (то есть без вмешательства численных методов).

Ну, например, существуют обычные вероятности - числа от 0 до 1, бери их да, умножай. Нет. Обычные вероятности не подходят по нескольким причинам:
* Чем больше фраза, тем больше умножений чисел от 0 до 1, тем ближе результат к 0.
* В связи с этим абсолютные значения "вероятностей" не имеют никакого смысла.
* Задавать их неудобно, нужны какие-то магические числа 0.57, 0.98, 0.05.
* Накладывается ограничение в виде того что сумма вероятностей для одного нетерминала должна быть 1.
* Смотри пример в /199

Вроде разъяснил, дальше продолжу обычное повествование.

В /184 я предложил интерфейс описания "абстрактных чиселок", который можно логично трактовать:
* +20% - значит что-то увеличивается на что-то, увеличивается на число больше что больше чем +10%
* -20% - аналогично верхнему уменьшается, и уменьшается сильнее, чем на -10%
* 60% - задаёт обычную вероятность

Вскоре я понял что нельзя смешивать обычную вероятность и эти +20%, -20%. Потому что обычная вероятность их съедает, и вообще всё заражает собой.

Поэтому выкидываем её и добавляем элемент: 0% - он означает, что ничего не изменится.

Назовём эту величину "уверенность". И введём операцию объединения "уверенностей" под символом ★.

Теперь главная проблема состоит в том, чтобы определить как эти уверенности задавать, какие у них свойства и как вычислять ★.

Я решил что -20% должно мапиться в -0.2, +20% в +0.2, а в итоге область определения должна быть [-1; 1].

Я начал с создания такой функции: https://www.desmos.com/calculator/njsni62kej

Её проблема в том что она не гладкая, и она даёт разные результаты в зависимости от порядка когда её применять. А ведь в грамматиках не задан конкретный порядок, и не знаешь когда надо выполнить ★, а когда нет. К тому же она получала данные в области [-1; 1], а возврщала в области [0; 1]. Но это легко поправляется.

Значит, самое главное свойство, которое мне нужно, это: (a ★ b) ★ c = (a ★ c) ★ b.

Далее я пытался гуглить, но безрезультатно. Пытался читать теорему Байеса, думать как её применить к своей задаче, тоже безрезультатно.

⬇️

⬆️

Затем я осознал, что я могу применить грубую силу!!! Я чёртов программист численных методов, я должен это использовать чтобы численно найти нужную мне функцию!

Итак, я должен был сделать следующую последовательность действий:
* Сформулировать свойства необходимой мне функции
* Запрограммировать расчёт выполнения этих свойств при помощи интегралов
* Найти библиотеку для задания гладких 2D функций по каким-то числам
* Использовать методы оптимизации, чтобы найти такие числа, которые на этих интегралах дают минимум
* Достаточно оптимизировать и использовать

Я думал что такой функции может не существовать, уж слишком хорошей она должна была быть.

Свойства я легко сформулировал, написал интеграл и начал тестировать. Моя линейная функция возвращала на этих свойствах 2. А идеальная функция должна 0. Самое плохое что там было - тройной интеграл для самого важного свойства (поэтому для точности с 10 точками требовалось 1000 вычислений функции).

Библиотеку для построения гладких 2D функций я не нашёл, поэтому пришлось применять свои знания с МКЭ, и самому программировать вычисление функции по числам-точкам.

Для методов оптимизации (нахождения минимума функции) я взял argmin-rs. Советую квазиньютоновские методы.

Затем я совместил это всё с методами оптимизации и...

Оно работало очень долго. Для задания 2D функции я требовал слишком много параметров, и многие из них были избыточны, так что времени тратилась уйма.

Затем я понял, что нужна визуализация! А тут как раз Антон рассказал про встраиваемый Питон в Rust! Немного повоевав с ним, я смог вывести получающуюся функцию через matplotlib, и даже plt.show() работало!

⬇️

⬆️

Функция получалась... ужасная, она была очень шумной, не монотонной, явно переобучалась где-то. Ну и метрика кое-как доходила до 0.04. Я ставил оптимизацию функции на несколько часов, и безрезультатно, в итоге у меня получалась полная чушь, да к тому же вырожденная, получалась функция, которая стремится сохранить первое значение.

⬇️

⬆️

Я сильно расстроился.

Но на следующий день мне пришло в голову, что на самом деле мои "веса", которые я сделал давно, были очень даже подходящими! Они идеально подходили для отрезка от 0 до 1 и умножения 0.8 на 1.2, но были неудобны для отрезка от 1 до бесконечности. Тогда я решил просто сворачивать эту бесконечность до 1 путём деления. Тогда +20% превращалось в 1+1/(1-0.2)=2.25. И знаете что? Я получил идеальную функцию, которую хотел! Она идеально удовлетворяла всем свойствам и была очень даже гладкой. А ещё она симметричная: от -1 до 0 ведёт себя так же как от 0 до 1.

Эх, так просто. А я даже не верил что она существует.

Результат я опубликовал здесь: github:confidence, старался написать код очень красиво и безопасно. В итоге понял, float - это динамическая типизация на уровне процессора, и я хочу чтобы он был на алгебраических типах данных)))0)

Но это уже совсем другая история, и тема следующего поста... А то я здесь целый месяц не писал.

⬇️

⬆️

Вот она, моя идеальная функция ❤️

А покрутить её можно здесь:
https://www.desmos.com/calculator/nadaxdx40e

Вообще я очень люблю отрезок [-1, 1].

Год назад, когда я писал курсовую по МКЭ, мне нужно было провести исследование того насколько хорошо метод работает на неравномерных квадратных сетках, построить графики или таблицы.

⬇️

⬆️

Если вы не знаете что такое неравномерная сетка, то вот иллюстрация (которую я нарисовал кодом). Свойство этой сетки в том, что каждый следующий элемент больше другого в c раз, где c - какое-то положительное число от 0 до бесконечности.

⬇️

⬆️

Все обычно строили таблицы, где брали несколько неравномерных сеток и точности на ней, и делали какие-то выводы. А я грёбаный перфекционист, я заставлял компьютер трудиться не покладая транзисторов, и поэтому перебирал с очень маленьким шагом всё что можно, и строил графики через латех.

Сначала я, как и все задавал число c от 0 до бесконечности. Получается, чем ближе c к нулю, тем сгущённей сетка к правому краю, а чем ближе она к бесконечности, тем сгущённей к левому.

Но проводить исследования на чём-то до бесконечности не удобно, взгляните на этот график:

⬇️

⬆️

Где мне здесь остановиться? На 10^5? На 10^10? Делать экспоненциальное возрастание икса и логарифмическую шкалу? Непонятно. Тем более это очень неудобно логически воспринимать: несимметрично право и лево как-то получается.

⬇️

⬆️

Тогда я принял решение придумать такую функцию, которая позволяет задавать неравномерные сетки очень удобно, чтобы для значения коэффициента -1, сетка сгущалась к левому краю, а при значении коэффициента 1 сетка сгущалась к правому краю.

Придумал и описал в отчёте.

Кстати, именно по этой формуле я нарисовал иллюстрацию из предыдущего сообщения.

⬇️