Convert Fractran into Brainfuck

Background

Fractran is an esoteric Turing-complete programming language invented by John Conway. A Fractran program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.

The reason that Fractran is Turing-complete is because it simulates a register machine. The number's prime factorization stores the contents of the registers, while the division and multiplication is a way to conditionally add and subtract from the registers. I would recommend reading the Wikipedia article (linked to above).

The Challenge

Your task is to write the shortest program possible that can take a valid Fractran program from STDIN as its only input and generates a valid BF program to STDOUT that simulates the Fractran program. There are two ways that you could simulate a Fractran program with BF.

NOTE: Your answer is not a BF program. Your answer is the code that generates the BF program from any given Fractran program. The goal is to get the BF program to be the equivalent of the Fractran program. (technically you could do the competition in BF, but it would be hard)

Option 1

Your program should output a BF program that does the following:

Takes exactly 1 number from STDIN in the form of the corresponding ASCII character (due to the way that BF input works), which is the input to the Fractran program.
Prints exactly 1 number to STDOUT in the form of the corresponding ASCII character, which is the output to from the Fractran program.

This option is meant to represent the exact input and output from a Fractran virtual machine.

Option 2

The BF code that your program produces should do the following:

Take input by having the prime factorization of the number already encoded in memory (prior to running the program). If the input is 28 (2*2*7), then there will be a value of 2 in the second cell and a value of 1 in the seventh cell (the pointer starts on cell 0). All other cells will be zero.
Give output by having the prime factorization of the output encoded in memory when the program terminates. If the output is 10, then there must be a value of 1 in each of cells 2 and 5. All other prime-numbered cells must have a value of zero. The content of other cells do not matter.

This option represents the computing model behind the Fractran language.

Rules and Requirements

Input (top your program) will be a list of fractions on STDIN. There will be one fraction per line with a comma between the numerator and denominator. An empty line represents the end of input. The fractions will always be reduced to lowest terms.
Your program's output should be a single-line, valid BF program to STDOUT. This program should be able to simulate that particular Fractran program according to one of the two options. For any input, the BF program generated should be able to produce the same output as the Fractran program.
You must state which option you chose.
You can choose the bounds on the BF memory and tape, and whether they are wrapping
CODE GOLF. Also, the size of the outputted BF programs does not matter, only the size of the program that is doing the converting.
Programs should only consist of printable ASCII

If I am ambiguous anywhere, do not hesitate to ask. This is a very complicated challenge to describe.

In addition, please post your program's generated BF code for the following input, as to provide an easy way to check if your program is working:

33,20
5,11
13,10
1,5
2,3
10,7
7,2

This program calculates the number of 1s in the binary expansion of a number. However, the input and output are formatted strangely (as with all Fractran programs). Input is of the form 2^A, while output is of the form 13^B.

PhiNotPi

Posted 2012-03-19T22:31:21.507

Reputation: 26 739

So basically you want a fractran interpreter in brainfuck. Everything else is fairly trivial. – captncraig – 2012-03-19T22:57:33.827

@CMP I want a program that outputs the BF version of a Fractran program. The code that does this conversion does not have to be in BF. The BF program itself is single-purpose. – PhiNotPi – 2012-03-19T23:01:41.047

1Are there limits on the brainfuck interpreter we use? Must we use byte sized cells, or can we use int cells? Bounded memory? Wrapping memory? Wrapping cells? Anything we want that makes it work? – captncraig – 2012-03-19T23:02:51.510

Anything you want to make it work, but please specify in your answer. – PhiNotPi – 2012-03-19T23:03:53.197

@PhilNotPi I know you want single purpose, but the most straightforward way is implementing an interpreter, and having the main program output that interpreter, somehow encoding the original program in memory somewhere. – captncraig – 2012-03-19T23:04:49.137

@CMP Ok, that can work. – PhiNotPi – 2012-03-19T23:08:22.363

The "instant accepted answer" criterion is impossible because Fractran can't handle input in the format specified. Clarifying details like that, and like CMP's questions about interpreter variants, is the purpose of the sandbox thread in meta.

– Peter Taylor – 2012-03-19T23:54:57.250

@PeterTaylor Yeah, that was a stupid mistake. Also, I probably should have put this in the sandbox thread. But, what can I do now? Should I delete the question and move it to the sandbox? – PhiNotPi – 2012-03-19T23:57:16.963

I would say no. The question looks pretty good to me. Unfortunately it does look like IO constraints make it impossible to have a real fractran self-interpreter. – captncraig – 2012-03-20T01:55:12.417

But holy cow, it looks like a self interpreter does exist. This thread has details: http://stackoverflow.com/questions/1749905/code-golf-fractran. I have no idea how they work, and I assume they require significant re-encoding of input, but wow.

– captncraig – 2012-03-20T02:06:06.670

Just to let everyone know, I now have a working 371 character Perl solution for you to beat. – PhiNotPi – 2012-03-20T03:40:17.067

I'm confused by your example program's claim that it calculates the number of 1s in the binary expansion. When I run it with 2 I get 13 (2->7->10->13). – Keith Randall – 2012-03-20T20:45:05.870

Can we assume the input fractions are in lowest terms? – Keith Randall – 2012-03-20T20:58:32.250

@KeithRandall Actually, it does compute the number of ones. The output will not be the actual number N though, but rather 13^N. (edited the question, pretty important info to leave out!). Fractran inputs and outputs are always formatted in strange ways. Also, you can assume that they will be lowest terms. – PhiNotPi – 2012-03-20T21:37:28.397

1It's probably possible to solve this with BF... – mbomb007 – 2015-04-17T14:10:51.993

Answers

Python, 182 chars

Option 1, standard byte cells. There are only 255 possible inputs (0 as an input doesn't really make sense), so I just run a Fractran interpreter 255 times in Python and generate a simple table lookup Brainfuck program encoding the results.

import sys
I=map(eval,sys.stdin)
P='+>,'
Q=''
for i in range(1,256):
 while i:j=i;i=([i*x/y for x,y in I if i%y==0]+[0])[0]
 r=j&255;P+='-[';Q=']<[-'+'+'*r+'.'+'-'*r+']>'+Q
print P+Q

Output for the example input (___ = 246 more nested conditions, I can't paste the whole result as it is too large):

+>,-[-[-[-[-[-[-[-[___]<[-+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.-------------------------------------------------------------------------------------------------------------------------------------------------------------------------]>]<[-+++++++++++++.-------------]>]<[-+++++++++++++.-------------]>]<[-+.-]>]<[-+++++++++++++.-------------]>]<[-+++++++++++++.-------------]>]<[-+++++++++++++.-------------]>]<[-+.-]>

Keith Randall

Posted 2012-03-19T22:31:21.507

Reputation: 19 865

+1 for the creativity. Also, what would happen if you fed this a Fractran program that was an infinite loop of some sort? The program would fail to produce an equivalent (infinitely-looping) BF program. Aha! – PhiNotPi – 2012-03-21T00:02:33.943

1@PhiNotPi: true, I may need to detect looping and special case that... – Keith Randall – 2012-03-21T01:54:29.653

7Actually, I think that determining whether a given Fractran program is an endless loop or not is equivalent to the halting problem. Good luck with that. :) – PhiNotPi – 2012-03-21T01:58:08.633

@PhiNotPi: yes, my last comment was a joke. – Keith Randall – 2012-03-21T03:03:34.093

1An interesting approach. Only shortcoming may be if the fractran spec says it needs to handle outputs greater than 255, which I know many programs rely on, so it seems a bit weird to take only the LSB of the result. – captncraig – 2012-04-03T18:39:12.497

1@CMP, the question specifically states that the input for option 1 is taken from ascii. – boothby – 2012-04-22T05:28:11.723

1@PhiNotPi determining whether or not a program halts, it slightly different than being able to create another program in another language such that it halts if and only if the original halts. The former is impossible, while the latter is done every day by compilers. – Cruncher – 2014-04-21T19:46:42.253

Python, 420 chars

This uses a sort of blend of options 1 and 2: It assumes that brainfuck is implemented with big integers (I use a Sage implementation). Input a fractran program, for example, 33/20,5/11,13/10,1/5,2/3,10/7,7/2. Then, pre-load a number, for example, 2^5, at the cursor. Then, run the output of this python script. Wait 44 seconds. The result, 13^2 sits where the cursor started. I didn't wait for the answer for 2^7.

s="[->>>+<<<]+["
for l in raw_input().split(','):
 a,b=map(int,l.split('/'))
 s+="[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>["+"[->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]<"*(b-1)+"[->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]<"+"[->+>+<<]>[-<+>]<"*a+"[-]>>[-<<+>>]<<<<<->>>>]<<]<<"
print s+">+<[->-<]>[-<+>]<]>>>[-<<<+>>>]"

This is my first brainfuck script. It can certainly be golfed further, but I've got other things to do until later tonight.

edit: rather than golf this further, I'm working on a solution for option 2. also, here's the output for the requested program:

[->>>+<<<]+[[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<>+<[->-<]>[-<+>]<]>>>[-<<<+>>>]

boothby

Posted 2012-03-19T22:31:21.507

Reputation: 9 038

That's a nice first Brainfuck script, +1. You can compute 2^7 with my Brainfuck interpreter in less than 5 seconds by the way. Also, shouldn't it be raw_input() instead of raw_input (or is it some quirk I don't know about) ?

– copy – 2012-03-22T19:27:26.793

@copy, thanks! you're right, raw_input() is necessary. I'm not surprised that competent brainfuck interpreters do better than my awful naive Sage implementation. – boothby – 2012-03-22T20:46:29.820

Perl, 326 characters

I am going to answer my own question hopefully to stimulate more answers. I am of course not eligible to win. This is option 2 with unbounded memory and cells, although it works on wrapping cells. Each fraction is converted into a single block of code. The newlines are for readability.

L:{$A=<>;
if($/eq$A){last L}
($B,$C)=eval$A;
$D=$E=$F=$G=$H=2;
while($C>1){
if($C%$H==0){
$C/=$H;
$R=">"x$H;
$L="<"x$H;
$D.=$R.'[-'.$L;
$E.=$R.'-'.$L;
if($H>2){$R.="+[->+<]]>[-<+>]<"}
else{$R.="+[-<+>]]<[->+<]>"}
$G=$R.$L.$G;
$H--}$H++}
$H=2;while($B>1){
if($B%$H==0){
$B/=$H;
$F.=">"x$H.'+'.'<'x$H;
$H--}$H++}
$I="+[-$I$D$E+$F$G]";
redo L}print$I

Here is the example output. This takes advantage of the fact that other characters are ignored as comments. This also appears to be a very short output compared to the other entries, although output size doesn't technically matter.

+[-+[-+[-+[-+[-+[-+[-2>>[-<<>>[-<<>>>>>[-<<<<<2>>-<<>>-<<>>>>>-<<<<<+2>>>+<<<>>>>>>>>>>>+<<<<<<<<<<<>>>>>+[->+<]]>[-<+>]<<<<<<>>+[-<+>]]<[->+<]><<>>+[-<+>]]<[->+<]><<2]2>>>>>>>>>>>[-<<<<<<<<<<<2>>>>>>>>>>>-<<<<<<<<<<<+2>>>>>+<<<<<>>>>>>>>>>>+[->+<]]>[-<+>]<<<<<<<<<<<<2]2>>[-<<>>>>>[-<<<<<2>>-<<>>>>>-<<<<<+2>>>>>>>>>>>>>+<<<<<<<<<<<<<>>>>>+[->+<]]>[-<+>]<<<<<<>>+[-<+>]]<[->+<]><<2]2>>>>>[-<<<<<2>>>>>-<<<<<+2>>>>>+[->+<]]>[-<+>]<<<<<<2]2>>>[-<<<2>>>-<<<+2>>+<<>>>+[->+<]]>[-<+>]<<<<2]2>>>>>>>[-<<<<<<<2>>>>>>>-<<<<<<<+2>>+<<>>>>>+<<<<<>>>>>>>+[->+<]]>[-<+>]<<<<<<<<2]2>>[-<<2>>-<<+2>>>>>>>+<<<<<<<>>+[-<+>]]<[->+<]><<2]

PhiNotPi

Posted 2012-03-19T22:31:21.507

Reputation: 26 739

Sage, 431 chars

This is a completely new solution. I figured out some better ways of doing things in brainfuck, and this properly implements Option 2. Newlines added for clarity. This can probably be golfed further, but it involves rewriting the BF to have a lower loop depth.

exec"f=factor;
J=''.join;
Q=L(a,b):Lz:a*z+b*-z;M=Q('<>');
C=Lj,k:(Ll:'[-%s+%s+%s]%s[-%s+%s]%s'%tuple(map(M,[-j,-k,l,-l,l,-l,k])))(j+k);
print '>+[>>>+'+J(map(L(n,m):reduce(Lr,(p,e):'[-%s%s%s[[-]<<+>>]%s<<%s]'%(M(4-p),C(6-p,2),'[-'*(e-1),']'*(e-1),r),f(m),'[-<<<->>>%s]'%J(map(L(p,e):M(4-p)+Q('+-')(e)+M(p-4),f(n/m))))+'<<<'+C(3,2),[map(QQ,x.split('/'))for x in raw_input().split(',')]))+'<<<<+>[-<->]<[->+<]>]'".replace('L','lambda ')

Sample output:

Given the input 33/20,5/11,13/10,1/5,2/3,10/7,7/2

>+[>>>+[->[->+>>+<<<]>>>[-<<<+>>>]<<[[-]<<+>>]<<[-<<[->>>>+>>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<<[-[[-]<<+>>]]<<[-<<<->>><<-->><+>>-<>>>>>>>+<<<<<<<]]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[->>>>>>>[-<<<<<+>>+>>>]<<<[->>>+<<<]<<[[-]<<+>>]<<[-<<<->>>>+<>>>>>>>-<<<<<<<]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[->[->+>>+<<<]>>>[-<<<+>>>]<<[[-]<<+>>]<<[-<<[->>>>+>>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<<[[-]<<+>>]<<[-<<<->>><<->>>-<>>>>>>>>>+<<<<<<<<<]]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[->[->+>>+<<<]>>>[-<<<+>>>]<<[[-]<<+>>]<<[-<<<->>>>-<]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[-<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[[-]<<+>>]<<[-<<<->>><<+>><->]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[->>>[-<+>>+<]>[-<+>]<<[[-]<<+>>]<<[-<<<->>><<+>>>+<>>>-<<<]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[-<<[->>>>+>>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<<[[-]<<+>>]<<[-<<<->>><<->>>>>+<<<]]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<<<<+>[-<->]<[->+<]>]

boothby

Posted 2012-03-19T22:31:21.507

Reputation: 9 038