Викилоги

• Как зарегистрироваться на курс
• Lab17
• Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)

Знаете ли вы Python?

1. Да
2. Нет

Вы должны войти в систему, чтобы участвовать в этом голосовании.

Проверим?

• Если нет, ничего страшного → идем на http://pythontutor.ru/, https://exercism.org/tracks/python

Знаете ли вы Jupyter-ноутбуки?

1. Да
2. Нет

Вы должны войти в систему, чтобы участвовать в этом голосовании.

• Если нет (и даже если да), идем на Lab17, там курс по ним.

Знаете ли вы теорию сложности с вероятностными классами (RP-BPP…)?

1. Да
2. Нет

Вы должны войти в систему, чтобы участвовать в этом голосовании.

Проверим?

• Если нет, ничего страшного разберемся в этом курсе.
  • Смотрим Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)#Темы
  • Смотрим Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)#Книга

Решали ли вы задачи на Leetcode/Codechef/Spoj… ?

1. Да
2. Нет

Вы должны войти в систему, чтобы участвовать в этом голосовании.

• Если нет, ничего страшного разберемся в этом курсе.

В продолжении темы Blog:Advanced Algorithms/Хорошие практики компактных Pyomo-формулировок на примере решения «Задачи о станках» рассмотрим рефакторинг решения Участник:PankratovViktor/Производство подразделяемых задач.

• Optprob/Хранение артефактов на складе
• ноутбук

• Blog:Advanced Algorithms/2022-12-06 «Воспроизведение статей» — на отл. — важно для отличников.
• Blog:Advanced Algorithms/Разбор оптимизационной задачи «Группировка людей»
• Blog:Advanced Algorithms/Хорошие практики компактных Pyomo-формулировок на примере решения «Задачи о станках»
• Blog:Advanced Algorithms/Задача о двух кучах камней и примеры использования различных ЦЛП-солверов
• Категория:На_проверку — через нее общение.
  • Не забывайте чинить и переводить туда из Категория:Проблемы_в_решении
  • План перехват → 5 бонусных баллов, кто найдет ошибку в чужом решении!
    • Категория:Возможно ошибка
  • Те, кто прошел отборочный блок с задачами — вас нет, ищите другой курс, фан в другом месте (чего только нет)

• • Те, кто решает задачи ради бонусов — решайте Spoj/Chef только они приносят бонусы.
• Не забывайте вопросы о постановке в страницу-решения → Участник:Philipakhiarov/Производство_штучных_изделий

Для тех, кому не хватило баллов, обязательная программа (алгоритмические задачи и бизнес-задачи) выполнена, и готовы идти на «отлично».

Концептуально:

• Это на «отл»
• Win-Win!
• Подготовка к защите дипломов-курсовых-кандидатских — моделирование диплома-научной работы и ее защиты.
• Анализ научной статьи про алгоритмы, с переложением ключевой части в Jupyter-ноутбук.
  • Полностью «переписывать статью не надо» — не надо переводить-копировать все содержание.
    • Доказательства не нужны.
  • Разобраться в введении
  • Моделировать постановку задачи (обычно это ЦЛП)
    • Возможно придумать тестовые данные, если их там нет или не прилагались к статье.
  • Воспроизвести максимально декомпозировав, основной алгоритм — попробовать смоделировать и воспроизвести алгоритм для решения.
  • Некоторые примеры работ в папке articles2jupyter-examples
  • глобальная проблема воспроизводимости + https://paperswithcode.com/ → мы помогаем решать.
  • Если что не получается — пингуйте.
  • Запишите к ним видеоролик, как в Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики
  • Научитесь пользоваться OBS — (см. также [1]), попробуйте использовать экранное рисование ([2]) и сделать это живым и доступным.
  • Запишите видео-презентацию и забросьте мне (unlisted youtube, файлохранилища…)

• Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах» и «Моделирование бизнес-задач»
  • Также, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в Lab.

• Выбирайте задачи из Открытые статьи для разбора, переходите к редактированию по «Беру…», резервируйте, как обычно …

• Идем на Lab
• Оформляем свои ноутбуки в папке «advalg-2022-homeworks»
• Учимся на готовых решениях коллег в соседних папках и решениях прошлых лет → articles2jupyter-examples

• Optprob/Группировка людей
• ноутбук

Несколько сумбурный разбор этой задачи сходу (но может это и хорошо, ошибка и поиск ошибок — полезно показать).

Студенту — не забыть доделать визуализацию результатата покрасивей (граф, кластеры, связи там). Например, как-то так → [1], [2]

