Codegolf - Нумерация Строки По Гёделю

Фон

числа Гёделя — это способ кодирования любой строки уникальным положительным целым числом с использованием простых факторизаций:

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

Затем, чтобы закодировать строку \$ x_1 x_2 x_3 \ldots x_n \$, где каждый \$ x_i \$ представляет собой целочисленный код символа, результирующее число равно

$$ \prod_{i=1}^n p_i^{x_i} = 2^{x_1} \cdot 3^{x_2} \cdot 5^{x_3} \cdot \ldots \cdot p_n^{x_n} $$

где \$ p_i \$ представляет собой \$ i \$-е простое число. Согласно фундаментальной теореме арифметики, это гарантированно дает уникальное представление.

В этой задаче мы будем рассматривать только строки, состоящие из символов, которые Гёдель изначально использовал для своих формул, и использовать их значения, а именно:

•  Input        Output
  ""           1
  "A"          512
  "~s0"        4320
  "0A0"        196830
  ")("         1451188224
  "sssss0"     160243083000
  "~(~0|~s0)"  42214303957706770300186902604046689348928700000
  "0s~|A()"    5816705571109335207673649552794052292778133868750
   

  : 1
• 0 : 3
• s : 5
• ~ : 7
• ~s0 : 9
• 0s~|A() : 11
• A : 13

...хотя для простоты символы | , ~ , и ∀ can be replaced by the ASCII symbols ∨ , ¬ , and ) соответственно.

(Я не знаю, почему Гёдель использовал для них только нечетные числа, но это то, что он назначил, поэтому мы придерживаемся этого)

Испытание

Учитывая строку, состоящую только из приведенных выше символов, выведите ее кодировку Гёделя как целое число.

