Código De Golfe:Fractran

https://stackoverflow.com/questions/1749905

20-09-2019
|

Pergunta

O Desafio

Escrever um programa que atua como um Fractran intérprete.O menor intérprete pela contagem de caracteres, em qualquer língua, é o vencedor.O seu programa deve ter duas entradas:O fractran programa a ser executado, e a entrada de número inteiro n.O programa pode ser em qualquer forma que seja conveniente para o seu programa - por exemplo, uma lista de 2-tuplas, ou uma lista fixa.A saída deve ser um número inteiro único, sendo o valor de registo no final de execução.

Fractran

Fractran é trivial esotérico idioma inventado por John Conway.Um fractran programa consiste de uma lista de positivo frações e um estado inicial n.O intérprete mantém um contador de programa, inicialmente, apontando para a primeira fração na lista.Fractran programas são executados da seguinte forma:

Verifique se o produto de o estado atual e a fração atualmente sob o contador de programa é um número inteiro.Se é, multiplique o estado atual de fração e repor o contador de programa para o início da lista.
Avançar o contador de programa.Se o fim da lista é atingido, parar, caso contrário, volte para o passo 1.

Para obter detalhes sobre como e por que Fractran works, consulte o esolang entrada e esta entrada no bom de matemática/matemática incorreta.

Vetores De Teste

Programa: [(3, 2)]
Entrada: 72 (2³3²)
Saída: 243 (3⁵)

Programa: [(3, 2)]
Entrada: 1296 (2⁴3⁴)
Saída: 6561 (3⁸)

Programa: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
Entrada: 72 (2³3²)
Saída: 15625 (5⁶)

Bônus de teste vetor:

Sua submissão não precisa executar este último programa corretamente para ter uma resposta aceitável.Mas parabéns se ele faz!

Programa: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
Entrada: 60466176 (2¹⁰3¹⁰)
Saída: 7888609052210118054117285652827862296732064351090230047702789306640625 (5¹⁰⁰)

Envios & Pontuação

Os programas são classificados estritamente pelo comprimento em caracteres mais curto é o melhor.Sinta-se livre para enviar um tanto bem estabelecidas e documentadas e um 'reduzido' versão do seu código, para que as pessoas possam ver o que está acontecendo.

A língua 'J' não é admissível.Isso é porque já existe uma conhecida solução de J em uma das páginas ligadas. Se você é um J fã, sorry!

Como um bônus extra, no entanto, qualquer pessoa que possa fornecer um trabalho fractran intérprete no fractran receberá 500 pontos de reputação bônus.No improvável evento de auto-hospedagem de intérpretes, aquele com o menor número de fracções vai receber a recompensa.

Os vencedores

O vencedor oficial, após o envio de um auto-hospedagem fractran solução composta de 1779 frações, é Jesse Beder da solução.Praticamente falando, a solução é muito lento para executar o mesmo 1+1, no entanto.

Incrivelmente, desde que este tenha sido espancado por um outro fractran solução - Amadaeus da solução em apenas 84 frações!Ele é capaz de executar os dois primeiros casos de teste em questão de segundos quando em execução no meu referência Python solução.Ele usa um romance método de codificação para as frações, que também merece um olhar mais atento.

Menções honrosas para:

Stephen Canon solução, em 165 caracteres de x86 assembly (28 bytes de código de máquina)
Jordan solução em 52 caracteres de ruby - que lida com números inteiros longos
Inútil solução em 87 caracteres do Python, que, apesar de não ser o mais curto Python solução, é uma das poucas soluções que não é recursiva, e, portanto, lida com mais programas com facilidade.É também muito legível.

Solução

Fractran - 1779 frações

(Edição:fixo)

(Espero que as pessoas ainda estão seguindo esta linha, porque isso levou um tempo!)

Parece isso não vai me deixar postar algo tão longo como este, por isso eu postei a Fractran de origem aqui.

A entrada é especificado da seguinte forma:

Primeiro, vamos codificar uma fração m/n = p_0^a0... p_k^ak por:

Comece com 1.Então, para cada ai:
Multiplique por p_2i^ai se ai > 0
Multiplique por p_2i+1^{-ai} se a_i < 0

Desta forma, podemos codificar qualquer fração como um número inteiro positivo.Agora, dado um progoram (sequência codificada frações F0, F1, ...), percebemos que, por

p_0^F0 p1^F1 ...

Finalmente, a entrada para o intérprete é dada por:

2^(program) 3^(input) 5

onde program e input são codificados como acima.Por exemplo, no primeiro teste de problema, 3/2 fica codificado para 15, assim que o programa é codificado para 2^15;e 108 fica codificado para 500.Então, nós passamos

