Подразделы

Другие разделы

Дата и время

27/02/2020 11:47:51

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printОписание программы

Типы данных
Поддерживаются шесть типов данных:
  • целые числа со знаком (64-битные)
  • символы без знака (8-битные)
  • последовательности
  • деки (двухсторонние очереди)
  • множества
  • ассоциативные массивы
Кроме этого есть два вспомогательных типа – неопределенное значение и функция, с которыми нельзя производить никаких вычислений.
Целые числа-константы можно записывать в десятичной форме (100), восьмеричной (0144) и шестнадцатеричной форме (0x64).
Символы-константы записываются в апострофах ('A'), также поддерживается запись символа восьмеричным кодом ('\101') и некоторые специальные символы ('\\' '\n' '\r' '\t' '\'' '\"') как в языке С.
Последовательности записываются в [], разделяя элементы пробелами или запятыми по желанию, например, [1 2 3] или [1,2,3]. Последовательность значений по порядку от `a` до `b` включительно можно записать так: ['a'..'z','A'..'Z'] или [10..0] (числа от 10 до 0 в обратном порядке). Последовательности символов можно записать в кавычках: "Строка символов".
Прочие контейнеры создаются путем добавления значений в пустой контейнер. Пустая очередь обозначается [<], пустое множество – [<<], пустой ассоциативный массив – [@].
Имена переменных являются глобальными и состоят из букв, цифр и символов подчеркивания. Имя должно начинаться с буквы или символа подчеркивания. Регистр букв важен.