• Старайтесь делать компактные и читаемые Pyomo-формулировки
  • тогда даже не понадобится куча плохочитаемых латех-пояснений.
• Посмотрите — как индексировать переменные и ограничения, как использовать слайсы в суммах, поменьше лишнего кода (особенно всяких скобок).
• Задача Optprob/Покупка станков
  • Решение Участник:Cherniavskii/BusinessProblems/Покупка станков (там ссылка на ноутбук).

«Задача о двух кучах камней и примеры использования различных ЦЛП-солверов»

• компактная задача и постановка, однако на которой зафейлился CBC — наш солвер «по умолчанию», и возник повод попробовать другие ЦЛП-солверы, и повод пошевелить постановку.

• Optprob/Поделить_поровну
• ноутбук

• Оценки по умолчанию уже есть
• Расхватывают простые задачи!
  • Пока еще есть из чего выбирать → Открытые бизнес-задачи
  • Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики
• Если что-то не понятно, смело смотрите Решенные бизнес задачи решения коллег.
  • Если у кого-то в чем-то затык — пишите мне, не затягивайте.
• Схема «балл за блок» плюс бонусы на еще балл.
  • У кого нет бонусных баллов, но хотите «отл» — скоро будут задания на «отл».
• Многие вышли на «хор» и близки к «отл» оценку
• Осталось по сути пара недель, не задерживаем.
• Созвон 2 декабря не факт что получится, конференция.

Кто решил бизнес-задачи, и чье решение уже проверено и признано правильным, — запишите разьясняющие видеоролики по вашим решениям с помощью OBS (это универсальное решение для создания видеодокументации — можно использовать камеру (и даже с хромакеем), можно использовать стилус для рисования, но на худой конец, просто скринкаст с нормальным звуком, ну и курсор можно сделать побольше... — так тоже пойдет.

Ох, понял, что никто не пошел смотреть ссылки, поэтому полезное тут повторю рядом

• Не экономьте битрейт при записи OBS — ставьте при записи 3 Mbit, потом видеохостинги сами ужмут. Или перепакуете. Главное, не потратить время, получив замыленный и нечитаемый текст юпитер-ноутбуков, очень обидно. Почти как не записать звук.
• Сначала запишите минутку видео со звуком и послушайте — например, выяснится, что звука вообще нет, или он ужасный (что-то с уровнем например — можно поиграть настройками OBS), а то и вовсе надо сменить микрофон. Для общажных условий, любой микрофон прищепка (стоит копейки, пригодится вам обязательно — сейчас все айти удаленное, непрерывные созвоны — и возможно вас еле терпят и ненавидят за бубнящий микрофон, но почему-то не говорят) может оказаться лучше обычного встроенного в ноутбук микрофона, который может поймать электрошумы из собственной схемы, эхо плохомеблированной комнаты общежития, и т.п.

• Сделайте полноэкранный режим броузера — больше места для полезной информации.
• Лучше в discopal-lab понажимать на кнопочку с плюсиком → это лучше, чем просто увеличивать шрифты во всем броузере, хотя и можно и так.
  • Особенно это важно, когда у вас слабое разрешение — 720 например.
• Полезно сделать курсор большим — в виндах, KDE и GNOME это настраивается по разному, но настраивается.

Потом можно либо мне файл прислать, либо сами на любой видеохостинг (ну хоть на ютуб в unlisted mode) можете загрузить — подошью ваше обьяснение, и это будет работать как обучающий материал для ваших коллег! Ну или поместите «На проверку» решение, написав, что дописали ролик. Просто если вы это сделаете «тихо», где-то добавив ссылку в ноутбук, я это просто не замечу....

Задача Optprob/Капитальные инвестиции

• Решение студента, и фидбек по нему

• Решение преподавателя с разбором

Ключевой вывод:

• Пусть будет больше говорящих переменных (про каждый факт)
• Их связывают простые ограничения
• И целевая функция простая
• Это будет легче верифицировать и модифицировать.
• Решатели сами выкинут лишние переменные и превратят модель в плоскую.

• Загадка по TL → Участник:Larin.dv/Tree_of_comprimes, почему важно приводить ссылки на решения. Знает кто почему так?
  • Квест на отл?
• Категория:Проблемы_в_решении
• В целом, все справились, кто не справился — отчислен.

Переходим к «Курс лекций «Эффективные алгоритмы»#Блок 2» (уже несколько недель его делают те, кто приходил на созвоны, несколько задержался придумывая задачи).

• Не забывайте добавлять ссылки на задачи → [1], [2] … теряю время.
• «Насыпано» несколько сотен задач из литкода (чтобы полегче), по темам, где стало маловато задач
• возможно с «ошибками» классификации,
• возможно слабенькие («сложение двух целых»)
• но это неважно.
• Многие пришли к финишу →

• Категория:Проблемы в решении — непроход по TL, прилагайте ссылки на сабмишн.
• Если не прорубаетесь с кодчиф-спож → оставьте тестовые данные → с вашим алгоритмом → Участник:Vshokorov/Codechef/QRYLAND
• Начинайте, кто боится — ну несложно же → User:Vshokorov/leetcode/find-center-of-star-graph
• Пробуйте Lab

• Решаем именно на Python!
  • Нужны решения именно на Python! (иногда встречающиеся решения не на Python это тестовый запуск в 2019)
  • → Категория:Проблемы в решении
  • [1], [2], [3], …
• Оформляем именно как подстраницу → [4], [5]
• Участник:Vshokorov/Codechef/QRYLAND — если никак не решается, делайте генератор тестовых данных (но отдельно, в файл!).
• A_index
• Надо насыпать новых. Обещаю много легких, из литкода.
• Поздравляем первых закрывших блок.
• Втягивайтесь! Ибо второй блок придется идти без вас!
  • 100500 решений ([6], Решенные практические задачи, [7]…)

• Начните решать! Все же очень просто!
  • Участник:GeraskinDA/longest-arithmetic-subsequence-of-given-difference
  • Участник:Cherniavskii/Solutions/Leetcode/maximum-element-after-decreasing-and-rearranging
• Не забудьте залогинится — решения скрываются от индексации (не бойтесь, поиском никто не найдет),
• Решайте задачи из разных тем! (См. «Bolyarich и динамическое программирование») — т.е. можно, но необязательно.
  • 6 задач из 4 тем. (если задача на 2 темы — удобно — «я размазываю») — пока еще никто не набрал, хотя многие близко (снизить до 5 из 4?).
  • Возможно нужны специальные занятия с отстающими.
  • Дедлайна нет, но так вы не успеете на остальные квесты (плюс вас будем ждать некоторое время).
• По оформлению
  • Используйте вики-ссылки.
  • Лишнее писать не обязательно. Ваше авторство зафиксировано.
    • Ну если вы не Участник:Ed.inozemtsev, Участник:Чеканов Кирилл
• Если еще и ссылка на проверочное решение — совсем замечательно.
  • Участник:Cherniavskii/Solutions/codechef/RIO1
  • Участник:Cherniavskii/Solutions/Leetcode/leetcode/maximum-number-of-darts-inside-of-a-circular-dartboard
• «Добрый день! Решаю задачу на codechef. Запустил свое решение, обернул весь в код try/except, но все равно на каких-то тестах возвращает RE, что это может значить? » [1]
  • Скорее всего таймлимит или падение. Если не получается, и жалко сил, — опубликуйте свой генератор тестовых данных, зачтем как задачу и бонусный балл — может следующие поколения добьют, или на сервере поправят таймлимит.

• Насчет ресерч части — если у вас есть что-то, что хотите потренировать срочно, можно начать с этого.

• Созвона завтра, 23го не будет.
• Вижу, что начали решать, так держать!
• Небольшой фидбек

• • все проверю в воскресенье, временно буду малодоступен.

• Пишем тест для регистрации на занятии.

• Начинаем работать.
  • Практикуемся В Алгоритмах

• Не вижу
  • Зарезервированные_практические_задачи
  • Категория:На проверку

На дом — проходим квест регистрации

• Lab

• Blog:Advanced Algorithms/Python-оптимизация алгоритма динамического программирования из codechef
• Blog:Advanced_Algorithms/Python-оптимизация жадного алгоритма из codechef
• Blog:Advanced Algorithms/Python-оптимизация алгоритма динамического программирования из codechef

Вопросы?

Кратко, что будет, чего не будет и что ждать.

• Лекций — не будет. Это бред и бессмыслица, особенно при дистанционке. Созвоны будут при небходимости, в формате семинара, может индивидуальные.
  • Асинхронная коллаборация — видеозаписи.
• Будет путешествие-квест, с разными активностями.
• Берем только практические вещи — алгоритмы для разных задач, особенно NP-полных.

Условно будет три блока

Базовая грамотность

• Python
• Простые алгоритмические задачи
• Нужно — везде, даже «собеседование в Яндекс на аналитика»
• Условно «уд»

Концептуально:

• Win-Win!
• Абсолютно практические задачи с собеседований.
  • LeetCode
  • CodeChef
  • SpojCode
  • Сотни решенных и нерешенных
• Условно поделены на «Dynamic Programming», «Greedy», «Random», «Sorting», «Numbers»
• Нужно быть залогиненным
  • Скрыто из интернета
• Изучайте Решенные практические задачи (Их там 1045)
• Надо решить N задач из 4 разных разделов. На Python.
  • 8 если до 2024-03-08
  • 12 если до 2024-04-08
  • 14 если до 2024-05-08
• За задачи из CodeChef и SpojCoding будут дополнительные бонусные очки (2 балла из настоящей 10 бальной оценки!), их решать сложнее, там не подсказывают тест вызвавший ошибку, там могут быть жесткие TL, надо больше стараться, и да, их надо решать именно на Python (любом, который есть на сервисе, хоть PyPy) оптимизировать вам могут помочь статьи:
  • Blog:Advanced_Algorithms/Python-оптимизация_жадного_алгоритма_из_codechef
  • Blog:Advanced_Algorithms/Python-оптимизация_алгоритма_динамического_программирования_из_codechef
  • Blog:Advanced_Algorithms/Путь_хакера_—_решение_задачи_с_codechef_на_питон._С_машинным_кодом
• Бонусные задачи вполне решаются, если их не боятся → вот из последних решений → Участник:Mishaglik/Solutions/Spoj/FRQPRIME

• Выбирайте задачи из Открытые практические задачи, переходите к редактированию по «Беру…» →

• • помечайте их как {{reserve-task|~~~~~}}
• Зарезервированные задачи убираются в Зарезервированные практические задачи

(Их там 87)

• • Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
• Решенное
  • Ну смотрите, как оформлено в прошлые годы
  • Решение на подстранице вашей личной страницы
    • Вики-ссылка на задачу
    • Python-код в «<source lang="python"></source>»
    • Метка «{{checkme}}», когда решите.

• • • Внизу вставка всего этого по клику →
• Они попадут в Категория:На проверку

(Их там 49)

• Как легче решать Python
  • Загрузка данных
  • Выбирайте более свежий CPython или PyPy.

Формулировка оптимизационных задач

• Pyomo
  • ЦЛП-постановки
• Jupyter-ноутбуки
• Lab
• Всегда способны решить (MVP-бизнес задачу)
• Условно «хор»

На отл:

• Набрать суммарные очки за тесты
  • например

• Теор-практический — взять некоторую тему из заданных (свежая статья, я отберу), и сделать ее разбор-презентацию-реализацию в каком-нибудь jupyter или cocalc-ноутбуке (там будет видно). Тут возможно будет и индивидуальная работа и может тренировка презентейшн скиллс, что полезно для ваших дипломов (сколько я смотрел защит, все ужасно).

Ну остальные новости будут в телеграм-чате, если что. Вопросы тоже там или напрямую.

Как зарегистрироваться — написано на основной странице курса, где все и будет https://discopal.ispras.ru/Advanced-algorithms

Регистраций открыта до 5 октября.

Подумайте еще раз — надо ли вам это. «Халявы», «Лекций», «Оценок за удаленную посещаемость» тут не будет. Даже «уд. нахаляву». Посмотрите, вокруг полно интересных курсов по выбору.

Курс в этом году выпал несколько сумбурный, ибо я пытался понять, почему получилась несколько разнородная группа, часть из которой проявляла мало активности, думал проблема в разности уровней и сильно занизил основную цель — вместо глубокой коллаборации с моделированием оптимизационных задач на юпитерноутбуках Lab, сконцентрировался на уровне «может решать простые алгоритмы на питон», «отпуская» тех, кому это явно скучно (хотя мне нравится, когда меня удивляют интересными подходами типа Blog:Advanced Algorithms/Путь хакера — решение задачи с codechef на питон. С машинным кодом).

Но оказалось, что многим из нашего списка вообще не нужны оценки, и собственно идея балансировки была не очень в тему («отпускать» надо было других).

Ну и ладно.

Учитывая, что с «вопросом — когда зачет и как» почему-то бегают к координатору, вместо того, чтобы спросить у меня (и хотя бы разок придти на созвон), пропишу все текстом.

• Оценки (хоть какие-то) выставил всем кому мог.
  • Если вы среди тех, кому оценка нужна, а у вас никакой нет — ну можно устроить что-то паллиативное типа «прохождение теста» (сборник из разбираемых ранее на созвонах вопросов) на «уд» (ну там хотя бы 50% баллов набрать).

Придете на созвон-зачет с тестом на «уд» 26 мая 2022?

Вы должны войти в систему, чтобы участвовать в этом голосовании.

• Хорошая новость для тех, кому нужна оценка получше. На самом деле, это базовый курс, и обычно^[1] эти оценки попадают в реальные журналы где-то в двадцатых числах июня. Т.е. есть возможность улучшить оценку, что есть, если интересно.

Win-Win → сами решайте, интересно ли, и тратить ли время (в целом, достаточно несложно).

→ продолжить чтение…

В процессе написания Blog:Advanced Algorithms/Python-оптимизация алгоритма динамического программирования из codechef, когда удалось получить питон-решение проходящее таймлимиты на PyPy, возник вопрос-челлендж, можно ли все-таки пройти этот квест на обычном питоне («CPython»).

Казалось, что это невозможно, ведь CPython грубо получает таймлимит больше в 2.5 раза, чем для PyPy (но это совсем небольшая фора), и для PyPy мы еле-еле вписались, а по нашим оценкам, наш же алгоритм на CPython работал на порядок медленней. Возможно ожидалась какая-то магия с использованием модулей numpy или collections, чтобы по сути, дергать питоном функции, написанные на си или даже высокообогащенном оружейном фортране.

Другие методы оптимизации — отдельные скомпилированные модули на С, компиляция Cython или Nuitka, тут явно невыполнимы — на вход принимается только один питон-файл.

Но оказалось, есть еще и путь хакера.

import copy
import ctypes
import mmap
import sys
 
DIGITS = 19
DP_SIZE = DIGITS * 2 * 2
 
 
def get_input():
    lines = sys.stdin.readlines()
    data = ' '.join(lines).strip()
 
    for token in data.split():
        yield token
 
 
func_bytes = (b'AWA\x89\xf7AVA\x89\xfeAUA\x89\xd5ATUSH\x83\xec8\x85\xd2u5Hc\xc7E1'
              b'\xe4\x8b,\x81\x85\xedy-C\x8d\x04wA\x8dDE\x00H\x98M\x89$\xc1H\x83\xc48L'
              b'\x89\xe0[]A\\A]A^A_\xc3\x0f\x1f\x80\x00\x00\x00\x00\xbd\t\x00\x00\x00A\x8d~'
              b'\x01D\x89\xc0H\x8bt$p)\xf8E\x85\xffH\x98A\x0f\x95\xc2L\x8d\x1c\xc6A9\xf8t'
              b'k\x8d\x04?1\xdbE1\xe4\x89D$\x08\x83\xfb\x02t\x19E\x84\xd2u\x14\x83'
              b'\xfb\x07\x0f\x87|\x00\x00\x00\xb8\xa8\x00\x00\x00H\x0f\xa3\xd8sq9\xddu51'
              b'\xd2\xbe\x01\x00\x00\x00E\x85\xedu)\x8bD$\x08\x01\xf0\x8d\x04BH\x98I\x8b'
              b'\x04\xc1H\x83\xf8\xfftdI\x01\xc4\x83\xc3\x019\xdd}\xb3\xe9U\xff\xff\xff\x0f'
              b'\x1fD\x00\x00M\x03#\xeb\xea\x0f\x1f\x001\xc0E1\xe4\xba\xa8\x00'
              b'\x00\x00\x83\xf8\x02t\x10E\x84\xd2u\x0b\x83\xf8\x07w\nH\x0f\xa3\xc2s\x04I'
              b'\x83\xc4\x01\x83\xc0\x019\xc5}\xe0\xe9\x19\xff\xff\xff\x909\xdd\x0f\x95'
              b'\xc2E\x85\xed\x0f\x95\xc01\xf6\t\xc2\x0f\xb6\xd2\xeb\x8b\x0f\x1f@\x00D\x88T$'
              b'/H\x83\xec\x08L\x89\\$(\xfft$xL\x89L$(D\x89D$8H\x89L$ \x89|$\x1c\xe8\xae\xfe'
              b'\xff\xffI\x01\xc4XZ\x8b|$\x0cH\x8bL$\x10D\x8bD$(L\x8bL$\x18L\x8b\\$ D'
              b'\x0f\xb6T$/\xe9M\xff\xff\xff')
 
assert len(func_bytes) <= mmap.PAGESIZE
 
func_buffer = mmap.mmap(-1, mmap.PAGESIZE, prot=mmap.PROT_READ | mmap.PROT_WRITE | mmap.PROT_EXEC)
 
func_type = ctypes.CFUNCTYPE(ctypes.c_longlong, ctypes.c_int, ctypes.c_int, ctypes.c_int, ctypes.POINTER(ctypes.c_int),
                             ctypes.c_int, ctypes.POINTER(ctypes.c_longlong), ctypes.POINTER(ctypes.c_longlong))
func_pointer = ctypes.c_void_p.from_buffer(func_buffer)
 
func = func_type(ctypes.addressof(func_pointer))
func_buffer.write(func_bytes)
 
token_generator = get_input()
next(token_generator)
 
dp = (ctypes.c_longlong * DP_SIZE)(*(-1 for _ in range(DP_SIZE)))
p10 = (ctypes.c_longlong * DIGITS)(*(10 ** i for i in range(DIGITS)))
 
for input_str in token_generator:
    N = len(input_str)
    input_digits = (ctypes.c_int * N)(*(int(ch) for ch in input_str))
 
    print(func(0, 0, 0, input_digits, N, copy.copy(dp), p10))

Идея — будем действовать как JIT. Мы можем переписать кусок кода на си, взять получившийся машинный код, внутри питона его записать в динамически выделенную память и запустить.

Мы можем выделить память с разрешением на чтение, запись и исполнение. Запись понятно для чего, а разрешение на исполнение означает, что процессор может сделать jmp или call в эту область и не крешнуться (разрешение на чтение казалось бы не нужно, но как ни странно, на x86-64 для исполнения также нужно разрешение на чтение):

func_buffer = mmap.mmap(-1, mmap.PAGESIZE, prot=mmap.PROT_READ | mmap.PROT_WRITE | mmap.PROT_EXEC)

Дальше мы пользуемся библиотекой ctypes в питоне — она позволяет из питона вызывать сишные функции. Для этого нам нужно указать какие аргументы наша функция будет принимать и что возвращать (чтобы питоновский код знал как нужно передавать аргументы перед тем как сделать call в наш код, а также как распарсить ответ):

func_type = ctypes.CFUNCTYPE(ctypes.c_longlong, ctypes.c_int, ctypes.c_int, ctypes.c_int, ctypes.POINTER(ctypes.c_int),
                             ctypes.c_int, ctypes.POINTER(ctypes.c_longlong), ctypes.POINTER(ctypes.c_longlong))

Вот как это соответствует нашей сишной функции:

int64_t calculate(int i, int taken, int ls, int *input_digits, int N, int64_t *dp, int64_t *p10)

Дальше нам нужно создать объект сишной функции и записать байты (о них дальше) в выделенную память:

func_pointer = ctypes.c_void_p.from_buffer(func_buffer)
func = func_type(ctypes.addressof(func_pointer))
func_buffer.write(func_bytes)

И после всего этого мы можем вызывать эту функцию как обычно, только нужно передавать аргументы нужных типов:

dp = (ctypes.c_longlong * DP_SIZE)(*(-1 for _ in range(DP_SIZE)))
p10 = (ctypes.c_longlong * DIGITS)(*(10 ** i for i in range(DIGITS)))
 
for input_str in token_generator:
    N = len(input_str)
    input_digits = (ctypes.c_int * N)(*(int(ch) for ch in input_str))
 
    print(func(0, 0, 0, input_digits, N, copy.copy(dp), p10))

Теперь о том как получить нужный машинный код и как вообще выбрать что компилировать.

Наши возможности в том что мы можем запустить довольно ограничены — мы не можем запустить что-либо что использует какие-либо библиотеки, потому что мы загружаем не «честный ELF», в котором можно подгружать библиотеки, делать релокации и многое другое, а только набор машинных инструкций. Это значит что мы не можем использовать ничего из libc — то есть без ввода/вывода, динамического выделения памяти, ничего из стандартной библиотеки плюсов — то есть без каких-либо структур данных сложнее статического массива.

Поэтому идеальный кандидат — функция calculate из оригинального кода на питоне. Она как раз использует только массивы фиксированного размера и простые операции:

def calculate(i, taken, ls):
    """
    i — индекс цифры
    taken — встречали ли простые цифры раньше
    ls — в текущем индексе можно делать полный перебор
    """
    global input_digits
    global dp
    global N
 
    limit = 9
 
    if not ls:
        limit = input_digits[i]
 
    res = 0
 
    for x in range(limit + 1):
        newtaken = taken or (x == 2) or (x == 3) or (x == 5) or (x == 7)
        newi = i + 1
 
        if newi == N:
            ret = newtaken
        else:
            newls = ls or (x != limit)
 
            if newls and newtaken:
                ret = p10[N - newi]
            else:
                cached = dp[newtaken][newls][newi]
 
                if cached != -1:
                    ret = cached
                else:
                    ret = calculate(newi, newtaken, newls)
 
        res += ret
 
    dp[taken][ls][i] = res
 
    return res

API ctypes позволяет нам запускать сишные функции — поэтому ее и напишем:

// file: inline.c
# include <stdint.h>
 
int64_t calculate(int i, int taken, int ls, int *input_digits, int N, int64_t *dp, int64_t *p10) {
    int limit = 9;
 
    if (!ls) {
        limit = input_digits[i];
    }
 
    int64_t res = 0;
 
    for (int x = 0; x <= limit; ++x) {
        int new_taken = taken || (x == 2) || (x == 3) || (x == 5) || (x == 7);
        int new_i = i + 1;
        int64_t ret;
 
        if (new_i == N) {
            ret = new_taken;
        } else {
            int new_ls = ls || (x != limit);
 
            if (new_ls && new_taken) {
                ret = p10[N - new_i];
            } else {
                int64_t cached = dp[4 * new_i + 2 * new_taken + new_ls];
 
                if (cached != -1) {
                    ret = cached;
                } else {
                    ret = calculate(new_i, new_taken, new_ls, input_digits, N, dp, p10);
                }
            }
        }
 
        res += ret;
    }
 
    dp[4 * i + 2 * taken + ls] = res;
 
    return res;
}

(глобальные переменные мы создаем на стороне питона и передаем как аргументы, также мы преобразовали многомерный массив dp в одномерный, чтобы не париться с указателями)

Дальше нам нужно это скомпилировать, и нужно передать некоторые нестандарные флаги. Обычно исполнение ELF начинается не с main, а с функции _start, которая вызывает функцию __libc_start_main из libc, которая подгружает переменные окружения, argv и многое другое, а только потом запускает main. Нам ничего такого не нужно, поэтому мы это отключаем с помощью флага -nostartfiles, и к тому же без этого компилятор ожидал бы от нас функцию main, которую мы писать не хотим. Также можем добавить -nolibc чтобы не было соблазна вызывать функции оттуда, хотя на результат это не повлияет. И конечно -O3 чтобы получить все оптимизации что есть.

$ gcc inline.c -nostartfiles -nolibc -o inline -O3

Можем проверить что в секции .text у нас лежит одна единственная функция (-d — вывод дизассемблера секции с кодом, -M intel — чтобы получить вывод в намного более приятном интеловском синтаксисе, а не в AT&T):

$ objdump -d -M intel inline
 
inline: file format elf64-x86-64
 
 
Disassembly of section .text:
 
0000000000001000 <calculate>:
    1000:       41 57                   push   r15
    1002:       41 89 f7                mov    r15d,esi
    1005:       41 56                   push   r14
    1007:       41 89 fe                mov    r14d,edi
    100a:       41 55                   push   r13
    100c:       41 89 d5                mov    r13d,edx
    100f:       41 54                   push   r12
    1011:       55                      push   rbp
    1012:       53                      push   rbx
    1013:       48 83 ec 38             sub    rsp,0x38
    1017:       85 d2                   test   edx,edx
    1019:       75 35                   jne    1050 <calculate+0x50>
    101b:       48 63 c7                movsxd rax,edi
    101e:       45 31 e4                xor    r12d,r12d
    1021:       8b 2c 81                mov    ebp,DWORD PTR [rcx+rax*4]
    1024:       85 ed                   test   ebp,ebp
    1026:       79 2d                   jns    1055 <calculate+0x55>
    1028:       43 8d 04 77             lea    eax,[r15+r14*2]
    102c:       41 8d 44 45 00          lea    eax,[r13+rax*2+0x0]
    ...
    ...

Также стоит заметить что наш код не использует никаких глобальных переменных, а значит нам нужна только секция .text из ELF. И еще все инструкции jmp и call используют относительные оффсеты для прыжков, поэтому наш код может быть загружен по любому адресу памяти, что нам и нужно, так как мы не можем полностью контроллировать какой адрес вернет mmap.

Нам осталось сдампить байты нашей функции в отдельный файл (-O binary = вывести сырые байты, -j .text = работать с секцией .text):

$ objcopy -O binary -j .text inline inline_bytes

И записать получившиеся байты внутрь кода в питоне, например так можно получить строку байт чтобы скопировать:

from pprint import pprint
 
with open('inline_bytes', 'rb') as f:
     pprint(f.read())

Какой будет вывод:

(b'AWA\x89\xf7AVA\x89\xfeAUA\x89\xd5ATUSH\x83\xec8\x85\xd2u5Hc\xc7E1'
 b'\xe4\x8b,\x81\x85\xedy-C\x8d\x04wA\x8dDE\x00H\x98M\x89$\xc1H\x83\xc48L'
 b'\x89\xe0[]A\\A]A^A_\xc3\x0f\x1f\x80\x00\x00\x00\x00\xbd\t\x00\x00\x00A\x8d~'
 b'\x01D\x89\xc0H\x8bt$p)\xf8E\x85\xffH\x98A\x0f\x95\xc2L\x8d\x1c\xc6A9\xf8t'
 b'k\x8d\x04?1\xdbE1\xe4\x89D$\x08\x83\xfb\x02t\x19E\x84\xd2u\x14\x83'
 b'\xfb\x07\x0f\x87|\x00\x00\x00\xb8\xa8\x00\x00\x00H\x0f\xa3\xd8sq9\xddu51'
 b'\xd2\xbe\x01\x00\x00\x00E\x85\xedu)\x8bD$\x08\x01\xf0\x8d\x04BH\x98I\x8b'
 b'\x04\xc1H\x83\xf8\xfftdI\x01\xc4\x83\xc3\x019\xdd}\xb3\xe9U\xff\xff\xff\x0f'
 b'\x1fD\x00\x00M\x03#\xeb\xea\x0f\x1f\x001\xc0E1\xe4\xba\xa8\x00'
 b'\x00\x00\x83\xf8\x02t\x10E\x84\xd2u\x0b\x83\xf8\x07w\nH\x0f\xa3\xc2s\x04I'
 b'\x83\xc4\x01\x83\xc0\x019\xc5}\xe0\xe9\x19\xff\xff\xff\x909\xdd\x0f\x95'
 b'\xc2E\x85\xed\x0f\x95\xc01\xf6\t\xc2\x0f\xb6\xd2\xeb\x8b\x0f\x1f@\x00D\x88T$'
 b'/H\x83\xec\x08L\x89\\$(\xfft$xL\x89L$(D\x89D$8H\x89L$ \x89|$\x1c\xe8\xae\xfe'
 b'\xff\xffI\x01\xc4XZ\x8b|$\x0cH\x8bL$\x10D\x8bD$(L\x8bL$\x18L\x8b\\$ D'
 b'\x0f\xb6T$/\xe9M\xff\xff\xff')

И это нужно скопировать, чтобы можно было в codechef послать только один файл:

func_bytes = (b'AWA\x89\xf7AVA\x89\xfeAUA\x89\xd5ATUSH\x83\xec8\x85\xd2u5Hc\xc7E1'
              b'\xe4\x8b,\x81\x85\xedy-C\x8d\x04wA\x8dDE\x00H\x98M\x89$\xc1H\x83\xc48L'
              b'\x89\xe0[]A\\A]A^A_\xc3\x0f\x1f\x80\x00\x00\x00\x00\xbd\t\x00\x00\x00A\x8d~'
              b'\x01D\x89\xc0H\x8bt$p)\xf8E\x85\xffH\x98A\x0f\x95\xc2L\x8d\x1c\xc6A9\xf8t'
              b'k\x8d\x04?1\xdbE1\xe4\x89D$\x08\x83\xfb\x02t\x19E\x84\xd2u\x14\x83'
              b'\xfb\x07\x0f\x87|\x00\x00\x00\xb8\xa8\x00\x00\x00H\x0f\xa3\xd8sq9\xddu51'
              b'\xd2\xbe\x01\x00\x00\x00E\x85\xedu)\x8bD$\x08\x01\xf0\x8d\x04BH\x98I\x8b'
              b'\x04\xc1H\x83\xf8\xfftdI\x01\xc4\x83\xc3\x019\xdd}\xb3\xe9U\xff\xff\xff\x0f'
              b'\x1fD\x00\x00M\x03#\xeb\xea\x0f\x1f\x001\xc0E1\xe4\xba\xa8\x00'
              b'\x00\x00\x83\xf8\x02t\x10E\x84\xd2u\x0b\x83\xf8\x07w\nH\x0f\xa3\xc2s\x04I'
              b'\x83\xc4\x01\x83\xc0\x019\xc5}\xe0\xe9\x19\xff\xff\xff\x909\xdd\x0f\x95'
              b'\xc2E\x85\xed\x0f\x95\xc01\xf6\t\xc2\x0f\xb6\xd2\xeb\x8b\x0f\x1f@\x00D\x88T$'
              b'/H\x83\xec\x08L\x89\\$(\xfft$xL\x89L$(D\x89D$8H\x89L$ \x89|$\x1c\xe8\xae\xfe'
              b'\xff\xffI\x01\xc4XZ\x8b|$\x0cH\x8bL$\x10D\x8bD$(L\x8bL$\x18L\x8b\\$ D'
              b'\x0f\xb6T$/\xe9M\xff\xff\xff')

Вот и все!