2^{2^15} 3^500 5

para o programa.A saída, então, é da forma

2^(program) 3^(output)

assim, no primeiro exemplo, ele vai ser

2^{2^15} 3^3125

Como funciona?

Eu escrevi uma meta-linguagem que compila para baixo para Fractran.Ele permite funções (simples Fractran e sequências de outras funções), e um while ciclo e if instrução (por conveniência!).O código para que possa ser encontrado aqui.

Se você deseja compilar o código para baixo para Fractran si mesmo, a minha (C++) programa pode ser encontrado aqui [tar.gz].Em uma impressionante exibição de dogfooding (e mostrando), eu usei o meu C++ parser de YAML yaml-cpp, então você teria que baixar e o link com que.Para tanto yaml-cpp e o "compilador", você vai precisar de O CMake para o cruz-plataforma makefile geração.

A utilização deste programa é:

./fracc interpreter.frp

O que ele lê o nome de uma função a partir da entrada padrão e escreve o correspondente de "pseudo-Fracção" (vou explicar o que, em um segundo) para a saída padrão.Portanto, para compilar o intérprete (a Interpretar função), você pode executar

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

A saída ("pseudo-Fractran") será uma sequência de linhas, cada uma com uma seqüência de caracteres separados por espaços dígitos.Uma linha corresponde a uma fração:se o nth dígitos na linha é an, e , em seguida, a fração é o produto de p_n^an.

É muito fácil converter-se que este Fractran, mas se você é preguiçoso, você pode usar to-fractions.py. [Nota:anteriormente eu tinha um programa C++, e eu tinha descuidadamente ignorado estouro de número inteiro.Eu traduzi-o para o Python para evitar isso.]

Nota sobre a entrada:se você quiser testar uma função diferente desta forma, a convenção é sempre o mesmo.Ele tem um número de parâmetros (geralmente o comentário acima a função explica isso) em pseudo-Fractran, para dar-lhe o que ele quer, além de um 1 no próximo slot (tão comum Fractran, multiplicar uma vez, o primeiro-que não uso).Este é um "sinal" de bits para a função para começar a ir.

No entanto,

