Не так давно довелось спонтанно поучаствовать в активности от 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 вызовов:

Можно даже на будущее прикинуть для некоторого диапазона значений (вряд ли можно ожидать в такого рода задачах больших значений):

Псевдонимы

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

p=print
p("hello")
p("word")

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

Немного технического

Просто список того что лежит на поверхности, но пусть будет, чтобы не забыть в стрессе:

• 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 символ

# иногда 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'
for _ in s: print(int(_) * 2, end='')  # 30 и возможность настроить разделитель
for _ in s: print(end=int(_) * 2)  # 27, но снова ограничения на тип строк

Приведение типа и условия

Явное и неявное приведение типа в 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({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. Пользуясь случаем,Т-Банк, от лица всех участников Стековки прошу у вас небольшую статью в которой будут условия задачек, и конечно же - решения из лидербордов, многие решения там содержали весьма вдохновляющие значения!