Код гольфа:Фрактран

https://stackoverflow.com/questions/1749905

20-09-2019
|

Вопрос

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

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

Фрактран

Фрактран — это тривиальный эзотерический язык, изобретенный Джон Конвей.Программа фрактрана состоит из списка положительных дробей и начального состояния n.Интерпретатор поддерживает счетчик программ, первоначально указывающий на первую дробь в списке.Программы Фрактрана выполняются следующим образом:

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

Подробную информацию о том, как и почему работает Фрактран, см. запись об эсоланге и эта запись по хорошей/плохой математике.

Тестовые векторы

Программа: [(3, 2)]
Вход: 72 (2³3²)
Выход: 243 (3⁵)

Программа: [(3, 2)]
Вход: 1296 (2⁴3⁴)
Выход: 6561 (3⁸)

Программа: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
Вход: 72 (2³3²)
Выход: 15625 (5⁶)

Бонусный тестовый вектор:

Для того чтобы ваш ответ был приемлемым, не обязательно, чтобы эта последняя программа выполнялась правильно.Но слава, если это так!

Программа: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
Вход: 60466176 (2¹⁰3¹⁰)
Выход: 7888609052210118054117285652827862296732064351090230047702789306640625 (5¹⁰⁰)

Представления и подсчет очков

Программы ранжируются строго по длине в символах – лучше самое короткое.Не стесняйтесь присылать как красиво оформленную и документированную, так и «мини-версию» вашего кода, чтобы люди могли видеть, что происходит.

Язык «J» недопустим.Это потому, что на одной из связанных страниц уже есть известное решение в J. Если вы фанат Джей, извините!

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

Победители

Официальным победителем, представившим самостоятельное решение фрактрана, состоящее из 1779 фракций, стал Решение Джесси Бедера.Однако на практике решение слишком медленное, чтобы выполнить даже 1+1.

Невероятно, но с тех пор это решение было побеждено другим фрактрановым решением — Решение Амадея всего за 84 дроби!Он способен выполнить первые два тестовых примера за считанные секунды при работе с моим эталонным решением Python.Он использует новый метод кодирования дробей, который также заслуживает пристального внимания.

Почетные упоминания:

Решение Стивена Кэнона, в 165 символах сборки x86 (28 байт машинного кода)
Решение Джордана в 52 символа рубина, который обрабатывает длинные целые числа
Решение Бесполезного в 87 символов Python, который, хотя и не является самым коротким решением Python, является одним из немногих решений, которые не являются рекурсивными и, следовательно, легко обрабатывают более сложные программы.Это также очень читабельно.

Решение

Фрактран - 1779 фракций

(Редактировать:зафиксированный)

(Я надеюсь, что люди все еще следят за этой темой, потому что это заняло некоторое время!)

Похоже, SO не позволит мне публиковать что-то подобное, поэтому я разместил исходный код Fracran. здесь.

Ввод указывается следующим образом:

Сначала мы кодируем дробь m/n = p_0^a0... p_k^ak к:

Начните с 1.Тогда для каждого ai:
Умножить на p_2i^ai если ai > 0
Умножить на p_2i+1^{-ai} если a_i < 0

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

p_0^F0 p1^F1 ...

Наконец, ввод в интерпретатор осуществляется следующим образом:

2^(program) 3^(input) 5

где program и input кодируются, как указано выше.Например, в первой тестовой задаче 3/2 кодируется в 15, поэтому программа кодируется в 2^15;и 108 кодируется в 500.Итак, мы проходим

2^{2^15} 3^500 5

в программу.Тогда вывод имеет вид

2^(program) 3^(output)

поэтому в первом примере это будет

2^{2^15} 3^3125

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

Я написал метаязык, который компилируется во Фрактран.Он позволяет использовать функции (простой фрактран и последовательности других функций), а также while петля и if заявление (для удобства!).Код для этого можно найти здесь.

Если вы хотите самостоятельно скомпилировать этот код во Fractran, мою программу (C++) можно найти. здесь [tar.gz].В потрясающей демонстрации экспериментальной проверки (и хвастовства) я использовал свой синтаксический анализатор C++ YAML. Ямл-cpp, поэтому вам придется скачать и связать его с ним.И для yaml-cpp, и для «компилятора» вам понадобится CMake для создания кроссплатформенного make-файла.

Использование этой программы:

./fracc interpreter.frp

Он считывает имя функции со стандартного ввода и записывает соответствующую «псевдодробь» (я объясню это через секунду) на стандартный вывод.Итак, чтобы скомпилировать интерпретатор (функцию Interpret), вы можете запустить

echo "Interpret" | ./fracc interpreter.frp > interpret

Выходные данные («псевдо-фрактран») будут представлять собой последовательность строк, каждая из которых содержит строку цифр, разделенных пробелами.Линия соответствует дроби:если nтретья цифра в строке an, то дробь является произведением p_n^an.