Eu não recomendo tentar executar o Fractran intérprete (infelizmente).Eu testei muitos de seus componentes, e, por exemplo, a função IncrementPrimes, o que leva um par de primos e retorna os próximos dois primos, leva cerca de 8 minutos para executar, usando o meu bobo C++ intérprete (não há necessidade de postar isso :).Além disso, ele vai (pelo menos) quadratically no número de chamadas de função -, dobrando o número de chamadas de função faz com que ele tome, pelo menos, quatro vezes mais (mais, se há while loops ou if declarações).Então, eu estou supondo que executar o interpretador vai demorar menos dias, se não anos :(

Então, como eu sei que ele funciona?Bem, é claro que eu não estou 100% certo, mas eu estou muito perto.Primeiro de tudo, eu testei muitos, muitos de seus componentes, e em particular, eu testei todos os elementos de meta-linguagem (sequências de funções e if e while instruções muito cuidadosamente.

Além disso, a meta-linguagem é fácil de traduzir para o seu idioma favorito, e ainda mais fácil de traduzir para C++, uma vez que todos os parâmetros das funções são passados por referência.Se você está se sentindo preguiçoso novamente, você pode baixar a minha tradução aqui [tar.gz] (não há makefile;é apenas dois .arquivos cpp, por isso chamando diretamente o gcc é bom).

Assim você pode comparar os dois intérpretes, execute o C++ versão (ele também tem entrada/saída em pseudo-Fractran), verificar o que funciona e, em seguida, convencer-se de que a meta-linguagem funciona também.

Ou!

Se você estiver se sentindo inspirado, e realmente quero ver esse intérprete interpretado, você pode escrever um "inteligente" Fractran intérprete com base em todo o tipo de Fractran de saída que temos.A saída é muito bem estruturado, sequências de funções são implementadas com o uso de sinais, por isso, se você de alguma forma cache onde o interpretador foi, você poderia saltar de imediato se nada de importante mudou.Este seria, eu acho, dramaticamente acelerar o programa (e, talvez, reduzindo tempo de execução por um ou mais poderes).

Mas, eu não estou realmente certo de como fazer isso, e eu estou feliz com o que está feito, então eu vou deixá-lo como um exercício para o leitor.

Outras dicas

Fractran: 84 frações

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]

Isso é escrito inteiramente à mão. Eu inventei um idioma pseudo para poder expressar as coisas com mais clareza, mas não escrevi um compilador e optei por escrever o código Fractran otimizado diretamente.

FTEVAL Recebe a entrada 3^initial_state * 5^encoded_program * 199, produz resultados intermediários 3^interpreted_program_state * 199, e interrompe completamente em um número divisível por 233.

O programa interpretado é incorporado como uma lista de 10 dígitos da base dentro de um único número de Base 11, usando o dígito "A" para marcar o limite, exceto no final. O programa de adição [3/2] é codificado como

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

O programa de multiplicação [455/33, 11/13, 1/11, 3/7, 11/2, 1/3] é codificado como

int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657

que é um número verdadeiramente grande.

O primeiro vetor de teste terminou em Menos de um segundo, produziu o resultado desejado após 4545 iterações e interrompeu após 6172 iterações. Aqui está a saída completa.

Infelizmente, o Sage Segfaulted quando eu tentei o segundo vetor de teste (mas acho que funcionará sob a implementação de Nick usando os principais vetores de expoente).

O espaço aqui é realmente muito pequeno para explicar tudo. Mas aqui está o meu pseudocódigo. Vou escrever meu processo em alguns dias, espero.

# 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 Assembléia, 165 caracteres (28 bytes do código da máquina).

O estado é aprovado em %rdi, o programa (ponteiro para matriz de frações com terminado nulo) está em %RSI. Os resultados são retornados em %Rax de acordo com as convenções usuais de chamadas no estilo C. O uso de convenções de chamadas não-padrão ou a sintaxe da Intel (esta é a sintaxe da AT&T) lançariam mais alguns caracteres, mas eu sou preguiçoso; Alguém pode fazer isso. Uma instrução ou duas ou duas quase certamente pode ser salva reorganizando o fluxo de controle, se alguém quiser fazer isso, sinta-se livre.

Os cálculos intermediários (numerador de estado*) podem ter até 128 bits de largura, mas apenas o estado de 64 bits é suportado.

_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

Exclua comentários, espaço em branco estranho e o rótulo detalhado _fractran para versão minimizada.

Rubi, 58 57 56 53 52 caracteres

Esta é a minha primeira entrada de golfe de código, por isso seja gentil.

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

Uso:

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

Linda versão (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

Rubi, 53 52 Usando racional

Inspirado por Solução de Gnibbler Consegui obter uma solução usando racional para baixo para 53 52 caracteres. ~~Ainda um mais longo que a solução (menos elegante) acima.~~

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

Uso:

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)

(UMA to_i Call para saída mais bonita adicionaria mais 5 caracteres.)

Golfscript - 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

Haskell, 102 caracteres

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 com restrições relaxadas no formato de entrada/saída.

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

Pitão, 83 82 81 72 70 caracteres.

É conveniente ter entrada como frações. A mesma idéia que na solução 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

C, 159 153 151 131 111 110 caracteres

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

Python - 53

Melhoria graças a Paul

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

casos de teste

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 sem usar fração

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

Python - 55

Este é um pouco teórico. Os dois primeiros casos funcionam bem, mas os outros dois falham da profundidade da recursão. Talvez alguém possa fazer com que funcione com uma expressão de gerador

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

Aqui está uma possibilidade, mas cresce para 65, mesmo sem incluir a importação

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()

F#: 80 chars

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

Aqui está uma versão expandida usando match pattern with |cases ao invés de 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

Código de teste:

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

E resultado (testado em f# interativo):

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

Editar Vamos nos divertir mais com isso e calcular alguns primos (consulte a página vinculada na postagem inicial). Eu escrevi uma nova função g Isso produz os valores intermediários do estado.

//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

Leva 4,7 segundos para tossir os 10 primeiros números primos:

> 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]

Este é, sem dúvida, o gerador de números mais bizarros e lentos que já escrevi. Não tenho certeza se isso é uma coisa boa ou ruim.

Um javascript um: 99 caracteres. Nenhum vetor de bônus :(

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 entrada está no formato [[a,b],[c,d]]. Aproveitei a leniência de JavaScript: em vez de fazer var x=0, y=0;, você pode adicionar quantos parâmetros quiser. Não importa se você realmente os passa ou não, pois eles são o padrão para null.

Versão bonita:

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;
};

Pitão, 110 103 95 87 caracteres

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

(mostra como dirigir)

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()

C#:

Versão arrumada:

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);
        }
    }
}

Versão reduzida pesando em 201 chars (sem as declarações de namespace ou nada disso, apenas a única instrução usando (não sistema) e a função principal):

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);}}}

Exemplos (a entrada é através dos argumentos da linha de comando):

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

Groovy, ~~136~~ ~~117~~ 107 caracteres.

Chame como Groovy Fractal.groovy [estado de entrada] [Vector do programa como lista de números

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

Amostra

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

Perl, 84 82 CHAR

Usa entrada padrão.

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

Leva 110 chars para passar no teste de bônus:

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

Haskell: ~~116~~ 109 caracteres

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}

