•  20-09-2019
  •  | 
  •  

Pregunta

The Challenge

Escribir un programa que actúa como un Fractran intérprete. El intérprete más corta por el recuento de caracteres, en cualquier idioma, es el ganador. Su programa debe tener dos entradas: El programa fractran a ser ejecutado, y el entero de entrada n. El programa puede estar en cualquier forma que sea conveniente para su programa - por ejemplo, una lista de 2-tuplas, o una lista plana. La salida debe ser un solo número entero, siendo el valor del registro al final de la ejecución.

Fractran

Fractran es un lenguaje esotérico trivial inventado por John Conway . Un programa fractran consiste en una lista de fracciones positivas y un estado n inicial. El intérprete mantiene un contador de programa, en un principio que apunta a la primera fracción en la lista. Fractran programas se ejecutan de la siguiente manera:

  1. comprobar si el producto del estado actual y la fracción actualmente en el contador de programa es un número entero. Si lo es, se multiplica el estado actual de la fracción actual y restablecer el contador de programa al principio de la lista.
  2. Haga avanzar el contador de programa. Si se alcanza el final de la lista, alto, de otro modo volver al paso 1.

Para obtener más detalles sobre cómo y por qué funciona Fractran, consulte la entrada esolang y esta entrada en matemáticas buena / mala matemáticas.

Prueba vectores

Programa: [(3, 2)]
Entrada: 72 (2 3 3 2 )
Salida: 243 (3 5 )

Programa: [(3, 2)]
Entrada: 1296 (2 4 3 4 )
Salida: 6561 (3 8 )

Programa: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)] < br> Entrada: 72 (2 3 3 2 )
Salida: 15625 (5 6 )

Bonus prueba vector:

Su presentación no tiene que ejecutar este último programa correctamente para ser una respuesta aceptable. Pero felicitaciones si lo hace!

Programa: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)] < br> Entrada: 60466176 (2 10 3 10 )
Salida: 7888609052210118054117285652827862296732064351090230047702789306640625 (5 100 )

Envío & Scoring

Los programas se clasifican estrictamente por la longitud en caracteres - más corto es el mejor. No dude en enviar un tanto una versión 'minified' de su código bien diseñado y documentado, y que la gente pueda ver lo que está pasando.

El lenguaje 'J' no es admisible. Esto es porque ya hay una solución muy conocida en J en una de las páginas enlazadas. Si eres un fan de J, lo siento!

Como un bono extra, sin embargo, cualquier persona que pueda proporcionar un intérprete fractran de trabajo en fractran recibirán una bonificación del 500 reputación. En el improbable caso de múltiples intérpretes autoalojamiento, el que tiene el menor número de fracciones recibirá la recompensa.

Los ganadores

El ganador oficial, después de presentar una solución fractran autoalojamiento que comprende fracciones 1779, es Jesse Beder de solución. En términos prácticos, la solución es demasiado lento para ejecutar incluso 1 + 1, sin embargo.

Aunque parezca increíble, esto ha sido desde entonces golpeado por otra solución fractran - solución de Amadaeus en sólo 84 fracciones! Es capaz de la ejecución de la primera two casos de prueba en cuestión de segundos cuando se ejecuta en mi solución Python referencia. Se utiliza un nuevo método de codificación para las fracciones, que es también digno de una mirada cercana.

Menciones de honor a:

¿Fue útil?

Solución

Fractran - 1779 fracciones

(Edit: fija)

(espero que la gente todavía están siguiendo este hilo, porque esto tomó un tiempo!)

Parece que sí no me deja publicar algo tan larga como esta, por lo que ha escrito la fuente Fractran aquí .

entrada se especifica de la siguiente manera:

En primer lugar, codificamos un m/n = p_0^a0... p_k^ak fracción por:

  • Comience con 1. A continuación, para cada ai:
  • Multiplicar por p_2i^ai si ai > 0
  • Multiplicar por p_2i+1^{-ai} si a_i < 0

De esta manera, codificar cualquier fracción como un número entero positivo. Ahora, dado un progoram (secuencia de fracciones codificados F0, F1, ...), codificamos que por 

p_0^F0 p1^F1 ...

Finalmente, la entrada al intérprete está dado por: 

2^(program) 3^(input) 5

donde program y input se codifican como anteriormente. Por ejemplo, en el primer problema prueba, 3/2 se codifica a 15, por lo que el programa se codifica a 2^15; y 108 se codifica a 500. Así, pasamos 

2^{2^15} 3^500 5

para el programa. La salida, a continuación, es de la forma 

