Новогодний контест

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

Для более сложных уровней можно было написать перебор, стартующий с всевозможных целых чисел, которые можно составить из «разрешённых» цифр, и генерирующий все выражения длин 1, 2, 3, и так далее путём составления всё более сложных и сложных выражений. Важно не запутаться в приоритетах, но LLM отлично пишет такой код.

В некоторых уровнях можно было также добавить дробные числа или числа в экспоненциальной записи (4e6), чтобы найти оптимальное выражение. Сделать это просто: достаточно лишь добавить такие числа в набор стартовых чисел, с которых начинается перебор. Кроме того, полезно начать использовать операцию логического отрицания к числу ~. Например, ~1 == -2 (объяснение, почему так).

Следующая группа уровней была посвящена шестнадцатеричной системе счисления, ведь она позволяет составлять выражения вообще без использования цифр! Решение тем не менее не меняется, достаточно лишь добавить и шестнадцатеричные числа в список стартовых, если уж никакие цифры, кроме нуля, использовать нельзя. Ноль нужен, так как шестнадцатеричные числа в питоне записываются как 0xBEA.

Но что делать, если запрещено использовать все цифры и даже ноль? Здесь на помощь придёт константа True, ведь True == 1 («Why is bool a subclass of int?»)! Таким образом, можно составить выражения, используя только True: например, (True+True<<True+True)+True == 9. Для этого нужно составить выражение, используя только единицы, а затем заменить все единицы на «True». Ну а для этого у нас уже готов код! Надо лишь упростить список стартовых чисел до [1] — ничего, кроме единицы, теперь использовать нельзя.

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

Последние уровни были посвящены случаю, когда запрещена и буква «e», а, значит, написать True больше нельзя... В этом случае единицу нужно заменить на not[]. Ну а если и квадратные скобки запрещены, то на not() или ()==() — ограничения были достаточно мягкими.

Примечание: операции вида ~(not[]) работают, но вызывают предупреждение в современном питоне:

>>> ~(not[])
<stdin>:1: DeprecationWarning: Bitwise inversion '~' on bool is deprecated and will be removed in Python 3.16. This returns the bitwise inversion of the underlying int object and is usually not what you expect from negating a bool. Use the 'not' operator for boolean negation or ~int(x) if you really want the bitwise inversion of the underlying int.
-2
        

К счастью, на дворе 2026, а питон 3.16 выйдет только в 2027 ;-)

Примечание 2: во время контеста участники нашли элегантный способ получать числовые константы:

b'"'[b''<b'']*b'K'[b''<b'']-b'\n'[b''<b'']

Кайф!

Я не знаю способа решить эту задачу лучше перебора (расскажите, если знаете!). Более того, существующие LLM с возможностью запускать код неплохо справляются перебирать ответы и находить правильный. Единственная проблема, которая может возникнуть, — ограничение по времени. Нам нужно перебирать достаточно эффективно, чтобы успеть пройти все уровни за пять часов контеста! В этом и заключалась основная сложность этой задачи.

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

Для более сложных уровней подойдёт тривиальный перебор всех возможных загаданных последовательностей и проверка каждой из них.

MAX_NUMBER = 10
NUMBER_COUNT = 4

for secret in itertools.permutations(range(1, MAX_NUMBER), NUMBER_COUNT):
    if is_valid(secret):
        return secret

def is_valid(secret: list[int]) -> bool:
    for numbers, bulls, cows in guesses:
        if score(secret, numbers) != (bulls, cows):
            return False
    return True

def score(secret: list[int], guess: list[int]) -> tuple[int, int]:
    bulls = sum(1 for i in range(len(secret)) if secret[i] == guess[i])
    common = len(set(secret) & set(guess))
    return bulls, common - bulls

Для ускорения этого перебора можно было реализовать перебор с возвратом (backtracking) — постепенно добавлять по одному числу в secret и поддерживать количество «быков» и «коров», которые уже набрались для каждой заданной попытки. Если хотя бы для одной они превышают необходимое количество, перебор останавливается, и мы переходим к следующим вариантам. Такой подход позволяет отсечь большое количество «мёртвых» ветвей перебора.

Но самое быстрое из известных мне решений переформулирует условие как SAT-задачу и использует один из существующих фреймворков для решения таких задач: например, Google OR-Tools или Microsoft Z3. Биндинги для этих библиотек существуют под многие языки программирования, а решение выглядит как объявление нужного количества переменных и формулирование всех ограничений. Например, в случае с Z3:

