C++: Fractran

FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Horton Conway.

A FRACTRAN program is an ordered list of positive fractions , together with an initial positive integer input n.

The program is run by updating the integer n as follows:

• for the first fraction, f_i, in the list for which nf_i is an integer, replace n with nf_i ;
• repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.

Conway gave a program for primes in FRACTRAN:

17 / 91, 78 / 85, 19 / 51, 23 / 38, 29 / 33, 77 / 29, 95 / 23, 77 / 19, 1 / 17, 11 / 13, 13 / 11, 15 / 14, 15 / 2, 55 / 1

Starting with n = 2, this FRACTRAN program will change n to , then , generating the following sequence of integers:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770,

After 2, this sequence contains the following powers of 2:

2² = 4, 2³ = 8, 2⁵ = 32, 2⁷ = 128, 2¹¹ = 2048, 2¹³ = 8192, 2¹⁷ = 131072, 2¹⁹ = 524288,

which are the prime powers of 2.

Your task is to write a program that reads a list of fractions in a natural format from the keyboard or from a string, to parse it into a sequence of fractions (i.e. two integers), and runs the FRACTRAN starting from a provided integer, writing the result at each step. It is also required that the number of step is limited (by a parameter easy to find).

#include <iostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <math.h>

using namespace std;

class fractran
{
public:
	void run( std::string p, int s, int l  )
	{
		start = s; limit = l;
		istringstream iss( p ); vector<string> tmp;
		copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( tmp ) );

		string item; vector< pair<float, float> > v;
		pair<float, float> a;
		for( vector<string>::iterator i = tmp.begin(); i != tmp.end(); i++ )
		{
			string::size_type pos = ( *i ).find( '/', 0 );
			if( pos != std::string::npos )
			{
				a = make_pair( atof( ( ( *i ).substr( 0, pos ) ).c_str() ), atof( ( ( *i ).substr( pos + 1 ) ).c_str() ) );
				v.push_back( a );
			}
		}

		exec( &v );
	}

private:
	void exec( vector< pair<float, float> >* v )
	{
		int cnt = 0; bool found; float r;
		while( cnt < limit )
		{
			cout << cnt << " : " << start << "\n";
			cnt++;
			vector< pair<float, float> >::iterator it = v->begin();
			found = false;
			while( it != v->end() )
			{
				r  = start * ( ( *it ).first / ( *it ).second );
				if( r == floor( r ) )
				{
					found = true;
					break;
				}
				++it;
			}

			if( found ) start = ( int )r;
			else break;
		}
	}
	int start, limit;
};
int main( int argc, char* argv[] )
{
	fractran f; f.run( "17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1", 2, 15 );
	return system( "pause" );
}

0 : 2
1 : 15
2 : 825
3 : 725
4 : 1925
5 : 2275
6 : 425
7 : 390
8 : 330
9 : 290
10 : 770
11 : 910
12 : 170
13 : 156
14 : 132

SOURCE

Content is available under GNU Free Documentation License 1.2.