All streams
Search
Write a publication
Pull to refresh
338
0.7
Валерий Черепенников @vvvphoenix

Vice President NNRC, Советник Губернатора НО

Send message

Вглядываясь в бездну.

Чем дольше живу, тем сильнее поражаюсь способности людей «заплетать» свои собственные мозги. И, кажется, программисты в этой области вне конкуренции.
Уже писал некоторое время назад, как я завел цикл внутри цикла с тем же именем счетчика.
Это было пару часов отчаяния, сопровождавшегося размышлениями о том, что фундаментальные законы мира внезапно изменились, а меня забыли поставить об этом в известность.
Недавно я повторил этот трюк, правда с некоторыми занятными модификациями. Был у меня в проге цикл по объектам в списке. Там смысл в том, что при некотором условии новый объект добавлялся в конец этого самого списка. Все бы ничего, но в этот момент счетчик объектов инкрементировался. А он то как раз и служил верхней границей цикла… В общем, как легко понять, дело кончилось segmentation fault… Но эту бажину (хотя она даже более заморочная на мой вкус) , я нашел относительно быстро, не успев погрузиться в бездну отчаяния. Кода было немного, поэтому обошлось без смен компилятора и переустановок IDE… В этот раз, можно сказать, повезло. И бездна отчаяния меня миновала. Но тот, кто ищет проблем, обязательно их находит. И что самое удивительное, что я их нахожу всегда в одном месте.
Я в-общем то хорошо знаю, что люди еще не придумали ничего хуже конечных автоматов (state machines). И вот уже 35 лет регулярно наступаю на одни и те же грабли… В этот раз мне всего-навсего нужен был один флаг. В задаче Винтика и Шпунтика используется нетривиальный алгоритм, многократно использующий рекурсию. Ну и мне нужен был этот флаг, как индикатор того, что некое событие произошло. А когда происходило другое событие, этот флаг сбрасывался. Стандартная, в-общем, ситуация, но внутренний голос немедленно поднял «красный флаг опасности» и зашептал в голове «Нахлебаешься, Валер, ой, нахлебаешься...» И вот тут бы мне остановиться и подумать, но я, как обычно, решил, что сейчас сделаю, а подумаю потом…
Все дело в том, что эти флажки (или состояния конечного автомата) имеют дурное свойство размножаться, куда быстрее чем кролики. За первым флажком немедленно последовал второй — ну просто для того, чтобы обозначить функцию, которая первый флаг установила. А потом третий, чтобы обозначить функцию, которая его сбросила… И мне уже казалось, что вот они разверзающиеся врата ада, но, конечно же, это было еще не так.
Ибо настоящий ад наступил, когда программа стала многопоточной. И это еще при том, что у меня есть хорошая привычка обкладывать модификацию всех этих флажков критическими секциями. Даже если не надо. Всегда легче потом убрать и удивиться тому, что все работает, чем сутками докапываться, почему нет. Это уберегло меня от многих проблем, но не уберегло от главной. Сейчас этих флажков в программе 12. И они живут своей собственной жизнью. Я уже не в состоянии отследить кто, где, когда и зачем их модифицирует. Начал думать о том, что надо бы ввести для каждого флажка некую структуру, которая будет содержать ответы на эти вопросы. Но тут уже внутренний голос встал на дыбы, и, как ни странно, в этот раз я его послушал.
Вот сижу теперь и думаю над романом (или длинным рассказом) о программисте, который взялся за непосильной сложности алгоритм и постепенно сходит с ума. Хуже того, что он это сам понимает, и ему становится страшно. Но поскольку он программист, то свой мозг он считает конечным автоматом, и пытается его «отлаживать». Таким образом запускается бесконечная цепь рекурсий. И периодически ему приходит в голову мысль, что надо все бросить и написать заново. Но он боится потому что давно уже потерялся и не знает на каком уровне рекурсии он находится… Такой вот юмористический (а может и не юмористический) хоррор с элементами мистики. И легким флером безнадеги из набоковской «Защиты Лужина».
Ну вот. Написал пост. Немного отвлекся. Пойду дальше код дебажить…😁

Tags:
+11
Comments3

Винтик, Шпунтик, включения и исключения.

Некоторое время назад я опубликовал задачу, в которой требовалось посчитать число раскрасок грани кубика Рубика в 3 цвета определенным способом. К этой задаче сводится тернарный кейс Винтика и Шпунтика. Напомню,

у нас есть грань размера 3x3 и нам надо покрасить 9 ячеек в три цвета. 3 - в красный, 3 - в желтый, и 3 - в зеленый. Сколько существует раскрасок при которых ни одна строка и ни один столбец не закрашены одним цветом?

