Golf Code: Thracran

Question

A task

Write a program that acts as a Fractran interpreter. The winner is the shortest interpreter in terms of the number of characters in any language. Your program must accept two inputs: the fractant program to be executed, and the integer n. The program can be in any form convenient for your program - for example, a list of 2 tuples or a flat list. The output must be a single integer that is the value of the register at the end of execution.

Fractran

Fractran is a trivial esoteric language invented by John Conway . The fractant program consists of a list of positive fractions and an initial state n. The interpreter maintains a program counter that initially indicates the first fraction in the list. Fractran programs run as follows:

• Check if the product of the current state and the fraction currently under the software counter is an integer. If so, multiply the current state by the current fraction and reset the program counter to the beginning of the list.
• Advance the program counter. If the end of the list is reached, stop; otherwise, return to step 1.

For more on how and why Fractran works, see the esolang entry and this entry for good math / bad math.

Test vectors

Program: [(3, 2)]
Entrance: 72 (2 ³ 3 ² )
Output: 243 (3 ⁵ )

Program: [(3, 2)]
Entrance: 1296 (2 ⁴ 3 ⁴ )
Output: 6561 (3 ⁸ )

Program: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)] <> Input: 72 (2 ³ 3 ² )
Output: 15625 (5 ⁶ )

Bonus Test Vector:

Your message does not have to execute this last program correctly in order to be an acceptable response. But it is true, if so!

Program: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)] <> Input: 60466176 (2 ¹⁰ 3 ¹⁰ )
Output: 7888609052210118054117285652827862296732064351090230047702789306640625 (5 ¹⁰⁰ )

Views and scoring

Programs occupy strictly the length in characters - the shortest is the best. Feel free to present both a beautifully laid out, and a documented and "minified" version of your code so people can see what is happening.

The language 'J' is not valid. This is because the already known solution in J is on one of the linked pages. If you're a J fan, sorry!

As an added bonus, however, anyone who can provide a working fractran translator in fractran will receive a bonus of 500 points. In the unlikely case of multiple translators for self-hosting, each with the shortest number of fractions will receive a reward.

Winners

The official winner, after submitting a self-organizing decision of a fractant containing 1779 fractions, is the decision of Jesse Beder . Practically speaking, the solution is too slow to execute even 1 + 1, however.

Incredibly, since then it has been beaten up by another fractran solution - Amadaeus solution in just 84 fractions! It is able to run the first two test cases in a few seconds while working on my original Python solution. He uses a new coding method for fractions, which also deserves close attention.

Honorable mentions:

• Stephen Canon solution , in 165 x86 build characters (28 bytes of machine code)
• Jordanian solution in 52 ruby ​​characters - which processes long integers
• A useless 87-character Python solution , which, although not the shortest Python solution, is one of the few solutions that are not recursive and therefore more complex programs with ease. It is also very readable.

Answer 1

Fractran - 1779 fractions

(Edit: fixed)

(I hope people still follow this topic because it took some time!)

It looks like SO won't let me post anything until this is, so I posted the Fractran source here .

The input is defined as follows:

First, we encode the fraction m/n = p_0^a0... p_k^ak :

• Start with 1. Then for each ai :
• Multiply by p_2i^ai if ai > 0
• Multiply by p_2i+1^{-ai} if a_i < 0

Thus, we encode any fraction as a positive integer. Now, given the program (sequence of encoded fractions F0, F1, ...), we encode that

 p_0^F0 p1^F1 ... 

Finally, input to the interpreter is specified:

 2^(program) 3^(input) 5 

where program and input encoded as above. For example, in the first test task 3/2 gets the encoding up to 15 , so the program gets the encoding up to 2^15 ; and 108 gets encoding up to 500 . So we go through

 2^{2^15} 3^500 5 

for the program. The output signal then has the form

 2^(program) 3^(output) 

so in the first example it will be

 2^{2^15} 3^3125 

---

How it works?

I wrote a metalanguage that compiles into Fractran. It allows you to use functions (simple Fractran and sequences of other functions) and a while and if while (for convenience!). The code for this can be found here .

If you want to compile this code to Fractran itself, my program (C ++) can be found here [tar.gz]. In a terrific dogfooding show (and showing off) I used my C ++ YAML yaml-cpp parser, so you will need to download and install a link with that. For iaml-cpp and the “compiler”, you will need CMake to generate a cross-platform makefile.

Using this program:

 ./fracc interpreter.frp 

It reads the function name from standard input and writes the corresponding "pseudo-fraction" (I will explain that per second) to standard output. So, to compile the interpreter (Interpret function), you can run

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

The output ("pseudo-Fractran") will be a sequence of strings, each of which contains a string of numbers separated by spaces. The string corresponds to the fraction: if the nth character in the string an , then the fraction is the product of p_n^an .

