Рубрика «Занимательные задачки» - 47

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

image
Этот и все последующие рисунки взяты из исходной статьи

В этой статье, я бы хотел обсудить гораздо более простое решение, которое позволяет решить эту задачу.
Читать полностью »

Предлагаю читателям «Хабрахабра» перевод публикации «100 Prisoners Escape Puzzle», которую я нашел на сайте компании DataGenetics. Все ошибки по данной статье присылайте, пожалуйста, в личные сообщения.

В этой задаче в тюрьме сидят 100 заключенных, каждый из которых пронумерован числами от 1 до 100. Тюремщик решает дать шанс заключенным на освобождение, он рассказывает им условия испытания, и если все заключенные пройдут тест, тогда они будут освобождены. Если хотя бы один из них провалит тест, то все заключенные умрут.

Математическая задача о 100 коробках и спасении заключенных - 1
Читать полностью »

Эта история начинается с этой статьи на Хабре. В ней приведен один из самых сложных кроссвордов, составленных программой (см. ниже).

Алгоритм формирования кроссвордов - 1

Я был уверен, что все кроссворды давным-давно генерируются программно и был несколько удивлен тем, что это может быть проблемой. Замечу, что речь идет именно о «канадских» кроссвордах, в которых каждое слово имеет пересечение с другим словом на каждой букве или очень близких к ним по сложности. В моей работе аналитика, не так много действительно сложных задач, поэтому мне стало интересно попробовать разработать алгоритм, который мог бы это сделать. Результат размышлений, подкрепленный программой для генерации кроссвордов, приводится в этой статье…
Читать полностью »

Задача о 64 монетах, двух заключённых и одной шахматной доске - 1

Примечания переводчика: поскольку я далёк как от математики, так и от английского языка, в переводе наверняка присутствуют мелкие неточности и грубые ошибки, так что замечания в личном сообщении/комментарии приветствуются. Перевод немного сокращён и переработан, частично в силу того, что некоторые фразы я не смог перевести/понять.
Оригинальные обозначения сторон монеты head/tail я заменил на аверс/реверс, чтобы не вносить путаницу русскоязычными орёл/решка. На иллюстрации выше слева аверс (head), справа реверс (tail).

Спасение невозможно?

Это одна из тех типичных загадок о заключённых, в которых вы приговорены к смерти и можете спастись, только если докажете свои умственные способности тюремщику. Вы и ваш друг были заключены в тюрьму. Ваш тюремщик предлагает вам испытание. Если вы его выполните, вы оба будете освобождены.
Читать полностью »

Доброго времени суток, читатели!

Экспорт Избранного на Хабре в PDF. Версия 2.0 - 1

Думаю, многих из вас когда-либо посещала мысль «вот бы сохранить статьи с Хабра». Такая же мысль посетила и меня чуть больше года назад.

Представляю вам новую версию программы закачки статей с Хабра, Гиктаймс и Мегамозг в формате PDF.

Новый проект называется HabraParse.

Проект состоит из библиотечки, которая парсит сайты, и скрипта, использующего лишь часть возможностей этой библиотеки. Скрипт написан на python3, для его работы потребуются модули docopt, requests и weasyprint (все их легко можно установить командой pip install name).

На текущий момент в скрипте имеются следующие возможности:

  • скачать статью по её ID;
  • скачать список URL избранного для заданного пользователя;
  • скачать статьи из избранного в папку в формате PDF или HTML (пока реализация HTML не на высоте, поэтому по умолчанию используется формат PDF, но он работает значительно дольше).

Использование опций --gt/--mm позволяет сохранять статьи с GeekTimes.ru и Megamozg.ru.

Краткое описание параметров скрипта

Usage:

  ./habraparse.py save_favs_list [--gt|--mm] <username> <out_file>
  ./habraparse.py save_favs [--gt|--mm] [-cn --save-html --limit=N] <username> <out_dir>
  ./habraparse.py save_post [--gt|--mm] [-c --save-html] <topic_id> <out_file>

По умолчанию все команды работают с проектом HabraHabr.ru.
При задании опций --gt/--mm скрипт будет работать с GeekTimes.ru/Megamozg.ru.

Команды:

  save_favs_list - сохранение в файл <out_file> списка URL избранного для пользователя <username>
  save_favs - сохранение в папку <out_dir> статей из избранного для пользователя <username>
  save_post - сохранение в файл <out_file> статьи с заданным ID

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

Читать полностью »

Пример из практики. Понадобилось разобрать вот такие строки из 0 и 1, что на фото 1 в ячейке A2.

image

Это кусочки BMP, что, впрочем, неважно.

Каждая последовательность длиной 4 байта, т.е. 32 бит. Нужно было извлечь из таких последовательностей серии единиц и измерить длину этих серий.

Для данного примера нужно было получить на выходе 1 2 1 2 7.

Можно было начать с распределения символов по столбцам, использовав штатную Экселевскую приблуду Данные/Текст по столбцам. Однако, это требует ручной установки 31 разделителя, что, конечно же, влом. Хотелось, чтобы было так: загрузил на лист кучку байт и сразу получил результат.

Поэтому пришлось нагородить набор костыликов.

В ячейке B2 избавился от лишних нулей формулой СЖПРОБЕЛЫ. Предварительно пришлось нули заменить на пробелы формулой ПОДСТАВИТЬ, а после сжатия вернуть их на место этой же формулой.

В C2 заехал 0. Это чисто служебный нолик, для дальнейшего копирования формул вправо и вниз.

В D2 — формула (видна на фото 2).

image

Находит позицию первого нуля. В E2 — второго и т.д. Как видим, в сжатой последовательности (B2) первый ноль — в позиции 2, второй — в 5-й, третий — в 7-й и 4-й ноль — в 10-й. В последовательности всего 4 нуля, и поэтому в H2 отобразилась бы ошибка #ЗНАЧ, если бы не обработка этой ошибки формулой ЕСЛИОШИБКА. Она заменяет #ЗНАЧ на 99. «Почему 99?» — вы можете спросить. Это число нам понадобится в дальнейших расчетах, терпение.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js