import std.datetime; // for the StopWatch struct. 
import std.string; //for the format(). 
import std.stdio; //printing. 
/// A struct that represents a cab. It doesn't do the checking that the one in the assignment does, though. 
struct taxiCab{
	int taxiNumber;
	int a, b, c, d;	
	string toString(){
		return format("car %s = [%s %s %s %s]",taxiNumber, a, b, c, d);
	}
}

/**
* Program that measures the time it takes to determine the taxi numbers less than 25000. 
* Author: Charles McAnany
*
*/
void main(){
	StopWatch sw;
	sw.start;
	for (int iters = 0; iters< 25000; iters++){
		taxiCab cabID = isTaxi(iters);
		if(cabID.c != 0){
			writeln(cabID);
		}
	}
	sw.stop;
	Ticks timeTaken = sw.peek;
	writefln("%s\t%s",25000,timeTaken.toSeconds!float);
	sw.reset;

}

/**
* isTaxi determines if an integer passed to it is a taxi number, that is, there exists
* an a, b, c, and d, none of them the same, such that 
* a^3+b^3 = n =c^3 +d^3. 
* returns: 
* a taxiCab struct, with a, b, c, and d if found. if only one solution to x^3+y^3 was found, 
* c and d will be zero. If none were found, then a and b will be zero as well. 
* parameters: 
* n is an integer that is to be checked for taxi number-ness. 
*/
taxiCab isTaxi(int n){
	int limit = cubeRootFloor(n) - 1;
	int hits = 0; 
	int[] results = [0,0,0,0];
	for (int i = 0; i < limit; i++) {
		int res = n - i*i*i;
		double cubeRoot = res^^(1/3.0);
		int nearestInt = cast(int) (cubeRoot + 0.5);
		double diff = (cubeRoot - nearestInt) * (cubeRoot - nearestInt);
		if (diff < 1e-10) {
			if (hits < 2 && results[1] != i) {
				results[hits * 2] = i;
				results[hits * 2 + 1] = nearestInt;
			}
			hits++;
		}
	}
	return taxiCab(n,results[0],results[1],results[2],results[3]);
}

/// finds the largest integer x such that x^3 < n 
int cubeRootFloor(int n){
	double cubeRoot = n ^^ (1/3.0);
	int crFl = cast(int) cubeRoot;
	return crFl;
}