Alex Rivera | Logout

Code Golf: Fractran

Asked 2009-11-17T16:06:48.380
49

The Challenge

Write a program that acts as a Fractran interpreter. The shortest interpreter by character count, in any language, is the winner. Your program must take two inputs: The fractran program to be executed, and the input integer n. The program may be in any form that is convenient for your program - for example, a list of 2-tuples, or a flat list. The output must be a single integer, being the value of the register at the end of execution.

Fractran

Fractran is a trivial esoteric language invented by John Conway. A fractran program consists of a list of positive fractions and an initial state n. The interpreter maintains a program counter, initially pointing to the first fraction in the list. Fractran programs are executed in the following fashion:

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

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

Test Vectors

Program: [(3, 2)]
Input: 72 (2332)
Output: 243 (35)

Program: [(3, 2)]
Input: 1296 (2434)
Output: 6561 (38)

Program:

code-golf esoteric-languages
Edit
Report

4 Answers

5

F#: 80 chars

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

Here's an expanded 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 result (tested in F# interactive):

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

Edit let's have some more fun with this, and calculate some primes (see linked page in the starting post). I've written a new function g that yields the intermediate values of the state.

//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)
    |
answered 2009-11-18T15:06:16.627
2

Perl, 84 82 char

Uses standard input.

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

Takes 110 chars to pass the bonus test:

use Math'BigInt blcm;@P=<>=~/\d+/g;$_=blcm<>;
($%,$=)=@P[$i++,$i++],$_*$%%$=or$i=0,($_*=$%)/=$=while$i<@P;print
answered 2009-11-17T17:29:05.550
2

Scheme: 326

I thought a Scheme submission was needed, for parity. I also just wanted the excuse to play with it. (Excuse my rudimentary knowledge, I'm sure this could 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 the bonus vector! (using Dr. Scheme, allocating 256 mb)

answered 2009-11-18T09:22:47.740
2

Reference implementation in Python

This implementation operates on prime factorizations.

First, it decodes a list of fraction tuples by encoding the numerator and denominator as a list of (idx, value) tuples, where idx is the number of the prime (2 is prime 0, 3 is prime 1, and so forth).

The current state is a list of exponents for each prime, by index. Executing an instruction requires first iterating over the denominator, checking if the indexed state element is at least the specified value, then, if it matches, decrementing state elements specified in the denominator, and incrementing those specified in the numerator.

This approach is about 5 times the speed of doing arithmetic operations on large integers in Python, and is a lot easier to debug!

A further optimisation is provided by constructing an array mapping each prime index (variable) to the first time it is checked for in the denominator of a fraction, then using that to construct a 'jump_map', consisting of the next instruction to execute for each instruction 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
answered 2009-11-22T22:33:27.147

Your Answer