А тут просто куча клеток разных времён как-то взаимодействуют...

⬇️

А это так правила записываны в коде))))))))))000)0 Конечно, эти массивы вычисляется. Вычислением просто занимается другой код.

⬇️

А это я проектировал правила на draw.io. Не пытайтесь понять, просто спойлер, в статье подробно расскажу об этом.

⬇️

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

Для предстоящей программки, где можно запускать обратимые клеточные автоматы я хочу сделать возможность задавать любые правила. Как я описывал в /239, любая перестановка массива от 0 до N является корректным правилом. Значит должна быть возможность задавать перестановку в виде чего-то, что можно скопипастить и вставить в программу.

На одном сайте с обратимыми автоматами перестановка задаётся так:

0,2,8,3,1,5,6,7,4,9,10,11,12,13,14,15

По мне это довольно скучно и не очень удобно.

Поэтому я придумал, что это надо отображать одним числом, которое можно менять на +1, -1, и оно будет корректным. А затем вообще переводить это число в систему счисления с основанием 64, чтобы оно было ещё короче.

Итак, для массива из N различных элементов существует N! возможных вариантов перестановки. Значит можно как-то пронумеровать каждую перестановку одним числом. И если сделать так, то пользователь сможет играться, меняя числа, у него всегда будет получаться корректное правило. Если он, конечно, не задаст число больше N!, но не допустить такую ошибку довольно легко.

Итак, перестановка, показанная вначале может быть записана числом как:

125023449600

Или если же это число перевести в 64-ричную систему счисления:

08D+rQ1

Я сделал маленькую библиотечку чтобы вычислять все эти вещи: permutation_string.

Всеми этими тремя способами в моей программе можно будет задавать правила.

Так же я хочу сделать GUI, чтобы правила можно было перетаскивать мышкой, и чтобы рядом писались все эти данные. Благо на megaui в macroquad сделать это довольно легко. Не знал кстати что Immediate Mode GUI такой простой о_О. Какой-то диссонанс происходит после того как ты делал гуй на всех этих коллбэках. Попробуйте почитать код, и потыкаться.

⬇️

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

Пусть у нас есть перестановка А из пяти элементов: [4,1,2,3,0]. Главное свойство любой перестановки - в ней все числа уникальны. Значит можно преобразовать этот массив в немного другой.

Пусть у нас ещё есть такой массив Б: [0,1,2,3,4].

Далее берём нашу перестановку, и говорим по какому индексу находится первый её элемент? 4 находится по индексу 4, так и записываем в массив Ц. Удаляем из массива Б и массива А число 4.

А = [1,2,3,0]. Б = [0,1,2,3]. Ц = [4].

Берём следующее число из А: 1. По какому индексу находится? 1. Так и записываем, удаляем из Б и А эти элементы.

А = [2,3,0]. Б = [0,2,3]. Ц = [4,1].

И теперь начинается самое интересное. Берём следующее число из А: 2. Оно находится по индексу 1. Так и записываем, и удаляем из А и Б.

А = [3,0]. Б = [0,3]. Ц = [4,1,1].

Ну и таким образом у нас в итоге получится: А = []. Б = []. Ц = [4,1,1,1,0].

Что интересного в массиве Ц? У него в каждом следующем элементе максимальное возможное число уменьшается на 1. То есть максимальный Ц = [4,3,2,1,0] возможен для перестановки: [4,3,2,1,0]. А Ц = [0,0,0,0,0] получается для перестановки [0,1,2,3,4].

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

0*0! + 1*1! + 1*2! + 1*3! + 4*4! = 105.

Получается это число находится в промежутке от 0 до N!-1. Вот так мы и пронумеровали каждую перестановку.

Кстати несложно модифицировать алгоритм, чтобы обрабатывать перестановки с повторяющимися элементами.

Последнее время Яндекс стал часто мне присылать письма о том как индексируется мой блог optozorax.github.io, и он оказывается по каким-то запросам даже есть в поиске, и на него раз в сто лет даже кто-то кликает! Это оказалось достаточно мотивирующим, чтобы я решился добавить на свой блог весь крутой контент, что лежит у меня на github.

Я сделал так, чтобы при помощи чёрной магии и git submodules в моём блоге публиковались посты, в которых находится содержимое файлов README.md из репозиториев, которые я указал.

Мой блог построен на Jekyll - дефолтном генераторе статических сайтов на GitHub Pages, поэтому я хакал именно его.

В итоге я смог этого добиться, но парой костылей. Я написал об этом пост в блоге: https://optozorax.github.io/submodules-jekyll

Кстати, там добавилось много статей, которые вам могут быть интересны, но вы их раньше никогда не видели, их можно посмотреть на главной странице: optozorax.github.io.

#мысли #вода_дарует_мысли

В Rust'е обработка ошибок хороша тем, что ты видишь в сигнатуре функции что возвращается Option<_>, Result<_, _>. За это его все любят, и за это же не любят концепцию исключений в языках типо C++. В расте ещё есть механизм под названием "паника" - это когда вся программа падает. Перехватывать панику - крайне плохой тон, потому что считается что это ошибка программирования, поэтому это никто не делает. Все перехватывают ошибки через Option/Result Поэтому все стараются писать код так, чтобы он не паниковал.

Но вот чтобы отслеживать какой метод паникует, необходимо читать доку. Например, метод remove на контейнере паникует, если данный элемент не найдётся. Кстати метода try_remove нету, и не очень хотят подобное что-то добавлять (подробности).

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

Поясняю: вот есть в Rust паникующие методы/функции. Хотелось бы их помечать их меткой аля panicking, и далее, если ты в своей функции используешь panicking функцию, то и свою функцию ты обязан пометить так же.

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

Ещё можно ввести метку nopure, которая ставится если ты модифицируешь какое-то глобальное состояние. Например, вызываешь print!().

Отличие этих всех меток от unsafe в расте в том, что unsafe можно отключить у метода. А эти метки должно быть нельзя отключить. Ну или можно отключить, но через unsafe {}.

Что дадут все эти метки? Ну во-первых, код с метками panicking, allocating, nopure будет считаться либо плохим, либо неподходящим для использования в библиотеках, и все будут стараться делать библиотеки с не-паникующими не-аллоцирующими чистыми методами. Это будет означать что такие методы вероятно очень быстрые и что они очень надёжные.

Например, если переписывать ядро Линукса на расте, то там определённо никто не хочет чтобы метод паниковал (наверное).

Я понимаю, что с точки зрения синтаксиса это будет очень запарно писать. Но такова цена. Типизацию тоже надо везде прописывать)

Может быть это можно будет использовать в библиотеках, вводя свои метки, упрощающие понимание/написание кода.

Хочу трейт коллекции (а для него надо 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.

⬇️

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