Codegolf — Оценить N-Ю Гипероперацию

Я понимаю, что это немного математика, но вот так.

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

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

Например.

STDIN outputs 2

3 3 4 outputs 65536

2 4 4 outputs 7625597484987

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

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

#код-гольф #арифметика

АПЛ, 62

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
   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
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

{(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} : Takes evaluated input (space-separated numbers evaluates to a numerical array) and apply function to it.

(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 : If n equals 1...
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)) : Return sum of first 2 elements (x+y)...
(n?a)b : Else if y equals 0...
(1?a)b=a+b (2?_)0=0 (_?_)0=1 (n?a)b=(n-1)?a$n?a$b-1 : Create numerical array [x,0,1] and return index (n?a)b ...
1?x=(x+) n?x=(!!)$iterate((n-1)?x)$signum$n-2 : Else return ∇(x,∇(x,y-1,n),n-1). (∇ is self-reference)

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

Например, n<2 would be the multiplication function and h=function(x,y=x,n)`if`(n<2,x^n+y,{z=n>2;while(y){z=h(x,z,n-1);y=y-1};+z}) выходы 15.

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

Руби, медленно, 86 84 83 символа

Руби, быстро, 96 94 93 символа

Первая версия способ слишком медленно в последнем тестовом примере, поэтому я добавил версию, в которой в качестве базового случая используется умножение, а не сложение. Первая версия требует много времени для расчета ])\; ; the second one is instanteneous (in the native IRB console; the web version is a bit slower).

Здесь показаны несколько красавиц Ruby:

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

Неявный возврат: это классная функция, вытекающая из предыдущей. Действительно, начиная последнюю строку функции с ]-1= is considered lame, even when not golfing.

Числа — это объекты в Ruby (даже ]; is an object). In ruby, integers have the method [ , который выполняет переданный ему блок несколько раз. Это лишь один из многих методов итератора Ruby. Здесь ] method lets us save two more characters over what [ позволяет нам.

унарный ] is the splat operator here. It turns an array into an argument list. Just like Javascript's [ , но это короче и лучше.

унарный [1 2 3 4] turns a procedure into a block. While {\;}9* это символ, он довольно хорошо преобразуется в процедуру. А именно, он превращается в процедуру, вызывающую \; on its argument and returns the result. Дополнительная информация о переполнении стека.

Можно было бы сделать это еще быстрее, используя \;\;\;\;\; as the base case, but I'm afraid it is not needed. It would only cost 11 characters, though, thanks to another beauty of ruby: the exponentiation operator \; . В Python есть этот оператор, но он не первый (как заметил @aka.nice — спасибо — в Фортране уже был этот оператор).

онлайн-интерпретатор Ruby доступен здесь: http://repl.it/Ikj/1

APL (Диалог Юникод), 31 23 22 байт (СБКС)

Сэкономлено 6 байт благодаря барботер

Попробуйте онлайн!

Может использоваться как " "/{~}/ .

Желе, 15 байт

Попробуйте онлайн!

