Соревнование

Реализовать тетрация (ака Power Tower или Hyperexponentiation) с наименьшим количеством символов.

Условия

• Не используйте «власть» оператор или его эквиваленты (такие как pow(x,y), x^y, x**yи т.д.)
• Ввод дан как: x y(разделенный пробелом)
• xвозведено в порядок само по себе y.
• Ваш метод должен быть в состоянии вычислить как минимум 4 3(4 возведено в степень 3 раза)

Скоринг

• Победа с наименьшим количеством очков: (количество символов)
• Бонусный вычет, если вы не используете оператор умножения (-5 баллов).
• Нет требований к скорости / памяти. Бери сколько хочешь.

Примеры

x, 0 -> 1

2, 2 -> 2^2 = 4

2, 4 -> 2^(2^(2^2)) = 65536

4, 3 -> 4^(4^4) = 4^256 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

Открыт для предложений / изменений / вопросов

J, оценка 7 (12 символов - 5 баллов за избежание умножения)

+/@$/@$~/@$~

использование:

   4 +/@$/@$~/@$~ 3
1.34078e154
t=.+/@$/@$~/@$~  NB. define a function
   4 t 3
1.34078e154
   2 t 2
4

Всего несколько вложенных складок:

• Используя умножение было бы */@$~/@$~
• Используя power, это было бы ^/@$~где $~создает массив, /является функцией сгиба.

Haskell, 87 85 - 5 == 80 82

import Data.List
t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)

Не использует ни возведения в степень, ни умножения, ни сложения (!), Просто перечисляет операции. Демонстрация:

Prelude> :m +Data.List
Prelude Data.List> let t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)
Prelude Data.List> t 2 2
4
Prelude Data.List> t 2 4
65536
Prelude Data.List> t 4 3

...
хм ... ты ничего не сказал о производительности или памяти, не так ли? Но, учитывая достаточно миллиардов лет и несколько петабайт ОЗУ, это все равно даст правильный результат (genericLength может использовать bigInt для подсчета длины списка).

GolfScript, 15 18 символов

~])*1\+{[]+*{*}*}*

Да, один из *операторов s является оператором умножения (упражнение: какое?), Поэтому я не могу претендовать на бонус в 5 символов. Тем не менее, он чуть короче, чем решение Питера .

Эта более ранняя версия с 15 символами в остальном такая же, но не выдает никаких выходных данных, когда второй аргумент равен 0. Спасибо res за обнаружение ошибки.

~])*{[]+*{*}*}*

J, 16 19 12 символов

*/@$~/1,~$~/

или как глагол (17 символов):

h=:[:*/@$~/1,~$~/

использование:

   h 2 4
65536

или принимая ввод с клавиатуры ( 24 27 20 символов):

*/@$~/1,~$~/".1!:1]1

спасибо FUZxxl за указание на мою глупость. :-)

Объяснение:

J читается справа налево, поэтому используется 2 4:

/используется для вставки глагола $~между каждой парой элементов в списке. $~берет левый элемент и формирует его, $используя правый элемент ( ~переворачивает аргументы) - так что это будет эквивалентно тому, 4 $ 2что даст вам список 2s длиной четыре элемента 2 2 2 2.

Теперь мы добавляем 1 к списку 1,~и затем делаем то же самое снова; /вставьте глагол */@$~между каждой парой элементов в списке. Этот глагол начинается таким же образом, $~но на этот раз он /вставляет *между каждым элементом вновь сгенерированного списка. @Просто убеждается , что */@$~работает как один глагол вместо двух. Это дает 2умноженное на себя достаточно времени, чтобы быть эквивалентным 2^4.

Страница словарного запаса J - я нахожу решение проблем с J забавным только из-за того, как это иногда делает вещи.

Добавление еще одной итерации для удаления *оператора имеет 2 проблемы

• Он имеет 17 символов ( +/@$~/,@$~/1,~$~/), что, даже с бонусом -5, слишком длинное
• Недостаточно памяти, если число становится слишком большим, поэтому не соответствует требованию возможности расчета 4 3

GolfScript (24 символа - 5 = 19 баллов)

