Занимательные задачки

Привет! Меня зовут Диана, и я математик, поэтому везде вижу числа. Этот текст я подготовила для МТС Диджитал.

Немного обо мне: выпускница мехмата МГУ, несу математику в мир со, страшно подумать, 2007 года. Обожаю находить связи между ежедневными ситуациями и разными математическими теориями. А еще — придумывать задачи с безобидными формулировками, но не всегда простыми решениями. Сегодня как раз принесла вам такие — теперь вам есть чем заняться в романтический вечер много вечеров!

Так что устройтесь поудобнее со своей второй половинкой или в компании себя любимого — и призовите на помощь смекалку! Ответы опубликую через 10 дней — 24 февраля. Погнали!

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

Сегодняшняя задача заставила попотеть и разработать различные способы оптимизации рекурсивного запроса как по количеству итераций, так и по объему используемой памяти.

Эта программа представляет собой свободную от зависимостей реализацию GPT-2. Она загружает матрицу весов и файл BPE из оригинальных файлов TensorFlow, токенизирует вывод при помощи простого энкодера, работающего по принципу частотного кодирования, реализует базовый пакет для линейной алгебры, в котором заключены математические операции над матрицами, определяет архитектуру трансформера, выполняет инференс трансформера, а затем очищает вывод от токенов при помощи BPE-декодера. Всё это — примерно в 3000 байт на C.

Код достаточно эффективно оптимизирован — настолько, что малый GPT-2 на любой современной машине выдаёт отклик всего за несколько секунд. Чтобы этого добиться, я реализовал KV-кэширование и применил эффективный алгоритм перемножения матриц, а также добавил опциональный OMP-параллелизм.

Взяв это за основу, можно создать некий аналог Chat GPT — при условии, что вас не слишком волнует качество вывода (объективно говоря, вывод получается просто ужасный… но решение работает). Здесь есть некоторые глюки (особенно с обработкой символов в кодировке UTF-8), а для эксплуатации модели размером XL с широким контекстным окном может потребоваться ~100 ГБ оперативной памяти. Но, если вы просто набираете текст в кодировке ASCII при помощи малого GPT2, то такая модель должна нормально работать примерно везде.

Я выложил весь код на GitHub, поэтому можете свободно брать его там и экспериментировать с ним.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

Многие слышали о классической игре сокобан, а кто-то наверняка играл в "Мудрого крота" из Роботландии. В этой части мы будем двигать ящики по складу, используя возможности json[b] и геометрического типа point.

Два месяца назад я написал Телеграм-бот, который помогает мне выхватывать дешёвые авиабилеты (и нет, это не рекламная интеграция). Я прикрутил Python-интеграцию к Telegram по протоколу для клиентов, чтобы читать сообщения из любых публичных групп, к backend-части на Spring — она позволяет через бота подписываться на эти группы и настраивать, какие сообщения выхватывать для вас.

За это время в бот пришли пользователи, и вместе мы встретили в этом пет-проекте несколько грабель: несколько грабель: блокировки Telegram-аккаунта за спам, неподходящая архитектура приложения из-за плохой проработки доменных моделей, отсутствие данных для пересылки сообщений через бота.

Я реанимировал бот, добавил несколько киллер-фичей и готов поделиться с вами всеми наработками. В статье найдёте код, ссылки на бот и примеры, как другие пользователи ищут через бот скидки на айфоны и много чего ещё.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

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

Привет, Хабр! На связи Фёдор Наумов, сервисный инженер К2Тех, по совместительству – руководитель описанных ниже работ. Сегодня я расскажу, как мы демонтировали радиатор дизель-генераторной установки (ДГУ) из здания, построенного практически «в облипку». Ловкость рук и никакого мошенничества – под катом!

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В этой части совсем простая идея по одновременному решению систем линейных уравнений "пачками".

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В этой части используем двойную рекурсию для "раскраски" регионов на карте.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В этой части снова сталкиваемся с вложенным в цикл рекурсивным поиском "в ширину".

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В этой части рассмотрим некоторые "грабли", на которые можно наступить, реализуя рекурсивные алгоритмы на SQL... Которые иногда можно сделать вовсе нерекурсивными, ускоряя запрос в десятки раз!

Рассмотрен способ приведения судоку: неправильного (со множеством решений) к правильному, то есть к судоку с единственным решением − . (9х9)-матрицей цифр, назначенной для неправильного судоку в качестве «Ответов на судоку». «Правка» неправильного судоку состоит в назначении для него минимального количества дополнительных цифр-подсказок, что не нарушает классической структуры судоку.

Предыстория и казус газетных судоку

