Pull to refresh
105
0
Артём Рипатти @ripatti

Математик-программист

Send message

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

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

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

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



Однако, с тех пор никто не мог уточнить ни верхнюю, ни нижнюю границы. Задача получила название Проблема Нелсона — Эрдёша — Хадвигера. Прошло 60 лет, и вот, в апреле 2018 года математик-любитель Обри де Грей предъявил граф единичных расстояний, который нельзя покрасить в 4 цвета.
Читать дальше →
Total votes 33: ↑32 and ↓1 +31
Comments 11

10 новых сказок о потерянном времени

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


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

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

Я уделил больше всего внимания первому пункту. Давайте посмотрим, что из этого получилось.
Скоро сказка сказывается, да не скоро дело делается
Total votes 32: ↑32 and ↓0 +32
Comments 48

Судоку: так сколько же их? Часть 2/2

Reading time 26 min
Views 8.9K
Привет Хабр! Это вторая часть перевода статьи про подсчет различных судоку.



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

Как обычно, мои комментарии выделены курсивом или спрятаны под спойлеры. Под спойлерами можно найти самое интересное — куски кода, которые верифицируют все числа, полученные в повествовании.
Читать дальше →
Total votes 19: ↑19 and ↓0 +19
Comments 6

Судоку: так сколько же их? Часть 1/2

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



К сожалению, оригинал данной статьи написан для дебилов очень широкого круга читателей, в том плане, что тема рассматривается не очень глубоко, но довольно подробно. При этом поясняется только общий подход к решению задачи, без технических деталей, и, фактически, обрывается на самом интересном месте формулировкой «ну а дальше они посчитали на компьютере». В итоге я немного дополнил изложение своими комментариями: они либо отмечены курсивом, либо спрятаны под спойлеры. В них раскрываются некоторые технические моменты более подробно. Возможно, пост вместе с этими комментариями суммарно тянет на полноценную статью, нежели чем на просто перевод, но я решил оставить все как есть (на самом деле, я не нашел кнопки перевода перевода обратно в обычную статью, а создавать новую публикацию только ради этого было лень).
Читать дальше →
Total votes 34: ↑33 and ↓1 +32
Comments 33

О сложности выращивания сакуры: как я участвовал в Ludum Dare 34

Reading time 14 min
Views 20K
Привет, хабр!

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

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


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

Не заглядывая под кат попробуйте подумать секунд 10 и прикинуть, насколько сложной может быть эта игра.
Читать дальше →
Total votes 62: ↑62 and ↓0 +62
Comments 20

Ктулхи в банке: как мы решали ICFPC 2015

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



В этом году в качестве задачи предлагалось написать решалку (или ИИ, кому как удобнее) для гексагонального тетриса. Все как в обычном тетрисе — укладываем фигурки, убираем заполненные строки, получая за это очки. Решение должно работать для разных размеров игрового поля и укладываемых фигурок произвольной конфигурации. Команды действий с фигурками (перемещения и повороты) кодируются обычными символами, в итоге решением является строка команд. За специальные секретные последовательности символов в строке-решении, называемые power words, даются дополнительные бонусные очки. По сюжету — данные строки именовались даваром, и организаторы собирали его для того, чтобы отсрочить пробуждение Ктулху.
Осторожно, около 3Мб картинок и гифок под катом
Total votes 54: ↑53 and ↓1 +52
Comments 1

Сортировка на односвязном списке за O(nlogn) времени в худшем случае с O(1) дополнительной памяти

Reading time 11 min
Views 57K
Все началось с данного топика на сайте 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. Прежде чем заглядывать под кат, предлагаю сначала самостоятельно подумать над алгоритмом. Если придумается что-то круче нашего варианта — напишите в комментариях.

Читать дальше →
Total votes 70: ↑67 and ↓3 +64
Comments 84

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

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

Я расскажу про так называемые алгоритмы расщепления (в частности, про DPLL-алгоритм), про теорему и числа Ван-дер-Вардена, а в заключение статьи мы напишем свой собственный алгоритм расщепления и за полчаса вычислений докажем, что число w(2; 5) равно 178 (первооткрывателям в 1978 году на это потребовалось более 8 дней вычислений).
Читать дальше →
Total votes 78: ↑73 and ↓5 +68
Comments 17

Great Permutator — опыт участия в бандлах и не только

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

image

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

Читать дальше →
Total votes 38: ↑38 and ↓0 +38
Comments 16

Roguelike/RPG на JavaScript (30 строк кода)

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

image

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

Читать дальше →
Total votes 89: ↑68 and ↓21 +47
Comments 21

Information

Rating
Does not participate
Location
Уфа, Башкортостан(Башкирия), Россия
Registered
Activity