2^(program) 3^(output)

por lo que en el primer ejemplo, va a ser 

2^{2^15} 3^3125

¿Cómo funciona?

escribí un metalenguaje que compila a Fractran. Permite funciones (Fractran simple y secuencias de otras funciones), y un bucle while y cuenta de if (por conveniencia). El código para que se puede encontrar aquí .

Si quieres compilar el código abajo a Fractran mismo, mi programa (C ++) se puede encontrar aquí [tar.gz.]. En un impresionante despliegue de dogfooding (y mostrando), he usado mi C ++ YAML analizador href="http://code.google.com/p/yaml-cpp/" yaml-CPP , por lo que lo tienes que descargar y enlace con eso. Por tanto yaml-CPP y el "compilador", tendrá que CMake para generar multiplataforma makefile.

El uso de este programa es: 

./fracc interpreter.frp

El lee el nombre de una función de la entrada estándar, y escribe el correspondiente "pseudo-Fracción" (I a explicar que en un segundo) a la salida estándar. Así que para compilar el intérprete (Interpretar la función), puede ejecutar 

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

La salida ( "pseudo-Fractran") será una secuencia de líneas, cada una con una cadena de dígitos separados por un espacio. Una línea corresponde a una fracción:. Si el dígito nth en la línea es an, a continuación, la fracción es el producto de p_n^an

Es muy fácil de convertir esto en Fractran, pero si usted es perezoso, puede utilizar to-fractions.py . [ Nota: : antes yo tenía un programa en C ++, y yo no había hecho caso de desbordamiento de entero sin cuidado. Lo traduje a Python para evitar esto.]

Nota acerca de la entrada : si quieres poner a prueba una función diferente de esta manera, la convención es siempre la misma. Tiene una serie de parámetros (por lo general el comentario anterior la función explica esto) en pseudo-Fractran, por lo que darle lo que quiere, además de un 1 en la siguiente ranura (lo que en Fractran ordinaria, se multiplica una vez por el primer primer que no va a usar). Esto es un poco de "señal" a la función para iniciar la marcha.

Sin embargo,

No recomiendo realidad tratando de ejecutar el intérprete de Fractran (por desgracia). Probé muchos de sus componentes, y, por ejemplo, la IncrementPrimes función, que tiene un par de números primos y devuelve los próximos dos números primos, toma alrededor de 8 minutos para ejecutar, usando mi tonta C ++ intérprete (sin necesidad de publicar eso :). Además, no hace falta (al menos) al cuadrado del número de llamadas de función - duplicando el número de llamadas de función hace que se tarda por lo menos cuatro veces más largo (más si hay bucles while o declaraciones if). Así que supongo que ejecuta el intérprete tendrá al menos días, si no años: (

Entonces, ¿cómo sé que funciona? Bueno, por supuesto que no estoy 100% seguro, pero estoy bastante cerca. Primero de todo, he probado muchos, muchos de sus componentes, y, en particular, he probado todos los elementos de la meta-lenguaje (secuencias de funciones y estados if y while) muy a fondo.

Además, el metalenguaje es fácil de traducir a su idioma favorito, e incluso más fácil de traducir a C ++, ya que todos los parámetros de las funciones se pasan por referencia. Si estás perezoso de nuevo, se puede descargar mi traducción href="http://www.math.uiuc.edu/~beder/interpreter-cpp.tar.gz" aquí [tar.gz.] (no hay makefile, es sólo dos archivos .cpp, así que llamar directamente gcc está muy bien)

.

Así se puede comparar los dos intérpretes, ejecutar la versión de C ++ (que también toma la entrada / salida de pseudo-Fractran), compruebe que que funciona, y luego convencerse de que el meta-lenguaje también funciona.

O!

Si te sientes inspirado, y realmente quieren ver este intérprete interpreta, puede escribir un intérprete de "inteligente" Fractran en torno al tipo de salida Fractran que obtenemos. La salida es muy estructurado - sucesiones de funciones se implementan utilizando señales, por lo que si de alguna manera caché donde estaba el intérprete, que podrían saltar allí inmediatamente si nada importante ha cambiado. Esto, creo, sería acelerar dramáticamente el programa (tal vez reducir el tiempo de funcionamiento de una o más potencias).

Sin embargo, no estoy muy seguro de cómo hacer esto, y estoy feliz con lo que está hecho, así que lo dejo como ejercicio para el lector.

Otros consejos

Fractran: 84 fracciones 

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]