~\1{1{0{+}?}?}{@\+@*}:?~

безумно медленно

(или 20 символов)

~\1{1{*}?}{@\+@*}:?~

намного быстрее

Python, 70

При этом используются вложенные evalвызовы, в итоге получая строку, "a*a*a*a...*a"которая оценивается. Почти половина баллов тратится на получение аргументов ... хотя я заметил, что некоторые другие решения не беспокоятся об этом.

a,b=map(int,raw_input().split())
exec"eval('*'.join('a'*"*b+'1'+'))'*b

Scala: 110

type B=BigInt
def r(a:B,b:B,f:(B,B)=>B):B=if(b>1)f(a,r(a,b-1,f))else a
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_))))

ungolfed:

type B=BigInt
def recursive (a:B, b:B, f:(B,B)=>B): B = 
  if (b>1) f (a, recursive (a, b-1, f)) 
  else a
recursive (2, 3, recursive (_, _, recursive (_, _, (_ + _))))

объяснение:

type B=BigInt
def p (a:B, b:B):B = a+b
def m (a:B, b:B):B = if (b>1) p (a, m (a, b-1)) else a
def h (a:B, b:B):B = if (b>1) m (a, h (a, b-1)) else a
def t (a:B, b:B):B = if (b>1) h (a, t (a, b-1)) else a

plus, mul, high (: = pow), тетрация - все работает одинаково. Общий шаблон может быть извлечен как рекурсивный метод, который принимает два BigInts и базовую функцию:

def r (a:B, b:B, f:(B,B)=>B):B = 
  if (b>1) f(a, r(a, b-1, f)) else a
r (4, 3, r (_,_, r(_,_, (_+_))))

Подчеркивания являются заполнителями для чего-то, что вызывается в этой последовательности, например, сложение plus (a, b) = (a + b); поэтому ( + ) - это функция, которая принимает два аргумента и добавляет их (a + b).

к сожалению, у меня возникают проблемы с размером стека. Это работает для небольших значений для 4 (например: 2) или если я уменьшу глубину на один шаг:

def h(a:B,b:B)=r(a,b,r(_,_,(_*_))) // size -7, penalty + 5
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_)))) 

Исходный код состоит из 112 символов, и если он действителен, то получится 107. Возможно, я узнаю, как увеличить стек

Расширенный алгоритм может быть преобразован в хвостовые рекурсивные вызовы:

type B=BigInt
def p(a:B,b:B):B=a+b
import annotation._
@tailrec
def m(a:B,b:B,c:B=0):B=if(b>0)m(a,b-1,p(a,c))else c
@tailrec
def h(a:B,b:B,c:B=1):B=if(b>0)h(a,b-1,m(a,c))else c
@tailrec
def t(a:B,b:B,c:B=1):B=if(b>0)t(a,b-1,h(a,c))else c

Хвостовой рекурсивный вызов длиннее исходного метода, но в длинной версии не вызвал переполнение стека - однако он не дает результата в разумные сроки. t (2,4) в порядке, но t (3,3) уже был остановлен мной через 5 минут. Тем не менее, это очень элегантно, не так ли?

// 124 = 119-5 bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,r(_,_,0,(_+_))))

А теперь то же самое, что и выше: используйте вонючее умножение (мы даже получаем прибыль, отказываясь от бонуса в 5, потому что мы экономим 7 символов: win = 4 символа)

// 115 without bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,(_*_)))

вызов:

timed ("t(4,3)")(t(4,3)) 
t(4,3): 1
scala> t(4,3)
res89: B = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

время выполнения: 1 мс.

Br ** nfuck, 128-5 = 123 байта