Вы можете предположить, что ввод будет состоять только из символов в наборе. ( .

Пример

Для строки ∀ :

• начнем с \$ 1 \$, мультипликативное тождество
• первый персонаж ∨ has code \$ 5 \$; the 1st prime is \$ 2 \$, so multiply by \$ 2 ^ 5 \$; the running product is \$ 32 \$
• 2-й персонаж ¬ has code \$ 3 \$; the 2nd prime is \$ 3 \$, so multiply by \$ 3 ^ 3 \$; the running product is \$ 864 \$
• третий персонаж s has code \$ 1 \$; the 3rd prime is \$ 5 \$, so multiply by \$ 5 ^ 1 \$; the running product is \$ 4320 \$
• поэтому окончательный ответ — \$4320\$

Тест-кейсы

Правила

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

#код-гольф #код-гольф #строка #теория чисел #целое число #простые числа

JavaScript (ES7), 75 72 байта

Ожидается массив кодов ASCII.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 def f(x):

P,p=[2],3

while len(P)<len(x):

P.append(p)

while 1:

p+=1

for i in P:

if p%i==0:break

else:break

i=1

for d,n in zip(x,P):i*=n**(2*"0s~|A()".find(d)+1)

return i
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Волшебная формула

Формула d;g;p;r;f(char*s){ // declare variables and function r=1 // init return value r to 1 p= // init prime number p to 1 for( ;*s;++s){ // loop over chars in s for(g=0;!g;) // loop until we find the next prime p++ // start by bumping p d= // init divisor d to p-1 g= // set g to non-zero p-1 as well for( ;d>1;) // loop over d until its 2 g=g&&p%d--; // g with only remain non-zero if // p is the next prime number r*=pow(p, ); // multiply r by p to the power of 17088/ *s%75|1 // the Gödel value for the ASCII // code, need the space so it's not } // interpreted as start of comment d=r; // return r } // was found by injecting random values into several handcrafted templates.

Точнее, шаблон для этого был d;g;p;r;f(char*s){for(p=r=1;*s;r*=pow(p,17088/ *s++%75|1))for(g=0;!g;)for(g=d=p++;d>1;)g=g&&p%d--;d=r;} with \$0<p<10^5\$, \$0<m_0<10^3\$ and \$12\le m_1 \le 15\$.

Прокомментировал

Желе, 13 11 байты

-2 спасибо Ник Кеннеди! (У меня была ошибка в коде поиска Python, поэтому мне не удалось найти хэш для домена l .)

Монадическая ссылка, принимающая список символов, который дает число Гёделя.

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

Как?

05AB1E, 16 15 байт

Попробуйте онлайн! Ссылка включает набор тестов. Принимает входные данные в виде списка символов (набор тестов ожидает список списков), экономя 1 байт благодаря @ovs. Объяснение:

Предыдущая версия принимала входные данные в виде строки, которую проще использовать: Попробуйте онлайн!

Шелуха, 21 20 19 байт

• Сэкономлен 1 байт благодаря caird coinheringaahing
• Сэкономлен 1 байт благодаря Доминику Ван Эссену.

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

Питон 2, 89 байт

Принимает входные данные в виде списка символов.

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

АВК, 109 102 байт

-7 байт; спасибо, @ovs!

Довольно наивно.

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

Негольфед

Япт, 26 24 23 байты

Фу! Не думаю, что я когда-либо больше завидовал языкам со встроенными списками простых чисел, показателей степени и тому подобного :\

Входные данные представляют собой массив кодовых точек. Сэкономил байт, заимствовав Формула Арно.

Попробуйте это

Япт, 24 байта

Japt довольно многословен, когда дело касается простых чисел: для получения N-го простого числа требуется 6 байт. Принимает входные данные как массив букв.

Попробуйте здесь.

Дж, 28 байт

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

Фактор + % anonymous function - take product of first argument... @(x)prod( primes(intmax) % all prime numbers < than limit of int32 table( ).Var1( )% take elements of array 1:nnz(x) % vector 1 to length of input .^ % element-wise power int32( )% casting to int32 arrayfun( ,x) % for each character in input @(y)find('0s~|A()'==y) % find index in '0s~|A()' 2* -1 % indices to symbol values ,'n') % shorthand 'native', return product of elements in same type as input , 64 bytes

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

Объяснение:

Это цитата (анонимная функция), которая принимает строку из стека данных в качестве входных данных и оставляет целое число в стеке данных в качестве выходных данных. Предполагая @(x)prod(table(primes(intmax)).Var1(1:nnz(x)).^int32(2*arrayfun(@(y)find('0s~|A()'==y),x)-1),'n') is on the data stack when this quotation is called...

• goedel_numbering= function(x){ # x is the input character vector; p=1 # initialize p to 1 (one less than the first prime); for(y in x){ # now cycle through each character y in x: while(sum(!(p=p+1)%%2:p)>1)1 # update p to the next prime T=T* # multiply T (initially 1) by p^ # p to the power of (regexpr(y,"0s~|A()",f=T) # the position of y in the string "0s~|A()" *2-1) # times 2, minus 1; } +T # finally, output T. } Duplicate the object on top of the data stack (TOS).

  Куча: function(x,p=1){for(y in x){while(sum(!(T=T+1)%%2:T)>1)1;p=p*T^(regexpr(y,"0s~|A()",f=T)*2-1)};p}

• 1##&@@(Prime[Range@Length@#]^#&@((Tr@StringPosition["0s~|A()",#]*2-1)&/@Characters@InputString[])) Take the length of a sequence.

  Куча: 4320

• Π Obtain a list of the first number of primes indicated by TOS.

  Куча: { 32 27 5 }

• v^ Swap the top two objects on the data stack.

  Куча: { 5 3 1 }

• { 2 3 5 } "\x05\x03\x01" Push a quotation for 5 чтобы использовать позже. Это функция, которая сопоставляет буквы нашего алфавита с числовыми значениями.

  Куча: map

• { 2 3 5 } 5 Apply a quotation to each element of a sequence, collecting the results into a sequence of the same length. Inside the quotation now during the first iteration...

  Куча: 2 * 1 +

• { 2 3 5 } 2 Push our alphabet string to the stack.

  Куча: index

• { 2 3 5 } 126 "0s~|A()" Find the index of NOS (next on stack) in TOS.

  Куча: "0s~|A()"

• { 2 3 5 } 126 Multiply by 2, then add 1.

  Куча: map

• Сейчас { 2 3 5 } "~s0" [ "0s~|A()"index 2 * 1 + ] will collect map в последовательность, которую он строит, и переходим к остальным элементам входной строки...

  Куча [ "0s~|A()"index 2 * 1 + ]

• В качестве примечания: строки в Factor — это просто массивы кодовых точек. Часто, когда мы сопоставляем строку, мы получаем строковый результат, но мы все равно можем выполнять с ними векторные математические операции и тому подобное. Эта строка эквивалентна { 2 3 5 } "~s0" .

• swap Component-wise exponentiation.

  Куча: "~s0" { 2 3 5 }

• nprimes Product.

  Куча: "~s0" 3

Математика, 120 106 102 99 байт

-14 байт, спасибо, pxeger!

Впервые играю в гольф, буду рад отзывам!

Р, 98 97 байт

Изменить: -1 байт благодаря pajonk

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

Входные данные — вектор символов.

MATLAB/Октава, 102 97 байт

Попробуйте это на Octave Online!* - У TIO возникли проблемы с функцией, выполнение превышает 60 секунд и прекращается.
Анонимная функция. Теоретически может работать вечно, но достигает максимума [ dup length nprimes swap [ "0s~|A()"index 2 * 1 + ] map v^ Π ] limit.
Объяснение:

Альтернативное решение как полнофункциональное, 103 байта длинный.

Попробуйте онлайн!*
Этот, с другой стороны, достигает максимума в £Èj}iY p"0s~|A()"aX ÑÄÃ× £ // Map the input with X as values, Y as indexes. Èj}iY // Get the Y-th prime p aX // to the power of the index of X in "0s~|A()" // string constant, ÑÄ // times two plus one to map to correct values. Ã× // Finally, reduce with multiplication, return result. limit.
Негольфед:

Можно написать функцию, которая не достигает максимума (... так легко), но выводит символические числа вместо целых чисел (и имеет 105 байт). Очень похоже на первую функцию:

*рекомендуется для тестирования заменить { # accumulator and currently seeing prime number a=1;p=2; for(i=1;i<=length($0);i++){ # multiply p_i^(x_i) a*=p**(index("0s~|A()",substr($0,i,1))*2-1); # get next prime p++; for(j=2;j<p;) if(p%j!=0) j++; else{ p++;j=2;}} # finally $0=a with something like a=1{for(p=2;i++<length;)for(a*=p++**(index("0s~|A()",substr($0,i,1))*(j=2)-1);j<p;)p%j++||p++<j=2}$0=a чтобы вычислить меньше простых чисел и тем самым сократить время выполнения (и это было сделано для примера TIO). Результат достигнет максимума гораздо быстрее, чем вы израсходуете все простые числа, так что не беспокойтесь об этом.

05AB1E, 19 байт

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

JavaScript (Node.js), 81 байт

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

Введите массив символов, выведите число.

Сохранено 1 байт Шэгги.

JavaScript (Node.js), 79 байт

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

Введите массив кодовых точек, выведите число.

Сохранено 1 байт Шэгги.

Я считаю кто-то может найти лучшие хэш-функции.

JavaScript (Node.js), 103... 94 байта

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

Принимает входные данные как массив символов. Наивная реализация.

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

Для каждого символа счетчик умножения "0s~|A()"sk·>.Ó by the exponential expression if incremented ⁽=ȧ,7ḥⱮḤ’ÆẸ - Link: list of characters, S ⁽=ȧ - 16481 7 - 7 , - literal pair -> [16481, 7] Ɱ - map across (c in S) with: ḥ - (c) hash (salt=16481, domain=[1..7]) Ḥ - double ’ - decrement ÆẸ - prime-index-exponentiate ([a,b,c,...]->2^a*3^b*5^c*...) является простым. Если нет, вспомните ⁽=ȧ,7ḥⱮḤ’ÆẸ until we get a prime number. Then logical-ANDs (short-circuit) with [1..7] .

Пиф, 28 байт

Тестовый набор

Наивное решение. Попробую найти другое решение... в конце концов.

[PHP], 175 байт

Моя первая попытка здесь, так что очевидно, что это будет отстой…

Я не мог придумать формулу для генерации простых чисел, поэтому ввел их все в массив. Очевидно, можно добиться большего. Кроме того, мой сервер не принимает просто

С (ГКК), ^{116 110} 106 байт

Сэкономлено 3 байта благодаря самому человеку Арно!!!
Сэкономлено 4 байта благодаря потолочный кот!!!

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

Вводит строку и возвращает ее номер Гёделя.

Использует формулу преобразования значений Magic ASCII в Gödel из Арно's JavaScript-ответ.

Комментированный код (перед некоторыми гольфами)

Питон 3, 190 байт

Попробуйте онлайн! Генерирует достаточное количество простых чисел для формирования числа Гёделя, а затем находит произведение.