Блог пользователя Nickolas

Автор Nickolas, 12 лет назад, По-русски

Roco — язык очень простой: с одной стороны, достаточно эзотерический, то есть все, что о нем нужно знать, помещается на две страницы, а с другой, достаточно емкий, чтобы на нем можно было писать сравнительно сложные программы, не ломая голову над каждой элементарной операцией, как в Brainfuck. Одна только возможность обращаться к переменной по имени (числовому, но все-таки имени) — уже подарок для программиста :-)

188A - Шестиугольные числа

Как обычно, первая задача проверяет способность участника выполнять базовые арифметические действия языка и решается по аналогии с примером.

iin [0]
mul [1] [0] 2
dec [1]
mul [1] [1] [0]
iout [1]
ac

Начиная со второй, задачи требуют постепенного освоения главной особенности языка — сопрограмм. Сопрограмма — это именованный фрагмент кода, который по умолчанию выполняется в бесконечном цикле. Нечто среднее между процедурой/функцией (без входных/выходных параметров и локальных переменных, зато с именем, по которому ее можно вызывать) и циклом (без счетчика цикла/условий выхода, но с возможностью прервать выполнение в любой момент), сопрограммы позволяют реализовать и то, и то.

188B - A + Reverse B

Ключевой элемент этой задачи — зеркальное отображение второго числа (прибавление к нему первого мы умеем делать еще со времен примера), которое можно сделать двумя способами: либо прочитать число как последовательность символов, одновременно накапливая его зеркальное отображение, либо прочитать его как число и затем обратить его математически. Я использовала второй способ; для этого понадобилась одна сопрограмма в роли цикла, прерывающегося, когда обращаемое число становится нулем.

/* coroutine to reverse a number [1] into [2] */
co reverse {
   eq [3] [1] 0
   if [3]
      ac
 
   /* find current number modulo 10 */
   mod [3] [1] 10
   /* add it to reversed number */
   mul [2] [2] 10
   add [2] [2] [3] 
   /* and divide current number */
   div [1] [1] 10
}
 
iin [0]
iin [1]
ca reverse
add [2] [2] [0]
iout [2]
ac

188C - НОК

В других языках самый простой способ посчитать НОД двух чисел использует рекурсию. Особенность сопрограмм Roco заключается в невозможности написать рекурсию с единственной сопрограммой, которая будет вызывать сама себя — при повторном вызове сопрограммы ее выполнение продолжается с того же места, на котором оно прекратилось в прошлый раз. Поэтому проще было переписать стандартный алгоритм в виде цикла.

/* [0] - a
   [1] - b
*/
co gcd {
  eq [2] [0] 0
  if [2]
    ac
  set [2] [1]
  set [1] [0]
  mod [0] [2] [1]
}
 
iin [0]
iin [1]
set [3] [0]
set [4] [1]
ca gcd
/* now  [1] is gcd */
div [5] [3] [1]
mul [5] [5] [4]
iout [5]
ac

188D - Звездочки

Усложним задачу еще немного: здесь нужен вложенный цикл — внешний по строкам и внутренний по звездочкам в строке. Внутренний цикл будет вызываться несколько раз (из последовательных итераций внешнего), поэтому здесь можно было забыть о вышеупомянутой особенности вызова сопрограмм (которая до сих пор жизнь особо не усложняла) и потратить время на дебаг странных и неожиданных результатов.

/* [0] - * quantity
   [1] - current line
   [2] - current * in line
*/
 
co one_row {
   lt [3] [1] [2]
   if [3]
      ac
   cout 42
   inc [2]
}
 
co print_all {
   lt [3] [0] [1]
   if [3]
      ac
   set [2] 1
   ca one_row
   cout 10
   inc [1]
}
 
iin [0]
set [1] 1
ca print_all
ac

188E - HQ9+

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

/* [0] - YES or NO
   [1] - current char
*/
 
co one_char {
   cin [1]
 
   eq [2] [1] 10
   if [2]
      ac
 
   /* H */
   eq [2] [1] 72
   or [0] [0] [2]
   /* Q */
   eq [2] [1] 81
   or [0] [0] [2]
   /* 9 */
   eq [2] [1] 57
   or [0] [0] [2]
}
 
co say_yes {
   cout 89
   cout 69
   cout 83
   cout 10
   ac
}
 
co say_no {
   cout 78
   cout 79
   cout 10
   ac
}
 
set [0] 0
ca one_char
/* output the result stored in [0] */
if [0]
   ca say_yes
dec [0]
if [0]
   ca say_no
ac

Три последние задачи — уже почти настоящее программирование :-) Они используют то, что к переменным в Roco обращаются не по именам, а по индексам, а индекс в свою очередь может быть значением переменной. С массивами уже можно сделать больше интересных вещей, но и коды становятся длиннее и уязвимее к ошибкам.

188F - Двоичная запись

