Fractran: 84 fractions

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]

ceci est écrit entièrement à la main. J'ai créé un pseudo langage pour pouvoir exprimer les choses plus clairement, mais je n'ai pas écrit de compilateur et j'ai choisi d'écrire directement du code Fractran optimisé.

FTEVAL prend entrée 3^initial_state * 5^encoded_program * 199 , produit des résultats intermédiaires 3^interpreted_program_state * 199 , et s'arrête complètement à un nombre divisible par 233 .

Le programme interprété est consultez une liste de base de 10 chiffres à l'intérieur d'une seule base 11 nombre, en utilisant le chiffre "un" pour marquer la limite, sauf à la fin. Le programme d'addition [3/2] est codé comme

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

le programme de multiplication[455/33, 11/13, 1/11, 3/7, 11/2, 1/3] est codé comme

int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657

qui est un nombre vraiment grand.

le premier vecteur d'essai terminé en moins d'une seconde , produit le résultat souhaité après 4545 itérations et arrêté après 6172 itérations. Voici la sortie complète .

malheureusement, sage a sauté lorsque j'ai essayé le second vecteur de test (mais je pense qu'il fonctionnera sous L'implémentation de Nick en utilisant des vecteurs premier exposant).

l'espace ici est vraiment trop petit pour tout expliquer. Mais ici, c'est mon pseudo. J'écrirai ma procédure dans quelques jours, j'espère.

# 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ée , 165 caractères (28 octets de code machine).