s = z3.Solver()

x = [z3.Int(f"x_{i}") for i in range(K)]
for xi in x:
    s.add(And(xi >= 1, xi <= N))

s.add(Distinct(x))

for numbers, bulls, cows in guesses:
    add_guess_constraints(s, x, numbers, bulls, cows)

Посмотреть, как можно написать add_guess_constraints()

def add_guess_constraints(solver, secret_vars, guess: list[int], bulls: int, cows: int):
    K = len(secret_vars)

    # Counting Bulls: positions where secret[i] == guess[i]
    bull_bools = [secret_vars[i] == guess[i] for i in range(K)]
    bull_count = z3.Sum([z3.If(b, 1, 0) for b in bull_bools])
    solver.add(bull_count == bulls)

    # Counting Cows
    exists_in_secret = []
    for value in guess:
        # 1 if the value is in the secret, 0 otherwise
        value_exists_in_secret = z3.Sum([z3.If(secret_vars[i] == value, 1, 0) for i in range(K)])
        exists_in_secret.append(value_exists_in_secret)

    total_common = z3.Sum(exists_in_secret)
    solver.add(total_common == bulls + cows)

Для поиска же минимального решения можно воспользоваться встроенным в z3 оптимизатором — z3.Optimize(), но в моих экспериментах он показал себя медленнее (YMMV!) следующего подхода: давайте переберём короткие префиксы в лексикографическом порядке (начнём с «1 2», затем «1 3», и так далее), зафиксируем их в нашем ответе и пробуем найти любое (необязательно минимальное!) решение с помощью z3.Solver(). Если находится, а с предыдущими префиксами не находилось, значит, мы нашли минимально возможный префикс! Продолжим наращивать его, пока не найдём ответ.

На обычном языке программирования такая программа выглядела бы элементарно:

input_line = read_line()
if input_line == "what":
    print("contest")
if input_line == "where":
    print("2026.andgein.ru")

К сожалению (или к счастью!) брейнфак не позволяет ни считывать сразу целую строчку, ни сравнивать строки, ни выводить их. Вместо этого он оперирует отдельными ячейками памяти или байтами (почитайте про язык в интернете, если раньше не работали с ним). В нём есть и другие особенности, но даже с этими наша программа вынуждена выглядеть как-то так:

# Skip first two characters, because they are always "wh"
input_character = read_character()
input_character = read_character()
input_character = read_character()
if input_character == "a": # "what" branch
    print("c")
    print("o")
    ... # Print all characters of "contest" one by one
if input_character == "e": # "where" branch
    print("2")
    print("0")
    ... # Print all characters of "2026.andgein.ru" one by one

Другой сложностью языка является то, что и сравнения if input_character == "a" в нём нет. Вместо этого мы должны вычесть из байта, ответственного за хранение input_character число 97 (ASCII-код буквы a) и затем результат сравнить с нулём, так как это единственное сравнение, доступное в языке. Поэтому проще всего будет отсортировать буквы, с которыми мы хотим сравнить input_character, и сравнить с ними по очереди путём постепенного вычитания:

# Skip first two characters, because they are always "wh"
input_character = read_character()
input_character = read_character()
input_character = read_character()
input_character -= 97    # ASCII code of "a"
if input_character == 0: # "what" branch
    print("c")
    print("o")
    ... # Print all characters of "contest" one by one

input_character -= 4     # ASCII code of "e" is 101, and 101 - 97 = 4
if input_character == 0: # "where" branch
    print("2")
    print("0")
    ... # Print all characters of "2026.andgein.ru" one by one

Осталось понять, что делать, если строчек больше, чем две, и некоторые из них отличаются в первом символе, а некоторые — например, в третьем. Ну что ж, ничего не поделаешь! Давайте сначала прочитаем первый символ, обработаем все возможные варианты для него, а дальше, если нужно, прочитаем остальное и снова обработаем все сценарии, пока не пойдём, что же надо выводить. Этих идей вместе с аккуратной реализацией и умением относительно эффективно выводить нужные строчки хватало, чтобы пройти 20 первых уровней, а то и больше.

Посмотреть уровни 1–20

2026

0 → 1
1 → 0

happy → new year
merry → christmas

eyes → coal
nose → carrot
arms → sticks
buttons → rocks

German → Frohe Weihnachten
Spanish → Feliz Navidad
Italian → Buon Natale

United States → Santa Claus
United Kingdom → Father Christmas
Russia → Ded Moroz
Netherlands → Sinterklaas
Norway → Julenissen
Finland → Joulupukki
Germany → Weihnachtsmann

