Я понимаю, что это немного математика, но - здесь идет.

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

Ваша цель - написать программу, которая принимает три целых числа x, y и n в качестве входных данных и выводит результат n-й гипероперации на x и y.

Например

1 1 1 выходы 2

2 4 4 выходы 65536

3 3 4 выходы 7625597484987

• Программа должна быть написана в кратчайшем коде.
• Вы можете получать входные данные STDINиз файла или из него.
• Библиотечные функции не допускаются.
• Входные ограничения: n будет ≥ 1.

http://en.wikipedia.org/wiki/Tetration дает хорошее объяснение на случай, если вы не сможете обдумать это.

Рубиновый, медленный, 86 84 83 персонажа

def f x,y,n
n>1?(c=x;2.upto(y){c=f(x,c,n-1)};c):x+y
end
p f *gets.split.map(&:to_i)

Рубин, быстро, 96 94 93 персонажа

def f x,y,n
n>1?(n>2?(c=x;2.upto(y){c=f(x,c,n-1)};c):x*y):x+y
end
p f *gets.split.map(&:to_i)

Первая версия является путем слишком медленно с последним тестом, поэтому я добавил версию , которая использует умножение в качестве базового случая вместо того. Первая версия требует возрастов для расчета 3 3 4; второй является мгновенным (в собственной консоли IRB; веб-версия немного медленнее).

Несколько красот Руби появляются здесь:

Почти каждое утверждение является выражением в рубине. Таким образом, вы можете заполнить точки с запятой внутри троичного оператора, если у вас достаточно круглых скобок. Coffeescript позаимствовал это. Он также заимствовал синтаксис вызова "без паренов".

Неявные возвраты: это классная функция, которая следует из предыдущего. Действительно, запуск последней строки функции с помощью returnсчитается хромым, даже когда он не играет в гольф.

Числа - это объекты в ruby ​​(даже nullэто объекты). В ruby ​​у целых чисел есть метод times, который выполняет блок, переданный ему несколько раз. Это всего лишь один из многих методов итераторов Ruby. Здесь uptoметод позволяет нам сохранить еще два символа поверх того, что timesпозволяет нам.

унарный *оператор здесь. Превращает массив в список аргументов. Так же, как у Javascript Function#apply, но он короче и лучше.

Унарный &превращает процедуру в блок. Хотя :to_iэто символ, он довольно хорошо преобразуется в процедуру. А именно, он превращается в процедуру, которая вызывает to_iсвой аргумент и возвращает результат. Больше информации о переполнении стека.

Было бы возможно получить это еще быстрее, используя n=3в качестве базового варианта , но я боюсь, что это не нужно. Это будет стоить всего 11 символов, хотя, благодаря еще одной красоте рубина: оператор возведения в степень **. В Python есть этот оператор, но он не первый (как заметил @ aka.nice - спасибо - у Fortran уже был этот оператор).

онлайн переводчик ruby ​​доступен здесь: http://repl.it/Ikj/1

APL, 62

{1=3⌷⍵:2⌷+\⍵⋄0=2⌷⍵:(⍵[3]⌊3)⌷⍵[1],0,1⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1}⎕

{...}⎕: Принимает оцененный ввод (разделенные пробелами числа преобразуются в числовой массив) и применяет к нему функцию.

1=3⌷⍵:: Если n равно 1 ...
2⌷+\⍵: вернуть сумму первых двух элементов (x + y) ...
⋄0=2⌷⍵:: иначе, если y равно 0 ...
(⍵[3]⌊3)⌷⍵[1],0,1: создать числовой массив [x, 0,1] и вернуть индекс min(n,3)...
⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1: В противном случае верните ∇ (x, ∇ (x, y-1, n), n-1). (∇ это ссылка на себя)

У меня есть оператор «гипер-рейзера», который принимает функцию и возвращает следующую гипероперацию

{⍺⍺/⊃⍴/⌽⍵}

Например, +{⍺⍺/⊃⍴/⌽⍵}будет функция умножения и +{⍺⍺/⊃⍴/⌽⍵}5 3выходы 15.

Но не могу заставить его повторяться. Может быть, кто-то еще может это сделать.

Python, 83

(На основании ответа flornquake )