Esto está escrito totalmente a mano. Me hice un pseudo lenguaje para poder expresar las cosas con más claridad, pero no me hizo escribir un compilador y optó por escribir código optimizado Fractran directamente.

FTEVAL toma 3^initial_state * 5^encoded_program * 199 de entrada, produce resultados intermedio 3^interpreted_program_state * 199, y completamente se detiene en un número divisible por 233.

El programa interpretado se Embebido como una lista de base de 10 dígitos dentro de un único número de base 11, usando el dígito "a" para marcar el límite excepto en el final. El programa de adición [3/2] se codifica como 

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

El programa de multiplicación [455/33, 11/13, 1/11, 3/7, 11/2, 1/3] se codifica como 

int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657

que es un número realmente grande.

El primer vector de prueba terminado en menos de un segundo , produjo el resultado deseado después de 4545 iteraciones y se detuvo después de 6172 iteraciones. Aquí es la salida completa .

Por desgracia, salvia segfaulted cuando probé el segundo vector de prueba (pero creo que va a trabajar en fase de ejecución de Nick usando vectores exponente).

El espacio aquí es realmente demasiado pequeño para explicar todo. Pero aquí está mi pseudocódigo. Voy a escribir mi proceso en un par de días, es de esperar. 

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

conjunto x86_64 , 165 caracteres (28 bytes de código de máquina).

Estado se pasa en% RDI, Programa (puntero a la matriz terminada en nulo de fracciones) es en% RSI. Los resultados se devuelven en% rax por las convenciones de llamada de tipo C habituales. El uso de convenciones de llamada no estándar o sintaxis de Intel (esto es AT & T sintaxis) se reduciría un poco más personajes, pero soy perezoso; otra persona puede hacerlo. Una instrucción o dos casi con toda seguridad se puede guardar reorganizando el flujo de control, si alguien quiere hacer eso, se siente libre.

cálculos intermedios (estado * numerador) puede ser de hasta 128 bits de ancho, pero está apoyado sólo el 64 estado de bit. 

_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

Eliminar comentarios, espacios en blanco extrañas, y el _fractran etiqueta detallado para la versión minimizada.

Ruby, 58 57 56 53 52 caracteres

Esta es mi primera vez la introducción del código de golf, así que por favor ser suave. 

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

versión de Pretty (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

Ruby, 53 52 usando racionales

yo era capaz de conseguir una solución a través de Rational hasta 53 52 caracteres. Sigue siendo uno más largo que la solución (menos elegante) anterior. 

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)

(Una llamada to_i para la salida más bonita añadiría más de 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 con suavizó las restricciones sobre el formato de entrada / salida. 

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

Python, 83 82 81 72 70 caracteres.

Es conveniente tener de entrada como objetos fractions.Fraction. La misma idea que en la solución de 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

Mejora gracias a Paul 

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

casos de prueba 

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 Sin utilizar Fracción 

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

Python - 55

Éste es algo teórico. Los dos primeros casos funcionan bien, pero los otros dos fallan a nivel de recursividad. Tal vez alguien puede conseguir que funcione con una expresión generadora 

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

Esto es una posibilidad, pero crece a 65, incluso sin incluir la importación 

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 caracteres 

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

Esto es una versión ampliada utilizando match pattern with |cases en lugar 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 ensayo: 

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

Y resultado (probado en Fa # interactiva): 

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

Editar vamos a tener un poco más de diversión con este, y calcular algunos números primos (véase la página vinculada en el puesto de partida). He escrito un nuevo g función que se obtienen los valores intermedios del 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

Toma la friolera de 4,7 segundos que soltar los primeros 10 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 es, sin duda, el generador de número primo más extraño y lento que he escrito. No estoy seguro de si eso es algo bueno o malo.

A Javascript uno: 99 caracteres . Sin vector de bonificación: (

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

entrada está en el formato [[a,b],[c,d]]. Aproveché indulgencia de Javascript: en lugar de hacer var x=0, y=0;, puede añadir tantos parámetros como desee. No importa si en realidad se pasa o no, ya que por defecto a null.

Pretty versión: 

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

Python, 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

(muestra cómo manejarlo) 

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

versión ordenado: 

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

versión reducida con un peso de 201 caracteres (sin las declaraciones de espacio de nombres ni nada de eso, sólo la única instrucción using (no del sistema) y la función 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);}}}

Ejemplos (de entrada es a través de los argumentos de línea de comandos): 

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.

Llamada [estado de entrada] fractal.groovy como maravilloso [vector 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

Ejemplo 

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

Perl, 84 82 Char

Utiliza la entrada estándar. 

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

Toma 110 caracteres para pasar la prueba de bonificación: 

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}