hey jude → beatles
one → u2
smells like teen spirit → nirvana

what → contest
where → 2026.andgein.ru
when → 1 january 2026

18:00 → getting ready
21:00 → warm-up chatter
23:30 → countdown hype
00:00 → cheers and chaos
02:00 → philosophical conversations

january 1 → sleepy victory
january 2 → mild denial
january 3 → inbox shock
january 4 → routine reboot
january 5 → okay, new year mode on

violin → string
flute → woodwind
trumpet → brass
drum → percussion
piano → keyboard

mercury → 1
venus → 2
earth → 3
mars → 4
jupiter → 5
saturn → 6
uranus → 7
neptune → 8

pawn → 1
knight → 3
bishop → 3
rook → 5
queen → 9

a → alpha
b → beta
g → gamma
d → delta
e → epsilon
z → zeta
i → iota
l → lambda
o → omicron

january → february
february → march
march → april
april → may
may → june
june → july
july → august
august → september
september → october
october → november
november → december
december → january

USD → United States
EUR → Eurozone
JPY → Japan
GBP → United Kingdom
AUD → Australia

banana → yellow
strawberry → red
kiwi → green
blueberry → blue
grape → purple

Inception → 2010
The Matrix → 1999
Interstellar → 2014
Titanic → 1997
Parasite → 2019

AAPL → Apple
MSFT → Microsoft
GOOGL → Alphabet
AMZN → Amazon
TSLA → Tesla

4 → tetrahedron
6 → cube
8 → octahedron
12 → dodecahedron
20 → icosahedron

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

1. При выводе строчки (например, «contest») нужно сначала получить байт 99 (ASCII-код буквы c), затем 111 (o), 110 (n) и так далее. Очевидно, что почти всегда нужно переиспользовать одну и ту же ячейку, так как если там уже записано 111, то получить 110 очень просто — надо просто вычесть единицу, а это одна инструкция в брейнфаке. Но как написать самую короткую программу для получения 111 из 99?

Для этого давайте заранее для всех пар байтов A и B найдём достаточно короткую программу, переводящую число A в B. Начнём с тривиальных программ — состоящих из многих инкрементов «+» и декрементов «-». Затем используем факт, что если есть программа, переводящая A в C, и программа, переводящая C в B, то их сумма переводит A в B. Напоследок, воспользуемся простым умножением. Например, [--->+++++++<] умножает число на 7/3 — то есть 6 перевод в 14, а 27 в 63.

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

2. Бывает, что строчки, которые надо вывести, одинаково начинаются или одинаково заканчиваются. Тогда можно сэкономить, выведя общий префикс/общий суффикс вне ветвлений.

3. Бывает, что общая логика генерации программы вставляет зануления [-], ненужные сдвиги <> или другие вещи, которые в итоге не нужны. Удалим их в самом конце, убедившись, что программа всё ещё ведёт себя ожидаемо. Для этого придётся написать интерпретатор брейнфака, но, к счастью, он занимает десять строчек пишется LLM-кой или импортируется библиотекой.

Посмотреть уровни 21–50

lift → elevator
lorry → truck
boot → trunk
petrol → gasoline
biscuit → cookie

New York → UTC-5
London → UTC+0
Tokyo → UTC+9
Sydney → UTC+10
Dubai → UTC+4

32 F → 0 C
68 F → 20 C
86 F → 30 C
104 F → 40 C
14 F → -10 C

hydrogen → 1
helium → 2
carbon → 6
oxygen → 8
iron → 26
copper → 29
zinc → 30
krypton → 36
silver → 47
tin → 50
iodine → 53
xenon → 54
gold → 79
mercury → 80
lead → 82
uranium → 92
plutonium → 94

H → Hydrogen
He → Helium
C → Carbon
O → Oxygen
Fe → Iron
Cu → Copper
Ag → Silver
Au → Gold

tennis → racket
soccer → ball
boxing → gloves
archery → bow
hockey → stick

phoenix → greek
kitsune → japanese
anubis → egyptian
kelpie → scottish

python → 1991
javascript → 1995
rust → 2010
go → 2009

python → snake
go → gopher
rust → gear cog
java → steaming coffee cup
javascript → yellow JS badge

Gryffindor → bravery
Hufflepuff → loyalty
Ravenclaw → wisdom
Slytherin → ambition

pi → 3.14159
e → 2.71828
phi → 1.61803
tau → 6.28318

