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.