Хочу трейт коллекции (а для него надо Generic Associated Types 😭), чтобы можно было в стандартную библиотеку добавить:

impl<K, V, C: Collection<V>> FromIterator<(K, V)> for BTreeMap<K, C> 

Чтобы я мог собирать итератор из пар в:

.collect::<BTreeMap<_, Vec<_>>>()

Без трейта коллекции можно написать что-то такое:

impl<K, V, C: FromIterator<V>> FromIterator<(K, V)> for BTreeMap<K, C> 

Но мне кажется такое невозможно написать, либо оно будет слишком unsafe, либо будет оверюзать умные указатели типо RefCell.

Отказ от телеги.

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

Подобное я практиковал ещё давно. Пожалуй мой самый радикальный, и самый первый опыт подобного случился в 11 классе. Перед 11 классом я напрокрастинировал всё лето, хотя на это лето у меня были планы по написанию одного проекта. Я понял, что всё своё время я трачу куда-то в интернет, не только в один вконтакт или ютуб. Поэтому на сентябрь 11 класса я принял радикальное решение - отказаться от интернета на месяц. Это было тяжело. Мне пришлось скачать кучу документации на комп заранее. Скачать музыку заранее. По вечерам я ощущал вакуум. Но уже в первые дни я заметил, что оказывается за 2 часа свободного времени можно сделать очень много, и мне это понравилось. После того опыта я не стал снова отрубать интернет на месяц, а уже пользовался интернетом далее, но благодаря таким радикальным действиям я смог научить себя тратить на него меньше времени.

Затем уже в университете я заметил, что очень много времени смотрю ютуб. Поэтому я внёс ютуб в файл hosts, и по сути заблокировал его на компьютере, и разрешал себе смотреть его только через телефон. А через телефон мне дико неудобно смотреть, поэтому получилось хорошо. Таким макаром я держал ютуб заблокированным на компьютере около 2 лет, и уже после возвращения ютуба на компьютер, я не трачу на него столько времени.

Тоже самое было с вконтакте, но там всё обошлось тем что я отписался от всех групп и в приложении Kate Mobile настроил так, чтобы при включении приложения открывалась страница с сообщениями, а не новостями, и вообще кнопки "новости" не было.

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

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

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

После двух недель, я не знаю что и сказать. Это круто. Для меня уже стало естественно, что у меня оказывается есть так много времени, и что я больше успеваю, и больше делаю. Я перестал отвлекаться, и каждые 10-30 минут чекать что там в каких чатах написали. Соответственно повысилась концентрация.

⬇️

Немного иронично, что в этот период отказа от телеги, Павел Дуров пишет пост: медуза, оригинал; где говорит что злые корпорации хотят чтобы мы потребляли как можно больше.

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

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

И видимо поэтому мне не стоит устанавливать тикток.

Кстати, глобально по этой теме рекомендую книгу "Пустышка. Что интернет делает с нашими мозгами.".

А ещё я смотрел стримы великого гроссмейстера neal_wu, где он за полтора часа решает то, на решение чего у меня уйдёт 7+ часов, и у него есть такая штука, которая позволяет очень быстро прогонять тесты по его задачке на основе *.in и *.out файлов, которые он создаст. Соответственно я захотел тоже себе такую фигню, но для раста. И сделал такую программку olytest. В ней я храню все тесты в двух файлах: in.txt, out.txt, и разделяю их символом \, чтобы не создавать кучу файлов для каждого теста.

В ней особо ничего интересного нету, разве что когда я её делал, параллельно запилил макрос для работы с библиотекой termcolor, которая позволяет рисовать цвета в консоль кросс-платформенно, для винды и для линукса. Макрос хранится тут: termcolor_macro, и его использование выглядит следующим образом: .

clrln!(stdout: b u (Color::Black)[Color::White] "Error:"; " cannot find file {}", filename);

