Когда-то давно друзья подарили вот такую головоломку:
Собрать её самостоятельно я так и не смог (всегда оставался один фрагмент). Посему было решено написать программу.
Для тех, кто не любит читать, решение доступно по ссылке (внимание, сильно нагружает процессор).
Читать полностью »
Эту лампу мне подарили на день рождения в прошлом году. Замечательная маленькая вещица — вы можете перемещать отдельные фрагменты, создавая любую форму, а они светятся по отдельности, питаясь через проводящие грани по периметру.
Из-за очевидной связи с тетрисом меня всегда раздражала одна вещь: лампу невозможно составить в чистый прямоугольник. Как бы я ни старался, всегда какой-нибудь кусочек торчал сбоку, а одного не хватало сверху, или получалась другая раздражающая комбинация.
7 ноября я решил выпустить 6 новых игр за 6 недель.
Если Вы еще не выпустили ни одной игрушки в AppStore, то ноябрь, декабрь — самые лучшие месяцы для этого события.
В этом году Вы, конечно, не успеете, но в 2015-ом вполне.
Я — успел.
Были высказаны следующие ограничения — 1) никаких Unity, 2) никаких клонов известных игр, 3) простейшее управление, 4) сложнейшее решение.
Игры получились интересные для меня, а значит местные математики одобрят. Разумеется, большинству игроков они окажутся не по зубам, поэтому заработка не принесут. Но какие-то доллары упадут, финансовый отчет за декабрь будет представлен в январе.
Читать полностью »
Хороший способ провести пятничный вечер — поиграть в новую головоломку 0h h1.
Смысл простой: нужно заполнить всё игровое пространство квадратиками красного и синего цветов. При этом запрещено размещать в ряд три квадрата одного цвета.
Красный квадрат создаётся одинарным щелчком, синий — двойным щелчком.
Читать полностью »
На этой неделе я начал читать бакалаврам Академического университета базовый курс по алгоритмам. Начинал я совсем с основ, и чтобы тем, кто с базовыми алгоритмами уже знаком, было чем заняться, я в начале пары сформулировал две, наверное, самые свои любимые задачки по алгоритмам. Давайте и с вами ими поделюсь. Решение одной из них даже под катом подробно расскажу. Но не отказывайте себе в удовольствии и не заглядывайте сразу под кат, а попытайтесь решить задачи самостоятельно. Обещаю, что у обеих задач есть достаточно простые решения, не подразумевающие никаких специальных знаний по алгоритмам. Это, конечно, не означает, что эти решения просто найти, но после пары один из студентов подошёл и рассказал правильное решение первой задачи. =) Если же вам интересно посмотреть на начало курса или порешать больше разных задач — приходите к нам на (бесплатный) онлайн-курс, который начнётся 15 сентября.
Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.
Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще). Ограничение на использование дополнительной памяти означает, что нельзя заводить дополнительный массив линейной длины, но можно заводить переменные.
Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).
Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.
Под катом — решение первой задачи. Ещё раз призываю вас заглядывать под кат только после того, как порешаете задачу. По второй задаче могу какую-нибудь подсказку сказать.
Читать полностью »
Со времён игры «2048» не было новых таких же увлекательных головоломок. Теперь есть: «Игра о квадратах».
Программист Джим Бамгарднер (Jim Bumgardner) в свободное время увлекается составлением лабиринтов. На днях он посетил супермаркет и увидел пачку с печеньем Kraft Mac & Cheese, на которой изображено «что-то очень знакомое».
Для постороннего человека картинка может показаться ничем не выдающейся, но Джим потратил много лет на написание программного обеспечения для генерации таких лабиринтов. Если посмотреть внимательнее, то можно увидеть вершины спирали Фибоначчи. По словам автора, это довольно уникальный дизайн.
Вышла новая часть серии головоломок «Загадки ДаВинчи: Викторина»! Всем, кто хочет прокачать свою эрудицию до немыслимых размеров, а также любителям побродить в чертогах разума — добро пожаловать под кат.
Более 50 лет назад автор популярных статей о математике в журнале Scientific American Мартин Гарднер предложил читателям задачу: «Можете ли вы разместить семь сигарет таким образом, чтобы каждая из них соприкасалась со всеми остальными?».
Читать полностью »
Недавно на Хабре появилась статья, в которой опубликована ссылка на игру 2048. Там же можно подробнее прочитать правила и попробовать сесть за эту увлекательную штуку (достаточное количество читательов уже этим побаловались).
Студентам физфака тоже было весело, поэтому мы придумали простую эвристическую выигрышную (по крайней мере, нам удалось набрать 2048 в 9 из 10 раз) стратегию этой игры.
Занумеруем идущие подряд столбцы (можно и строки, но в дальнейшем я буду говорить о столбцах) от 1 до 4 (последовательно слева направо или справа налево). Основополагающим принципомЧитать полностью »