It is very easy to convert this to Fractran, but if you are lazy, you can use to-fractions.py . [ Note : I used to have a C ++ program, and I casually ignored integer overflow. I translated it into Python to avoid this.]

Input note : if you want to test another function this way, the convention will always be the same. It has a number of parameters (as a rule, the comment above the function explains this) in the pseudo-fractal, so give it what it wants, plus 1 in the very next slot (so, in the usual Fractran, we multiply once by the first right one that it will not be used ) This is the “signal” bit to trigger the function.

---

However

I do not recommend actually trying to run the Fractran interpreter (alas). I tested many of its components and, for example, the IncrementPrimes function, which takes a pair of primes and returns the next two primes, takes about 8 minutes using my silly C ++ interpreter (no need to publish this :). Plus, it is (at least) quadratic in the number of function calls - doubling the number of function calls makes it take at least four times (more if there are while or if loops). Therefore, I assume that starting the interpreter will take at least several days, if not years: (

So how do I know this works? Well, of course, I'm not 100% sure, but I'm pretty close. First of all, I tested many, many of its components, and, in particular, very carefully tested all elements of the metalanguage (function sequences and if and while ).

In addition, the metalanguage is easy to translate into your favorite language and even easier to translate to C ++, since all function parameters are passed by reference. If you feel lazy again, you can download my translation here [tar.gz] (there is no makefile, these are just two .cpp files, so a direct call to gcc is fine).

So, you can compare the two interpreters, run the C ++ version (it also accepts I / O in pseudo-Fractran), check that this works, and then convince yourself that the metalanguage also works.

---

Or!

If you feel inspired and really want the interpreted interpreter to be interpreted, you can write a "smart" Fractran interpreter based on the type of Fractran output received. The output is very structured - function sequences are implemented using signals, so if you somehow cache where the interpreter was, you can jump right there if nothing important has changed. This, I think, will dramatically speed up the program (possibly, reduce the execution time by one or more privileges).

But I'm not quite sure how to do this, and I'm happy with what I did, so I will leave this as an exercise for the reader.

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] 

It is written entirely by hand. I made a pseudo-language to be able to express things more clearly, but I did not write a compiler and decided to write optimized Fractran code directly.

FTEVAL accepts the input 3^initial_state * 5^encoded_program * 199 , produces intermediate results 3^interpreted_program_state * 199 and completely stops at a number divisible by 233 .

The interpreted program is embedded in the list of ten-digit base digits within the same base number 11, using the number "a" to mark the border, except at the very end. The add-on program [3/2] is encoded as

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

The multiplication program [455/33, 11/13, 1/11, 3/7, 11/2, 1/3] is encoded as

 int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657 

which is a really big number.

The first test vector, completed in less than one second , gave the desired result after 4545 iterations and stopped after 6172 iterations. Here is the full conclusion .

Unfortunately, the sage interrupted when I tried the second test vector (but I think that it will work when implementing Nick using simple exponent vectors).

The space here is too small to explain. But here is my pseudo code. Hopefully I will write my process in a couple of days.

 # Notations: # %p # designates the exponent of prime factor p that divides the # current state. # mov xy # 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 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 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 assembly , 165 characters (28 bytes of machine code).

The state is passed in% rdi, the program (a pointer to an array with zero termination of fractions) is in% rsi. The results are returned in% rax for the usual C-style calling conventions. Using non-standard calling conventions or Intel syntax (this is AT & T syntax) will cause a few more characters to drop, but I'm lazy; someone else can do it. A team or two can almost certainly be saved by reconfiguring the control flow, if anyone wants to do this, feel free to.

Intermediate calculations (state numerator *) can have a width of up to 128 bits, but only the 64-bit state is supported.

 _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 

Remove comments, extraneous spaces and _fractran shortcut for minimized version.

Answer 4

Ruby 58 57 56 53 52 characters

This is my first ever golf game, so please be careful.

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

Using:

 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 

Pretty 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

Inspired by gnibbler solution I was able to get a solution using Rational before 53 52 characters. Another longer than the (less elegant) solution above.

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

Using:

 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) 

(A to_i call for more beautiful output will add 5 more characters.)

Answer 5

Golfscript - 32

    
     {: ^ {1 = 1 $ \%!} ?. 1 = {~ @ \ / * ^ f} {} if}: 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

Answer 6

Haskell , 102 characters

 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 with relaxed restrictions on the input / output format.

 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

Answer 7

C , 159 153 151 131 111 110 characters

 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 fc
 $ 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

Answer 8

Python, 83 82 81 72 70 characters.

It is convenient to have an entrance as fractions. Fractional objects. Same idea as in 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 

Answer 9

Python - 53

Improvement thanks to Paul

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

testcases

 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 Without using a fraction

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

Python - 55

This is somewhat theoretical. The first two cases work fine, but the other two do not work with recursion depth. Maybe someone can make it work with a generator expression

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

There is one possibility, but it grows to 65, even without import

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

Answer 10

F #: 80 characters

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

Here's an extended version using match pattern with |cases instead of 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 

Test code:

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

And the result (tested in F # interactive):

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

Edit , let's have some more dinner with this and calculate some prime numbers (see the related page in the start message). I wrote a new function g , which gives intermediate state values.

 //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 gp (x,pp) = seq { match x,pp with |x,(e,d)::t -> yield x yield! gp (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 

Gets a whopping 4.7 seconds to cough the first 10 primes:

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

This is without a doubt the most bizarre and slowest prime number generator I've ever written. I'm not sure if this is good or bad.

Answer 11

Python 110 103 95 87 characters

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

(shows how to manage it)

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

Answer 12

FROM#

Typical Version:

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

Cut a version weighing 201 characters (without namespace declarations or any of them, only one using statement (not a system) and the main function):

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

Examples (input is through command line arguments):

 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 

Answer 13

Javascript one: 99 characters . No bonus vector: (

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

The input signal is in the format [[a,b],[c,d]] . I took advantage of Javascript: instead of doing var x=0, y=0; you can add as many parameters as you want. It doesn't matter if you really pass them or not, as they are null by default.

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

Answer 14

Groovy , 136 117 107 characters.

Call as groovy fractal.groovy [input state] [program vector as a list of numbers]

 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 

Example

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

Answer 15

Perl, 84 82 char

Uses standard input.

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

Accepts 100 characters to pass the bonus test:

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

Answer 16

Lua:

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

Compact code weighing 98 characters (the abbreviation suggested by Scoregraphic in my other answer, and more is suggested by 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) 

Run from the command line, first specifying the base number, and then a series of fractions represented as numbers with space division, for example:

 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 

(I manually typed some of them because it is a pain to get material from the command line, although this is the results returned)

DOES NOT process the bonus vector: (

Answer 17

Perl 6: 77 Characters (Experimental)

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

A new line is optional. Call:

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

Readable Version:

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

Notes:

• Colon notation first @program: pointy-sub does not work with current implementations; first use BLOCK, @program.

• Rakudo seems to have Rat buggies giving incorrect results. The current Niecza launches all test programs correctly and quickly, including the "bonus" fraction.

Answer 18

Pattern: 326

I thought that to present parity, a representation of the Scheme was required. I also just wanted to play with him. (Sorry for your rudimentary knowledge, I am sure that this can be optimized, and I am open to 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))))) 

Tests:

(fractran_interpreter 108 0 '(3/2))

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

I get a bonus vector! (using Dr. Scheme, allocating 256 mb)

Answer 19

Haskell: 116 109 characters

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

It turned out to be a bit of a fake entrance to Dario.

Answer 20

Implementing Links in Python

This implementation works on simple factorizations.

First, it decodes the alternating tuple list, coding the numerator and denominator as a list of tuples (idx, value), where idx is the number of primes (2 is just 0, 3 is prime 1, and therefore e).

The current state is a list of indicators for each number, by index. The execution of the command requires first iterating over the denominator, checking whether the indexed state element is at least a given value, then, if it matches, reduces the state elements specified in the denominator and increases them indicated in the numerator.

This approach is about 5 times faster than performing arithmetic operations on large integers in Python and is much easier to debug!

Further optimization is ensured by constructing an array that compares each simple index (variable) with the first one when it is checked in the denominator of the fractional part, and then using this to build a "jump_map" consisting of the following instructions to execute for each command in the program.

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

Answer 21

Haskell, 142

- -.

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

Answer 22

Java, 200 192 179

, , Java , , . , .

:

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

java -cp. F 108 455 33 11 13 1 11 3 7 11 2 1 3

 15625 

java -cp. F 1296 3 2

 6561 

:

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

Answer 23

73

, RS ⁵ RS, 104 :

(define(fpn)(let l((qp)(nn))(if(null? q)n(let((a(* n(car q))))(if(integer?
a)(lpa)(l(cdr q)n))))))

:

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

, λ lambda let/cc ( PLT, . , ), Ruby , 73 ( , , , Jordan; , ).:

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

λ let/cc , 111 (88, call/cc ):

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

λ let/cc :

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

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

Answer 24

... dc 84 chars

a dc solution (OpenBSD)

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

:

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

Answer 25

I can’t leave comments, but here is a “slightly” shorter version of the RCIX C # version (I believe 7 characters are shorter)

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

which uses

 Func<string,decimal> d=Convert.ToDecimal 

and causes d(); instead

 using b=Convert; 

and re-calling b.ToDecimal(); .

I also removed the unnecessary pair of curly braces around the else statement to get 1 char :).

I also replaced a[i+1]with a[++i], and in the next package I replaced i+=2with i++to get another char: P