Написать программу с тремя аргументами в Jelly сложно, хотя в этой задаче нам, по крайней мере, нужно использовать один из них только один раз. Итак, эта программа принимает три аргумента в порядке ~{\(.{3${[4$\2$4$.~}4$(*}{;;+}if])\;}.~ and recurses as a dyadic function. Roughly a hybrid of это решение Аккермана с ответ пользователя на APL.

Как это работает

Питон, 83 года

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

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

Для ++y^self*y the output is |i s|i:=0class.s:='x'f r.[i<s]*2`($+*(i<s)) .

Питон, 96 92

Вход: ^m sendTo:self
Выход: (m selector size>2)asBit printString

Укорочено с помощью пары Идеи @WolframH.

Smalltalk Squeak 4.x добавляет много байтов!

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

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

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

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

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

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

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

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

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

Даже без учета утилит это уже 71+31=102 символа...

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

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

Обратите внимание, что f:y n:n n=1or:[^(2to:y)inject:self into:[:x :i|self f:x n:n-1]].^self+y is a shorted form of 7625597484987 .

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

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

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

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

и в этом случае у нас также есть более короткий код, потому что мы можем заменить 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()) with ṛ+⁵ðx’ß@ƒ>2¥ðỊ? Main program as a dyadic link. Left = n, Right = y, 3rd arg (⁵) = x A..ðB.......ðC? If C then A else B Ị If n <= 1 ṛ+⁵ Then y + x x’ß@ƒ>2¥ Else... x’ y copies of n-1 ß@ƒ>2 Reduce with the program itself flipped, with the default value being n>2 (1 or 0)

За такую ​​высокую цену код работает со вторым целым числом = 0 :)

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

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

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

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

{ ×a←⍺-1: ⍝ Check if n is greater than 1 a←⍺-1 ⍝ Assign n - 1 to a variable a to reuse later × ⍝ Sign of a (0 if addition, 1 otherwise) a∇⍣⍵×⍺-2 ⍝ Apply the (n-1)th hyperoperation y times to x ×⍺-2 ⍝ Sign of n-2 (the identity for the nth hyperoperation ⍣ ⍝ Power operator, apply ∇ ⍝ the derived function (f x) ⍵ ⍝ y times ×⍺-2 ⍝ to the identity a ⍝ With n-1 as the new n ⋄ ⍵ + ⍺⍺ ⍝ n is 1 (addition) } ``` is the eval operator. In case of strings, it treats the string as a GolfScript program. Luckily, a space-separated list of integers is a valid GolfScript program that pushes those integers on the stack. Compared to this, my previous version of the input routine ( n (x f) y , разделенный по пробелу и оценочный каждый) довольно неубедительно. В случае функций он вызывает функцию. Когда ему предшествует {×a←⍺-1:a∇⍣⍵×⍺-2⋄⍵+⍺⍺} (clone), it calls the function with itself as the first argument.

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

Первое требование понятно. Вам нужно как-то указать аргументы. Хорошо, если они тоже сохранят свои исходные позиции. Второе требование неудачно, особенно потому, что возвращаемое значение находится на вершине стека, а в Golfscript нет возможности удалить любой элемент стека. Вы можете повернуть стек и удалить новый верхний элемент, но он быстро накапливается. ** is fine. n=3 нет. Вы можете сделать to_i in a loop ( :to_i ; стоимость: 6 символов для отбрасывания до 9 элементов или 7 символов для отбрасывания до 99 элементов), но мы можем сделать лучше:

Golfscript имеет первоклассные массивы. Он также имеет синтаксис литерала массива & . What's unexpected is that Function#apply и * are not actually a part of the syntax. They are merely two operators: times отмечает текущую позицию в стеке, и upto collects every element until it finds the start-of-array mark or runs out of stack, and discards the mark. You can even tear these two apart and see what happens. Well, quite an interesting thing:

Я говорил, что в Golfscript нет понятия стековых фреймов? Я солгал. Это кадр стека: times . You can discard it all at once: null . Но что, если мы хотим сохранить возвращаемое значение? Вы можете закрыть фрейм стека при входе в функцию (тогда у нас будет слегка искаженная версия передачи по массиву — неинтересная концепция), или мы можем закрыть фрейм стека и взять его последний элемент вместо того, чтобы полностью отбрасывать его: return or we can uncons the last element instead, and затем отказаться от кадра: 3 3 4 . They're the same length, but the latter is slightly cooler, so I'm using it.

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

Круви - 77

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

Р, 70 байт

Попробуйте онлайн!

Как отмечалось в других ответах, возврат к гипероперации сложения n=1 происходит довольно медленно к тому времени, когда n>3, а гипероперация является тетрацией или хуже. ТИО ссылка включает рекурсивную версию, начинающуюся с n=2 (умножение), чтобы проверить, что подход верен и работает для последнего тестового примера...

Р, 78 74 байта

(для всех n, включая n=0)

Попробуйте онлайн!

Это была одна из тех разочаровывающих задач, когда я не мог удержаться и не попытался написать кратчайший текст. общий решение, даже если n=0 не требовалось в вопросе.
Поведение n=0 (приращение) и n=1 (сложение) отличается от всех последующих гиперопераций, поскольку y=1 не является тождественной функцией для этих двух случаев. Я обошел это, остановив рекурсию, когда +{⍺⍺/⊃⍴/⌽⍵} , and returning {⍺⍺/⊃⍴/⌽⍵} , которому удается удовлетворить как случаи n=1, так и n=0.
Для дополнительной красоты (за счет еще +2 байтов) мы можем указать значение по умолчанию для y из x, что означает, что его вообще не нужно предоставлять в качестве аргумента для n = 0, поскольку это можно рассматривать как унарная операция над y.
Итак: +4 байта потрачено впустую, но теперь я счастливее.

Хаскелл, 45 байт

Попробуйте онлайн!

Назовите это с min(n,3) .

Хаскелл, 51 байт

Попробуйте онлайн!

Скопировано прямо из формулы гипероперации на Википедия. Назовите это с ⋄0=2⌷⍵: .

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

тест:

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

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

тест: