Путь хакера — решение задачи с codechef на питон. С машинным кодом
В процессе написания Blog:Advanced Algorithms/Python-оптимизация алгоритма динамического программирования из codechef, когда удалось получить питон-решение проходящее таймлимиты на PyPy, возник вопрос-челлендж, можно ли все-таки пройти этот квест на обычном питоне («CPython»).
Казалось, что это невозможно, ведь CPython грубо получает таймлимит больше в 2.5 раза, чем для PyPy, и для PyPy мы еле-еле вписались, а по нашим оценкам, наш же алгоритм на CPython работал на порядок медленней. Возможно ожидалась какая-то магия с использованием модулей numpy или collections, чтобы по сути, дергать питоном написанные на си или даже высокообогащенном оружейном фортране функции.
Другие методы оптимизации — отдельные скомпилированные модули на С, компиляция Cython или Nuitka, тут явно невыполнимы — на вход принимается только один питон-файл.
Но оказалось, есть еще и путь хакера.
Указан неподдерживаемый язык.
Вы должны указать язык следующим образом: <source lang="html4strict">...</source>
Поддерживаемые языки:
4cs, 6502acme, 6502kickass, 6502tasm, 68000devpac, abap, actionscript, actionscript3, ada, algol68, apache, applescript, apt_sources, arm, asm, asp, asymptote, autoconf, autohotkey, autoit, avisynth, awk, bascomavr, bash, basic4gl, bf, bibtex, blitzbasic, bnf, boo, c, c_loadrunner, c_mac, caddcl, cadlisp, cfdg, cfm, chaiscript, cil, clojure, cmake, cobol, coffeescript, cpp, cpp-qt, csharp, css, cuesheet, d, dcl, dcpu16, dcs, delphi, diff, div, dos, dot, e, ecmascript, eiffel, email, epc, erlang, euphoria, f1, falcon, fo, fortran, freebasic, freeswitch, fsharp, gambas, gdb, genero, genie, gettext, glsl, gml, gnuplot, go, groovy, gwbasic, haskell, haxe, hicest, hq9plus, html4strict, html5, icon, idl, ini, inno, intercal, io, j, java, java5, javascript, jquery, kixtart, klonec, klonecpp, latex, lb, ldif, lisp, llvm, locobasic, logtalk, lolcode, lotusformulas, lotusscript, lscript, lsl2, lua, m68k, magiksf, make, mapbasic, matlab, mirc, mmix, modula2, modula3, mpasm, mxml, mysql, nagios, netrexx, newlisp, nsis, oberon2, objc, objeck, ocaml, ocaml-brief, octave, oobas, oorexx, oracle11, oracle8, oxygene, oz, parasail, parigp, pascal, pcre, per, perl, perl6, pf, php, php-brief, pic16, pike, pixelbender, pli, plsql, postgresql, povray, powerbuilder, powershell, proftpd, progress, prolog, properties, providex, purebasic, pycon, pys60, python, q, qbasic, rails, rebol, reg, rexx, robots, rpmspec, rsplus, ruby, sas, scala, scheme, scilab, sdlbasic, smalltalk, smarty, spark, sparql, sql, stonescript, systemverilog, tcl, teraterm, text, thinbasic, tsql, typoscript, unicon, upc, urbi, uscript, vala, vb, vbnet, vedit, verilog, vhdl, vim, visualfoxpro, visualprolog, whitespace, whois, winbatch, xbasic, xml, xorg_conf, xpp, yaml, z80, zxbasic
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))
Дальше тут написать про фишки как тут загрузка происход а дальше расписать, как получен этот код (от ассемблерного кода и алгоритма до этой магической строки…)
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.