Как и прежде, ближе к Новому году в почтовых ящиках жителей нашего городского округа чаще стали появляется номера газеты «Восточный округ» (ВО). И традиционно в конце каждого номера приводится головоломка судоку. И наверное, тоже уже традиционно, эти судоку ̶ неправильные, то есть имеют много решений (ответов), и только одно из них назначено в виде заполненной цифрами таблицы как «Ответы на судоку». На этот раз судоку, попавшееся на глаза (в номере ВО №40 (563)), побило все прежние рекорды по числу решений (их оказалось 83 132), из которых уважаемому читателю предложено как-то угадать единственное, приведённое в газете как «Ответы на судоку». На такой казус газетных судоку я прежде обращал внимание редакции газеты ВО. И на этот раз я не удержался, и  не внял просьбе близких: «перестать заниматься ерундой» не тратить время на публикацию в сети. Год назад, анализируя последние номера газеты ВО 2023 года, я предлагал (см. habr.com/ru/articles/787496) «подправлять» подобные неправильные судоку так, чтобы они имели единственное решение. Но предлагаемая тогда «правка» налагала на судоку дополнительные ограничения, меняя их классическую структуру. Например, для судоку №149 из sudoku.bestcrosswords.ru/generator, имеющего 26918 отличных друг от друга решений, предлагалось дополнительно потребовать, чтобы на побочной диагонали матрицы располагался полный набор цифр от 1 до 9. Это дополнительное требование меняло классическую структуру судоку и усложняло восприятие привычной головоломки.
 А как дополнить исходную таблицу судоку минимальным числом новых  цифр-подсказок, чтобы получилось судоку с классической структурой и единственным решением, например, с тем, что приведено в газете как  «Ответы на судоку»? В этом и состоит задача, решение которой позволит преодолеть казус  газетных судоку.

Если я хочу посмотреть видео — разве для этого обязательно покидать vim?

Что ж, прямо в заголовке этого поста я пообещал вам продемонстрировать Bad Apple в vim, пользуясь только поисковыми запросами. Вот Bad Apple в vim, всё, что здесь меняется — только поисковый запрос:

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В этой части воспользуемся возможностями линейной генерации и подсчета уникальных значений.

В ходе нашего исследования, охватывавшего записи SPF, DKIM и DMARC на 1 миллионе самых популярных веб-сайтов мы с удивлением обнаружили более 1 700 открытых DKIM-ключей длиной менее 1 024 бит каждый. Эта находка нас удивила, поскольку RSA-ключи короче 1 024 бит расцениваются как небезопасные, и их не рекомендуется использовать в DKIM с 2018 года, когда был введён в действие документ RFC 8301.

Просто из любопытства мы решили проверить, а удастся ли нам взломать один из таких ключей. Мы стремились извлечь закрытый ключ из открытого RSA-ключа, так, чтобы можно было подписывать им электронные сообщения, выдавая себя за их подлинного отправителя. Кроме того, нас занимало, пройдут ли DKIM-верификацию электронные письма, подписанные таким скомпрометированным ключом. Мы решили проверить крупнейших провайдеров электронной почты —  в частности, Gmail, Outlook.com и Yahoo Mail — вдруг они просто с порога откажутся проверять цифровые подписи, сгенерированные настолько коротким ключом.

Для нашего эксперимента мы выбрали домен redfin.com, на котором нашли 512-разрядный открытый RSA-ключ по адресу key1._domainkey.redfin.com (сейчас он уже не доступен):

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В сегодняшней статье посмотрим, как можно использовать рекурсию для перебора комбинаций.

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

Надеюсь, вы к этому готовы? Соображение и логическое мышление уже восстановились? А если проверить? Да, есть у меня один способ...

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

С интегралами начинают знакомится еще в старших классах, продолжают их изучать в университете. В основном все задачи на интегрирование в курсах школы и университетов счетные, но в этой статье мы постарались собрать самые интересные и красивые задачи, по нашему скромному мнению. Отчасти красота состоит в том, что для их решение вам нужна лишь смекалка, пытливость ума и знание, что интеграл от функции на отрезке от до b

()  —  это просто площадь под графиком функции . Поэтому перед тем,

как

открыть решение обязательно попробуйте порешать самостоятельно!

Ответ: да! И вот же он:

Игра запускается, и вы можете перемещаться по миру 64x64x64 при помощи клавиш WASD. Пробелом прыгаем, мышью осматриваемся. Щёлкнув левой кнопкой мыши, можно разрушить блок, а правой — установить землю.

Можно просмотреть QR-код при помощи следующей команды под Linux:

zbarcam -1 --raw -Sbinary> /tmp/m4k &&chmod +x /tmp/m4k  && /tmp/m4k

-1: выйти после того, как код будет просканирован

--raw: не обрабатывать его как текст

--Sbinary: воспользоваться двоичной конфигурацией

Проект выложен на GitHub здесь:TheSunCat/Minecraft4k