Здесь текст "Error:" выведется жирным (буква b), подчёркнутым (буква u), чёрным цветом (круглые скобки) на белом фоне (квадратные скобки), а после него будет обычный println! без форматирования и цветов, с одним аргументом. Кстати на этом макросе очень хорошо можно увидеть что macro_rules у растишки довольно юзабельный, ибо я такой сложный макрос написал довольно легко.

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

⬇️

Олимпиадное программирование.

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

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

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

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

Затем я посмотрел сериал "Ход королевы", суть которого я к сожалению не буду рассказывать, ибо не люблю спойлерить, советую просто посмотреть.

Затем ещё у нас в университете проходила олимпиада, на которую я решил не идти, ведь там мне придётся прогать на C++, а я такой вот вредный растоман, и вообще на Раст я решил окончательно уйти из-за олимпиады в Барнауле, где я хотел написать что-то на плюсах, и это было дико неудобно, а на расте ведь есть итераторы. И вот я решил не идти на олимпиаду, а меня туда позвал преподаватель, с которым я хорошо знаком. И стало как-то неловко.

Ну и плюс в это время я отказался от телеги и у меня появилось свободное время.

А ещё какой-то чувак усомнил мою веру в себя, сказав что "мне надо больше читать, чем писать".

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

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

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

⬇️

И вот недавно, 4 декабря, прошёл ещё один контест на этом сайте, и мне очень понравилось как он прошёл. Я быстро решил задачу А, а потом прочитал задачу Б и офигел от её сложности и моего непонимания как решать... Я подумал сдаться, но потом сказал себе что нельзя, взял бумажку и карандаш, и начал крутить эту задачу и так и эдак, в итоге математически вывел что оказывается там что-то независимо, и полностью понял как её решить. Затем уже быстро запрограммировал и она прошла. Затем я пытался решить задачу Ц, но во время олимпиады не смог, ибо неправильно прочитал условие. Меня вдохновило что я осилил задачу Б (хотя она была второй по лёгкости), и я решил после контеста решать дальше. В итоге я смог полностью своим умом добить задачу Ц. Затем снова при помощи бумажки обнаружил решение задачи Д. Затем подумал что понял как решать задачу Е, запрограммировал и она не прошла, затем взялся за бумажку, и её тоже добил. И вот я дошёл до задачи Ф. Это последняя и самая сложная задача, у которой в тэгах написано страшное словосочетание: "динамическое программирование". Я начал её крутить, исследовать, а затем понял что уже 5 утра, и надо бы спать.

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

В этот момент я почувствовал себя Бет Хармон из сериала "Ход королевы" 😂

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

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

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

⬇️

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

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

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

Так же я придумал ещё один метод над Option: any_or_both_with, при помощи которого можно считать минимум или максимум засунутых в Option величин (надо бы в далёком и прекрасном будущем создать на это MR как сделал вафель >_<).

Так же мне нравится политика codeforces в том, что я могу использовать заранее написанный код, поэтому я собираю коллекцию полезных штук для олимпиадок, отлаживаю их и покрываю тестами: olymp/templates.

⬇️

Вот я вернулся, и тупая телега расположила посты в неправильном порядке -_- Сорян.

В свободное время я продолжаю развивать olytest - прогу для быстрого тестирования программ во время олимпиадного программирования.

Последние фичи:
1. Возможность тестировать конкретный экзешник - a, b, e1. Раньше тестирование запускалось только из main.rs файла, и прошлый код приходилось стирать.
2. Появились CLI команды для генерации и удаления кода экзешников.

Следующие фичи будут обозначаться отдельно, потому что я хочу их прокомментировать.

Фича #3: Автоматический парсинг страницы на codeforces, извлечение имён всех задач и тестов с входными и выхоными данными.

Я парсю html через соответствующие библиотеки, и обращаюсь к результату через селекторы, например все входные данные описываются так: "div.input pre". Что удивительно, для растишки все такие библиотеки есть, и подключаются в два клика.

Фича #4: Возможность указывать в тесте чекер (который ты напишешь как обычный экзешник), который будет интерактивно общаться с программой, и проверять её результат.