Esto terminó como algo de una imitación de la entrada de Darío.

Esquema: 326

pensé que era necesaria una presentación esquema, para la paridad. Asimismo, sólo quería una excusa para jugar con él. (Disculpen mi conocimiento rudimentario, estoy seguro de que esto podría ser optimizado, y estoy abierto a sugerencias!) 

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

Pruebas:

(fractran_interpreter 108 0 '(3/2))

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

Me sale el vector de bonificación! (usando Dr. Scheme, la asignación de 256 mb)

Lua:

código ordenado: 

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 con un peso de 98 caracteres (reducción sugerida por Scoregraphic en mi otra respuesta, y más sugerido 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)

Ejecutar desde la línea de comandos, suministrando el número base primera entonces la serie de fracciones que se presentan como números con separación espacial, como la siguiente: 

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

(tecleado manualmente algo de eso en porque es un dolor para conseguir cosas fuera de la línea de comandos, aunque eso es los resultados devueltos)

No maneja el vector de bonificación por desgracia: (

implementación de referencia en Python

Esta aplicación funciona en factores primos.

En primer lugar, decodifica una lista de tuplas fracción codificando el numerador y el denominador como una lista de (IDX valor) tuplas, donde idx es el número del primer (2 es primo 0, 3 es primo 1, y así sucesivamente).

El estado actual es una lista de exponentes para cada primo, por el índice. Ejecución de una instrucción requiere primera iteración sobre el denominador, comprobando si el elemento de estado indexada es al menos el valor especificado, entonces, si coincide, decrementar elementos estatales especificados en el denominador, e incrementando los especificados en el numerador.

Este enfoque es de aproximadamente 5 veces la velocidad de hacer operaciones aritméticas con números enteros grandes en Python, y es mucho más fácil de depurar!

Una optimización adicional se proporciona mediante la construcción de una matriz mapear cada índice prime (variable) a la primera vez que se comprueba en el denominador de una fracción, a continuación, utilizando que para construir un 'jump_map', que consta de la siguiente instrucción a ejecutar para cada instrucción en el 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 es opcional. Llamar como: 

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

versión legible: 

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

Notas:

  1. El first @program: pointy-sub notación de colon no funciona en las implementaciones actuales; primero BLOCK, @program tiene que ser utilizado en su lugar.

  2. Rakudo parece tener un cochecito Rat dar resultados incorrectos. Niecza actual ejecuta todos los programas de prueba correctamente y rápidamente, incluyendo la fracción "prima".

Haskell, 142 caracteres

Sin ninguna bibliotecas adicionales y I completo / O. 

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

Creo que todo el mundo sabe que Java no tendría la aplicación más corto, pero quería ver cómo se compararía. Resuelve los ejemplos triviales, pero no el bono único.

Esta es la versión 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 

15625

java -cp. F 1,296 3 2 

6561

Esta es la versión limpia-up: 

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

Mi primer intento, al hacer esto con R completamente estándar 5 RS Esquema, se situó en 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))))))

Correr contra algunos artículos en el vector de prueba: 

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

Si se estima que λ está obligado a lambda y se define let/cc (como lo son en el Esquema PLT; véase más adelante para las definiciones para la ejecución de este en los Esquemas que no definen aquellos), entonces se puede adaptar Jordan's segunda solución Rubí al Esquema, que sale a 73 caracteres (tenga en cuenta que el orden de los argumentos es el reverso de mi primera solución, pero lo mismo que Jordan, en esta versión, que salva un carácter):. 

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

Si no tengo λ y let/cc predefinido, entonces éste está en el puesto 111 caracteres (88 si se define la abreviatura call/cc bastante común): 

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

Definiciones de λ y let/cc: 

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

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

Un poco tarde ... dc 84 caracteres

Sólo por diversión una solución dc (OpenBSD) 

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

Maneja todos los casos: 

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

No puedo dejar comentarios todavía, pero aquí es una versión "ligeramente" más corto de C # versión de RCIX (creo que es de 7 caracteres más cortos) 

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 utiliza 

Func<string,decimal> d=Convert.ToDecimal

y llamadas d(); en lugar de 

using b=Convert;

y llamar repetidamente b.ToDecimal();.

También se han quitado un par innecesario de llaves de todo el else para ganar 1 carácter:.)

I también se sustituye el a[i+1] con a[++i] y en el siguiente cuerpo más Substituí i+=2 con i++ para ganar otro Char: P

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top