Brainfuck Story

Давним давно, коли ми ще не народилсь, жив був Алан Тьюрінг. І Алан Тьюрінг придумав машину, і була вона потужна, універсальна. Але настільки незрозуміла, що навіть сам Алан Тьюрінг зробив помилки, коли придумував її.

Тому Урбан Мюллер створив іншу, простішу машину. Яка складається з двох стрічок пам'яті (з комірками по одному байту), двох індексів та 8 команд.

Стрічка пам'яті

Стрічка пам'яті складається з комірок розміром 1 байт, тобто, з чисел від 0 до 255. При старті програми вся стрічка заповнена нулями. Кількість комірок –- як правило 32768 (але насправді можна і необмежено).

Існує індекс, який вказує на якусь з цих комірок, і може бути переміщений вліво або вправо. Комірка, на яку вказує індекс, називається поточною.

Стрічка програми

Стрічка програми також складається з комірок розміром 1 байт, але на цей раз з символів по кодуванню ASCII.

Вісім з цих символів є командними, всі інші –- ігноруються.

Також є індекс команди, який вказує на якийсь з символів в стрічці програми. Після обробки символу індекс переміщається до наступної команди в стрічці програми, окрім деяких випадків.

Ось приклад програми, яка виводить hello world:

+[-[<<[+[--->]-[<<<]]]>>>-]>-.---.>..>.<<<<-.<+.>>>>>.>.<<.<-.

8 команд