А вот это уже интересно. Чтобы понимать что такое интерактивное общение, можете прочитать условия этой задачи: https://codeforces.com/contest/1451/problem/E2. Очевидно, что такую задачу тестировать довольно нетривиально. Нужно написать две программы: одна решает саму задачу, другая осуществляет интерактивное общение для заданного массива.

То есть, у нас есть программы А и Б. А решает задачу, а Б общается с А, предоставляя ей информацию на вход. Что есть тест? Например, у нас есть массив 0 0 2 3. Как нам протестировать что программа А способна получить этот массив? Можно подать его на вход Б, Б выведет нужную информацию и далее будет общаться с А.

Значит, изначально, тест мы записываем в stdin Б, затем stdout от Б мы направляем на stdin А, а stdout от A направляем на stdin Б. А как можно после этого узнать правильный ли выдала ответ программа А или нет? Б может записывать вердикт в свой stderr.

И существует два вида тестов:
* Обычный тест: вход теста подаётся на stdin программы, а выход теста сравнивается с stdout программы.
* Тест с чекером: вход теста подаётся чекеру на вход, а выход теста сравнивается с stderr чекера.

Что интерено, такой схемой можно описать любой из вариантов тестирования олимпиадной задачи:
* Когда ответов существует множество, и ответ нужно проверять какой-то программой.
* Когда нужно сгенерировать большой тест для тестирования программы на скорость.
* Ну и конечно, интерактивное общение как в той задаче.

Например, если у нас задача подразумевает простые тесты, то встаёт вопрос, а как быть когда у нас выход теста сравнивается от чекера, а не от программы? Можно просто написать в чекере, чтобы он весь stdout программы транслировал в свой stderr.

А теперь самое интересно, как это запрограммировать? Окей, создаём два процесса через std::process::Command, берём их входы и выходы, и пытаемся читать и писать через read-write. И сталкиваемся с проблемой, что ввод в расте по умолчанию блокирующий. Это означает, что если прямщас байтов нету, то вызов read будет ждать пока программа не выведет данные.

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

Это приводит к тому, что нужно использовать неблокирующий ввод-вывод. А как я понял, официально, и кросс-платформенно он существует только в виде машинерии async/await, и, например, в tokio.

⬇️

Я про async/await не знал абсолютно ничего, и очень тяжело было прийти к первому рабочему прототипу. Я всё же хотел сделать всё очень императивно, найти такой метод, который мне мог бы чётко сказать: ПРЯМ_ЩАС_БАЙТОВ_НЕТУ. Такой метод правда есть, и он называется poll_read, но он какой-то очень сложный, ему нужен какой-то контекст, какой-то waker, а я не знаю откуда всё это взять. Поэтому пришлось извращаться как есть, и несложными измышлениями, и поверхностным чтением документации я пришёл к тому, что нужно использовать макрос select!{}, который из нескольких футур выбирает ту, которая завершится первой.

У нас может быть две главные футуры:
* Чтение stdout чекера
* Чтение stdout программы

После того как мы прочитали хоть сколько-нибудь информации из каждого источника, мы можем сразу записывать в stdin другого. Так что макрос select!{} вполне подходит, но он мне как-то не нравится, ибо с ним надо было иметь для каждого читателя по отдельному буферу, и я хотел прийти всё же к ПРЯМ_ЩАС_БАЙТОВ_НЕТУ.

Затем благодаря помощи Вафеля обнаружился метод futures::poll_fn, который позволяет вызывать сложнющий poll_read без ручного создания всяких контекстов итд. Я как увидел этот метод, сразу понял, что мне нужен был именно он, и недоумевал, почему такой прекрасный метод не суют во все туториалы и вводные по async/await'у в расте.

В итоге я пришёл к такому коду: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=163960a0f7031364984e2099c0a4de66 .

Он вроде работал, и всё было хорошо, но затем я заметил, что когда один из процессов начинает паниковать и выводить кучу инфы в stderr, которая не умещается в буфер, у меня переставало работать считывание. Тупо зависало. Когда я пытался локализовать в каком месте оно зависало, и писал макрос dbg!(), ОНО НЕ ЗАВИСАЛО. Когда я пытался сделать работу помедленней, и ставил sleep(100ms), ОНО НЕ ЗАВИСАЛО. Я погрешил на async/await, что из-за своей сложности они создают какие-то квантовые эффекты, измерение которых приводит к их исчезновению.

