Among Us

Структура, в которой хранятся данные в Among Us, называется стек. Стек представляет собой последовательно соединенные ячейки с информацией. Различные команды в этом языке программирования работают с этими ячейками: добавляют туда информацию, извлекают ее оттуда и т д.

Букве a в кодировке ASCII соответствует код 97, а букве b — 98.

В этом языке программирования введенные данные сохраняются в стеке — некоторой последовательности ячеек, в которой каждая ячейка связана с предыдущей. Для решения задачи не обязательно знать о том, что такое стек и как он устроен. Достаточно понять, что символы хранятся в памяти в каком-то порядке и извлекать их можно в порядке, обратном тому, в котором они были введены в стек. Анализируя первый пример, мы понимаем, что команда YELLOW SUS вводит элемент в стек, а GREEN SUS выводит. Также мы знаем, что введенные элементы добавляются в начало стека из условия. Значит, GREEN SUS выводит начальный элемент стека.

Из второго примера мы понимаем, что PURPLE SUS удаляет начальный элемент стека.

Осталось понять, что делают еще два цвета. Мы вводим два символа. Выводится какой-то код, потом выводится начальный элемент стека, а потом элемент удаляется, и так два раза. Можем предположить, что непонятный код — это ASCII-номер из таблицы, про который написано в условии. Осталось понять, ASCII какого элемента выводит BLACK SUS. Если предположить, что он выводит ASCII последнего элемента стека, то, после удаления первого, BLACK SUS выведет то же число. У нас вывелось два разных числа, значит он выводит ASCII первого элемента.

Рассмотрим следующий пример. Осталось понять работу команды LIME SUS, в остальных командах мы уже разобрались. Этот цвет выводит то же, что и BLACK SUS, но в два раза больше, значит, он выводит ASCII первого элемента базы, умноженный на 2.

Как же понять ASCII-код букв? Если мы сравним коды букв в условии, то поймем, что они различаются на разность между позициями этих букв в алфавите. Таким образом, мы легко можем определить ASCII каждой буквы.

Ответ:

>> h

>> 204

Among Us — это многопользовательская онлайн-игра, которая была невероятно популярна в 2020 году в том числе и в русскоязычном комьюнити и внесла немало сленговых неологизмов в русский язык. Игроки Among Us управляют смешными разноцветными человечками в скафандрах («амогусами»). По сюжету игры они находятся на космическом корабле и выполняют различные задания, чтобы продолжить свой путь. Однако среди команды есть предатели («импостеры»). Их цель — убивать членов команды и устраивать поломки на космолете. Предатели определяются в рандомизированном порядке до начала игры и имеют ряд способностей, отличающих их от остальных «амогусов». Игроки должны работать вместе, чтобы вычислить предателей и изгнать их с корабля до того, как они смогут нанести ущерб. По сути правила игры сильно напоминают знакомую всем настольную игру «Мафия»: в «Among Us» даже есть чат, нужный для того, чтобы договориться о том, кого следует подозревать и кого нужно исключить из команды, однако на обсуждение дается весьма ограниченное количество времени. Поэтому общение в чате в основном состоит из однословных предложений, содержащих всем понятные игровые термины. К примеру:

Цвета в сообщениях игроков указывают на «амогусов» в скафандрах определенного цвета. Вопросы «Где?» и «Кто?» задаются с целью узнать место убийства и личность «импостера». Чтобы сказать, что какой-то игрок ведет себя подозрительно, про него могут написать, что он «сусси». На нормативном русском языке диалог на картинке звучал бы так:

    Леруха: Где произошло убийство?
    APOLON VI: Убийца — это белый.
    красный: Убийство произошло в коммуникации.

Один из фанатов игры «Among Us» создал эзотерический язык программирования, команды в котором являются частотными словами во внутриигровых чатах англоязычных игроков — вопросительными местоимениями («where», «who»), игровыми локациями («electrical»), названиями цветов и словом «sus» (от англ. «suspicious» — «подозрительный»). Термин «эзотерический» означает, что язык «Among Us» не используется для каких-то научных или промышленных целей и является сугубо шуточным. Существует великое множество эзолангов. Причины, по которым они создаются, во многом роднят их с конлангами — искусственными языками, авторы которых придумывают для них грамматику, составляют словари и изобретают письменность. В основном, эзо- и конланги связаны с какими-то известными книгами, фильмами, играми и/или призваны продемонстрировать интересную особенность, не присущую ни языкам программирования, ни естественным языкам. Про эзотерические языки программирования и их связь с естественными языками подробно написано в послесловии к задаче «Шекспиру и не снилось!», а про разделение искусственных языков по цели их создания можно прочитать в книге Александра Пиперски «Конструирование языков: От эсперанто до дотракийского».

Наверняка вы хоть раз сталкивались с такой проблемой при попытке открыть скачанный из интернета файл на своем компьютере: вместо понятных и привычных глазу букв, цифр и знаков препинания на экране отображаются непонятные закорючки. В таких случаях проблема обычно решается ручной сменой кодировки — специального способа присваивать символам последовательности двоичного кода. Программы на «Among Us» сохраняют данные, введенные пользователем, в ASCII — одной из стандартных кодировок. Для того, чтобы однозначно кодировать любые символы нулями и единицами, было предложено несколько различных вариантов сопоставления. С древних времен, задолго до изобретения компьютеров, люди искали способы передавать информацию через доступные символы — вспомнить хотя бы водяной телеграф, сигнальные огни и семафор. В 1840 году был изобретен код Морзе, легший в основу других систем, из которых потом развился предшественник ASCII — ITA2 (Международный телеграфный алфавит). ITA2 кодирует 26 букв латинского алфавита, 10 цифр и некоторое количество служебных символов сочетаниями из пяти позиций. Передача данных от оператора к оператору осуществлялась при помощи пробития машинкой дыр в ленте специальным образом.

