Не так давно довелось спонтанно поучаствовать в активности от T‑банка. Кроме всяких «интересных» заданий, там были задачки и на кодинг. Критерием победы в задачах «Стековки» были не O(n), не микросекунды, а краткость кода, твёрдо измеренная в символах, что тоже по своему интересно. «Как написать решение используя минимальное число символов?».
С одной стороны это были задания на компактный алгоритм, с другой стороны – на знания возможностей языка. Я к такого рода задачам не готовился, но по ходу дела мне показалось, что приёмы, которые можно придуматьприменить при таких метриках, вполне стоило бы обобщить, структурировать, и применять уже с меньшими когнитивными нагрузками. Заинтересовало? Добро пожаловать за странными конструкциями и хацкер-бонусом.
Некоторые особенности
Поскольку в текущих условиях пробелы и переносы строк не считаются, то очевидный совет использовать при необходимости отступы не в 4 пробела, а только в 1 – не имеет смысла. Тут даже напротив, разумнее написать две строки
print("Hello")
print("World")чем ужиматься в прокрустово ложе однострочника:
print("Hello");print("World")Ведь разделитель в виде переноса строки бесплатен, а ";" – целый штрафной символ! Так что все дальнейшие подходы, приёмы и метрики будут неявно исходить из бесплатности пробелов и переносов.
Функции как способ DRY
Сперва рассмотрим пару вариантов объявления переиспользуемой функции, а потом сделаем неутешительный вывод о накладных расходах:
def a(b): return bЦелых 15 символов. Но возвращать значения внезапно дешевле так:
a = lambda b:bВсего 11 символов! Обещанный же печальный вывод в том, что даже 10 символов накладных расходов на объявление – это много. Предположим, что повторяемый код вычисляет сумму цифр половины счастливого билетика
sum(map(int, d)) == sum(map(int, b))Как ни странно – а лучше оставить как есть. 10 символов на объявление, 15 символов кода, да ещё два раз по 4 символа на вызов, вот и получили 33 символа, что больше чем просто два раза повторить код в 15 символов. Отсюда можно вывести критерий окупаемости lambda-функции, действующий код в которой равен L символам, и имеет в дальнейшем N вызовов:
Можно даже на будущее прикинуть для некоторого диапазона значений (вряд ли можно ожидать в такого рода задачах больших значений):
N\L | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
2 | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ✅ |
3 | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
4 | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
Псевдонимы
По образу и подобию пункта выше сразу приходим к выводу, что выгодность объявления псевдонимов встроенным функциям зависит от повторяемости и длины функции.
p=print
p("hello")
p("word")
На этот раз неочевидность в том, что выгода от такого подхода наступает очень быстро, буквально с трёх повторений, даже на коротких функциях:
N\L | 3 | 4 | 5 |
2 | ❌ | ❌ | ✅ |
3 | ✅ | ✅ | ✅ |
Немного технического
Просто список того что лежит на поверхности, но пусть будет, чтобы не забыть в стрессе:
from package import *– плохо в продакшене, но экономия на множественных импортах.from package import some_function as f– псевдоним сразу при импортеa, b, c = 1, 2, 3– распаковки.i+=1; j*=2; k/=2инкременты[:2]; [::]– слайсы, со всеми своими возможностями (а также налогом в три штрафных символа).[i*2 for i in range(2)]– comprehensions
Циклы
Кроме использования списковых и прочих включений первейший помощник в краткой форме записи, это конечно map (особенно когда дело доходит до обработки input()). Где-то рядом находится потенциально полезные zip и reduce (но этот тянет за собой солидный штраф в виде импорта)
# иногда map (без лямбды)
s = '123456'
a = [int(_) for _ in s] # 17
b = map(int, s) # 12, но на руках генератор
c = list(map(int, s)) # 18 - приведение к списку проиграет comprehension символ
d = [*map(int, s)] # 15 если применить распаковку итератора
*e, = map(int, s) # 14, если произвести распаковку с присваиванием (и упрощённым объявлением tuple, без скобок)
# иногда comprehension (что-то односложное, но для map нужна уже lambda)
a = [int(_)*2 for _ in s] # 19
b = map(lambda x: int(x)*2, s) # 25 (!) и на руках генераторКроме того, в этом же разделе также рассмотрим способ приведения последовательности в строку через join. Зачастую, это нужно в аккурат чтобы вывести в stdout решение задачи. Так что рассмотрим различные подходы к задачи формирования строки - и её вывода. Эталонный вариант на 17 символов, когда у нас есть готовая последовательность, и бонусом - возможность настроить разделитель, в т.ч. для формирования непрерывной строки:
s = [1,2,3,4,5,6]
print(''.join(s)) #17Однако точнее приглядеться к деталям можно, если предположить, что где-то уже был цикл для формирования чего-то там:
s = '123456'
a = [int(_) * 2 for _ in s] # 19
print(''.join(a)) # 19+17=36
# ИЛИ
print(''.join([int(_)*2 for _ in s])) # 33Как будто бы кратко, но при этом мы заплатили налог на join в размере 6 символов. А можно ли вообще без него? Можно! (Кроме того, пример выше не полон, и сломается, т.к. str.join() хочет последовательность строк, так что на последовательности чисел - выгода ещё больше):
s = '123456'
print(*(int(_) * 2 for _ in s), sep='') # 32 за счёт распаковки + возможность настроить разделитель
for _ in s: print(int(_) * 2, end='') # 30 + возможность настроить разделитель
for _ in s: print(end=int(_) * 2) # 27, но снова ограничения на тип строкЕсли же всё-таки на руках готовая последовательность, можно совместить распаковку с отказом от разделителей (и без дополнительного приведения типа элементов к строке).
s = '123456'
print(''.join([int(_)*2 for _ in s])) # 33Приведение типа и условия
Явное и неявное приведение типа в Python позволяет разные приятные мелочи, в том числе взять и пройти вот такую цепочку оптимизации
if a==b:
print('A')
else:
print('B')
# ИЛИ
print('A') if a==b else print('B')
# ИЛИ
print('A' if a==b else 'B')
# ИЛИ сложное приведение типа строки в булево и ленивые вычисления
print(a==b and 'A' or 'B')
# ИЛИ сложное приведение типа условия в int и ленивые вычисления
print(a==b and 'A' or 'B')
# ИЛИ явно по типу (неоптимально, но наглядно)
print({True:'A', False: 'B'}[a==b])
# ИЛИ неявно по приведённому типу int(bool) по индексу
print(['B','A'][a==b])
# ИЛИ неявно по приведённому типу int(bool) по индексу внутри строки
print('BA'[a==b])А отсюда уже и один шаг до тёмной магии:
На вход подается шесть цифр – номер билета. Выведите YES, если сумма первых трёх цифр равна сумме последних трех, иначе выведите NO.
Скрытый текст
Перемешать строку, чтобы получить правильный индекс начала для слайса, и с заданным шагом в два символа получить нуж��ую подстроку
v = list(map(int,input()))
b = sum(v[:3])!=sum(v[3:])
print('YNEOS'[b::2])
Если взять в одну руку богатство строковых операций, шаблонификаций, в другую - тот факт что принцип DRY не всегда работает на экономию символов, а в третью – eval() то, чисто в теории, можно за счёт трюков со строками собрать из кусочков компактного текста более объёмный и выполнить его в eval, с тем чтобы сэкономить символ другой. К задачам ивента этого я эффективно применить не смог, но вообще, как метод - это работает:
c = input()
t = 'sum(map(int,c[%s]))'
b = eval(f"%s!=%s"%(t%':3',t%'3:'))
print('YNEOS'[b::2])Скорее это даже можно отнести к альтернативным методам объявления и вызова переиспользуемой функции, но накладные расходы на форматирование шаблонов оказываются довольно высокими, увы. С другой стороны, это настраивает на должный лад, чтобы перейти к обещанным попыткам найти в возможностях языка что-нибудь особенно тонкого и полезного.
Батарейки входят в комплект
Как известно, простейший способ вывести в консоль "Hello world!" – вот такой:
from __hello__ import main
main()Так что идеальное решение задач на краткость кода должно выглядеть как-то так:
import winДевять символов, красивые в своей лаконичности. Доля истины в том, что в "идеальном конечном результате"™ нам нужно взять взять конечное решение "откуда-то", а не писать самим. Что можно попробовать?
Скачать
Решение на основе exec и встроенных инструментов http-запросов. Возможные минусы:
Решение кодом по существу может оказаться короче
Проверочная платформа скорее всего не пропустит запрос наружу. :(
Вот рабочее решение, к сожалению, не сработавшее в песочнице для проверок решения:
from urllib.request import *
exec(urlopen("https://clck.ru/3Q6mzY").read())также подметим пару удобных тонкостей:
.read() вернёт байтовую строку
exec ест не только строковые представления строк кода, но и байтовые
Проверить ограничения платформы
Одна из первых гипотез, которая пришла в голову. "Ну а вдруг описание модуля – не считается за код". Не сработало. Но вы пробуйте обязательно, мало ли как настроены проверки будут именно в вашем случае.
"""a=lambda b:sum(map(int,b))
c=input()
print('YES'if a(c[:3])==a(c[3:]) else'NO')"""
exec(__doc__)(но если бы сработало, было бы очень-очень близко к идеальному решению, да)
Сжать-разжать
Ещё один сумрачный способ – сжать код в zip, потом сжатый код и его разжатие-выполнение собственно и запускать. На практике бинарные данные получаются очень многосимвольными, с точки зрения текстового представления, а степень сжатия для столь малых объёмов кода – чуть ли не отрицательная. (BASE64 и вовсе увеличивает объём на треть) Запоминаем, и переходим к...
Эврика
Что ж, раз сжатые бинарные данные выглядят как многосимвольная каша b'x\xdaK\xb4\xcdI\xccMJITH\xb2*.\xcd\xd5\xc8M,\xd0\xc8\xcc+ нужно:
Действовать без сжатий
Оставаться в пределах ANCII
Сделать так, чтобы нас "посчитали правильно"
и вот тут мы вспоминаем, что "пробелы и переносы строк не считаются".
print(0)
# ИЛИ
text = 'print(0)'
exec(text)
codes = []
for _ in text:
codes.append(ord(_))
print(ord(_))
# ИЛИ
line = ''.join(chr(_) for _ in codes)
exec(line)В коде выше мы увидим посимвольное кодирование-раскодирование-выполнение, а также вывод в консоль:
112
114
105
110
116
40
48
41Набор чисел, который легко можно представить в виде строк из пробелов, соответствующей длины:
░░░░░░...112░
░░░░░░░...114░
░░░░...105░
░░░░░...110░
░░░░...112░
░...40░
░░░░...48░
░░...41░И соответственно в виде кода:
v="""░░░░░░...112░
░░░░░░░...114░
░░░░...105░
░░░░░...110░
░░░░...112░
░...40░
░░░░...48░
░░...41░"""
codes=map(len,a.split('\n')Помня о том, что exec готов принимать байтовые строки, можем обойтись и без chr:
exec(bytes(map))Таким образом, можно поджать-собрать код в многострочный однострочник:
exec(bytes(map(len,"""░░░░░░...112░
░░░░░░░...114░
░░░░...105░
░░░░░...110░
░░░░...112░
░...40░
░░░░...48░
░░...41░""".split('\n'))))Можно ли сделать лучше? Можно, но только при допущении, что знак табуляции тоже не считается. Тогда, примирив сторонников пробелов и табуляции, сэкономим на задании символа в split и лишних кавычках многострочника:
exec(bytes(map(len,'░░░░░░...112░→░░░░░░░...114░→░░░░...105░→░░░░░...110░→░░░░...112░→░...40░→░░░░...48░→░░...41░'.split('→'))))34 символа (независимо от объёма кода), то что надо. Код выше нагляден, но не работает. Поэтому для самостоятельной проверки привожу простой кодогенератор:
line = b"print(0)"
lines = (' ' * b for b in line)
with open('prod.py', 'w') as file:
file.write(f'exec(bytes(map(len,"{'\t'.join(lines)}".split("\t"))))')и рабочий, но не очень наглядный результат его работы (prod.py):
exec(bytes(map(len," ".split(" "))))34 символа, можете пересчитать сами). Удачи в странных задачах и их условиях, и пишите в комментариях, как ещё можно уплотнять код, ведь наверняка я много чего упустил.
P.S. Пользуясь случаем,Т-Банк, от лица всех участников Стековки прошу у вас небольшую статью в которой будут условия задачек, и конечно же - решения из лидербордов, многие решения там содержали весьма вдохновляющие значения!