.jpg → photograph
.png → picture
.svg → vector image
.wav → audio
.epub → ebook
.yaml → config
.md → markdown text
.csv → comma-separated values
.mp4 → video
.ttf → font
.ico → icon

triangle → 3
square → 4
pentagon → 5
hexagon → 6

3 → triangle
4 → square
5 → pentagon
6 → hexagon

200 → OK
201 → Created
204 → No Content
301 → Moved Permanently
302 → Found
400 → Bad Request
401 → Unauthorized
403 → Forbidden
404 → Not Found
500 → Server Error
502 → Bad Gateway
503 → Service Unavailable

monet → impressionism
picasso → cubism
kahlo → surrealism
van gogh → post-impressionism
dali → surrealism
kandinsky → abstract
pollock → abstract expressionism
cezanne → post-impressionism
rothko → color field
hopper → realism

voyager 1 → interstellar
cassini → saturn
new horizons → pluto

AA → 1.5V
AAA → 1.5V
9V → 9V
CR2032 → 3V

hearts → red
diamonds → red
clubs → black
spades → black

tokyo → mega
vienna → large
reykjavik → small
new york → mega
shanghai → mega
berlin → large
lisbon → medium
zurich → medium
oslo → small

baguette → france
naan → india
pita → middle east
focaccia → italy
tortilla → mexico
brioche → france
injera → ethiopia
pretzel → germany

heart → circulatory
lungs → respiratory
kidneys → urinary
liver → digestive
stomach → digestive
pancreas → endocrine
brain → nervous
skin → integumentary
spleen → lymphatic

+ → add
- → subtract
* → multiply
/ → divide

titan → saturn
ganymede → jupiter
triton → neptune
enceladus → saturn
charon → pluto
phobos → mars
deimos → mars

git status → what changed?
git add → remember this
git commit → lock in a snapshot
git push → send it away
git pull → get latest from others

greenland → atlantic
madagascar → indian
fiji → pacific
iceland → atlantic
sri lanka → indian
hawaii → pacific
new guinea → pacific
sumatra → indian
canary islands → atlantic

cerulean → #007BA7
vermillion → #E34234
chartreuse → #7FFF00
ultramarine → #3F00FF
crimson → #DC143C
indigo → #4B0082
turquoise → #40E0D0
gold → #FFD700
salmon → #FA8072
magenta → #FF00FF

( → )
) → (
[ → ]
] → [
{ → }
} → {
> → <
< → >

Hippogriff → XXX
Acromantula → XXXX
Phoenix → XXXX
Niffler → XXX
Basilisk → XXXX
Chinese Fireball → XXXXX
Gnome → XX

2+2 → 4
2*2 → 4
3+3 → 6
3*3 → 9
4+4 → 8
4*4 → 16

Примечание: во всех уровнях можно написать ещё более короткую программу, ответы выше — не предел!

Во-первых, задачу можно было решить вручную! По моим оценкам на это должно было уйти часа два-три, но, кажется, некоторые команды наловчились делать это быстрее :-) Дальше поговорим об автоматическом решении.

Глобально, вроде, ничего сложного — надо лишь построить небольшой пайплайн по распознаванию объектов на изображении. Существенное количество первых уровней не содержали на себе ничего, кроме лего-человечков, поэтому если вы научились отделять их от фона, вы уже могли набрать существенное количество баллов.

Однако позже лего-человечки появлялись вместе с другими игрушками, так что хочется отличать их. Всего разных человечков было не так много, поэтому можно было попробовать написать код для автоматического вырезания их с фона и поворачиванию, а затем вручную разметить, что из этого лего-человечек, а что нет.

А можно было взять дата-сет из лего-человечков и обучить классификатор на распознавание именно таких объектов. Например, вот этот дата-сет отлично распознаёт все фигурки (кроме, правда, скелета — тот распознаётся примерно в 50% случаев).

Для классификации объектов можно было выбрать любую подходящую модель. Я выбрал YOLOv8, а обучение в современных фреймворках, к счастью, делается в три строчки:

from ultralytics import YOLO

model = YOLO('yolov8n.pt')
dataset_yaml_path = "path/to/lego/dataset/data.yaml"
results = model.train(data=dataset_yaml_path, epochs=100, imgsz=640)

print("Training Complete!")
print("Your new .pt file is located in the 'runs' folder created in this directory.")
print("Look for: runs/detect/train/weights/best.pt")