Картинка ниже дает примеры возможных и невозможных раскрасок

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

  1. Шаг 0. Знак +. Полное число раскрасок 9 ячеек в три цвета.

    C_0 =+C(9,3,3,3) = +\frac{9!}{3!3!3!}=+1680

  2. Шаг 1. Знак -. Число раскрасок, при которых одна строка или один столбец закрашен одним цветом. Строки и столбы у нас "равноправны". Таким образом, мы получаем множитель 2, исходя из геометрии (а точнее просто размерности) задачи. Теперь, допустим, мы закрашиваем одну строчку(столбец) каким то одним цветом (допустим красным). Выбор цвета(1 из 3) дает нам С(3,1)=3 варианта. Выбор позиции дает еще 3 варианта. Запишем это как n!/(n-k)! Теперь нам нужно покрасить еще 6 (n(n-1)) ячеек в два цвета (желтый и зеленый). Что дает С(6,3) =  6!/(3!3!)В итоге,

    C_1 =-2*C(3,1)*3!/(3-1)!* C(6,3) = -2*3*3*\frac{6!}{3!3!}=-360

  3. Шаг 3. Знак +. Когда у нас одновременно есть две строки или два столбца закрашенные одним цветом. Аналогично, 2- множитель размерности. Теперь нам надо выбрать 2 из 3 трех цветов. Получим, С(3,2) =3. Геометрическое размещение дает множитель 3!/(3-2)!. Ну и далее нам останется закрасить оставшиеся три ячейки оставшимся цветом. Что дает нам ровно С(3,3) = 1 вариант. Получаем,

    C_2 =+2*C(3,2)*3!/(3-2)!*C(3,3) = +2*3*6*1=+36

  4. Шаг 4. Знак -. Все три столбца или строки закрашены одним цветом. 2 - геометрический множитель. С(3,3) = 1 - выбор цветов. 3!/(3-3)! = 6 количество размещений. Итак,

    C_3 =-2*n! = -2*3!=-12

    А теперь соберем все вместе и получим.

    C = \frac{(n^2)!}{(n!)^n} +2*\sum_{k=1}^n(-1)^kC(n,k)\frac{n!}{(n-k)!}\frac{(n(n-k))!}{(n!)^{n-k}} (*)

Или для нашего случая n = 3

C = C_0+C_1+C_2+C_3=1680-360+36-12 = 1344

И это правильный ответ. При домножении на 2^3 =8дает 10752 - решение задачи Винтика и Шпунтика в тернарном случае.

Формулу (*) наверняка можно как то упрощать, но я не буду сейчас этим заниматься. Скажу лишь, что она работает для любых n. В частности, если нам нужно посчитать раскраски квадрата 4x4 в 4 цвета формула* дает.

C = C_0+C_1+C_2+C_3+C_4=63063000-1108800+10080-192+48=61964136

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

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

Tags:
Total votes 14: ↑14 and ↓0+19
Comments1

Подводя промежуточные итоги

Ареопаг челленджа имени Винтика и Шпунтика в лице @qbertych и вашего покорного, посовещавшись, принял решение выплатить @ripatti половину призового фонда конкурса (25000р). Артем опубликовал две замечательные статьи:

Винтик и Шпунтик, часть 1: формула включений-исключений

Винтик и Шпунтик, часть 2: гиперкубы, шляпы и фартуки

Он не только расширил постановку задачи, но и сумел ближе всех подобраться к решению кватернарного случая. Однако, само решение до сих пор неизвестно, и челлендж продолжается. На кону вторая половина призового фонда (еще 25 штук). Каждый может попробовать свои силы.

Tags:
Total votes 11: ↑11 and ↓0+16
Comments0

Винтик, Шпунтик и Кубик Рубика

Я давно подозревал, что между задачей про Винтика и Шпунтика и кубиком Рубика есть определенная связь. И вот только сейчас придумал простую аналогию. Представьте, что у нас есть грань размера 3x3 и нам надо покрасить 9 ячеек в три цвета. 3 - в красный, 3 - в желтый, и 3 - в зеленый. Сколько существует раскрасок при которых ни одна строка и ни один столбец не закрашены одним цветом?

Картинка ниже дает примеры возможных и невозможных раскрасок

У задачки есть три уровня сложности

  1. Написать код, который считает число возможных раскрасок.

  2. Посчитать то же самое число аналитически (то есть "на бумажке"🧐)

  3. Очевидно, что задача обладает некоторым набором симметрий. Иными словами перестановка строк (эта группа изоморфна S3) переводит решение в решение. То же самое с перестановкой столбцов (тоже S3). Также "перекрашивание" (красные в желтые, желтые в зеленые и тп) дает еще одно S3. Ну и наконец транспонирование матрицы или поворот на 900 (2700) также переводит решение в решение. Вопрос "со звездочкой" - сколько существует орбит решений относительно действия этой группы?

    Маленькая подсказка - можно воспользоваться теоремой Редфилда-Пойа. Но окончательного ответа я с ее помощью получить не смог...😒

Tags:
Total votes 7: ↑7 and ↓0+12
Comments0

Information

Rating
1,856-th
Location
Нижний Новгород, Нижегородская обл., Россия
Works in
Date of birth
Registered
Activity