Операции
Операция . позволяет получить элемент последовательности, дека (нумерация ведется с нуля), элемент ассоциативного массива (ключ может быть символом, числом или контейнером) или вызывать функцию. Например, выражение "ABCD".2 вернет символ 'C'.
Операция - выполняет смену знака для целых чисел или получение последовательности в обратном порядке. Например, выражение -"ABCD" вернет "DCBA". К символам и прочим контейнерам эта операция неприменима.
Операция ! проверяет, что значение является нулевым. Нулевым считается также пустой контейнер.
Унарная операция @ возвращает случайный элемент последовательности. К другим типам унарная операция неприменима. Для генерации случайных чисел и символов используется бинарная форма операции: выражение 1@10 возвращает случайное целое число от 1 до 10, а 'a'@'z' – случайную строчную букву.
Операция ~ возвращает случайную перестановку элементов последовательности, а для целых чисел – инвертирует биты в числе. К другим типам эта операция неприменима.
Операция $ преобразует целое число в строку (последовательность символов), а строку в число. К символам эта операция неприменима. Для преобразования числа в строку с заданной шириной и основанием системы счисления используется операция $ с двумя аргументами. Например, выражение "05o"$101 вернет "00145", а выражение "5d"$101 вернет "  101". Первый символ '0' означает, что число до нужной ширины нужно дополнить '0', иначе ' '. Последний символ 'X' или 'x', указывает что используется основание 16, символ 'o' – 8, символ 'd' – 10. Точка в формате позволяет вывести целое число как вещественное, например, выражение ".3"$101 вернет 0.101. Эту операцию можно применять для превращения любого значения контейнера в строку, при этом в качестве первого аргумента указывается последовательность. Первый элемент последовательности используется как разделитель для элементов контейнера, а остальные элементы последовательности – для форматирования элементов контейнера.
Операция # преобразует целое число в символ, а символ в целое число (номер символа). Для контейнеров операция возвращает количество элементов. Примеры: #'A' равно 65, #65 – 'A', #[0,0,0] – 3.
Операция ? определяет тип значения. Результат 0 соответствует неопределенному значению, 1 – символу, 2 – целому числу, 3 –последовательности, 4 – функции, 5 – деку, 6 – множеству, 7 – ассоциативному массиву. Для констант тип значения увеличивается на 8. Например, выражение ?7 вернет 10 (=8+2).
Операция * для целых чисел вычисляет их произведение. Если один из аргументов операции последовательность или символ, операция возвращает последовательность из заданного другим аргументом числа повторений. Например, выражение 3*"ABC" вернет "ABCABCABC". Для множеств эта операция находит их пересечение.
Операция / для целых чисел вычисляет их частное. Если один из аргументов операции последовательность `s`, то операция отделяет `k` первых (для `k//s`) или `k` последних (для `s//k`) элементов последовательности. Например, выражение 3/"TEXT" вернет "TEX". К другим типам эта операция неприменима.
Операция % для целых чисел вычисляет остаток от деления. Если первый аргумент операции контейнер, то операция возвращает количество вхождений второго аргумента в последовательность. Например, выражение "ABRACADABRA"%'A' вернет 5. Для ассоциативных массивов выполняется поиск ключа, а не значения.
Операция - для целых чисел вычисляет их разность. Если один из аргументов операции последовательность `s`, то операция удаляет `k` первых (для `k-s`) или `k` последних (для `s-k`) элементов последовательности. Например, выражение 3-"ABCDE" вернет "DE". Если первый аргумент – множество, то возвращается из множества удаляется указанные в качестве второго аргумента значения. К прочим типам эта операция неприменима.
Операция + для целых чисел вычисляет их сумму. Если оба аргумента операции последовательности, то операция выполняет сцепление двух последовательностей. Если последовательностью является только один из аргументов, то происходит добавление другого аргумента в начало или конец последовательности. Например, выражение 'X'+"ABC" вернет "XABC". Если первый аргумент – контейнер, то к нему добавляются указанные в качестве второго аргумента значения. При добавлении последовательности, дека или множества к ассоциативному массиву считается, что элементы в добавляемом контейнере пронумерованы по порядку, начиная с 0. Добавление скалярного значения приводит к добавлению в массив неопределенного значения с этим ключом.
Операция << для целых чисел выполняет поразрядный сдвиг влево. Если оба аргумента операции последовательности, то операция выполняет сортировку (если это необходимо) аргументов и слияние полученных упорядоченных последовательностей. Если последовательностью является первый аргумент, то выполняется сортировка и вставка в упорядоченную последовательность второго аргумента. Например, выражение []<<"TEST" вернет "ESTT". Для упорядоченных последовательностей операции поиска элемента и подсчета количества выполняются быстрее. Операция <<= добавляет элемент в множество и в ассоциативный массив (с неопределенным значением) и значения в начало дека.
Операция >> для целых чисел выполняет поразрядный сдвиг вправо. Если первый аргумент является последовательностью, то из последовательности удаляется первое вхождение второго аргумента. Например, выражение "TEST">>'S' вернет "TET". Операция >>= удаляет элемент из множества или ассоциативного массива.
При любом сравнении двух значений считается, что неопределенное значение < символ < целое число < последовательность < функция < дек < множество < ассоциативный массив. Контейнеры сравниваются лексикографически. Операция <? возвращает минимальный из своих аргументов, а операция >? – максимальный из своих аргументов. Например, выражение 5<?3 вернет 3. Операции сравнения < > <= >= == != возвращают число 0 или 1 в зависимости от результата сравнения.
Операция & для целых чисел выполняет поразрядное логическое "и", а операция | – поразрядное логическое "или".
Операция ^ для целых чисел выполняет поразрядное логическое "исключающее или". Если первый аргумент является последовательностью, то операция возвращает индекс первого вхождения второго аргумента (нумерация с 0). Если элемента нет, то операция вернет -1. Например, выражение "TEST"^'S' вернет 2.
Тернарная операция ? : возвращает в зависимости от значения первого аргумента значение второго или третьего аргумента. Например, выражение 1<2 ? 3 : 4 вернет 3.
Операция = выполняет присваивание второго аргумента в ячейку памяти, заданную первым аргументом. Операция >< выполняет обмен двух ячеек памяти. Операции + - * / % << >> <? >? ^ & | можно комбинировать с операцией присваивания, например, a+=b интерпретируется как a=a+b.
Результатом операции ; является значение второго аргумента. Первый аргумент вычисляется, но игнорируется. Специальным вариантом использования этой операции является игнорирование результата выражения при создании пустой последовательности: [выражение;].
Префиксные и постфиксные операции ++ -- можно применять к числам и символам для увеличения или уменьшения их на 1. В постфиксном варианте операции возвращают значение до изменений. Для дека префиксная операция -- удаляет первый элемент, а постфиксная – удаляет последний элемент. Для последовательности применима только постфиксная операция --, что позволяет использовать последовательность в качестве стека.
Приоритеты и ассоциативность операций
ОперацияПорядок выполнения
. -- ++слева направо
унарные - ! @ ~ $ # ?справа налево
бинарные @ $неассоциативные
* / %слева направо
+ -слева направо
<< >> <? >?слева направо
< > <= >= == !=неассоциативные
&слева направо
^слева направо
|слева направо
? :неассоциативные
= += -= *= /= %= <<= >>= ^= &= |= <?= >?= ><справа налево
;неассоциативные
При использовании унарных операций - ? $ @ в последовательности [], разделенной пробелами, рекомендуется ставить скобки вокруг операции и её аргумента. Например, последовательность [4 -3] интерпретируется как [1], правильно писать [4,-3] или [4 (-3)].