На чём обучать модель? Можно и на современном процессоре, но чтобы уложиться в ограниченное время контеста, я арендовал виртуальный сервер с относительно простой для этих целей GPU (RTX 4000 ADA) и меньше чем за $1 в час натренировал модель. Для ещё большей скорости можно взять, например, H100 или H200 — на таком небольшом дата-сете они должны справиться за минуты.

Останется правильно выстроить пайплайн:

1. Разрезаем картинку на квадраты.
2. Каждый квадрат передаём в model.predict(...) с правильно подобранными параметрами. Например, я рекомендую agnostic_nms=True, imgsz=2048 и iou=0.5. Если тоже используете YOLO, то подробнее о параметрах читайте в документации.
3. Останется правильно подобрать порог, после которого обнаруженного объекта можно считать лего-человечками. Обычно рекомендуется брать хотя бы 50%, а то и 75%.

Посмотреть картинки со всех уровней

№	Картинка	Количество лего-человечков
1		10
2		25
3		37
4		34
5		39
6		85
7		105
8		93
9		68
10		78
11		93
12		96
13		60
14		97
15		89
16		188
17		170
18		168
19		154
20		186
21		163
22		195
23		190
24		181
25		192
26		222
27		273
28		176
29		194
30		212
31		291
32		151
33		184
34		342
35		285
36		474
37		339
38		392
39		536
40		626
41		694
42		239
43		358
44		373
45		325

Оказывается, картинку можно восстановить однозначно, даже если количество кусочков достаточно большое! Начнём, однако, со случая, когда кусочков немного. В этом случае можно просто перебрать все возможные перестановки и выбрать те из них, в которых получается правильный PNG-файл.

Посмотреть картинки уровней 1–4

№	Кусочков	Вопрос	Восстановленная картинка
1	3	How many birds are on the wire?
2	4	How many cars are preparing for the race?
3	5	What's a title of this famous book?
4	8	How many fish are in the aquarium?

В следующих уровнях количество кусочков увеличивается до 18, 38 и даже 113, и просто перебрать все перестановки не получится. Однако достаточно вспомнить, что PNG-файл состоит из кусочков — «чанков», каждый из которых содержит контрольную сумму CRC32. Если один чанк оказывается на стыке двух кусочков нашего разрезанного файла, то можно быстро узнать, могут ли эти кусочки стоять рядом — достаточно проверить, что контрольная сумма в чанке посчитана верна.

Запустим перебор с возвратом, который будет пробовать добавить какой-нибудь кусочек к уже склееному началу файла. Начать файл легко — в первом кусочек должен быть заголовок PNG-файла (восемь фиксированных байтов) и чанк IHDR, содержащий, среди прочего, размеры картинки в пикселях. Переберём кандидатов на место следущего кусочка, и проверим контрольную сумму в чанке на стыке. Если она совпадает, то с большой вероятностью это и есть правильный кусочек, можно перебирать дальше, потом ещё дальше, и так далее, пока картинка полностью не восстановится.

Посмотреть картинки уровней 5–9

№	Кусочков	Вопрос	Восстановленная картинка
5	18	How many donuts are on a plate?
6	36	How many clouds are in the sky?
7	38	How many slices of pizza weren't eaten?
8	73	How many chairs are on the image?
9	113	How many eyes does the robot have?

Но что делать, если один чанк занимает сразу несколько кусочков? Тогда нужно перебрать сразу несколько кусочков, чтобы собрать один чанк и проверить его контрольную сумму, а этого мы себе позволить уже не можем...

В этом случае поможет чтение информации непосредственно о пикселях из чанков IDAT. Дело в том, что если склеивать кусочки в неправильном порядке, то картинка будет восстанавливаться корретно (по крайней мере пока мы не дочитаем до конца чанка и не проверим CRC), но выглядеть она будет как-то так:

Обратите внимание на нижние строчки пикселей — это мы приклеили неправильный кусочек! Наличие такого «шума» можно определить автоматически и на основании него откинуть соответствующий кусочек.

Посмотреть картинки уровней 10+

№	Кусочков	Вопрос	Восстановленная картинка
10	30	How many blue carriages are on a train?
11	269	How many fire blocks are on the image?
12	398	How many candles are on the cake?
13	537	How many buttons does the snowman have?
14	356	How many cups are on the table?
15	567	How many steps are on the staircase?

Важно отметить, что во многих уровнях не нужно восстанавливать всю картинку, достаточно восстановить половину или две трети. Если время от времени в переборе сохранять ту часть картинки, что уже восстановлена, то ответ можно получить значительно раньше.