Конвертировать это во фрактран очень легко, но если вам лень, вы можете использовать to-fractions.py. [Примечание:раньше у меня была программа на C++, и я по неосторожности игнорировал целочисленное переполнение.Я перевел это на Python, чтобы избежать этого.]

Примечание о вводе:если вы хотите протестировать таким образом другую функцию, соглашение всегда будет одним и тем же.У него есть ряд параметров (обычно это объясняется комментарием над функцией) в псевдо-Фрактране, поэтому дайте ему то, что он хочет, плюс 1 в самом следующем слоте (поэтому в обычном Fractran умножьте один раз на первое простое число, которое он не будет использовать).Это бит «сигнала» для начала работы функции.

Однако,

Я не рекомендую на самом деле пытаться запустить интерпретатор Fractran (увы).Я протестировал многие его компоненты, и, например, функцию IncrementPrimes, который принимает пару простых чисел и возвращает следующие два простых числа, занимает около 8 минут для запуска, используя мой глупый интерпретатор C++ (нет необходимости публиковать это :).Кроме того, количество вызовов функций увеличивается (как минимум) квадратично — удвоение количества вызовов функций приводит к увеличению времени как минимум в четыре раза (больше, если есть while петли или if заявления).Так что я предполагаю, что запуск интерпретатора займет как минимум дни, если не годы :(

Откуда мне знать, что это работает?Ну, конечно, я не уверен на 100%, но я довольно близок к этому.Прежде всего, я протестировал многие-многие его компоненты, и в частности, я протестировал все элементы метаязыка (последовательности функций и if и while заявления) очень тщательно.

Также метаязык легко перевести на ваш любимый язык, а еще проще — на C++, поскольку все параметры функций передаются по ссылке.Если вам снова лень, вы можете скачать мой перевод. здесь [tar.gz] (мейкфайла нет;это всего лишь два файла .cpp, поэтому прямой вызов gcc вполне подойдет).

Таким образом, вы можете сравнить два интерпретатора, запустить версию C++ (она также принимает ввод/вывод в псевдо-фрактране), проверить, работает ли она, а затем убедиться, что метаязык тоже работает.

Или!

Если вы чувствуете вдохновение и Действительно Если вы хотите увидеть интерпретацию этого интерпретатора, вы можете написать «умный» интерпретатор Fractran, основанный на типе вывода Fractran, который мы получаем.Вывод очень структурирован — последовательности функций реализуются с использованием сигналов, поэтому, если вы каким-то образом закэшируете место, где находился интерпретатор, вы сможете сразу же перейти туда, если ничего важного не изменится.Я думаю, это значительно ускорило бы программу (возможно, сократив время ее выполнения на одну или несколько способностей).

Но я не совсем уверен, как это сделать, и доволен тем, что сделано, поэтому оставлю это в качестве упражнения для читателя.

Другие советы

Фрактран:84 фракции

FTEVAL = [197*103/(2^11*101), 101/103, 103*127/(2*101), 101/103, 109/101,
  2*23/(197*109), 109/23, 29/109,197*41*47/(31*59), 11^10*53/(127*197), 197/53,
  37/197, 7^10*43/(11^10*37), 37/43, 59/(37*47), 59/47, 41*61/59, 31*67/(41*61),
  61/67, 7*67/(127*61), 61/67,101/71, 73/(127^9*29), 79/(127^2*73),
  83/(127*73), 89/(2*29), 163/29, 127^11*89/79, 337/83, 2*59/89, 71/61,
  7*173/(127*163), 163/173, 337*167/163, 347/(31*337), 337/347, 151/337,
  1/71,19*179/(3*7*193), 193/179, 157/(7*193), 17*181/193, 7*211/(19*181),
  181/211, 193/181, 157/193, 223/(7*157), 157/223, 281*283/239,
  3*257*269/(7*241), 241/269, 263/241, 7*271/(257*263), 263/271, 281/263,
  241/(17*281), 1/281, 307/(7*283), 283/307, 293/283, 71*131/107, 193/(131*151),
  227/(19*157), 71*311/227, 233/(151*167*311), 151*311/229, 7*317/(19*229),
  229/317, 239*331/217, 71*313/157, 239*251/(151*167*313), 239*251/(151*313),
  149/(251*293), 107/(293*331), 137/199, 2^100*13^100*353/(5^100*137),
  2*13*353/(5*137), 137/353, 349/137, 107/349, 5^100*359/(13^100*149),
  5*359/(13*149), 149/359, 199/149]

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

FTEVAL принимает участие 3^initial_state * 5^encoded_program * 199, дает промежуточные результаты 3^interpreted_program_state * 199, и полностью останавливается на числе, кратном 233.

Интерпретируемая программа встраивается в виде списка цифр по основанию 10 внутри одного числа по основанию 11, используя цифру «а» для обозначения границы, за исключением самого конца.Программа сложения [3/2] кодируется как

int("3a2", 11) = 475.

Программа умножения [455/33, 11/13, 1/11, 3/7, 11/2, 1/3] кодируется как

int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657

это действительно большое число.

Первый тестовый вектор завершился в менее одной секунды, дал желаемый результат после 4545 итераций и остановился после 6172 итераций.Вот полный вывод.

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

Здесь действительно слишком мало места, чтобы все объяснить.Но вот мой псевдокод.Надеюсь, через пару дней опишу процесс.

# Notations:
# %p
#     designates the exponent of prime factor p that divides the
#     current state.
# mov x y
#     directly translates to the fraction y/x; its meaning: test if x divides
#     the current state, if so divide the current state by x and multiply it by
#     y.  In effect, the prime exponents of x and y are exchanged.  A Fractran
#     program only comprises of these instructions; when one is executable, the
#     program continues from the beginning.
# dec x => mov x, 1
#     wipes out all factors of x
# inc x => mov 1, x
#     this form is here for the sake of clarity, it usually appears in a
#     loop's entry statement and is merged as such when compiled
# sub n ret m {...}
#     conceptually represents a Fractran sub-program, which will execute just
#     like a normal Fractran program, that is, the sub-program's statements
#     execute when triggered and loop back.  The sub-program only exits when none of
#     its statement is executable, in which occasion we multiply the program's
#     state by m.  We can also explicitly break out early on some conditions.
#     It is also possible to enter a sub-prorgram via multiple entry points and
#     we must take care to avoiding this kind of behavior (except in case where
#     it is desirable).

# entry point 101: return 29
# Divide %2 modulo 11:
#   - quotient is modified in-place
#   - remainder goes to %127
sub 101 ret 101 { mov 2^11, 197 }
sub 101 ret 109 { mov 2, 127 }
sub 109 ret 29 { mov 197, 2 }

# entry point 59: return 61
# Multiply %127 by 10^%31 then add result to %7,
# also multiply %31 by 10 in-place.
sub 59 ret 41*61 {
  mov 31, 197*41
  sub 197 ret 37 { mov 127, 11^10 }
  sub 37 { mov 11^10, 7^10 }
}
sub 61 ret 61 { mov 41, 31 }
sub 61 ret 61 { mov 127, 7 } # the case where %31==0

# entry point 71: return 151 if success, 151*167 if reached last value
# Pop the interpreted program stack (at %2) to %7.
sub 71 {
  # call sub 101
  inc 101

  # if remainder >= 9:
  mov 29*127^9, 73
  #     if remainder == 11, goto 79
  mov 73*127^2, 79
  #     else:
  #         if remainder == 10, goto 83
  mov 73*127, 83
  #         else:
  #             if quotient >= 1: goto 89
  mov 29*2, 89
  #             else: goto 163
  mov 29, 163

  # 79: restore remainder to original value, then goto 89
  mov 79, 127^11*89

  # 83: reached a border marker, ret
  mov 83, 337

  # 89: the default loop branch
  # restore quotient to original value, call 59 and loop when that rets
  mov 2*89, 59
  mov 61, 71

  # 163: reached stack bottom,
  # ret with the halt signal
  sub 163 ret 337*167 { mov 127, 7 }

  # 337: clean up %31 before ret
  sub 337 ret 151 { dec 31 }
}

# entry point 193, return 157
# Divide %3 modulo %7:
#   - quotient goes to %17
#   - remainder goes to %19
sub 193 ret 17*181 {
  mov 3*7, 19
}
mov 7*193, 157
sub 181 ret 193 { mov 19, 7 }
mov 193, 157
sub 157 ret 157 { dec 7 }

# entry point 239: return 293
# Multiply %17 by %7, result goes to %3
mov 239, 281*283
sub 241 { mov 7, 3*257 }
sub 263 ret 281 { mov 257, 7 }
mov 281*17, 241
sub 283 ret 293 { dec 7 }

# entry point 107: return 149 if success, 233 if stack empty
# Pop the stack to try execute each fraction
sub 107 {
  # pop the stack
  inc 71*131

  # 151: popped a value
  # call divmod %3 %7
  mov 131*151, 193

  # if remainder > 0:
  mov 19*157, 227
  #     pop and throw away the numerator
  mov 227, 71*311
  #     if stack is empty: halt!
  mov 151*167*311, 233
  #     else: call 239 to multiply back the program state and gave loop signal
  mov 151*311, 229
  sub 229 ret 239*331 { mov 19, 7 }
  # else: (remainder == 0)
  #     pop the numerator
  mov 157, 71*313
  #     clear the stack empty signal if present
  #     call 239 to update program state and gave ret signal
  mov 151*167*313, 239*251
  mov 151*313, 239*251

  # after program state is updated
  # 313: ret
  mov 293*251, 149
  # 331: loop
  mov 293*331, 107
}

# main
sub 199 {
  # copy the stack from %5 to %2 and %13
  sub 137 ret 137 { mov 5^100, 2^100*13^100 }
  sub 137 ret 349 { mov 5, 2*13 }

  # call sub 107
  mov 349, 107

  # if a statement executed, restore stack and loop
  sub 149 ret 149 { mov 13^100, 5^100 }
  sub 149 ret 199 { mov 13, 5 }
}

сборка x86_64, 165 символов (28 байт машинного кода).

Состояние передается в %rdi, программа (указатель на массив дробей, завершающийся нулем) — в %rsi.Результаты возвращаются в %rax в соответствии с обычными соглашениями о вызовах в стиле C.Использование нестандартных соглашений о вызовах или синтаксиса Intel (это синтаксис AT&T) приведет к потере еще нескольких символов, но я ленив;это может сделать кто-то другой.Пару инструкций почти наверняка можно спасти, переорганизовав поток управления, если кто-то захочет это сделать, не стесняйтесь.

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

_fractran:
0:  mov     %rsi,   %rcx    // set aside pointer to beginning of list
1:  mov    (%rcx),  %rax    // load numerator
    test    %rax,   %rax    // check for null-termination of array
    jz      9f              // if zero, exit
    mul     %rdi
    mov   8(%rcx),  %r8     // load denominator
    div     %r8
    test    %rdx,   %rdx    // check remainder of division
    cmovz   %rax,   %rdi    // if zero, keep result
    jz      0b              // and jump back to program start
    add     $16,    %rcx    // otherwise, advance to next instruction
    jmp     1b
9:  mov     %rdi,   %rax    // copy result for return
    ret

Удалите комментарии, лишние пробелы и подробный ярлык. _fractran для минимизированной версии.

Рубин, 58 57 56 53 52 символа

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

def f(n,c)d,e=c.find{|i,j|n%j<1};d ?f(n*d/e,c):n end

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

irb> f 108, [[455, 33], [11, 13], [1,11], [3,7], [11,2], [1,3]]
=> 15625

irb> f 60466176, [[455, 33], [11, 13], [1, 11], [3, 7], [11, 2], [1, 3]]
=> 7888609052210118054117285652827862296732064351090230047702789306640625

Красивая версия (252):

def fractran(instruction, program)
  numerator, denominator = program.find do |numerator, denominator|
    instruction % denominator < 1
  end

  if numerator
    fractran(instruction * numerator / denominator, program)
  else
    instruction
  end
end

Рубин, 53 52 с использованием Rational

Вдохновлен решение гнибблера Мне удалось найти решение с помощью Rational вплоть до 53 52 персонажа. ~~Все еще на один дольше, чем (менее элегантное) решение выше.~~

def f(n,c)c.map{|i|return f(n*i,c)if i*n%1==0};n end

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

irb> require 'rational'
irb> f 60466176, [Rational(455, 33), Rational(11, 13), Rational(1, 11), Rational(3, 7), Rational(11, 2), Rational(1, 3)]
=> Rational(7888609052210118054117285652827862296732064351090230047702789306640625, 1)

(А to_i вызов более красивого вывода добавит еще 5 символов.)

Гольфскрипт - 32

    
    {:^{1=1$\%!}?.1={~@\/*^f}{}if}:f

    ; 108 [[3 2]] f p
    # 243
    ; 1296 [[3 2]] f p
    # 6561
    ; 108 [[455 33][11 13][1 11][3 7][11 2][1 3]] f p
    # 15625
    ; 60466176 [[455 33][11 13][1 11][3 7][11 2][1 3]] f p
    # 7888609052210118054117285652827862296732064351090230047702789306640625

Хаскелл, 102 символа

import List
import Ratio
l&n=maybe n((&)l.numerator.(n%1*).(!!)l)$findIndex((==)1.denominator.(n%1*))l

$ ghci
Prelude> :m List Ratio
Prelude List Ratio> let l&n=maybe n((&)l.numerator.(n%1*).(!!)l)$findIndex((==)1.denominator.(n%1*))l
Prelude List Ratio> [3%2]&108
243
Prelude List Ratio> [3%2]&1296
6561
Prelude List Ratio> [455%33,11%13,1%11,3%7,11%2,1%3]&108
15625

88 со смягченными ограничениями на формат ввода/вывода.

import List
import Ratio
l&n=maybe n((&)l.(*)n.(!!)l)$findIndex((==)1.denominator.(*)n)l

Prelude List Ratio> let l&n=maybe n((&)l.(*)n.(!!)l)$findIndex((==)1.denominator
Prelude List Ratio> [455%33,11%13,1%11,3%7,11%2,1%3]&108
15625 % 1

Питон, 83 82 81 72 70 символов.

Удобно вводить данные в виде дробей. Объекты Fraction.Та же идея, что и в решении Ruby.

def f(n,c):d=[x for x in c if x*n%1==0];return d and f(n*d[0],c) or n

# Test code:
from fractions import Fraction as fr
assert f(108, [fr(3, 2)]) == 243
assert f(1296, [fr(3, 2)]) == 6561
assert f(108, [fr(455, 33), fr(11, 13), fr(1, 11), fr(3, 7), fr(11, 2), fr(1, 3)]) == 15625
assert f(60466176, [fr(455, 33), fr(11, 13), fr(1, 11), fr(3, 7), fr(11, 2), fr(1, 3)]) == 7888609052210118054117285652827862296732064351090230047702789306640625

С, 159 153 151 131 111 110 символов

v[99],c,d;main(){for(;scanf("%d",v+c++););while(d++,v[++d])
*v%v[d]?0:(*v=*v/v[d]*v[d-1],d=0);printf("%d",*v);}

$ cc f.c
$ echo 108 3 2 . | ./a.out; echo
243
$ echo 1296 3 2 . | ./a.out; echo
6561
$ echo 108 455 33 11 13 1 11 3 7 11 2 1 3 . | ./a.out; echo
15625

Питон - 53

Улучшение благодаря Павлу

f=lambda n,c:next((f(n*x,c)for x in c if x*n%1==0),n)

тестовые примеры

from fractions import Fraction as fr
assert f(108, [fr(3, 2)]) == 243
assert f(1296, [fr(3, 2)]) == 6561
assert f(108, [fr(455, 33), fr(11, 13), fr(1, 11), fr(3, 7), fr(11, 2), fr(1, 3)]) == 15625
assert f(60466176, [fr(455, 33), fr(11, 13), fr(1, 11), fr(3, 7), fr(11, 2), fr(1, 3)]) == 7888609052210118054117285652827862296732064351090230047702789306640625

Python — 54 без использования дроби

f=lambda n,c:next((f(n*i/j,c)for i,j in c if n%j<1),n)

Питон - 55

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

f=lambda n,c:([f(n*i/j,c)for i,j in c if n%j<1]+[n])[0]

Вот одна возможность, но вырастает до 65 даже без учета импорта

from itertools import chain
f=lambda n,c:(chain((f(n*i/j,c)for i,j in c if n%j<1),[n])).next()

Ф#:80 символов

let rec f p=function|x,(e,d)::t->f p (if e*x%d=0I then(e*x/d,p)else(x,t))|x,_->x

Вот расширенная версия с использованием match pattern with |cases вместо function:

//program' is the current remainder of the program
//program is the full program
let rec run program (input,remainingProgram) =
    match input, remainingProgram with
        | x, (e,d)::rest -> 
            if e*x%d = 0I then //suffix I --> bigint
                run program (e*x/d, program) //reset the program counter
            else    
                run program (x, rest) //advance the program
        | x, _ -> x //no more program left -> output the state

Тестовый код:

let runtests() = 
    [ f p1 (108I,p1) = 243I
      f p1 (1296I,p1) = 6561I
      f p2 (108I,p2) = 15625I
      f p2 (60466176I,p2) = pown 5I 100]

И результат (проверено в интерактивном режиме F#):

> runtests();;
val it : bool list = [true; true; true; true]

Редактировать давайте поиграем с этим еще немного и вычислим несколько простых чисел (см. связанную страницу в начальном посте).Я написал новую функцию g что дает промежуточные значения состояния.

//calculate the first n primes with fractran
let primes n = 
    let ispow2 n = 
        let rec aux p = function
            | n when n = 1I -> Some p
            | n when n%2I = 0I -> aux (p+1) (n/2I)
            | _ -> None
        aux 0 n

    let pp = [(17I,91I);(78I,85I);(19I,51I);(23I,38I);(29I,33I);(77I,29I);(95I,23I); 
              (77I,19I);(1I,17I);(11I,13I);(13I,11I);(15I,14I);(15I,2I);(55I,1I)]

    let rec g p (x,pp) =
        seq { match x,pp with 
                |x,(e,d)::t -> yield x
                               yield! g p (if e*x%d=0I then (e*x/d,p) else (x,t))
                |x,_ -> yield x }

    g pp (2I,pp)
    |> Seq.choose ispow2
    |> Seq.distinct
    |> Seq.skip 1 //1 is not prime
    |> Seq.take n
    |> Seq.to_list

Чтобы узнать первые 10 простых чисел, требуется целых 4,7 секунды:

> primes 10;;
Real: 00:00:04.741, CPU: 00:00:04.005, GC gen0: 334, gen1: 0, gen2: 0
val it : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29]

Это, без сомнения, самый странный и медленный генератор простых чисел, который я когда-либо писал.Я не уверен, хорошо это или плохо.

Javascript: 99 символов.Нет бонусного вектора :(

function g(n,p,q,i,c){i=0;while(q=p[i],c=n*q[0],(c%q[1]?++i:(n=c/q[1],i=0))<p.length){};return n;};

Ввод в формате [[a,b],[c,d]].Я воспользовался снисходительностью Javascript:вместо того, чтобы делать var x=0, y=0;, вы можете добавить столько параметров, сколько захотите.Не имеет значения, передаете ли вы их на самом деле или нет, поскольку по умолчанию они null.

Красивая версия:

function g(n,p) {
    var q, c, i=0;
    while(i < p.length) {
        q = p[i];
        c = n * q[0];
        if(c % q[1] != 0) {
            ++i;
        } else {
            n = c % q[1];
            i = 0;
        }
    }
    return n;
};

Питон, 110 103 95 87 символов

frc.py

def f(n,c):
 d=c
 while len(d):
  if n%d[1]:d=d[2:]
  else:n=d[0]*n/d[1];d=c
 return n

test.py

(показывает, как им управлять)

from frc import f
def test():
 """
 >>> f(108, [3,2])
 243
 >>> f(1296, [3,2])
 6561
 >>> f(108, [455,33,11,13,1,11,3,7,11,2,1,3])
 15625
 >>> f(60466176, [455, 33,11, 13,1, 11,3, 7,11, 2,1, 3])
 7888609052210118054117285652827862296732064351090230047702789306640625L
 """
 pass
import doctest
doctest.testmod()

С#:

Удобная версия:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            int ip = 1;
            decimal reg = Convert.ToInt32(args[0]);
            while (true)
            {
                if (ip+1 > args.Length)
                {
                    break;
                }
                decimal curfrac = Convert.ToDecimal(args[ip]) / Convert.ToDecimal(args[ip+1]);
                if ((curfrac * reg) % 1 == 0)
                {
                    ip = 1;
                    reg = curfrac * reg;
                }
                else
                {
                    ip += 2;
                }
            }
            Console.WriteLine(reg);
            Console.ReadKey(true);
        }
    }
}

Урезанная версия весом в 201 символ (без объявлений пространства имен или чего-либо подобного, только один оператор using (не системный) и функция Main):

using System;namespace T{using b=Convert;static class P{static void Main(string[] a){int i=1;var c=b.ToDecimal(a[0]);while(i+1<=a.Length){var f=b.ToDecimal(a[i])/b.ToDecimal(a[i+1]);if((f*c)%1==0){i=1;c*=f;}else{i+=2;}}Console.Write(c);}}}

Примеры (ввод осуществляется через аргументы командной строки):

input: 108 3 2
output: 243.00
input: 1296 3 2
output: 6561.0000
input: 108 455 33 11 13 1 11 3 7 11 2 1 3
output: 45045.000000000000000000000000

классный, ~~136~~ ~~117~~ 107 символов.

Вызов как groovy fractal.groovy [состояние ввода] [вектор программы как список чисел]

a=args.collect{it as int}
int c=a[0]
for(i=1;i<a.size;i+=2) if(c%a[i+1]==0){c=c/a[i+1]*a[i];i=-1}
println c

Образец

bash$ groovy fractal.groovy 108 455 33 11 13 1 11 3 7 11 2 1 3
Output: 15625

Перл, 84 82 символа

Использует стандартный ввод.

@P=<>=~/\d+/g;$_=<>;
($a,$%)=@P[$i++,$i++],$_*$a%$%or$i=0,$_*=$a/$%while$i<@P;
print

Для прохождения бонусного теста требуется 110 символов:

use Math'BigInt blcm;@P=<>=~/\d+/g;$_=blcm<>;
($%,$=)=@P[$i++,$i++],$_*$%%$=or$i=0,($_*=$%)/=$=while$i<@P;print

Хаскелл: ~~116~~ 109 символов

f p x[]=x
f p x((n,d):b)|x*n`mod`d==0=f p(x*n`div`d)p|True=f p x b
main=do{p<-readLn;x<-readLn;print$f p x p}

В конечном итоге это стало своего рода подделкой выступления Дарио.

Схема:326

Я думал, что для паритета необходимо представление схемы.А еще мне просто нужен был повод поиграть с этим.(Извините за мои элементарные знания, я уверен, что это можно оптимизировать, и я открыт для предложений!)

#lang scheme
(define fractran_interpreter
(lambda (state pc program)
    (cond
        ((eq? pc (length program)) 
            (print state))
        ((integer? (* state (list-ref program pc)))
            (fractran_interpreter (* state (list-ref program pc)) 0 program))
        (else
            (fractran_interpreter state (+ pc 1) program)))))

Тесты:

(fractran_interpreter 108 0 '(3/2))

(fractran_interpreter 60466176 0 '(455/33 11/13 1/11 3/7 11/2 1/3))

Я получаю бонусный вектор! (с помощью Dr.Схема, выделение 256 мб)

Луа:

Аккуратный код:

a=arg;
ip=2;
reg=a[1];
while a[ip] do
    curfrac = a[ip] / a[ip+1];
    if (curfrac * reg) % 1 == 0 then
        ip=2;
        reg = curfrac * reg
    else
        ip=ip+2
    end
end
print(reg)

Компактный код весом в 98 символов (сокращение, предложенное Scoregraphic в моем другом ответе, и дополнительные предложения, предложенные gwell):

a=arg i=2 r=a[1]while a[i]do c=a[i]/a[i+1]v=c*r if v%1==0 then i=2 r=v else i=i+2 end end print(r)

Запустите из командной строки, указав сначала базовое число, а затем серию дробей, представленную в виде чисел с разделением пробелами, как показано ниже:

C:\Users\--------\Desktop>fractran.lua 108 3 2
243
C:\Users\--------\Desktop>fractran.lua 1296 3 2
6561
C:\Users\--------\Desktop>fractran.lua 108 455 33 11 13 1 11 3 7 11 2 1 3
15625

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

НЕ обрабатывает бонусный вектор, к сожалению :(

Эталонная реализация на Python

Эта реализация работает с простыми факторизациями.

Во-первых, он декодирует список кортежей дробей, кодируя числитель и знаменатель в виде списка кортежей (idx, значение), где idx — это номер простого числа (2 — простое число 0, 3 — простое число 1 и т. д.).

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

Этот подход примерно в 5 раз быстрее выполнения арифметических операций с большими целыми числами в Python, и его намного проще отлаживать!

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

def primes():
  """Generates an infinite sequence of primes using the Sieve of Erathsones."""
  D = {}
  q = 2
  idx = 0
  while True:
    if q not in D:
      yield idx, q
      idx += 1
      D[q * q] = [q]
    else:
      for p in D[q]:
        D.setdefault(p + q, []).append(p)
      del D[q]
    q += 1

def factorize(num, sign = 1):
  """Factorizes a number, returning a list of (prime index, exponent) tuples."""
  ret = []
  for idx, p in primes():
    count = 0
    while num % p == 0:
      num //= p
      count += 1
    if count > 0:
      ret.append((idx, count * sign))
    if num == 1:
      return tuple(ret)

def decode(program):
  """Decodes a program expressed as a list of fractions by factorizing it."""
  return [(factorize(n), factorize(d)) for n, d in program]

def check(state, denom):
  """Checks if the program has at least the specified exponents for each prime."""
  for p, val in denom:
    if state[p] < val:
      return False
  return True

def update_state(state, num, denom):
  """Checks the program's state and updates it according to an instruction."""
  if check(state, denom):
    for p, val in denom:
      state[p] -= val
    for p, val in num:
      state[p] += val
    return True
  else:
    return False

def format_state(state):
  return dict((i, v) for i, v in enumerate(state) if v != 0)

def make_usage_map(program, maxidx):
  firstref = [len(program)] * maxidx
  for i, (num, denom) in enumerate(program):
    for idx, value in denom:
      if firstref[idx] == len(program):
        firstref[idx] = i
  return firstref

def make_jump_map(program, firstref):
  jump_map = []
  for i, (num, denom) in enumerate(program):
    if num:
      jump_map.append(min(min(firstref[idx] for idx, val in num), i))
    else:
      jump_map.append(i)
  return jump_map

def fractran(program, input, debug_when=None):
  """Executes a Fractran program and returns the state at the end."""
  maxidx = max(z[0] for instr in program for part in instr for z in part) + 1
  state = [0]*maxidx

  if isinstance(input, (int, long)):
    input = factorize(input)

  for prime, val in input:
    state[prime] = val

  firstref = make_usage_map(program, maxidx)
  jump_map = make_jump_map(program, firstref)

  pc = 0
  length = len(program)
  while pc < length:
    num, denom = program[pc]
    if update_state(state, num, denom):
      if num:
        pc = jump_map[pc]
      if debug_when and debug_when(state):
        print format_state(state)
    else:
      pc += 1

  return format_state(state)

Перл 6:77 персонажей (экспериментальный)

sub f(@p,$n is copy){
loop {my$s=first {!($n%(1/$_))},@p or return $n;$n*=$s}}

Новая строка не является обязательной.Звоните как:

say f([3/2], 1296).Int;
say f([455/33, 11/13, 1/11, 3/7, 11/2, 1/3], 60466176).Int;

Читабельная версия:

sub Fractran (@program, $state is copy) {
  loop {
    if my $instruction = first @program:
      -> $inst { $state % (1 / $inst) == 0 } {
      $state *= $instruction;
    } else {
      return $state.Int;
    }
  }
}

Примечания:

Обозначение двоеточия first @program: pointy-sub не работает в текущих реализациях;вместо первого BLOCK необходимо использовать @program.
Похоже, у Ракудо есть багги. Rat дает неправильные результаты.Текущая Niecza правильно и быстро запускает все тестовые программы, включая «бонусную» часть.

Хаскель, 142 символа

Без каких-либо дополнительных библиотек и полноценного ввода/вывода.

t n f=case f of{(a,b):f'->if mod n b == 0then(\r->r:(t r f))$a*n`div`b else t n f';_->[]}
main=readLn>>=(\f->readLn>>=(\n->print$last$t n f))

Джава, 200 192 179 символов

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

Вот уменьшенная версия:

class F{public static void main(String[]a){long p=new Long(a[0]);for(int i=1;i<a.length;){long n=p*new Long(a[i++]),d=new Long(a[i++]);if(n%d<1){p=n/d;i=1;}}System.out.print(p);}}

Java -CP.Ж 108 455 33 11 13 1 11 3 7 11 2 1 3

Java -CP.Ф 1296 3 2

Вот очищенная версия:

public class Fractran {

    public static void main(String[] args) {
        long product = new Long(args[0]);

        for (int index = 1; index < args.length;) {
            long numerator = product * new Long(args[index++]);
            long denominator = new Long(args[index++]);

            if (numerator % denominator < 1) {
                product = numerator / denominator;
                index = 1;
            } // if
        } // for

        System.out.print(product);
    }
}

Схема 73 символа

Моя первая попытка сделать это с помощью совершенно стандартного R.⁵Схема RS имела длину 104 символа:

(define(f p n)(let l((q p)(n n))(if(null? q)n(let((a(* n(car q))))(if(integer?
a)(l p a)(l(cdr q)n))))))

Выполнение нескольких элементов тестового вектора:

> (f '(3/2) 1296)
6561
> (f '(455/33 11/13 1/11 3/7 11/2 1/3) 60466176)
7888609052210118054117285652827862296732064351090230047702789306640625

Если вы предполагаете, что λ связан с lambda и let/cc определяется (как в схеме PLT;определения для запуска этого в схемах, которые их не определяют, см. ниже), тогда я смогу адаптировать Второе решение Джордана на Ruby к Scheme, который содержит 73 символа (обратите внимание, что порядок аргументов противоположен моему первому решению, но такой же, как у Джордана;в этой версии это экономит один символ).:

(define(f n p)(let/cc r(map(λ(i)(if(integer?(* n i))(r(f(* n i)p))))p)n))

Если у меня нет λ и let/cc предопределено, то этот имеет длину 111 символов (88, если довольно распространен call/cc аббревиатура определена):

(define(f n p)(call-with-current-continuation(lambda(r)(map(lambda(i)(if(integer?(*
n i))(r(f(* n i)p))))p)n)))

Определения λ и let/cc:

(define-syntax λ 
  (syntax-rules () 
    ((_ . body) (lambda . body)))

(define-syntax let/cc 
  (syntax-rules () 
    ((_ var . body) (call-with-current-continuation (lambda (var) . body)))))

Немного поздно...84 символа постоянного тока

Просто для развлечения а dc решение (OpenBSD)

[ss1sp]s1[Rlp1+sp]s2?l1xz2/sz[z2/ds_:bl_:az0<L]dsLx
1[;als*lp;b~0=1e2lpdlz!<L]dsLxlsp

Он обрабатывает все случаи:

$ dc fractran.dc  
455 33 11 13 1 11 3 7 11 2 1 3 60466176
7888609052210118054117285652827862296732064351090230047702789306640625

Я пока не могу оставлять комментарии, но вот «немного» более короткая версия версии RCIX на C# (думаю, она на 7 символов короче)

using System;namespace T{static class P{static void Main(string[] a){int i=1;Func<string,decimal> d=Convert.ToDecimal;var c=d(a[0]);while(i+1<=a.Length){var f=d(a[i])/d(a[++i]);if((f*c)%1==0){i=1;c*=f;}else i++;}Console.Write(c);}}}

который использует

Func<string,decimal> d=Convert.ToDecimal

и звонки d(); вместо

using b=Convert;

и неоднократно звонил b.ToDecimal();.

Я также удалил ненужную пару фигурных скобок вокруг оператора else, чтобы получить 1 символ :).

Я также заменил a[i+1] с a[++i] и в следующем теле else я заменил i+=2 с i++ чтобы получить еще одного персонажа :P

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow