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

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

Итак, разбор задач. Лично для меня Befunge — один из тех языков, на которых горадо проще писать код, чем читать его (а уж искать баги в чужом — вообще каторга; в таком случае отсутствие взломов не может не радовать). Поэтому я ограничусь описанием общей идеи решения и приведением авторского кода — чисто чтобы показать, что автор не только издеваться над участниками горазд, но и сам решать может.

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

&:2*1-*.@

"Утешительная" задача, требующая только понимания принципа работы со стеком. Дублируем прочитанное число n, верхнюю копию умножаем на 2 и вычитаем из результата один — теперь в стеке два числа n и 2n - 1. Перемножаем их и выводим на печать.

B. Gnikool Ssalg

> ~ : 25*- #v_ $ >:#,_ @
^           <

Здесь проще всего воспользоваться основным свойством стека — элементы вынимаются из него в порядке, обратном тому, в котором их складывали. Решение разбивается на два цикла: в первом нужно прочитать входные данные до конца строки (символа #10) и оставить все прочитанные символы в стеке, во втором — выводить элементы стека, пока он не опустеет. Для организации цикла используются операторы _ и |, но нужно помнить о том, что они удаляют из стека тот элемент, в зависимости от которого выполнение программы направляется по одному или другому пути. Поэтому если этот элемент в перспективе еще может пригодится, его лучше продублировать, выполнить сравнение, а потом использовать оставшуюся копию.

C. Десятичная сумма

0 &>: #v_ $. @
       >1- \ & + \v
   ^              <

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

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

D. Возведедение в степень

&30p & &32p 1 \ >:#v_ $. 25*, @
                   >1- \ 30g * 32g % \v
                ^                     <

Задание усложняется еще немного: сейчас на каждой итерации нужно жонглировать более чем двумя числами, поэтому одним стеком не обойтись — в Befunge, в отличие от некоторых других стековых языков, нет команды, которая позволила бы добраться до элементов стека глубже второго, не теряя верхних элементов. Поэтому придется освоить использование "памяти" — ячеек программы, не занятых собственно программой. Вообще-то основное назначение команд p и g — написание самомодифицирующего кода, но нормальной памяти произвольного доступа в языке нет, приходится изощряться :-)

С использованием памяти все внезапно становится просто: a и c записываются в память, на стеке остается только текущее значение степени и количество оставшихся умножений. В теле цикла нужные значения извлекаются из памяти непосредственно перед их применением, чтобы не засорять стек.

E. Числа трибоначчи

031p032p133p & > 31g 32g + 33g + 39*1-% 32g 31p 33g 32p 33p v
               | :-1                                        <
               > 31g . 25*,@

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

F. Разложение на множители

& 211p > : 1 - #v_ 25*, @ > 11g:. /    v
                > : 11g %!|
                          > 11g 1+ 11p v
       ^                               <

В этой задаче проще всего было забыть код, который молниеносно слетает с кончиков пальцев на любом нормальном контесте :-), и вспомнить, как это решалось когда-то давно. Само число достаточно маленькое, поэтому можно проверить все числа от 2 до n и не возиться с проверкой до корня из n. Кроме того, если сразу делить текущее число на найденный множитель, можно не пропускать составные делители, потому что на них число все равно не будет делиться. Наконец, если множитель найден, не обязательно сразу искать степень, в которой он входит в разложение — достаточно не увеличивать его на этой итерации цикла, и на следующей он снова найдется. Храним n в стеке, текущий множитель — в памяти и опять же аккуратно выполняем действия по каждой ветви программы, и задача решена.

G. CAPS LOCK ON

> ~ : 25*- #v_ 25* , @         >48*-v
            > :: "`"` \"{"\` * |    > , v
                               >    ^
^                                       <

Эта задача была очень похожа на пример CamelCase из приведенной статьи о Befunge. Она была даже легче — не нужно было запоминать тип предыдущего символа. Самым сложным, пожалуй, было освоение оператора "больше" и применение его к нужным значениям.

H. Скобки

v                > "ON" ,,   v
> ~ : 25*- #v_ $ |           > 25*, @
                 > "SEY" ,,, ^
            > : 58*- #v_ v
                      > \ : 58*- #v_v
                                  \ $
^                        <        <$<

В оригинале я собиралась давать строки, состоящие из трех типов скобок, но к тому времени, как я реализовала проверку сбалансированности хотя бы одного типа, я осознала, что меня не поймут. Даже с одним типом возни достаточно много. Решать можно двумя способами: хранить на стеке сами открывающие скобки (в случае с несколькими типами скобок так бы и пришлось делать) или просто количество скобок, оставшихся незакрытыми. Ответ "NO" дается в двух случаях — если текущая скобка — закрывающая, а на стеке/в счетчике пусто, или если после конца входных данных на стеке/в счетчике остались еще открывающие скобки.

I. Сортировка массива

v
> 543** >     :#v_ $&>           :#v_ 1 > :0g >    :#v_ $ 1+: 543** `! #v_ 25*,@
        ^-1p0\0:<    ^-1 p0\+1 g0:&<          ^-1\.:\<
                                        ^                               <

Опять же, забываем о приятных мелочах типа Arrays.sort() и обращаемся к истокам, а именно к сортировке подсчетом. Размер программы на Befunge — 25 строк на 80 столбцов; заданные числа могут варьироваться от 1 до 60, следовательно, мы можем хранить количество чисел i в ячейке (0, i), если в этой области программы (первая строка) не будет нужных нам команд. Программа будет состоять из трех основных циклов — инициализация ячеек памяти нулями, чтение входных данных и увеличение значений в соответствующих ячейках и преобразование итоговых количеств в отсортированный массив.

