Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.

Про инфракрасную фотографию на Хабре уже писали (например, здесь и здесь). Напомню, что диапазон видимого света — от 0.4 до 0.7 мкм, инфракрасный диапазон начинается с 0.7 мкм и продолжается до миллиметровых волн. Обычная цифровая камера (даже с удалённым ИК-поглощающим фильтром) работает, в лучшем случае, до длины волны 1.05 микрона. Диапазон работы тепловизоров (тоже ИК-камеры) гораздо дальше — примерно 7-14 мкм. А что между ними?

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

В 2011-2013 гг. австралийский писатель Грег Иган (Greg Egan) опубликовал трилогию Orthogonal (The Clockwork Rocket, The Ethernal Flame, The Arrows of Time). В книгах описан удивительный мир, в котором нет жидкостей и электрических зарядов, обитают четырёхглазые разумные существа, способные менять форму и размножающиеся делением, использующие воздух не для химических реакций, а для охлаждения своего тела, а свет — для передачи нервных импульсов. Скорость света в этом мире непостоянна: фиолетовые фотоны движутся заметно быстрее красных. Поэтому звёзды выглядят не как белые точки, а как радужные полоски

Прочитав статью про семь соприкасающихся цилиндров, я задумался: действительно ли эта задача такая сложная? Или ей просто раньше никто всерьёз не занимался?
Положение бесконечного цилиндра известного радиуса в пространстве задаётся четырьмя независимыми величинами (имеет 4 степени свободы). Для семи цилиндров в общем положении потребуется 28 величин. Каждое условие «два цилиндра касаются» даёт одно ограничение, всего остаётся 7 степеней свободы. Шесть из них — перемещения пространства, последнее остаётся на саму конфигурацию. То есть, у нас должно получиться одно или несколько однопараметрических семейств конфигураций, если только не помешает топология (из-за которой решений может не оказаться вообще).
Вместо цилиндров нам удобнее работать с прямыми. Если диаметры двух цилиндров одинаковы и равны, допустим, единице, то они касаются (внешним образом) тогда и только тогда, когда расстояние между их осями равно единице. Учтём этот факт, и пойдём искать семь красных перпендикулярных прямых...

Если вам понадобится алгоритм сортировки массива, который:

• Работал бы гарантированно за O(N*log(N)) операций (обменов и сравнений);
• Требовал бы O(1) дополнительной памяти;
• Был бы устойчивым (то есть, не менял порядок элементов с одинаковыми ключами)

