• Хроматическое число плоскости не меньше 5

      Задача о хроматическом числе плоскости формулируется следующим образом: в какое наименьшее число цветов можно раскрасить плоскость так, чтобы любые две точки на расстоянии 1 были покрашены в различные цвета?

      Эту задачу сформулировали Хуго Хадвигер и Пал Эрдёш в сороковых годах XX века. Независимо от них примерно в то же самое время этой задачей занимались Эдуард Нелсон и Дж. Р. Исбелл. После работы Хадвигера 1961 года об открытых на тот момент проблемах, хроматическое число плоскости стало активно изучаться.

      Сразу же было показано, что в 3 цвета плоскость требуемым образом раскрасить нельзя, однако 7 цветов достаточно. Действительно, легко выбрать на плоскости несколько точек так, что некоторые из них находятся на расстоянии ровно 1 (такая конструкция точек называется графом единичных расстояний), и затем перебором показать, что в 3 цвета эти точки раскрасить невозможно. Примеры таких графов — веретено Мозера и граф Голомба приведены на картинке ниже. Чтобы показать, что 7 цветов достаточно, замостим плоскость правильными шестиугольниками со стороной 0.4 и закрасим их по определённому паттерну, как на картинке ниже. Тогда, как несложно убедиться, концы любого отрезка длины 1 будут лежать в разных шестиугольниках различных цветов.



      Однако, с тех пор никто не мог уточнить ни верхнюю, ни нижнюю границы. Задача получила название Проблема Нелсона — Эрдёша — Хадвигера. Прошло 60 лет, и вот, в апреле 2018 года математик-любитель Обри де Грей предъявил граф единичных расстояний, который нельзя покрасить в 4 цвета.
      Читать дальше →
    • 10 новых сказок о потерянном времени

        Привет Хабр! Я решил продолжить серию статей про гипотезу Эйлера, написав несколько улучшенных версий программ для решения диофантова уравнения вида a5 + b5 + c5 + d5 = e5.


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

        1. Эффективный алгоритм
        2. Быстрая реализация
        3. Мощное железо
        4. Распараллеливание

        Я уделил больше всего внимания первому пункту. Давайте посмотрим, что из этого получилось.
        Скоро сказка сказывается, да не скоро дело делается
      • Судоку: так сколько же их? Часть 2/2

        • Translation
        Привет Хабр! Это вторая часть перевода статьи про подсчет различных судоку.



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

        Как обычно, мои комментарии выделены курсивом или спрятаны под спойлеры. Под спойлерами можно найти самое интересное — куски кода, которые верифицируют все числа, полученные в повествовании.
        Читать дальше →
        • +19
        • 6.5k
        • 6
      • Судоку: так сколько же их? Часть 1/2

        • Translation
        Привет Хабр! Данная публикация возникла после просматривания этого поста, в котором автор пытается посчитать количество различных судоку. Желая более точно разобраться в вопросе, я за пару минут нагуглил точный ответ, приведенный в данной статье. Текст этой статьи мне показался интересным сам по себе, поэтому я решил сделать перевод (в довольно вольном стиле).



        К сожалению, оригинал данной статьи написан для дебилов очень широкого круга читателей, в том плане, что тема рассматривается не очень глубоко, но довольно подробно. При этом поясняется только общий подход к решению задачи, без технических деталей, и, фактически, обрывается на самом интересном месте формулировкой «ну а дальше они посчитали на компьютере». В итоге я немного дополнил изложение своими комментариями: они либо отмечены курсивом, либо спрятаны под спойлеры. В них раскрываются некоторые технические моменты более подробно. Возможно, пост вместе с этими комментариями суммарно тянет на полноценную статью, нежели чем на просто перевод, но я решил оставить все как есть (на самом деле, я не нашел кнопки перевода перевода обратно в обычную статью, а создавать новую публикацию только ради этого было лень).
        Читать дальше →
      • О сложности выращивания сакуры: как я участвовал в Ludum Dare 34

          Привет, хабр!

          В данном посте речь пойдет о моем участии в конкурсе Ludum Dare 34, который был около трех недель назад.

          В результате получился пазл под названием Growing Sakura, геймплей которой можно видеть на гифке (не пугайтесь, она весит всего 300Кб):


          Кратко о правилах игры: изначально у нас есть гексагональное поле и несколько корневых бутонов (или один, как на гифке выше). Из него можно пустить 3 ветки (двумя способами — кликая левой или правой кнопкой мыши). Из каждого бутона на ветке левым кликом мыши можно сделать Y-разветвление, а правым — просто продолжить ветку дальше (I-разветвление). Если в каком либо направлении ветка расти не может (соответствующая клетка занята или в нужном направлении нет клетки) — то ветка не растет. В соответствии с последним условием нужно правильно выбирать порядкок «разворачивания» веток. В итоге получится дерево (или несколько деревьев) такое, что между двумя смежными ветками нет острых углов. Цель игры — покрыть все клетки игрового поля.

          Не заглядывая под кат попробуйте подумать секунд 10 и прикинуть, насколько сложной может быть эта игра.
          Читать дальше →
        • Ктулхи в банке: как мы решали ICFPC 2015

            Небольшой отчет о том, как мы решали ICFP Contest 2015. Мы участвовали в данном соревновании впервые, однако результат получился довольно неплохой. Можно поискать нас в таблице промежуточных результатов под именем «WILD BASHKORT MAGES». Финальные результаты ожидаются в течение нескольких ближайших недель, когда организаторы протестируют все решения на полном наборе тестов.



            В этом году в качестве задачи предлагалось написать решалку (или ИИ, кому как удобнее) для гексагонального тетриса. Все как в обычном тетрисе — укладываем фигурки, убираем заполненные строки, получая за это очки. Решение должно работать для разных размеров игрового поля и укладываемых фигурок произвольной конфигурации. Команды действий с фигурками (перемещения и повороты) кодируются обычными символами, в итоге решением является строка команд. За специальные секретные последовательности символов в строке-решении, называемые power words, даются дополнительные бонусные очки. По сюжету — данные строки именовались даваром, и организаторы собирали его для того, чтобы отсрочить пробуждение Ктулху.
            Осторожно, около 3Мб картинок и гифок под катом
            • +52
            • 11.9k
            • 1
          • Сортировка на односвязном списке за O(nlogn) времени в худшем случае с O(1) дополнительной памяти

              Все началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:
              1. Время выполнения — гарантированные O(nlogn).
              2. Использование O(1) дополнительной памяти.
              3. Применимость для сортировки данных в односвязных списках (но не ограничиваясь ими).

              Оговорки на все три ограничения:
              1. Гарантированные O(nlogn) означают, что, например, среднее время быстрой сортировки не подходит — должно получаться O(nlogn) для любых, даже самых худших входных данных.
              2. Рекурсию использовать нельзя, поскольку она подразумевает O(logn) памяти на хранение стека рекурсивных вызовов.
              3. Произвольного доступа к элементам сортируемого массива нет, мы можем двигаться итератором от любого элемента только к соседнему (за O(1)), причем только в одном направлении (вперед по списку). Модифицировать сам список (перевешивать указатели на следующие элементы) нельзя.

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

              Под катом можно узнать, что в итоге получилось у нас.

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

              Читать дальше →
            • Алгоритмы расщепления и числа Ван-дер-Вардена

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

                Я расскажу про так называемые алгоритмы расщепления (в частности, про DPLL-алгоритм), про теорему и числа Ван-дер-Вардена, а в заключение статьи мы напишем свой собственный алгоритм расщепления и за полчаса вычислений докажем, что число w(2; 5) равно 178 (первооткрывателям в 1978 году на это потребовалось более 8 дней вычислений).
                Читать дальше →
              • Great Permutator — опыт участия в бандлах и не только

                  Всем привет! В данной статье я поделюсь своим опытом продвижения компьютерной игры и участия в бандлах на примере моего проекта Great Permutator, который я очень неспешно пилю вот уже почти полтора года. Возможно, этот опыт кому-то покажется интересным, а кому-то даже окажется полезным. Общий тон статьи несколько негативный, рассказывающий «где были ошибки» и «как лучше не делать», нежели «как у нас все круто и хорошо».

                  image

                  Но, обо всем по порядку.

                  Читать дальше →
                • Roguelike/RPG на JavaScript (30 строк кода)

                  После серии постов про реализацию простеньких игрушек на JavaScript в 30 строчек, решил попробовать себя в этом «соревновании». Посидев вечер, получилось создать «полноценную» Roguelike/RPG (я не слишком разбираюсь в жанрах, но вышло что-то в этом направлении). Заодно поизучал JavaScript (до этого на нем никогда не писал, как-то все C++ балуюсь).

                  image

                  Особенности:
                  • Случайно генерируемый мир
                  • Прокачка персонажа
                  • 3 вида врагов и финальный босс
                  • Инвентарь с бутылочками зелья и магазин для их пополнения

                  Читать дальше →