Code Golf: Fractran

Question

Le Défi

Écrire un programme qui agit comme un Fractran interprète. Le plus court interprète en nombre de caractères, dans n'importe quelle langue, est le gagnant. Votre programme doit prendre deux entrées: L'fractran programme d'être exécuté, et la saisie de l'entier n. Le programme peut être dans n'importe quelle forme qui est pratique pour votre programme - par exemple, une liste de 2-tuples, ou une liste à plat. La sortie doit être un entier, soit la valeur du registre à la fin de l'exécution.

Fractran

Fractran est trivial ésotérique langage inventé par John Conway. Un fractran programme consiste en une liste de fractions positives et de l'état initial n. L'interprète maintient un compteur de programme, initialement pointant vers la première fraction dans la liste. Fractran programmes sont exécutés de la manière suivante:

1. Vérifier si le produit de l'état actuel et de la fraction actuellement sous le compteur de programme est un entier. Si elle est, il faut multiplier le courant de l'état par le courant de la fraction et de réinitialiser le compteur de programme pour le début de la liste.
2. L'avance le compteur de programme. Si la fin de la liste est atteinte, arrêter la, sinon retourner à l'étape 1.

Pour plus de détails sur le comment et le pourquoi Fractran, reportez-vous à la esolang entrée et cette entrée sur maths bon/mauvais en mathématiques.

Vecteurs De Test

Programme: [(3, 2)]
Entrée: 72 (2³3²)
Sortie: 243 (3^{de 5})

Programme: [(3, 2)]
Entrée: 1296 (2⁴3⁴)
Sortie: 6561 (3⁸)

Programme: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
Entrée: 72 (2³3²)
Sortie: 15625 (5⁶)

Bonus vecteur de test:

Votre présentation n'a pas besoin d'exécuter cette dernière correctement le programme pour être une réponse acceptable. Mais bravo si c'est le cas!

Programme: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
Entrée: 60466176 (2¹⁰3¹⁰)
Sortie: 7888609052210118054117285652827862296732064351090230047702789306640625 (5¹⁰⁰)

Soumissions Et De Notation

Les programmes sont classés uniquement par la longueur en caractères plus courte est la meilleure. N'hésitez pas à présenter à la fois un joliment présentés et documentés et une "compacte" version de votre code, afin que les gens peuvent voir ce qui se passe.

La langue " J " n'est pas recevable. C'est parce qu'il y a déjà une solution bien connue en J sur l'une des pages liées. Si vous êtes un J-ventilateur, désolé!

Comme un bonus supplémentaire, cependant, toute personne qui peut fournir un travail fractran interprète dans fractran recevrez un 500 réputation de point de bonus. Dans le cas peu probable de plusieurs auto-hébergement, les interprètes, l'un avec le plus petit nombre de fractions de recevoir la prime.

Les gagnants

L'officiel vainqueur, après avoir déposé une auto-hébergement fractran solution comprenant 1779 fractions, est Jesse Beder de la solution. Pratiquement parlant, la solution est trop lent à exécuter, même 1+1, cependant.

Incroyablement, cela a depuis été battu par un autre fractran solution - Amadaeus la solution de seulement 84 fractions! Il est capable d'exécuter les deux premiers cas de test dans une affaire de secondes lors de l'exécution sur ma référence Python solution. Il utilise une nouvelle méthode de codage pour les fractions, ce qui est également intéressant d'examiner de près.

Mentions honorables:

• Stephen Canon de la solution, en 165 caractères de x86 assemblée (28 octets de code machine)
• La jordanie solution dans 52 caractères de rubis qui manipule des entiers longs
• Inutile de solution dans 87 caractères de Python, qui, bien que pas le plus court Python solution, est l'une des rares solutions qui n'est pas récursive, et donc des poignées plus difficile de programmes avec facilité. Il est également très lisible.

Answer 1

Fractran - 1779 fractions

(Edit: fixe)

(J'espère que les gens sont toujours en suivant ce fil, car cela a pris du temps!)

Il apparaît DONC ne me permet pas de poster quelque chose tant que cela, donc je l'ai posté le Fractran source ici.

L'entrée est spécifié comme suit:

Tout d'abord, nous coder une fraction m/n = p_0^a0... p_k^ak par:

• Commencez avec 1. Ensuite, pour chaque ai:
• Multiplier par p_2i^ai si ai > 0
• Multiplier par p_2i+1^{-ai} si a_i < 0

De cette façon, nous codent pour aucune fraction sous la forme d'un entier positif. Maintenant, étant donné un progoram (séquence codée fractions F0, F1, ...), on encode que par

p_0^F0 p1^F1 ...

Enfin, les commentaires de l'interprète est donnée par:

2^(program) 3^(input) 5

où program et input sont codés comme ci-dessus. Par exemple, dans le premier essai de problème, 3/2 encodés à l' 15, de sorte que le programme est codé à l' 2^15; 108 encodés à l' 500. Donc, nous passons

2^{2^15} 3^500 5

pour le programme. La sortie est de la forme

2^(program) 3^(output)

ainsi, dans le premier exemple, il va être

2^{2^15} 3^3125

---

Comment ça fonctionne?

J'ai écrit un méta-langage qui se compile en bas à Fractran. Il permet aux fonctions (simple Fractran et les séquences des autres fonctions), et un while boucle et if déclaration (pour plus de commodité!). Le code qui peut être trouvé ici.

Si vous voulez compiler le code en bas à Fractran vous-même, mon (C++) le programme peut être trouvé ici [tar.gz]. Dans un superbe écran de dogfooding (et montrer), j'ai utilisé mon C++ YAML analyseur yaml-rpc, de sorte que vous aurez à télécharger et le lien avec. Pour les deux yaml-rpc et le "compilateur", vous aurez besoin de CMake pour la croix-plate-forme de génération de makefile.

L'utilisation de ce programme est:

./fracc interpreter.frp

La il lit le nom d'une fonction à partir de l'entrée standard et écrit le correspondant de "pseudo-Fraction" (je vais l'expliquer dans une seconde) sur la sortie standard. Afin de compiler l'interprète (l'interprète de la fonction), vous pouvez exécuter

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

La sortie ("pseudo-Fractran") sera une séquence de lignes, chacune avec une chaîne séparée par des espaces chiffres. Une ligne correspond à une fraction: si l' nème chiffre de la ligne est - an, alors la fraction est le produit de l' p_n^an.

Il est très facile de convertir cette Fractran, mais si vous êtes paresseux, vous pouvez utiliser to-fractions.py. [Note: auparavant, j'avais un programme C++, et j'avais négligemment ignoré débordement d'entier. Je l'ai traduit pour Python pour éviter cela.]

Remarque à propos de l'entrée: si vous voulez tester une autre fonction de cette manière, la convention est toujours le même. Il a un certain nombre de paramètres (généralement le commentaire ci-dessus la fonction explique cela) en pseudo-Fractran, afin de lui donner ce qu'il veut, en plus d'un 1 sur le prochain emplacement (si ordinaire Fractran, multiplier une fois par le premier le premier qu'il n'est pas utilisé). C'est un "signal" bits de la fonction de fréquenter.

---

Cependant,

Je ne recommande pas réellement d'essayer d'exécuter la Fractran interprète (hélas). J'ai testé plusieurs de ses composants, et, par exemple, la fonction IncrementPrimes, qui prend une paire de nombres premiers et renvoie les deux premiers, prend environ 8 minutes pour exécuter, à l'aide de mon idiot C++ interprète (pas besoin de post :). De Plus, il va (au moins) quadratiquement dans le nombre d'appels de fonction, soit le double du nombre d'appels de fonction fait au moins quatre fois plus long (et plus si il y a while boucles ou if des déclarations). Donc je suppose que l'exécution de l'interprète va prendre au moins jours, si pas des années :(

Alors, comment puis-je savoir que cela fonctionne? Eh bien, bien sûr, je ne suis pas certaine à 100%, mais je suis assez proche. Tout d'abord, j'ai testé beaucoup, beaucoup de ses composants, et en particulier, j'ai testé tous les éléments du méta-langage (séquences de fonctions et d' if et while des déclarations) très soigneusement.

Aussi, le méta-langage est facile à traduire dans votre langue préférée, et encore plus facile à traduire en C++, puisque tous les paramètres des fonctions sont passés par référence. Si vous êtes paresseux, vous pouvez télécharger ma traduction ici [tar.gz] (il n'y a pas de makefile, c'est juste deux .fichiers cpp, de sorte que la possibilité d'appeler directement gcc est très bien).

De sorte que vous pouvez comparer les deux interprètes, exécutez la version C++ (il prend également en entrée/sortie pseudo-Fractran), vérifier que ça fonctionne, et puis vous convaincre que le méta-langage fonctionne aussi.

---

Ou!

Si vous vous sentez inspiré, et vraiment envie de voir cet interprète interprété, vous pouvez écrire un "sage" Fractran interprète basé autour du type de Fractran de sortie que nous recevons. La sortie est très structuré, des séquences de fonctions sont mises en œuvre à l'aide des signaux, donc si vous en quelque sorte de cache où l'interprète a été, vous pouvez sauter immédiatement si rien d'important n'a changé. C'est, je pense, serait d'accélérer considérablement le programme (peut-être la coupe de temps en cours d'exécution par un ou plusieurs pouvoirs).

Mais, je ne suis pas vraiment sûr de savoir comment le faire, et je suis heureux avec ce qui est fait, donc je vais le laisser comme un exercice pour le lecteur.

Answer 2

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]

C'est écrit entièrement à la main. J'ai fait une pseudo-langue pour être en mesure d'exprimer les choses plus clairement, mais je n'ai pas écrit un compilateur et a choisi d'écrire optimisé Fractran code directement.

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

Le programme interprété est embeded comme 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. L'ajout du programme [3/2] est codée en tant que

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

La multiplication programme [455/33, 11/13, 1/11, 3/7, 11/2, 1/3] est codée en tant que

int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657

ce qui est vraiment un grand nombre.

Le premier vecteur de test fini en moins d'une seconde, produit le résultat souhaité après 4545 itérations et s'est arrêté après l'6172 itérations. Ici est la production complète.

Malheureusement, la sauge segfaulted quand j'ai essayé le deuxième vecteur de test (mais je pense que ça va marcher en vertu de Nick mise en œuvre à l'aide de premier exposant de vecteurs).

L'espace ici est vraiment trop petite pour tout expliquer. Mais ici, c'est mon pseudo. Je vais écrire mes processus dans une couple de jours, je l'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 }
}

Answer 3

x86_64 assemblée, 165 caractères (28 octets de code machine).

L'état est passé en %de l'aqr, Programme (pointeur à null tableau de fractions) est en %rsi. Les résultats sont renvoyés en %rax par l'habituel style C conventions d'appel. L'aide non-standard des conventions d'appel ou Intel syntaxe (c'est AT&T syntaxe) baisserait un peu plus de caractères, mais je suis paresseux; quelqu'un d'autre peut le faire. Une instruction ou deux peut presque certainement être sauvé par une réorganisation du flux de contrôle, si quelqu'un veut le faire, n'hésitez pas.

Calculs intermédiaires (état*numérateur) peut être jusqu'à 128 bits de large, mais seulement 64 bits de l'état est pris en charge.

_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

Supprimer les commentaires, étrangères espaces, et les verbose étiquette _fractran pour la version réduite.

Answer 4

Ruby, 58 57 56 53 52 caractères

C'est mon tout premier code de golf de l'entrée, de sorte 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 utilisation Rationnelle

Inspiré par gnibbler la solution , j'ai été en mesure d'obtenir une solution à l'aide de Rational bas à 53 52 caractères. Encore un de plus que l' (moins élégant) la solution 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)

( to_i Appelez pour plus jolie sortie serait ajouter plus de 5 caractères.)

Answer 5

Golfscript - 32

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

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