def h(x,y,n):r=n>2;exec"r=h(x,r,n-1);"*y*(n>1);return(x+y,r)[n>1]
print h(*input())

Очень медленно для больших результатов.

Для 2, 4, 4выхода есть 65536.

Питон, 96 92

def h(x,y,n):r=1;exec(n>2)*y*"r=h(x,r,n-1);";return(r,(x+y,x*y)[n>1])[n<3]
print h(*input())

Вход: 3, 3, 4
Выход:7625597484987

Укорочено, используя пару идей @ WolframH .

Гольфскрипт, медленный, 39 знаков

 ~{\(.{3${[4$\2$4$.~}4$(*}{;;+}if])\;}.~

(живая ссылка)

Это стандартный рекурсивный алгоритм с базовым случаем n = 1 (сложение) (т.е. медленно). То же самое, что я использовал в своем решении Ruby

Вот версия с моими аннотациями (в основном, со стеком). Это не включает одну оптимизацию, которую я добавил позже:

~{            #read the input and do (x y n f)
 \(.{         #(x y f n-1); if(n-1)
  3${         #(x y f n-1 c)
   4$\2$4$.~  #(x y f n-1 x c n-1 f); call
  }3$(*       #y-1 times
  {\;}4*
 }{           #else
  ;;+         #return (x+y)
 }if
}.~           #once

~является оператором eval. В случае строк он обрабатывает строку как программу GolfScript. К счастью, разделенный пробелами список целых чисел является допустимой программой GolfScript, которая помещает эти целые числа в стек. По сравнению с этим, моя предыдущая версия подпрограммы ввода ( " "/{~}/разделенная пробелами и eval каждая) довольно хромая. В случае функций это вызывает функцию. Когда ему предшествует .(клон), он вызывает функцию с собой в качестве первого аргумента.

Гольфскрипт не совсем подходит для создания рекурсивных алгоритмов. Если вам нужен рекурсивный алгоритм, который нельзя оптимизировать с помощью хвостового вызова, вам нужно создавать и уничтожать фреймы стека, чтобы сохранить ваши переменные. На большинстве языков это делается автоматически. В golfscript вы должны фактически клонировать переменные (фактически, записи стека) и уничтожить записи стека, которые вам больше не нужны. Golfscript не имеет понятия стековых фреймов. Я говорил, что GolfScript является языком, основанным на стеке?

Первое требование понятно. Вы должны указать аргументы как-то. Хорошо только, если они сохранят свои исходные позиции. Второе требование является неудачным, особенно потому, что возвращаемое значение находится на вершине стека, а у golfscript отсутствует возможность удалить любой элемент стека. Вы можете вращать стек и отбрасывать новый верхний элемент, но это быстро накапливается. \;Это хорошо. \;\;\;\;\;нет. Вы можете сделать это \;в цикле ( {\;}9*; стоимость: 6 символов для отбрасывания до 9 элементов или 7 символов для отбрасывания до 99 элементов), но мы можем добиться большего:

Golfscript имеет первоклассные массивы. Он также имеет синтаксис литерала массива [1 2 3 4]. Что неожиданным является то , что [и ]на самом деле не является частью синтаксиса. Это всего лишь два оператора: [помечает текущую позицию в стеке и ]собирает каждый элемент, пока не найдет метку начала массива или не выйдет из стека, и не сбросит метку. Вы даже можете разорвать эти два на части и посмотреть, что произойдет. Ну, довольно интересная вещь:

Я говорил, что у golfscript нет концепции стековых фреймов? Я солгал. Это кадр стека: [. Вы можете отказаться от всего этого сразу ];. Но что, если мы хотим сохранить возвращаемое значение? Вы можете закрыть кадр стека при входе в функцию (тогда у нас есть слегка искаженная версия передачи по массиву - неинтересная концепция), или мы можем закрыть кадр стека и взять его последний элемент вместо того, чтобы полностью его отбросить: ]-1=или мы может uncons последний элемент вместо этого, а затем отбросить фрейм: ])\;. Они одинаковой длины, но последний немного круче, поэтому я его использую.

Таким образом, вместо 6 или 7 символов для очистки, мы можем сделать с 5. Я все еще чувствую, что это может быть больше в гольфе, но эй, мы сохранили характер.

Smalltalk Squeak 4.x аромат много байтов!