Но затем мне всё же удалось найти место, куда можно поставить dbg!() без исчезновения квантовых эффектов, но это ничего не дало. Затем я нарушил своё отстранение от телеги и зашёл в async-чатик и задал там свой вопрос (и сейчас понял что там в коде неправильная ссылка): https://xn--r1a.website/rust_async/29266 (можно не читать). Мне никто не отвечал, поэтому я продолжил решать проблему самостоятельно. И как это обычно у меня бывает, благодаря тому что для чатика я очень хорошо сформулировал вопрос, я начал понимать свою проблему лучше, и потом размышлениями пришёл к такому:

В моём методе poll_read вызывается внутри цикла постоянно и через очень короткие промежутки времени. Когда я ставил задержку или dbg!(), эти промежутки времени увеличивались. А у async/await есть такая штука как waker, и по идее poll_методы нужно вызывать только после того как твоего waker'а ткнут носом что всё закончилось. А я их вызывал в цикле. И видимо, на внутреннюю машинерию асинхронного кода и регистрацию этих waker'ов тратилось время больше, чем мои промежутки времени в цикле, поэтому у меня "неблокирующее" чтение никак не могло выдать результат, который бы отличался от Pending.

В общем я осознал свою ошибку и вернулся на select!{}. И как я потом замерил, select!{} использует минимальное число обращений к чтению, потому что блокируется на всех футурах, если они все не дают результат прямщас. А это значит, что он и эффективней.

⬇️

Фича #5: Модифицировал синтаксис тестов. Теперь он хранится в одном файле, поддерживает экранирование, поддерживает задание чекера, и состоит всего из трёх символов.

Более подробно:
* Вход и выход теста теперь находится в одном файле по совету Сергея Совы.
* Разные тесты разделяются символом \.
* Вход и выход разделяются либо символом ~, либо символом %. Первый символ пишется в случае обычного теста, а второй в случае наличия чекера. Если нужно, чтобы тест не сравнивался с чем-то, а его результат просто вывелся на экран, то выход может быть просто набором пробельных символов.
* Так же я сделал токенизацию выхода программы и теста, чтобы лишние пробелы и лишние пустые строки не влияли на результат, и чтобы легко было сравнивать.
* Экранировать один из трёх управляющих символов можно тупо написав его два раза.

Для синтаксиса тестов я старался выбирать символы, которые практически никогда не встречаются в тестах олимпиадных задачек, но иногда всё же могут встретиться, и экранировать их - важно. Я часто замечаю, что экранированию синтаксиса уделяется мало внимания при проектировании языка описания чего-то. Для меня растовские строки с r#"text"# стали откровением в области экранирования, ведь это гениально, сделать хэши, чтобы можно было без проблем писать кавычки. Жаль что эти строки являются raw, и внутри них нельзя писать \n чтобы обознчаить перенос строки. Я бы хотел обычную строку, но с хэшами: #" "hi" - says\nsimon "#.

Далее в olytest у меня осталось три жирных пункта:
* Добавить возможность писать в олимпиадной программе include!(), чтобы вместо этого подставлялся нужный текст, и генерировался в отдельный файл, чтобы вручную не копипастить.
* Добавить поддержку ЯП: C++ и Python/PyPy. Это самые частые языки для олимпиадного программирования.
* Написать доку на английском и русском.

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

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

⬇️

Тестирование всех экзешников.

⬇️

Тестирование той самой задачи с использованием чекера.

⬇️

Так же происходит замер времени, если указать флаг -t.

С НГ! Желаю в этом году чтобы произошёл качественный переход, после которого от тебя все отстанут и будут меньше трепать нервы и отнимать время

В копилочку о том почему шкалам оценки нужно переосмысление, которое я описывал в этом посте.

How gamers see review scores now.