Генерация теста
Программа генерации состоит из последовательности генерирующих элементов и команд. К генерирующим элементам относятся:
  • Последовательность генерирующих элементов и команд в {}
  • Печать значения константы, переменной или результата функции: 'A', X, X.I, func.(x+1)
  • Печать значения по формату: "05"$101 выведет 00101, ","$[1..5] выведет 1,2,3,4,5
  • Печать результата выражения в (): (A+B)
  • Печать последовательности в []: [1 ['A'] 3] выводится как 1A3
  • Печать случайного элемента последовательности: @ "ABC"
  • Печать случайной перестановки элементов последовательности: ~ "ABC"
  • Повтор генерации элемента фиксированное число раз: 3*{'+' 1} выведет +1+1+1
  • Бесконечный повтор генерации элемента: !*{'A'} выведет AAA... (для выхода из цикла нужно использовать !!)
  • Повтор генерации элемента, пока некоторое значение не станет нулевым: [N=3;] N?*{'+' (--N)} выведет +2+1+0
  • Повтор генерации, используя значения из контейнера: [1..5]^x*{'+' x} выведет +1+2+3+4+5 или
    [3,7,1]^k:x*{k'-'x' '} (k – значение ключа в массиве или порядковый номер в других контейнерах) выведет 0-3 1-7 2-1
  • Выбор генерируемого элемента в зависимости от условия: (1<2)?3:4 выведет 3
  • Случайный выбор генерируемого элемента: 'A'|'B'/5|'C'/10 (после символа / указывается кратность появления элемента, по умолчанию 1, т.е. символ 'A' будет выведен с вероятностью 1/16, 'B' – 5/16, 'С' – 10/16).
К командам управления относятся:
  • Запись сгенерированного текста в переменную: X={3*'A'}
  • Возврат из функции или программы: >> (пустой результат) или >x (вернуть значение x)
  • Выход из цикла: !!
  • Определение функции: fact:={(_>1)?{>(_*fact.(_-1))}:>1} (аргументы функции доступны под именем _)

Вызов генератора
При вызове программы можно указать значения для некоторых переменных (только целые числа) и начальное зерно для датчика случайных чисел (seed). По умолчанию датчик случайных чисел будет инициализирован текущим временем.
По умолчанию загрузка программы происходит из стандартного ввода (клавиатура), а вывод – на стандартный вывод (экран). Но если указать имена файлов, то ввод и вывод будет выполняться из этих файлов.
gener test.g – программа в test.g, вывод на экран
gener N=10 01.g 01.in – программа в 01.g, вывод в 01.in, переменной N присваивается значение 10
gener seed=10 <01.g >01.in – вариант с перенаправлением ввода-вывода, датчик случайных чисел инициализируется зерном 10.

Примеры программ
Тесты для задачи "BB-коды"
Случайный набор символов:
100*{100*@"[]/IUB " "\n"}
Случайный набор BB-кодов:
100*{ 25*{"[" {"/"|""} @"IUBiub" "]"} "\n"}
Случайный тест для задачи "Дом тысячи дверей" (размеры лабиринта n и m задаются в аргументах командной строки при вызове генератора):
[map=n*[m*'.'+'\n'];] // Создаем матрицу из символов '.'
set:=
{ [i=_.0;]
  (i<n)?*
  { [j=_.1;]
    (j<m)?*[map.i.j=@_.2;j+=2;]
    [i+=2;]
  }
}
set.[0 0 "+"] // Расставляем углы комнат
set.[0 1 "^v"] // Расставляем двери
set.[1 0 "<>"]
mark:={
  !*{
    [i=0@(n-2)|1;j=0@(m-2)|1;]
    (map.i.j=='.')?{[map.i.j=_;] !! } 
  }
}
mark.'*' // Текущая позиция
5*mark.'$' // 5 монет
map
Случайный тест для задачи "Пиццерия-2" (размеры карты n и m, количество домов k задаются в аргументах командной строки при вызове генератора):
// генерация карты n*m
n' 'm'\n'
[map=n*[m*[0]];]
// разбрасывание k домов
k*{[map.(0@(n-1)).(0@(m-1))=(-1@100);]}
// поиск 0
[i=j=0;] map.i.j?*{(++j==n)?[j=0;++i;]}
// пометка достижимых клеток (алгоритм BFS)
[step=n*[m*[-1]];step.i.j=0;q=[<]+[i,j];]
go:={
  (_.0<0 | _.0>=n | _.1<0 | _.1>=m)? >>
  (map.(_.0).(_.1)<0)? >>
  (step.(_.0).(_.1)>=0)? >>
  [step.(_.0).(_.1)=st;]
  (map.(_.0).(_.1)>0)? >>
  [q+=[_.0, _.1];]
}
q?*{
  [i=q.0;j=q.1;----q;st=step.i.j+1;] 
  go.[i+1, j]
  go.[i-1, j]
  go.[i, j+1]
  go.[i, j-1]
}
// пометить недостижимые клетки -1
step^i:row*{row^j:v*{(v<0)?[map.i.j=-1;]}}
// напечатать
["\n"," "]$map "\n"
Случайная перестановка из чисел от 1 до N:
N'\n'
' '$(~[1..N])'\n'
loading