+ –- додати 1 до поточної комірки пам'яті
- –- відняти 1 у поточній комірці пам'яті
> –- перемістити індекс пам'яті на 1 комірку вправо
< –- перемістити індекс пам'яті на 1 комірку вліво
. –- вивести на екран поточну комірку пам'яті як ASCII символ
, –- ввести з клавіатури в поточну комірку пам'яті символ як код по таблиці ASCII
[ –- якщо поточна комірка містить нуль, то перемістити індекс програми до наступного ], з врахуванням вкладеності квадратних дужок. Інакше –- йти далі по програмі
] –- якщо поточна комірка містить не нуль, то перемістити індекс програми до попереднього [, з врахуванням вкладеності квадратних дужок. Інакше –- йти далі по програмі

При додаванні/відніманні операція виконується по модулю 256 (тобто, якщо в комірці 255, то команда + перетворить його в 0).

Завдання

Тест

Щоб перевірити, чи зрозуміла вам ця машина, пройдіть тест.

https://forms.gle/AcxjonqgFtsBxT6e8

Перевіряти роботу можна на сайті https://mitxela.com/other/brainfuck

Інтерпретатор Brainfuck

Напишіть свій інтерпретатор цієї машини. Щоб перевірити його правильність, він повинен:

виконувати hello world

+[-[<<[+[--->]-[<<<]]]>>>-]>-.---.>..>.<<<<-.<+.>>>>>.>.<<.<-.

вміти грати в хрестики нулики: https://mitxela.com/projects/bf_tic_tac_toe

Розшифрувати код

Ось обфускований код для інтерпретатора brainfuck:










































code = """V*mgE00000000000000000jU506+i$0COY&002h-WB_CVgaBj#g92IrWCCOZgaBFrWC>&kWC(--S^{JR
QvfLnV*mgE00000000000000000RI306+i$0CN@q003nGS^;DLS^{JRWCLUbgaKLuWC2qEDF)gFQ*>c;
Wlre;0001E0{{R300000000000{{R30ssI2LjV8(a~c2u0DJ**2z&u<1Y`kc0ek>o0DJ;`0AB%Q08;=d
0#0%P0000f0@?#%a&p=QX>Md?cqs$g1aoC<W^w`m0043W0001~0CEKY008<4Vsc?=Ze}iUdD;kHUukY>
bYEWs0001U1ONa4009sIdJa=`VRU6KUtei%X>?y-DFRM%0RR91DFoUGUtexvZDn6y+6rG^ZEs|CY-L|x
+6-S`adlyAZeeX@Ute+u0001T1poj5as>bY0CEKY0043Z0001T000000ssI2a{>SW00;qc00000V*&sG
000000000000IC200jU507C!(0CVyH004XeWC3deawdELY5;ryY5^GlWC9leWCIoed;n?yd;n?zJOFOU
d;w$xYXWjid;n?yd;n?z831Gg7yx7g765zzY5;ryY5_a|ZlZhvWCd#ia)5jQ1ORFQWCAw;0svnDbOL+;
Y5;=)d;n?zYXWlad;n?ypaWzEp#cE^Zf<-5WCv>ka;SU&1ORFQWCAz<0svnDd;n?zWCm*ha_(dXd;nho
Zbp0oWC&{la?ErDbOn3>Y5;ryY5^Glg8^g-WC~;pjROGyZX$dEWDIKpa_)2nbO(a~WCj@kg8^g%765zz
Y5;ryY5_a|WB^kDDGg5g0W0YN0002#00961`T;Ha0X}j80002`0X*6PF4_Q8DFWI9Wo~5J1!in@b7=Yj
EGY<b0ssI2asvPW0NMj=Wp3IAVQ_F|Ze-d8aB^vGblL-BXmZ*EZ*pYX1!-<@b#y5L+68lTVRU8M0&j3~
1poj5as>bY0CENZ007ztZDDI=UvF>+0001UAOHXW009UA9svje9svje4gnAW4gm-O4gm@Q2muHI903Rc
avlHx0CExl002%#V+8;J000000000001N;C00{s907C!(0CTnh0049Vd;o(1WC3deau8$yQviGcau|F8
ZUl4zg8+R2d;)SXd;(+uWB`Q%8323%Ujk$TeFbC!eFkR$eFuC6bO3w+g8^g%7yxSkkO6Y0d<A3!HvoMF
d;oj}8326<d<bL&YXWj=WCeW#d;@cKd<bL)YXWk(bOU4ubOd|`d<c98d;w|&d;w|#WC)D~g8~5nWC3IV
YzBP^d<bL)YXWkvd<mcjWCNiA0RV0ad<mcjWC@`G0RVgkWC3dckO6Wqd<2jIawcR7WDA4<eF}5~WDI-=
n*d}DodbLdd;w|#WB_~tY6XP?832O;7XV}q7XW+;d;w|#d;w|&831Pig8>%+WDgerd<uL4Y65%#Y6WBi
7XV}cg#sA>g8>%+g8=~mbO?L_d<cUA0RVgmWDsitkO6XTd<UQjd<CHa0RVgfY65%#Y6TepWC3dekO6X}
d<J9zYXFb|a-?(sd<TO8WCIugeFkwnd<bL_YXWjSd<UQkWCEc9eG7B|d<TO8d<JU*kO6X(WCDE#aXfqm
WCCjfay)zsWCIugeFbqmbOU4(d;w|#g8~5nWB^kDDHBd|0RR91>Hq)#|8fif007zncvSiUA$kdNb#88H
Zf80mDFxaDb8BgEavcBw0NMp}bYWv_asvPW0CEBV003v2nVFfHnYlk>0RR9100000000000RR911ONa4
Qvd(}a})po0AvB60AvDW1B3v407L+T0igj?04W4cauNUl0Am3F000000000000062000F5002_}0046u
0001I0DJ&l5`6)50DJ+10iXe70HFbq0&xUW04V|K0{{R3DFWI9b98dr1#)V2b95;J+5#>xav%Tz0CEKY
0043Y0001T1^@s6+6p{uX>)XAZ*6csF#rGna|8eY00sa80D3BNb#7m9a&KoYJZx`cVQh0gE^cXKWiC8y
Z)0I>b3QISY-w|JV{dJ6J}Cj(1Zr<-ZYcrU0c>&w0001T1poj5as~hZ0NMm@X=7zD0001U0ssI200DXy
a&>NBaB^>FE<9{+V_|G_J}z!)V`X{<Ze@6MIv{!kAbcPodIcL>G%;;@1{+&2J1}kf0bBY3UD^Q(DGPEI
0001T00000asmJV0CE@r007zqWNBk`asvPW0NMm}X>DcN1#@g=WpHvH0001T7XSbN+5>QJa48Jh1aNY1
XL1|>003G8ZDnoR1!QGnb!S=$c4>2UVQgu7Wm*bwa&Ko}X>Md?cyb~D0043$0001T9RL6Taxee@0CFn;
007zqY+-YBas>bY0CEKY0043Z0002m2y%69UvP47XBhwh0CPqF000013;_fI4gmxK4gmxK1OWsA5&;MS
2muHI1OW^I903Rc2muTN3IPfM1_1~JRsjkD3IPfM903ji2muNK4gm%M2muNKay9?}04W7>5&!@IPEJNf
DFbo<0001T9smFUay9?}0CEKY0043Y0001T1poj5as~hZ0NMyVZEs|CY-K(I0001U1ONa44h0Aj"""

import marshal, base64
exec(marshal.loads(base64.b85decode(code.replace('\n',''))))

# def run_prog(prog='', mem=None, visualize=False)
#    prog -- код
#    mem  -- стартова пам'ять
#    visualize -- покрокове виконання

run_prog('+>>+')

Потрібно

його розшифрувати
знайти спосіб, як відтворити такий метод обфускації

Конвертер

Написати конвертер програми з Brainfuck у еквівалентну програму на Python.

Замірити швидкодію оригінального алгоритму і конвертованого для програми факторіалу http://progopedia.com/example/factorial/18/ за допомогою timeit

Форматування синтаксису

Напишіть форматтер для Brainfuck програми. Квадратні дужки формують вкладені цикли, тому їх треба відділяти індентацією. Але якщо всередині дужок не міститься інших циклів, і його довжина менше 5 символів, то не треба розбивати на кілька рядків.

Приклад форматування:

+
[
  -
  [
    <<
    [
      +
      [--->]
      -
      [<<<]
    ]
  ]
  >>>-
]
>-.
---.
>..
>.
<<<<-.
<+.
>>>>>.
>.
<<.
<-.

Мульти конвертер

Той факт, що Brainfuck ігнорує некомандні символи (а саме, ігнорує символ коментування #), можна використати для написання програми, яка буде одночасно виконуватись і в Python, і в Brainfuck.

Наприклад, ми можемо написати так:









arr = [0, 0, 0, 0]  # ok
i = 0               # ok
arr[i] += 5         # +++++
while arr[i] > 0:   # [
    i += 1          #   >
    arr[i] += 5     #   +++++
    i -= 1          #   <
    arr[i] -= 1     #   -
                    # ]

Код зліва написаний на Python, код справа –- на Brainfuck.

І хоч цей код запуститься у Python, він не буде працювати як задумано в Brainfuck, бо в Пайтон коді використовуються квадратні дужки, знаки плюс, більше та мінус. Але якщо від них позбутись, то це стане можливо!

Як позбутись від квадратних дужок, крапки, коми, плюса, мінуса та більше?

Ну, від > позбутись просто. Python вважає що будь-яке ненульове число –- це True в умовних операторах. Тому
```
while arr[i] > 0:   # [
-->
while arr[i]:       # [
```

Від коми , можна позбутись таким трюком

arr = [0, 0, 0, 0]               # ok
-->
arr = list(b'\x00\x00\x00\x00')  # very ok
-->
arr = list(b'\x00')*4            # wow such nice much ok

В brainfuck є трюк під назвою "коментар". Наприклад, цей код
```
#                               # Brainfuck preamble [-][
def plusX(x): arr[i] += x
m = -1
i = 0
#                               # ]
arr = list(b'\x00')*4           # ok
plusX(5)                        # +++++
plusX(m*5)                      # -----
```
виконає перший та п'ятий рядок в Brainfuck, але проігнорує три між ними. Це стається через те, що [-] обнуляє будь-яке число, і наступна [ ніколи не запустить код всередині квадратних дужок. Фактично, коментар.

Ці трюки дозволяють написати програму, яка буде одночасно коректною Python та Brainfuck програмами. Напишіть алгоритм, який перетворює brainfuck програму у таку подвійну Python/Brainfuck програму.

Багатогранний інтерпретатор

Виділіть ваш алгоритм цієї машини у бібліотеку brain.py. Після цього потрібно буде написати 4 варіанти інтерпретатора, всі для різних інтерфейсів:

BF на черепашці. Черепашка дозволяє реагувати на клавіші одразу як вони натискаються. Зробити так, щоб алгоритм BF вводив текст через події .onkey()) і виводв текст через методи turtle.write(). Текст програми потрібно вставляти через буфер обміну (при натисненні якоїсь кнопки).
BF через BF. Повинна бути можливість запустити інтерпретатор BF в BF, і в результаті має вийти повноцінний BF, який може виконати hello world. Зробити зчитування програми з файлу
BF телеграм бот. Написати ТГ бота, який буде виконувати введений BF код і видавати результат. Реалізувати таймаут та обмеження на пам'ять
BF діскорд бот. Написати Діскорд бота, який буде виконувати введений BF код і видавати результат. Реалізувати таймаут та обмеження на пам'ять