+<<+<<,<,[>[>+>>+<<<-]>[<+>-]>[>[>>+>+<<<-]>>>[<<<+>>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>[-]>[<<+>>-]<<<<-]>>[<<+>>-]+<[-]<<<<-]>>>.

Ввод осуществляется в форме символов с кодовыми точками чисел, желаемых в качестве входных данных. Выход такой же.

Объяснение придет, когда у меня будет время ниже. Получу ли я бонусные баллы за то, что не использовал возведение в степень, умножение или даже сложение?

Cell 3 (0-indexed) is the running total x.
This calculates the nth tetration of a.

+<<+<<,<,                                       Initialize tape with [n, a, 0, 1, 0, 1]
[                                               While n:
  >[>+>>+<<<-]>[<+>-]                             Copy a 3 cells to right: [n, a, 0, x, a, 1]
  >[                                              While x:
    >[>>+>+<<<-]>>>[<<<+>>>-]                       Copy a 2 cells to right: [n, a, 0, x, a, 1, a, 0]
    <<[>[>+>+<<-]>>[<<+>>-]<<<-]                    Cell 7 = prod(cell 5, cell 6)
    >[-]>[<<+>>-]<<<<-]                             Move this value to cell 5. End while.
  >>[<<+>>-]+<[-]<<<<-]                           Update x to result of exponentiation. End while.
>>>.                                            Print the result!

Это работает (проверено) для x 0, 0 x, x 1, 1 x, x 2, 2 3, и2 4 . Я пытался 3 3, но он работал в течение нескольких часов без завершения (в моей реализации Java - возможно, не оптимально) (РЕДАКТИРОВАТЬ: в EsotericIDE @ Timwi [Это здорово! Вы все должны попробовать]. Не повезло.). Теоретически это работает до размера ячейки конкретной реализации.

Python, 161 - 5 (без оператора *) = 156

r=xrange
def m(x,y):
 i=0
 for n in r(y):i+=x
 return i
def e(x,y):
 i=1
 for n in r(1,y+1):i=m(i,x)
 return i
def t(x,y):
 i=1
 for n in r(y):i=e(x,i)
 return i

взывать:

t(2, 4)

Perl, 61 символ

вот странный

sub t
{
  ($x,$y,$z)=@_;
  $y>1&&t($x,$y-1,eval$x."*$x"x($z-1||1))||$z
}

использование:

print t(2,4,1)

Mathematica , 40 33

Это не совсем соответствует правилам, но в любом случае это не оспаривает самый короткий код, и я надеюсь, что он будет кому-то интересен.

m@f_:=Fold[f,1,#2~Table~{#}]&;

m[m@Sum]

Это создает функцию «тетрации» при запуске, но аргументы должны быть заданы в обратном порядке. Пример:

m[m@Sum][3, 4]

1340780792994259709957402499820584612747936582059239337772356144372176 4030073546976801874298166903427690031858186486050853753882811946569946 433649006084096

Haskell:  58  51 символ с умножением или без него.

i f x 1=x;i f x n=f$i f x$n-1
t=i(\o n->i(o n)n)(+)4

Ungolfed:

bump op n a = iterate (op n) n !! (fromIntegral $ a-1)
tetrate = iterate bump (+) !! 3

Более короткое определение происходит от вставки «bump» и определения пользовательской версии «iterate». К сожалению, результат невозможен, но начинание с (*) вместо (+) дает приличную скорость. В ghci:

Prelude> let i f x 1=x;i f x n=f$i f x$n-1
(0.00 secs, 1564024 bytes)
Prelude> let t=i(\o n->i(o n)n)(*)3
(0.00 secs, 1076200 bytes)
Prelude> t 4 3
13407807929942597099574024998205846127479365820592393377723561443721764030073546
976801874298166903427690031858186486050853753882811946569946433649006084096
(0.01 secs, 1081720 bytes)

Руби 66 59 символов

def e(x,y)
r=1
(1..y).each{t=x
(2..r).each{t*=x}
r=t}
r
end

Питон, 112 символов

Числа должны быть первым и вторым аргументом: python this.py 4 3
**оператор не используется.
*используемый. Это довольно просто реализовать, точно так же **, но стоит более 5 символов.

import sys
p=lambda y:y and x*p(y-1)or 1
t=lambda y:y>1 and p(t(y-1))or x
x,y=map(long,sys.argv[1:])
print t(y)

C 117 105 99 символов

EDIT: Объединять две функции pи rв одну, сэкономив несколько символов.
Из 99 символов 52 выполняют фактические вычисления (включая определения переменных). Остальные 47 предназначены для обработки ввода и вывода.
BUG: плохо обрабатывает полномочия 0 (например 0 2). Должен найти минимальную стоимость исправления. Это не ошибка, я забыл, что 0 2не определено.

Успешно обрабатывает 4 3, и даже дает точный результат. Тем не менее, может быть неточным для некоторых меньших чисел.
Печатает номер с трейлингом .000000.

x,y,z;
double R(){return--y?!z?y=R(),R(z=1):x*R():x;}
main(){
    scanf("%d%d",&x,&y);
    printf("%f\n",R());
}

Фактор, 187 символов

USING: eval io kernel locals math prettyprint sequences ;
IN: g
:: c ( y x o! -- v )
o 0 = [ x y * ] [ o 1 - o!
y x <repetition> 1 [ o c ] reduce ] if ;
contents eval( -- x y ) swap 2 c .

Перед гольфом:

USING: eval io kernel locals math prettyprint sequences ;
IN: script

! Calculate by opcode:
!   0 => x * y, multiplication
!   1 => x ^ y, exponentiation
!   2 => x ^^ y, tetration
:: calculate ( y x opcode! -- value )
    opcode 0 = [
        x y *
    ] [
        ! Decrement the opcode. Tetration is repeated exponentiation,
        ! and exponentiation is repeated multiplication.
        opcode 1 - opcode!

        ! Do right-associative reduction. The pattern is
        !   seq reverse 1 [ swap ^ ] reduce
        ! but a repetition equals its own reverse, and 'calculate'
        ! already swaps its inputs.
        y x <repetition> 1 [ opcode calculate ] reduce
    ] if ;

contents eval( -- x y )         ! Read input.
swap 2 calculate .              ! Calculate tetration. Print result.

Я не удалил оператор умножения *. Если бы я это сделал, то мне нужно было бы добавить некоторую логику, выражающую, что сумма пустой последовательности равна 0, а не 1. Эта дополнительная логика будет стоить больше, чем бонус -5.

Нарушитель правил, 124 + 10 = 134 символа

USING: eval kernel math.functions prettyprint sequences ;
contents eval( -- x y ) swap <repetition> 1 [ swap ^ ] reduce .

Эта программа имеет более низкий балл, но оператор возведения в степень ^нарушает правила. В правилах написано «(количество символов) + (10 * (количество операторов power))», поэтому я применил штраф +10. Тем не менее, правила также гласят: «Не используйте оператор« power »», поэтому любая программа, использующая этот штраф, нарушает правила. Поэтому эта программа из 134 символов не является правильным ответом, и я должен представить свою более длинную программу из 187 символов в качестве ответа.

Haskell 110 - 5 = 105

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

data N=Z|S N
a&+Z=a
a&+S b=S$a&+b
_&*Z=Z
a&*S b=a&+(a&*b)
_&^Z=S Z
a&^S b=a&*(a&^b)
_&>Z=S Z
a&>S b=a&^(a&>b)

Это зависит от того, хватит ли у вас терпения набрать числа Пеано (и не покажет ответ. Если вы действительно хотите запустить его, добавьте несколько строк (90 символов):

f 0=Z
f a=S$f$a-1
t Z=0
t(S a)=1+t a
main=interact$show.f.(\[x,y]->x&>y).map(f.read).words

Рубин, 47 46 45

t=->x,n{r=x;2.upto(n){r=([x]*r).inject :*};r}

Луа: 133 символа, без умножения

a,b=io.read():match"(%d+) (%d+)"a,b,ba=a+0,b+0,a for i=1,b-1 do o=1 for i=1,a do o=o+o for i=1,ba-b do o=o+o end end a=o end print(o)

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

Ввод «4 3» в выводы стандартного ввода:

1.3407807929943e+154

VBA, 90 символов

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

90 символов, без степенных операторов, использует умножение = 90

Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:b=b*x:Next:f=b:Next:MsgBox f
End Sub

116 символов, без силовых операторов, без бонуса умножения (-5) = 111

Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:For i=1 To x:a=a+b:Next:b=a:a=0:Next:f=b:Next:MsgBox f
End Sub

ПРИМЕЧАНИЕ: VBA имеет проблемы с печатью числа, когда результат очень большой (то есть 4, 3), но он вычисляет правильно, поэтому, если, например, вы хотите ИСПОЛЬЗОВАТЬ это число, вам будет хорошо. Кроме того, даже БОЛЬШИЕ числа переполнены (то есть 3, 4).

Perl 6 , 32 байта

->\a,\b{(1,{[*] a xx$_}...*)[b]}

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

(1, { [*] a xx $_ } ... *)это ленивая последовательность, которая генерирует Power Tower, каждый элемент представляет собой список, который состоит из первого входного параметра areplicated ( xx), количество раз равное предыдущему элементу ( $_), этот список затем сокращается с помощью умножения ( [*]). Из этой последовательности мы просто вынимаем b-ый элемент.

Лямбда-исчисление, 10-5

(с использованием церковного кодирования и De Bruijn Indeces )
λλ(1λ13)λ1

объяснение

Без Де Брейны индексы: λa,b.(b λc.ca)λc.c:

λa,b.                                                 define the anonymous function f(a,b)=
     (b                                                apply the following function b times
        λc.                                                    the anonymous function g(c)=
           ca)                 apply c to a because of church encoding this is equal to a^c
              λc.c                              the identity function, 1 in church encoding

Если вы определите, exp_a(x)=a^xэта программа определяет, a↑↑b=exp_a^b(1)где^b обозначается ее изменение.

Я не уверен, разрешено ли это, потому что caтехнически это эквивалентно тому, a^cчто оно не является действительно встроенным, и только побочный эффект от того, как целые числа кодируются в лямбда-исчислении.

Javascript: 116 символов

function t(i){y=i.split(' ');a=y[0];b=y[1];return+b&&p(a,t(a+' '+(b-1)))||1}function p(a,b){return+b&&a*p(a,b-1)||1}

t ('4 3') Выходы:

1.3407807929942597e+154

Питон (111) (113) нет *

r=lambda x,y:(x for _ in range(y));t=lambda x,y:reduce(lambda y,x:reduce(lambda x,y:sum(r(x,y)),r(x,y)),r(x,y),1)

6 *** 3 - 36 тыс. Цифр))

Upd: нужно добавить начальное значение, чтобы соответствовать t (X, 0) = 1

Haskell: 88-5 символов без умножения, 59 символов с умножением

Без умножения:

h x y=foldr(\x y->foldl(\x y->foldl(+)0(replicate x y))1(replicate y x))1(replicate y x)

Есть, вероятно, способы, которыми я мог бы немного поиграть в гольф.

С умножением:

h x y=foldr(\x y->foldl(*)1(replicate y x))1(replicate y x)

И, наконец, не разглаженная программа:

mult x y = foldl (+) 0 (replicate x y)
expo x y = foldl (mult) 1 (replicate y x)
h x y = foldr (expo) 1 (replicate y x)

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

Ракетка 58 (нет *)

(define(t x y)(if(= y 0)1(for/product([i(t x(- y 1))])x)))

Common Lisp, 85 символов

(lambda(b c)(let((r b)u)(dotimes(c c r)(setf u 1 r(dotimes(c b u)(setf u(* u r)))))))

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

Другое решение, вдохновленное решением Python от Boothby. Это на 1 символ меньше, чем в приведенном выше решении.

(lambda(a b)(eval`(*,@(loop for x below b nconc(loop for x below a nconc`(,a,a))))))

Питон 3 - 68

(включая штраф в 10 баллов для оператора)

a,b=input().split()
r=1
exec("r=%s**r;"%a*int(b))
print(r)

Ябасич , 71 байт

Функция , которая принимает входной сигнал aи bкак пространство разделителей строки.

Input""a,b
d=a^(b>0)
For i=2To b
c=a
For j=2To d
c=c*a
Next
d=c
Next
?d

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

р 71 - 5 = 66 байт

function(x,y,b=x){for(i in 2:y)b=cumprod(z<-rep(x,b))[sum(z|1)];cat(b)}

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

-5 за уклонение *, что оказалось сложнее, чем я ожидал. Он взрывается очень быстро и не будет работать (если у него не было больше памяти), но он удовлетворяет всем необходимым критериям.