J. Расчет календаря

56*1+ :10p :30p :50p :70p :80p :52*0p :62*0p 1- :2-20p :40p :60p :90p 92+0p v
v % *:*45 : &                                                               <
    >                      > 20g 1+ 20p v
> ! |             >         v
    > : 52*:* % ! |
                  > : 4 % !|
v                          <<           <
                         > . 00g . 25*, @
> $100p & > : 00g 0g ` ! |
                         > 00g 0g - 00g 1+ 00p v
          ^                                    <

Еще одна задача, которая на нормальном высокоуровневом языке решается очень просто, а на Befunge — в лучшем случае неаппетитно. Прежде всего инициализируем ряд ячеек памяти количествами дней в месяцах нормального, невисокосного года. Затем считываем номер года, проверяем его на високосность и при необходимости изменяем количество дней в феврале. Наконец, считываем номер дня и в цикле вычитаем из него количество дней в текущем месяце, увеличивая при этом номер текущего месяца. Насколько проще решалась бы эта задача, если бы наш календарь был немного лучше упорядочен!

Разбор задач Unknown Language Round 4
  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только сейчас понял, что число записывается в ячейку в виде однобайтового числа, а не символа [0-9]!
А я-то парился с 4-ой задачей, кодируя символы по десятичным разрядам...
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Довольно забавно, что интерпретатор на джаве работает не так, как если его запускать просто из питона ( если приведенный выше код F проходит на нём ). В интерпретаторе WASABI содержимое ячеек воспринимается как знаковый char, вроде бы... Если вводить большие простые числа (больше 128), то получается бесконечный цикл с выводом -1... Из-за этого я не решился хранить делитель просто в одной ячейке... :(
И ещё одним расхождением является то, что в стеке не могут лежать длинные числа...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Да, char в Wasabi от -128 до +127, мне пришлось это прочувствовать в задаче про разложение на простые.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите, пожалуйста, почему к задаче 2, этот код http://ideone.com/ph4u8 выводит "Ошибка времени исполнения". Локально(интерпретатор Wasabi) работает нормально.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Когда считывается последний символ с кодом #10 управление по оператору | идет вниз. А там вообще неизвестно что - непечатный символ.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Какой именно символ - непечатный?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        символ в 4 строке 9 столбце у меня отображается квадратиком
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
всё-таки что происходит, при попытке выполнить команду : (дублирование вершины стека) для пустого стека?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    По всей видимости, ничего. А если не верится и очень любопытно - можно же посмотреть код интерпертатора)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    В стеке должен появиться нуль.
    На сайте разработчика было написано, что если попытаться вычитать элемент из пустого стека, то получишь нолик.
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
wow!!!! great language!!! the hardest one ever on these contests!!! however thanks for these attractive contests!
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
It totally beyond my mind,I have never believe a language can be so funny.thanks to this contest.
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Re: Array Sorting: did you intentionally set the input size to 100 to defeat comparison-based implementations? My first instinct was to go with the counting sort too (mainly because I remembered it as the easiest way to implement sorting in Brainfuck) but I think it would have been nice to allow a variety of approaches.

For example, I have a nice solution using Gnome sort that only works with less than 80 elements because that's the number of cells in a single row. It's not very hard to change it to use a rectangular area of the board instead, but that does increase the implementation complexity somewhat. (The advantage of Gnome sort is that it only uses a single array index, which is easily kept on top of the stack.)

On an unrelated note, it's a shame that these Befunge programs are so hard to read, as I'm sure many competitors had quite creative solutions that are doomed to go unappreciated. That being said, I loved competing in an esoteric language for a change (I usually only do that in the CodeJam qualification round), and I regret showing up an hour to late for this (and as a result being unable to finish the last problem).
  • 13 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
    Not intentionally; I didn't realize anybody would be willing to go for comparison-based sorting, since I wasn't :-)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    At least your programm passes if there are 80 elements... I don't know why i have tried to implement bubble sort) but it timelimits at 40 elements... While with java interpreter it runs well :) Scripting lanugages are so slow :(
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Yes, the timelimit is problematic. If I modify my Gnome sort to work with larger input the added complexity makes it just barely too slow. But insertion sort runs in time (using the first two rows of the grid to store the array).

      For the befungee interpreter, the trick seems to be to make your loops as short as possible, eliminating any spaces, because skipping over whitespace takes times too.

13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

 Этот контест мне напомнил то, что я видел на сайте http://www.hacker.org/. Там есть IT/хак/крипто-квест (challenges), если в этом квесте более-менее продвинуться, то начинают появляться задания на написание программ на местных (самопальных?) языках HVM и SuperHack. Второй из них сильно напоминает Befunge. Посмотрите, кому интересно :)

13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
I surprised at this contest ;) Interesting language...Thx for solutions
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
just a note, for problem J you don't have to programmatically write the #days in each month to the source code, because after all, it is the source code so you can that data into your program directly using ascii chars to represent integers in the range 28-31
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Characters with these ASCII-codes are invisible (something-separators), and some Befunge interpreters might not work well with them. I tried to show code which is portable, if this word can be used for Befunge programs :-)
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      the ascii chars could be offset (which can be accounted for by modifying the code); for example the character '0' could represent 28 days, '1' could represent 29, etc.
      but yes you're correct of course.