Сжатие инструкций для CFR[]

Евгений Степанищев — Mon, 06 Nov 2023 18:43:46 +0500

Выложил свою программу для перевода растра в инструкции для интерпретатора CFR[]. Написана, к слову, на «Гоу». Что-то давно я не программировал на этом языке, вот и решил смазать свежим опытом уже начавшие ржаветь знания.

Самая интересная часть там — про оптимизацию. Из-за наличия цикла для однократного повторения, в который можно что-то вкладывать, программу можно писать сильно по-разному. Можно прямолинейно — FFFFFFFFFFFFFF, а можно упаковать в цикл — [F[FFF]], станет чуть короче.

RR[CF][FF][CCC]CF[F[RRR]]FCC[FF]F[FRR]FFCC[FF][CC][F[RRR]]CC[FF]FF[FRR]F[CC][CF][CCC]CF[FC]C[F[RRR]][FF]FF[CCC][FRR][FCCFF[CCC]][F[RRR]][FF]FF[FRR][FF]FFF

Из-за того, что интерпретатор позволяет писать программы не более чем в 256 инструкций, инструкции приходится ужимать циклами, а чтобы не делать это вручную, хочется как-то автоматизировать.

Я реализовал довольно очевидную идею — делаем две переменные, одна указывает на начало инструкций, вторая — на середину. Вырезаем подстроку между двумя этими индексами, ищем её сразу за правым индексом, если находим, заменяем на вырезанное, оборачивая в цикл и начинаем сканировать заново. Если не находим, сдвигаем сначала правый указатель к началу, повторяем поиск, потом левый к центру, повторяем поиск. Естественно по ходу надо отбрасывать куски, где не сбалансированы скобки, это совсем просто.

Мои рассуждения на бумаге по порядку обхода картинки

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

При этом немного смещается координаты отрисовки картинки. Её можно было бы возвращать обратно, но зачем? Интерпретатор и так рисует в центре холста, так что сдвиг — это не принципиально, только размер кодирующей последовательности увеличится.

Блоги: заметки с тегом googlego

Сжатие инструкций для CFR[]