то вам, скорее всего, предложат ограничиться любыми двумя из этих трёх пунктов. И, в зависимости от вашего выбора, вы получите, например, либо сортировку слиянием (требует O(N) дополнительной памяти), либо пирамидальную сортировку (неустойчив), либо сортировку пузырьком (работает за O(N²)). Если вы ослабите требование на память до O(log(N)) («на рекурсию»), то для вас найдётся алгоритм со сложностью O(N*(log(N)²) — довольно малоизвестный, хотя именно его версия используется в реализации метода std::stable_sort().

На вопрос, можно ли добиться выполнения одновременно всех трёх условий, большинство скажет «вряд ли». Википедия о таких алгоритмах не знает. Среди программистов ходят слухи, что вроде бы, что-то такое существует. Некоторые говорят, что есть «устойчивая быстрая сортировка» — но у той реализации, которую я видел, сложность была всё те же O(N*(log(N)²) (по таймеру). И только в одном обсуждении на StackOverflow дали ссылку на статью B-C. Huang и M. A. Langston, Fast Stable Merging and Sorting in Constant Extra Space (1989-1992), в которой описан алгоритм со всеми тремя свойствами.

Раз уж неделя «Морского боя» на Хабре продолжается, добавлю и я свои два цента.
При попытке найти оптимальную стратегию для игры за компьютер довольно быстро приходим к такому приближению:

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

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


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

На первый взгляд, задача кажется неподъёмной. Число конфигураций представляется порядка 10²⁰ (на самом деле их несколько меньше — ближе к 10¹⁵), так что на полный перебор времени уйдёт слишком много. Перебирать раскраски поля и оставлять только допустимые — не лучше: всё равно нам каждую комбинацию придётся просмотреть.

Что же ещё попробовать? Любой олимпиадник тут же ответит — динамическое программирование. Но как его организовать?

Язык 4DL был изобретён в 2001 г. автором Cliff L. Biffle. Как он сам объяснил, придумал он его во-первых, потому, что до этого языков с четырехмерными программами не существовало, а во-вторых, потому что четырёхмерное пространство довольно сложно для понимания, и надо же дать людям возможность потренировать мозги.

Русская Википедия относит этот язык к семейству «фунгеоидных». Это языки, ведущие свой род от языка Befunge, программы в котором записываются в виде символов на прямоугольной решётке и могут выполняться в произвольном направлении. В 4DL для представления программы используется четырёхмерная решётка, и направлений её выполнения, соответственно, 8.

Программа на 4DL может выглядеть, например, вот так:

 X  ,  B  /  \  B  +  2  B  -  <  ?  T  B  -  T
 y  __ 10 __ __ 7  __ __ A  __ __ __ __ 07 __ __ 
------------------------------------------------------------------
 __ Y  __ __ __ __ __ __ __ __ .  __ x  __ __ x  ||  __ __ __ __ __ __ __ __ __ __ 20 __ __ __ __ __
 t  X  __ __ __ q  +  2  q  -  <  ?  Z  q  -  Z  ||  z  __ __ __ __ __ __ __ __ .  b  .  x  __ __ x

Эта программа написана не на «базовом» языке, а на его расширении, но об этом позже.

Различные реализации игры «Жизнь» описывались на Хабре уже неоднократно. В этой статье, в качестве продолжения этой темы, рассматривается ещё один её вариант: в качестве игрового поля используется регулярная решётка на плоскости Лобаческого. Описываются общие методы использования плоскости Лобачевского в программах и необходимые для этого математические приёмы.
Как возникла плоскость Лобачевского, достаточно известно. В позапрошлом веке господа Гаусс, Лобачевский и Бойяи, проживавшие примерно в одно время в разных странах тогдашней Европы, задумались, что будет, если отменить пятый постулат Евклида и заменить его на противоположную аксиому. Оказалось, что не случится ничего плохого, и никаких противоречий не возникнет. Заметная часть последующего изучения неевклидовой геометрии была посвящена выяснению того, кто из них у кого украл идею этой самой геометрии.
Менее известно, что несмотря на «отрицательный» способ определения неевклидовой геометрии (вместо того, чтобы сказать, что через точку проходит ровно одна прямая, не пересекающая данную, мы говорим, что таких прямых может быть сколько угодно), мы, тем не менее, получаем систему теорем и формул, не менее стройную, чем та, что есть в евклидовой геометрии. И одновременно, у нас есть гораздо большее разнообразие геометрических фигур, в том числе, разбиений плоскости на правильные многоугольники.

Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным O(N*log(N)), невозможно. Поэтому, когда karlicos поделился ссылкой на описание такого алгоритма, меня это заинтересовало. Поиск по сети показал, что про алгоритм люди знают, но никто им особо не интересуется, его считают сложным и малоэффективным. Хотя, может быть, они имеют в виду какую-то «стабильную» версию этого алгоритма, но нестабильная при этом все равно никому не нужна.

Но я все-таки решил попробовать.

В очередной раз мне попалась задача – найти в облаке точек место их наибольшего сгущения. На этот раз ситуация была такой:

• есть некоторое количество (можно считать, что не более 16 миллионов) измерений набора параметров. Число параметров в наборе – от 2 до 5.
• измерение параметров может быть относительно успешным – тогда их результат будет неподалеку от истинного (параметры и тип распределения неизвестны), либо не успешным – тогда результат будет случайным (опять-таки с неизвестными параметрами распределения). Определить по одиночному измерению, было ли оно успешным, нельзя.
• Можно считать, что точка сгущения существует. Если их несколько с близким качеством (которое формально так и не определяется), можно выдать любую.
• ответ нужно дать за один проход по исходным данным: перевычислять их или сохранять целиком – дорого.
• И, как обычно, хочется, чтобы алгоритм выглядел попроще, а работал побыстрее.

У меня возникла такая задача: нужно обработать файл с данными. Файл разбит на секции длиной около 1 МБ, каждая из них содержит в упакованном виде примерно 100000 записей.Число записей может меняться от секции к секции и записано в заголовке каждой из них. В процессе обработки секция распаковывается, и каждая запись превращается в 20 целых чисел. Для обработки нужно хранить текущую распакованную секцию и несколько предыдущих (где-то 5-10, но может быть и больше – заранее неизвестно, сколько). Вопрос в том, как выделять память для распаковки секций.

Проект, в рамках которого надо решить задачу, пишется на C# под VS 2008 (использование вставок из других языков категорически не приветствуется), основная система, под которой будет работать готовая программа – Windows 7, 64 bit (по крайней мере, пока). И, как обычно, обрабатывать нужно побыстрее.
Первый вопрос, который возникает – надо ли организовывать пул массивов для распаковки, или можно захватывать массив для каждой новой секции заново. Второй вопрос – какой должна быть структура этого массива, что лучше – работать с линейными массивами в 8 МБ длиной, или разбить массив на куски поменьше и организовать, например, массив массивов. Во втором случае – какой должна быть длина этих кусков.

В первой части публикации я рассказывал про поиски планеров в 3-мерной игре «Жизнь» (с 26 соседями у клетки). Там было несколько примеров того, что удалось найти. Но оказалось, что правил с планерами несколько больше, чем я ожидал вначале. Хотя и ненамного…

Программа, которая искала планеры, выдала довольно много «подозрительных» стартовых конфигураций. Но планеры были далеко не во всех. Во многих случаях возмутителями спокойствия оказывались пульсары – периодические конструкции с периодами, не являющимися делителями 60.

Чаще всего, период таких пульсаров равнялся 8:

Правило B5/S2,3:

После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «Hashlife». Он несколькими фразами описан в Википедии, и приведенной там картинки с комментарием («конфигурация через 6 октиллионов поколений») для меня было достаточно, чтобы держаться от этой идеи подальше: сколько же ресурсов нужно этому алгоритму? Стоит ли за него браться вообще?

Общая идея алгоритма такая.

Допустим, что у нас есть квадрат поля размером N*N (N>=4 – степень двойки). Тогда мы можем однозначно определить состояние его центральной области размером (N/2)*(N/2) через T=N/4 шага. Если мы запомним состояние исходного квадрата и результат его эволюции в словаре, то сможем в следующий раз, встретив такой квадрат, сразу определить, что с ним станет.

Предположим, что для квадратов N*N эволюцию на N/4 шага мы считать умеем. Пусть у нас есть квадрат 2N*2N. Чтобы просчитать его развитие на N/2 шагов, можно сделать следующее.

Разобьем квадрат на 16 квадратиков со стороной N/2. Составим из них 9 квадратов со стороной N, для каждого из них найдем результат эволюции на N/4 шага. Получится 9 квадратов со стороной N/2. В свою очередь, из них составим уже 4 квадрата со стороной N, и для каждого из них найдем результат эволюции на N/4 шага. Полученные 4 квадрата со стороной N/2 объединим в квадрат со стороной N – он и будет ответом.

Многим известна игра «Жизнь», изобретенная Дж.Конвеем еще в 1970 г. Еще шире известен один из объектов этой игры – планер (или глайдер) – движуееся образование из 5 клеток:

.

В 1987 г. Были найдены первые планеры в трехмерных версиях «жизни» ( www.complex-systems.com/pdf/16-4-7.pdf ). К сожалению, из случайных конфигураций они возникают очень редко (в отличие от двумерной версии). Я решил поискать правила игры, в которых планеров было бы побольше.

Возьмем машину, у которой система команд точно такая же, как в языке brainfuck, но которая работает на ленте, в ячейки которой можно поместить любые целые числа. Переполнения в арифметических операциях не происходит, команда "+", примененная к положительному числу, всегда даст положительный результат, и т.п. Спрашивается: можно ли работать на такой машине, какие возникнут проблемы и как их обойти?

Преимущества очевидны: раз нет переполнений, то нет нужды и в длинной арифметике, можно одинаково работать с массивами любой длины и т.п. Но довольно быстро мы замечаем, что наш любимый способ очистки ячейки ("[-]") не работает: если в ячейке было отрицательное значение, то программа зацикливается. Аналогично, мы не можем свободно использовать команду копирования "[->+<]" — она тоже работает только для неотрицательных чисел.

Получается, что при программировании нам надо внимательно следить за знаками содержимого ячеек (проще всего — не допускать появления отрицательных чисел вообще), а если возникнет число, знак которого неизвестен — работать с ним специальным образом

Здесь мы рассмотрим две задачи: во-первых, запрограммируем оператор «if(a>b) C; else D;» где a и b неотрицательны, а C и D — какие-то действия, а во-вторых, научимся обнулять, копировать и определять знак произвольного числа.

Недавно на одном из форумов, посвященных многомерным пространствам, был задан вопрос: «А какие игры реализованы в нетривиальных пространствах, в частности, нет ли где реализации игры Каркассон на плоскости Лобачевского?» Вопрос мне показался интересным, тем более, что про эту игру я ни разу не слышал.

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

Понятно, что простор для обобщений в сторону нетривиальной геометрии огромен. Можно вместо квадратных карточек разработать треугольные или шестиугольные. Можно укладывать квадратные карточки на поверхность куба (появится 8 особых точек, в которых сходятся 3 а не 4 карточки, но это не очень принципиально). Можно нарисовать на плоскости Лобачевского квадратную сетку, в каждой вершине которой сходится 5 (или 6, или бесконечно много) квадратов. А можно заменить квадратные клетки на кубические и строить карту в пространстве.

Я выбрал последний вариант. Очень уж интересно было посмотреть на то, как будет выглядеть карта местности на четырехмерной планете.

Программу, решающую головоломку «пентамино» я написал в качестве одной из первых своих программ. Дело было давно, программа как-то работала, всех вариантов найти не успела… В общем, написал и забыл.

На днях, наводя порядок на столе, решил, что пора бы убрать валяющуюся без дела головоломку «Mini Bedlam Cube»:



А перед этим ее неплохо бы собрать. Головоломка состоит из 13 фигур — 12 составлены из 5 кубиков, одна из четырех; шесть фигур симметричные, три из них — плоские. Фигуры нужно уложить в коробку 4x4x4. Надо сказать, что периодически я вспоминал об этих кубиках, пытался с ними справиться, но так ничего и не вышло. Поэтому возникла идея — написать программу, решающую головоломку, причем затратить как можно меньше усилий, а потом решить старый вопрос: что выгоднее — перебирать фигуры или клетки, и в каком порядке.

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

В комментариях к статье «Рейтрейсер на JavaScript» ее автор ankh1989 рассказал о планах написать рейтрейсер для четырехмерного пространства. Кое-какие свои мысли на эту тему я попробую изложить здесь.