Я мог бы реализовать одну из рекурсивных форм в Integer в 71 символ

f:y n:n n=1or:[^(2to:y)inject:self into:[:x :i|self f:x n:n-1]].^self+y

Тогда чтение из файла или FileStream stdin будет стоить мне руки ... Squeak явно не был разработан как язык сценариев. Поэтому я потрачу много байтов на создание собственных утилит общего назначения, не связанных с проблемой:

Реализуйте этот 21-символьный метод в Stream (чтобы пропустить seaparators)

s self skipSeparators

Реализуйте этот метод с 20 символами в поведении (для чтения экземпляра из потока)

<s^self readFrom:s s

Затем 28 символов в строке (для создания дескриптора файла)

f^FileDirectory default/self

Затем 59 символов в FileDirectory (для создания readStream)

r^FileStream concreteStream readOnlyFileNamed:self fullName

Затем 33 символа в BlockClosure (чтобы оценить его n раз)

*n^(1to:n)collect:[:i|self value]

Затем 63 символа в массиве (оцените аргумент с получателем и аргументы, взятые из массива)

`s^self first perform:s asSymbol withArguments:self allButFirst

затем решите проблему, оценив этот фрагмент кода 31 в любом месте для чтения из файла с именем x

|s|s:='x'f r.[0class<s]*3`#f:n:

Даже без учета коммунальных услуг, это уже 71 + 31 = 102 символа ...

Теперь, поскольку я уверен, что потеряю codeGolf, у меня есть более забавная реализация в Integer:

doesNotUnderstand:m
    (m selector allSatisfy:[:c|c=$+])or:[^super doesNotUnderstand:m].
    self class compile:
        m selector,'y y=0or:[^(2to:y)inject:self into:[:x :i|self'
        ,m selector allButLast,'x]].^'
        ,(Character digitValue:()asBit)
        ,(m selector size-2min:1)hex last.
    thisContext sender restart

Этот метод определит (скомпилирует) двоичные сообщения, сделанные из n +, если он не существует (не понят получателем сообщения m), и возобновит выполнение в начале контекста отправителя. Я вставил дополнительный возврат каретки и пробелы для удобства чтения.

Обратите внимание, что (m selector size-2min:1)hex lastэто сокращенная форма (m selector size>2)asBit printString.

Если бы не демонстрация злых сверхдержав Smalltalk, последнее утверждение можно было бы заменить на более короткие и простые

^m sendTo:self

Теперь реализуем утилиту 28 символов в Character (чтобы повторить ее n раз в строке)

*n^String new:n withAll:self

Затем оцените это выражение из 43 символов:

|i s|i:=0class.s:='x'f r.[i<s]*2`($+*(i<s))

Мы можем ускорить еще на 10 символов, реализовав в Integer:

++y^self*y

и в этом случае у нас также есть более короткий код, потому что мы можем заменить ^',(m selector size-2min:1)hex lastна^1'

При такой высокой цене код работает со вторым целым числом = 0 :)

Groovy - 77

h={x,y,n->n<2?x+y:y<2?x:h(x,h(x,y-1,n),n-1)}
print h(args.collect{it as int})

Примечание: это требует неприличного количества стека (и времени) для не крошечных аргументов.

Система компьютерной алгебры AXIOM, байты 69

p(x,y,n)==(n<=1=>y+x^n;n=2=>y*x;n=3=>x^y;y<=0=>1;p(x,p(x,y-1,n),n-1))

тест:

(2) -> p(1,1,1)
   (2)  2
                                                 Type: Expression Integer
                                   Time: 0.05 (IN) + 0.03 (OT) = 0.08 sec
(3) -> p(2,4,4)
   (3)  65536
                                                 Type: Expression Integer
                                                              Time: 0 sec
(4) -> p(3,3,4)
   (4)  7625597484987
                                                 Type: Expression Integer
                                                              Time: 0 sec

Это устранит некоторую рекурсию ... Возможно, я переставлю x и y в некотором возвращении ... есть ли другие тестовые значения?

APL (NARS), символы 61, байты 122

{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}

тест:

  h←{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}
  h 1 1 1
2
  h 2 4 4
65536
  h 3 4 4
∞
  h 3 3 4
7625597484987