ITA2

Для наглядности представим два варианта — нанесения и ненанесения точки на ленту — как знакомый нам двоичный код. При однозначном сопоставлении каждого символа коду вариантов бы попросту не хватило, так как последовательностей из пяти нулей или единиц всего 32. Поэтому при вводе пользователь специальным кодом указывает, что он собирается напечатать — букву или какой-то иной символ. Например, чтобы напечатать «MI-6», потребуется написать «11111» (код, который обозначает, что дальше идут буквы), «11100» («M»), «00110» («I»), «11011» (код, который обозначает, что дальше идут не буквы), «00011» («–»), «10101» («6»).

Со временем возможности объема хранения информации расширились и был изобретен TTS (TeleTypeSetter) — шестибитный способ кодирования, при котором бит уходил на то, чтобы каждому символу присваивать значение либо буквы, либо не буквы. Это сделало систему кодировки информации более безопасной. Ранее при поломке одного бита в коде значение всего сообщения могло потеряться, если этот бит находился внутри кусочка кода, показывающего тип символов после него. Теперь при поломке одного бита могло потеряться лишь значение одного символа во всем сообщении.

К 1963 году появился ASCII и начал кодировать символы уже семибитными последовательностями. Появление этой системы расширило количество возможных для использования символов до 2⁷ = 128 и позволило различать регистр вводимых букв. Однако эта кодировка по-прежнему работала только с латиницей и другие алфавиты с ее помощью использовать было нельзя, поэтому через какое-то время появились ее аналоги с большим количеством кодируемых символов. О том, какие кодировки пришли на смену ASCII рассказывается в послесловии к задаче «Юникод на Новый Год».

Как и некоторые другие языки программирования, Among Us является стековым. Это значит, что основным способом хранения и передачи параметров в нем являются стеки — списки каких-то элементов, сцепленных друг с другом последовательно.

Чтобы объяснить, как работает стек, неплохо подойдет аналогия с детской пирамидкой. Самое первое «колечко», которое кладется в стек, оказывается в самом низу, а сверху помещаются новые. Иначе говоря, если мы захотим взять какое-то из «колечек», нам придется сначала достать все, что находятся выше него.

По сути, любой элемент стека хранит информацию не только о себе, но и о том, что за элемент находится перед ним. Так, каждые две последовательные «ячейки» стека оказываются связаны между собой. В некотором смысле эта идея — что все элементы из стека указывают на какие-то другие элементы из стека — похожа на то, как слова связываются во фразы в естественных языках. Действительно, рисуя для предложения синтаксическое дерево, мы стрелочками указываем, как слова однонаправленно указывают друг на друга, иначе говоря, управляют. Рассмотрим пример предложения, где каждое слово управляет последующим:

Его можно представить и в виде некоторого подобия стека:

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

Конечно же, далеко не во всех предложениях русского языка и далеко не во всех предложениях естественных языков в принципе возможна подобная последовательная связь между словами. Тогда назовем информацию, которую нам дает каждое слово о том, что с ним согласуется, индексом и представим, что индекс может относиться не к следующему в предложении слову, а просто к любому. Подобные системы называются индексированными языками — в иерархии Н. Хомского они относятся к контекстно-свободным, а точнее, являются их обобщением. Индексированные языки порождаются индексированными грамматиками, состоящими из:

N — набора нетерминальных символов;
T — набора терминальных символов;
I — набора индексов;
P — конечного набора продукций или правил;
E — начального символа.

В статье С. Пулмана и Г. Ритчи (1984) приводится пример представления категории числа в предложении в виде индексированной грамматики для английского языка. Попробуем подобрать аналогичный пример для русского.

Примеры предложений с одними и теми же лексемами и различием в категории числа:

а) Железная труба упала.
б) Железные трубы упали.
в) *Железная трубы упала.
г) *Железные труба упали.
д) *Железная труба упали.
е) *Железные труба упала.
ж) *Железные трубы упала.
з) *Железная трубы упали.

Индексированная грамматика:

N = { E, S, NP, V, N, A }

T = { железная, железные, труба, трубы, упала, упали }

I = { s, p }

P = { E → S.s, E → S.p, S → NP V, NP → A N, V.s → упала, V.p → упали, A.s → железная, A.p → железные, N.s → труба, N.p → трубы }

Стартовый символ — Е.

Пояснение:

S — предложение, NP — именная группа, V — глагол, N — существительное, А — прилагательное, s — единственное число, p — множественное число.

Порождаемые грамматикой деревья:

Заметим, что благодаря индексам никакие предложения с * породиться не могут.

Стековые языки программирования также обнаруживают еще одно интересное сходство с некоторыми естественными языками: для записи команд они используют постфиксную нотацию. В постфиксной нотации аргументы записываются перед командой: 1 1 +. Во многих языках мира предикат также находится в конце предложения после субъекта и объекта.

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

Библиография:
1. Pulman S., Ritchie G. D. Indexed Grammars and Intersecting Dependencies. — 1985.
2. Gazdar G. Applicability of indexed grammars to natural languages. — Springer Netherlands, 1988. — С. 69–94.
3. Chomsky N. Syntactic structures // Syntactic Structures. — De Gruyter Mouton, 2009.
4. А. Пиперски. Конструирование языков: От эсперанто до дотракийского. — М.: ООО «Альпина Паблишер», 2017. — 270 с.

Задача использовалась на VII Устной олимпиаде по лингвистике НИУ ВШЭ — 2022.