Isso acabou como um pouco de uma imitação da entrada de Dario.

Esquema: 326

Eu pensei que era necessária uma submissão de esquema, para paridade. Eu também só queria a desculpa para brincar com ela. (Desculpe meu conhecimento rudimentar, tenho certeza de que isso pode ser otimizado e estou aberto a sugestões!)

#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)))))

Testes:

(fractran_interpreter 108 0 '(3/2))

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

Eu recebo o vetor de bônus! (Usando o Dr. Scheme, alocando 256 MB)

Lua:

Código arrumado:

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)

Código compacto pesando em 98 chars (Redução sugerida pelo ScoreGraphic na minha outra resposta e mais sugerida por 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)

Corra da linha de comando, fornecendo o número base primeiro e depois a série de frações apresentadas como números com separação de espaço, como o seguinte:

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

(digitou manualmente um pouco disso, porque é uma dor tirar as coisas da linha de comando, embora esse seja os resultados retornados)

Não lida com o vetor de bônus tristemente :(

Implementação de referência em Python

Esta implementação opera com as principais fatorizações.

Primeiro, ele decodifica uma lista de tuplas de fração codificando o numerador e o denominador como uma lista de tuplas (idx, valor), onde o IDX é o número do prime (2 é o Prime 0, 3 é o Prime 1 e assim por diante).

O estado atual é uma lista de expoentes para cada primo, por índice. A execução de uma instrução requer a primeira iteração sobre o denominador, verificando se o elemento de estado indexado for pelo menos o valor especificado; então, se corresponder, diminuir os elementos do estado especificados no denominador e incrementando os especificados no numerador.

Essa abordagem é cerca de 5 vezes a velocidade de fazer operações aritméticas em grandes números inteiros em Python e é muito mais fácil de depurar!

Uma otimização adicional é fornecida pela construção de um mapeamento de matriz cada índice primário (variável) até a primeira vez que é verificado no denominador de uma fração e, em seguida, usando isso para construir um 'jump_map', consistindo na próxima instrução para executar para cada instrução no programa.

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)

Perl 6: 77 caracteres (experimental)

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

Newline é opcional. Ligue como:

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

Versão legível:

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

Notas:

A notação do cólon first @program: pointy-sub não funciona nas implementações atuais; Primeiro bloco, @programa deve ser usado.
Rakudo parece ter um buggy Rat dando resultados incorretos. O NIECZA atual executa todos os programas de teste corretamente e rapidamente, incluindo a fração "bônus".

Haskell, 142 caracteres

Sem bibliotecas adicionais e E/S completa.

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))

Java, 200 192 179 caracteres

Acho que todo mundo sabe que Java não teria a mais curta implementação, mas eu queria ver como isso se compararia. Ele resolve os exemplos triviais, mas não o bônus.

Aqui está a versão minimizada:

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. F 108 455 33 11 13 1 11 3 7 11 2 1 3

Java -CP. F 1296 3 2

Aqui está a versão limpa:

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);
    }
}

Esquema 73 caracteres

Minha primeira tentativa, de fazer isso com R completamente padrão R⁵Esquema RS, chegou a 104 caracteres:

(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))))))

Correndo contra alguns itens no vetor de teste:

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

Se você assumir isso λ é obrigado a lambda e let/cc é definido (como eles estão no esquema PLT; veja abaixo as definições para executar isso em esquemas que não os definem), então eu posso me adaptar A segunda solução de rubi da Jordânia para o esquema, que chega a 73 caracteres (observe que a ordem de argumento é o inverso da minha primeira solução, mas o mesmo que a de Jordan; nesta versão, que salva um personagem).:

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

Se eu não tiver λ e let/cc Predefinido, então este chega a 111 caracteres (88 se o razoavelmente comum call/cc A abreviação é definida):

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

Definições de λ e let/cc:

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

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

Um pouco tarde ... DC 84 chars

Apenas para se divertir um dc Solução (OpenBSD)

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

Ele lida com todos os casos:

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

Ainda não posso deixar comentários, mas aqui está uma versão "ligeiramente" mais curta da versão C# da RCIX (acredito que é 7 chars mais curto)

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);}}}

que usa

Func<string,decimal> d=Convert.ToDecimal

e chamadas d(); ao invés de

using b=Convert;

e ligando repetidamente b.ToDecimal();.

Também removi um par desnecessário de aparelhos encaracolados ao redor da declaração eliminada para ganhar 1 char :).

Eu também substituí o a[i+1] com a[++i] E no corpo seguinte, substituí i+=2 com i++ Para ganhar outro char: P

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow