Путь хакера — решение задачи с codechef на питон. С машинным кодом

Ссылки сюда (15) →

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

Дальше тут написать про фишки как тут загрузка происход а дальше расписать, как получен этот код (от ассемблерного кода и алгоритма до этой магической строки…)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

— Стас Фомин • 02:27, 19 мая 2022 • нет комментариев