est passé en %rdi, le programme (pointeur vers le tableau des fractions à fin nulle) est en %rsi. Les résultats sont retournés en % rax selon les conventions habituelles D'appel de style C. Utiliser des conventions d'appel non standard ou la syntaxe Intel (c'est la syntaxe AT&T) ferait tomber quelques caractères supplémentaires, mais je suis paresseux; quelqu'un d'autre peut le faire. Une ou deux instructions peuvent presque certainement être sauvées ré-organiser le contrôle de flux, si quelqu'un veut le faire, n'hésitez pas.

les calculs intermédiaires (état*numérateur) peuvent avoir jusqu'à 128 bits de large, mais seul l'état 64 bits est supporté.

_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     ,    %rcx    // otherwise, advance to next instruction
    jmp     1b
9:  mov     %rdi,   %rax    // copy result for return
    ret

supprimer les commentaires, les espaces vides et l'étiquette verbeuse _fractran pour la version minimisée.

Ruby, 58 57 56 53 52 les caractères

c'est ma toute première entrée de golf de code, donc s'il vous plaît être doux.

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

Utilisation:

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

Jolie version (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 using Rational

inspiré par gnibbler la solution j'ai été en mesure d'obtenir une solution Rationnelle à 53 52 caractères. toujours un de plus que la solution (moins élégante) ci-dessus.

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

Utilisation:

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)

(un to_i appel pour une sortie plus jolie ajouterait 5 caractères supplémentaires.)

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 caractères

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 avec des restrictions assouplies sur le format d'entrée/sortie.

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 des personnages.

il est commode d'avoir entrée comme fractions.Les objets de Fraction. Même idée que dans Ruby solution.

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 les caractères

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

amélioration grâce à Paul

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

cas de tests

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 sans Fraction

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

Python-55

celui-ci est quelque peu théorique. Les deux premiers cas fonctionnent bien, mais les deux autres échouent à la profondeur de récursion. Peut-être que quelqu'un peut le faire fonctionner avec un expression de la génératrice

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

Voici une possibilité, mais augmente à 65 même sans inclure l'importation

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 caractères

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

Voici une version augmentée en utilisant match pattern with |cases au lieu 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   

code D'essai:

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

et résultat (testé en F# interactive):

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

Modifier let's amuser un peu plus avec cela, et de calculer des nombres premiers (voir page liée dans le poste de départ). J'ai écrit une nouvelle fonction g qui donne les valeurs intermédiaires de l'état.

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

met 4,7 secondes à cracher les 10 premiers nombres premiers:

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

c'est, sans aucun doute, le générateur de nombres premiers le plus bizarre et le plus lent que j'ai jamais écrit. Je ne sais pas si c'est une bonne ou une mauvaise chose.

Javascript: 99 caractères . Pas de vecteur bonus: (

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

est dans le format [[a,b],[c,d]] . J'ai profité de la clémence de Javascript: au lieu de faire var x=0, y=0; , vous pouvez ajouter autant de paramètres que vous le souhaitez. Peu importe que vous les passiez ou non, puisqu'ils sont par défaut à null .

Jolie version:

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 les caractères

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

(montre comment le conduire)

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

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

version réduite pesant en 201 chars (sans les déclarations d'espace de noms ou tout autre, juste la seule déclaration d'utilisation (pas de système) et la fonction principale):

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

Exemples (l'entrée est à travers des arguments de ligne de commande):

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 des personnages.

Appelez-moi groovy fractal.groovy [état] [programme de vecteur de la liste des numéros]

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

échantillon

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

Perl, 84 82 char

utilise une entrée standard.

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

prend 110 chars pour passer le test bonus:

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

Haskell: 116 109 caractères

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}

cela a fini par être un peu une réplique de l'entrée de Dario.

Schéma: 326

j'ai pensé qu'une soumission de schéma était nécessaire, pour la parité. Je voulais aussi l'excuse pour jouer avec. (Excusez mes connaissances rudimentaires, je suis sûr que cela pourrait être optimisé, et je suis ouvert aux suggestions!)

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

Essais:

(fractran_interpreter 108 0 '(3/2))

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

j'ai le vecteur bonus! (en utilisant le Dr Scheme, l'allocation de 256 mo)

Lua:

en ordre de code:

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)

code Compact pesant à 98 caractères (réduction suggérée par Scorgraphic sur mon autre réponse, et plus suggérée par 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)

exécuter à partir de la ligne de commande, en fournissant le numéro de base d'abord puis la série de fractions présentées comme des nombres avec séparation de l'espace, comme suit:

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

(tapé manuellement une partie de celui-ci dans Parce que c'est une douleur pour obtenir des choses hors de la ligne de commande, bien que ce soit les résultats retournés)

ne gère pas le vecteur bonus tristement: (

implémentation de référence en Python

cette implémentation fonctionne sur des factorisations de premier ordre.

tout d'abord, il décode une liste de tuples de fraction en encodant le numérateur et le dénominateur comme une liste de tuples (idx, valeur), où idx est le nombre du premier (2 est le PREMIER 0, 3 est le premier 1, et ainsi de suite).

l'état actuel est une liste d'exposants pour chaque prime, par index. L'exécution d'une instruction nécessite d'abord de itérer sur le dénominateur, vérifier si l'élément d'état indexé est au moins la valeur spécifiée, puis, s'il correspond, décrémenter les éléments d'état spécifiés dans le dénominateur, et augmenter ceux spécifiés dans le numérateur.

cette approche est environ 5 fois la vitesse de faire des opérations arithmétiques sur les grands entiers en Python, et est beaucoup plus facile à déboguer!

une autre optimisation est fournie par la construction d'un réseau cartographiant chaque prime index (variable) pour la première fois, il est vérifié dans le dénominateur d'une fraction, puis l'utilise pour construire un "jump_map', composé de la prochaine instruction à exécuter pour chaque instruction du programme.

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 Caractères (expérimental)

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

retour à la ligne est facultative. Appel:

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

version lisible:

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

Notes:

1. la notation first @program: pointy-sub ne fonctionne pas sur les implémentations actuelles; le premier bloc @doit être utilisé à la place.

2. Rakudo semble avoir un buggy Rat donnant des résultats incorrects. Niecza actuel exécute tous les programmes de test correctement et rapidement, y compris la fraction "bonus".

Haskell, 142 caractères

sans bibliothèques supplémentaires et complet I/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 caractères

je pense que tout le monde sait que Java n'aurait pas l'implémentation la plus courte, mais je voulais voir comment cela se comparerait. Il résout les exemples triviaux,mais pas le bonus.

Voici la version minimisée:

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 1296 3 2

6561

Voici la version nettoyée:

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

schéma 73 caractères

ma première tentative, à faire cela avec tout à fait standard R ⁵ RS Scheme, est venu à 104 caractères:

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

courant contre quelques éléments du vecteur d'essai:

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

si vous supposez que λ est lié à lambda et let/cc est défini (comme ils sont dans le schéma PLT; voir ci-dessous pour les définitions pour exécuter ceci dans les schémas qui ne définissent pas ces), Alors je peux adapter la deuxième solution de Ruby de Jordan à Scheme, qui sort à 73 caractères (notez que l'ordre d'argument est l'inverse de ma première solution, mais le même que de Jordan; dans cette version, qui sauve un caractère).:

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

si je n'ai pas λ et let/cc prédéfinis, alors celui-ci vient à 111 caractères (88 si le assez commun call/cc abréviation est définie):

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

Définitions de λ et 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 peu en retard... dc 84 caractères

Juste pour le plaisir d'un dc solution (OpenBSD)

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

Il gère tous les cas:

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

Je ne peux pas encore laisser de commentaires Mais voici une version" légèrement "plus courte de la version C# de RCIX (je crois que c'est 7 caractères plus court)

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

qui utilise

Func<string,decimal> d=Convert.ToDecimal

et appelle d(); au lieu de

using b=Convert;

et appelant à plusieurs reprises b.ToDecimal(); .

j'ai aussi enlevé une paire inutile de lacets bouclés autour de l'énoncé else pour gagner 1 char :).

j'ai également remplacé le a[i+1] par a[++i] et dans le corps suivant j'ai remplacé i+=2 par i++ pour obtenir un autre char :p