Недостаток двоичной записи состоит в том, что цифры вычисляются, начиная с младших разрядов, а выводить их нужно, начиная со старших. В принципе и эту задачу можно сделать без использования массивов — сначала "отобразить зеркально" это число в двоичной записи (тем же математическим приемом, что и в 188B - A + Reverse B), а потом выводить цифры отображения в том порядке, в котором они вычисляются. Но для пущей поучительности я приведу решение, которое вначале вычисляет цифры числа и записывает их в массив, а потом проходит по нему в обратном порядке и выводит их. Аккуратно с границами массива — легко вывести что-нибудь ненужное или не вывести все цифры, но это отслеживается на любом тесте.

/* [0] - current number
   [1] - index of last digit calculated
   [2]..[9] - service cells
   [10]..[[1]] - the actual digits of the number
*/
 
co calculate_digits {
   /* stop when the number is 0 */
   eq [3] [0] 0
   if [3]
      ac
 
   /* get next digit - put it to its location directly */
   mod [[1]] [0] 2
   /* update the number and its notation length */
   div [0] [0] 2
   inc [1]
}
 
co output_digits {
   /* stop when the next digit printed will be outside of the number */
   eq [3] [1] 9
   if [3]
      ac
 
   /* output the digit at [1] */
   iout [[1]]
   dec [1]
}
 
 
iin [0]
set [1] 10
ca calculate_digits
dec [1]
ca output_digits
ac

188G - Сортировка массива

В отличие от Befunge-раунда, в котором дебютировала эта задача, в Roco размер памяти ограничен только технически, а не концептуально, и не накладывал ограничений на алгоритм решения — сортировку сравнениями можно было писать с тем же успехом, что и сортировку подсчетом. Я выбрала последнюю, но в ходе реализации столкнулась с неожиданным багом. Помните, что сопрограммы продолжают выполняться с того же места, на котором остановились в прошлом вызове? Так вот, здесь это оказалось важно: если сопрограмма print_one_number вызывалась для нулевого количества чисел после ее предыдущего вызова, она успевала вывести одну копию этого числа еще до того, как выясняла, что на этот раз их выводить не нужно. Пришлось поставить дополнительную проверку, чтобы вызывать ее только для положительного количества чисел.

/* [1]..[100] - the counts of numbers
   [101] - quantity of numbers
   [102] - current number
   [103] - current index
*/
 
iin [101]
 
set [103] 1
co init {
   eq [104] [103] 101
   if [104]
      ac
   set [[103]] 0
   inc [103]
}
ca init
 
set [103] 0
co read {
   eq [104] [103] [101]
   if [104]
      ac
   iin [102]
   inc [[102]]
   inc [103]
}
ca read
 
set [102] 1
co print_sorted {
   eq [104] [102] 101
   if [104]
      ac
   set [103] 1
   co print_one_number {
      gt [104] [103] [[102]]
      if [104]
         ac
      iout [102]
      cout 32
      inc [103]
   }
   /* due to coroutine property (!), call only for positive quantity of numbers*/
   gt [104] [[102]] 0
   if [104]
      ca print_one_number
   inc [102]
}
ca print_sorted
ac 

188H - Стек

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

/* [0] - current character
   [1] - current stack size
   [2]..[9] - service
   [10]... - stack
*/
 
co plus {
   dec [1]
   add [3] [1] 9
   add [4] [3] 1
   add [[3]] [[3]] [[4]]
   ac
}
 
co multiply {
   dec [1]
   add [3] [1] 9
   add [4] [3] 1
   mul [[3]] [[3]] [[4]]
   ac
}
 
co number {
   sub [2] [0] 48
   inc [1]
   add [3] [1] 9
   set [[3]] [2]
   ac
}
 
co process {
   cin [0]
   /* end of line */
   eq [2] [0] 10
   if [2]
      ac
   /* digit - push on the stack */
   gt [2] [0] 47
   if [2]
      ca number
   eq [2] [0] 43
   if [2]
      ca plus
   eq [2] [0] 42
   if [2]
      ca multiply
}
 
set [2] 0
ca process
/* output the topmost element of the stack */
add [2] [1] 9
iout [[2]]
ac 
Разбор задач Surprise Language Round 6
  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Странно...
В посте указано, что нельзя написать рекурсию, используя одну сопрограмму.
А у меня во время соревнования получилось написать рекурсивное решение для вычисления НОД, 
используя следующее описание:
gcd(a,b)=gcd(b,a mod b), при b>0; a, при b=0.
Код сопрограммы:

/*[1] и [2] — числа a и b, [3]- вспомогательная переменная*/
co gcd{
  set [3] [2]
  mod [2] [1] [2]
  set [1] [3]
  if [2]
    ca gcd
  ac
}

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Мне кажется, что на самом деле получилась не рекурсия, а тот же цикл, только записанный иначе. Функция 1 вызывает функцию 2 "ca gcd", функция 2 начинает выполняться со следующей строки "ac", сразу останавливается и происходит возврат обратно в функцию 1, которая начинает выполняться заново с первой строки, что и создает иллюзию выполнения функции 2 с ее начала.