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

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

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



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

Привет Хабр! Я решил продолжить серию статей про гипотезу Эйлера, написав несколько улучшенных версий программ для решения диофантова уравнения вида a⁵ + b⁵ + c⁵ + d⁵ = e⁵.


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

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

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

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



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

Как обычно, мои комментарии выделены курсивом или спрятаны под спойлеры. Под спойлерами можно найти самое интересное — куски кода, которые верифицируют все числа, полученные в повествовании.

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



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

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

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

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


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

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

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



В этом году в качестве задачи предлагалось написать решалку (или ИИ, кому как удобнее) для гексагонального тетриса. Все как в обычном тетрисе — укладываем фигурки, убираем заполненные строки, получая за это очки. Решение должно работать для разных размеров игрового поля и укладываемых фигурок произвольной конфигурации. Команды действий с фигурками (перемещения и повороты) кодируются обычными символами, в итоге решением является строка команд. За специальные секретные последовательности символов в строке-решении, называемые power words, даются дополнительные бонусные очки. По сюжету — данные строки именовались даваром, и организаторы собирали его для того, чтобы отсрочить пробуждение Ктулху.

Все началось с данного топика на сайте 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, который я очень неспешно пилю вот уже почти полтора года. Возможно, этот опыт кому-то покажется интересным, а кому-то даже окажется полезным. Общий тон статьи несколько негативный, рассказывающий «где были ошибки» и «как лучше не делать», нежели «как у нас все круто и хорошо».



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

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



Особенности:

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