capicuas.cpp

//
// Compilacion: Como el usuario lo estime conveniente.
//              Si se define HAVE_GMP entonces hay que linkear contra libgmp y libgmpxx, e.g.:
//
//              $> CXXFLAGS="-Wall -O3 -DHAVE_GMP" LDLIBS="-lgmp -lgmpxx" make capicuas
//
// Uso: ./capicuas
//      ./capicuas <primer-numero> <ultimo-numero>
//      ./capicuas <primer-numero> <ultimo-numero> <precision>
//      ./capicuas <primer-numero> <ultimo-numero> <precision> <max-iteraciones>
//
// Precision es "i", "l" o "ll", representando "int", "long" y "long long", y es el tipo de dato que
// se usa para hacer los calculos y guardar los resultados. Si se compila usando GMP tambien se puede
// usar la precision "gmp". La unica forma de llegar a un millon de iteraciones de forma correcta es
// usando gmp; los tipos de datos nativos hace overflow despues de no mas de ~30-40 iteraciones, por
// lo que las respuestas que entregarian pasadas ese numero de iteraciones serian incorrectas.
//
// El codigo es relativamente largo por la flexibilidad que se da en la precision a usar, y el chequeo
// de overflow; si esa funcionalidad no estuviera presente el codigo seria bastante mas simple.
//
// Resultados para precision "int" y "long" en Linux x86_64. Usando "gmp" con 1000 iteraciones no se converge
// a nuevos resultados, y usando mas de 10000 iteraciones ya toma demasiado tiempo.
//
// $> time ./capicuas 100 1000 i
// n=167, capicua=88555588, iteraciones=11
// n=266, capicua=88555588, iteraciones=11
// n=365, capicua=88555588, iteraciones=11
// n=464, capicua=88555588, iteraciones=11
// n=563, capicua=88555588, iteraciones=11
// n=662, capicua=88555588, iteraciones=11
// n=761, capicua=88555588, iteraciones=11
// n=860, capicua=88555588, iteraciones=11
// n=829, capicua=88555588, iteraciones=10
// n=928, capicua=88555588, iteraciones=10
// n=193, capicua=233332, iteraciones=8
// n=292, capicua=233332, iteraciones=8
// n=391, capicua=233332, iteraciones=8
// n=490, capicua=233332, iteraciones=8
// n=589, capicua=1136311, iteraciones=8
// n=688, capicua=1136311, iteraciones=8
// n=787, capicua=1136311, iteraciones=8
// n=886, capicua=1136311, iteraciones=8
// n=949, capicua=2322232, iteraciones=8
// n=985, capicua=1136311, iteraciones=8
//
// real    0m0.006s
// user    0m0.001s
// sys     0m0.006s
// $> time ./capicuas 100 1000 l
// n=187, capicua=8813200023188, iteraciones=23
// n=286, capicua=8813200023188, iteraciones=23
// n=385, capicua=8813200023188, iteraciones=23
// n=484, capicua=8813200023188, iteraciones=23
// n=583, capicua=8813200023188, iteraciones=23
// n=682, capicua=8813200023188, iteraciones=23
// n=781, capicua=8813200023188, iteraciones=23
// n=880, capicua=8813200023188, iteraciones=23
// n=869, capicua=8813200023188, iteraciones=22
// n=968, capicua=8813200023188, iteraciones=22
// n=989, capicua=89540004598, iteraciones=19
// n=739, capicua=5233333325, iteraciones=17
// n=838, capicua=5233333325, iteraciones=17
// n=899, capicua=133697796331, iteraciones=17
// n=937, capicua=5233333325, iteraciones=17
// n=998, capicua=133697796331, iteraciones=17
// n=999, capicua=8939779398, iteraciones=16
// n=177, capicua=8836886388, iteraciones=15
// n=276, capicua=8836886388, iteraciones=15
// n=375, capicua=8836886388, iteraciones=15
//
// real    0m0.008s
// user    0m0.001s
// sys     0m0.008s
// $> time ./capicuas 100 1000 ll
// n=187, capicua=8813200023188, iteraciones=23
// n=286, capicua=8813200023188, iteraciones=23
// n=385, capicua=8813200023188, iteraciones=23
// n=484, capicua=8813200023188, iteraciones=23
// n=583, capicua=8813200023188, iteraciones=23
// n=682, capicua=8813200023188, iteraciones=23
// n=781, capicua=8813200023188, iteraciones=23
// n=880, capicua=8813200023188, iteraciones=23
// n=869, capicua=8813200023188, iteraciones=22
// n=968, capicua=8813200023188, iteraciones=22
// n=989, capicua=89540004598, iteraciones=19
// n=739, capicua=5233333325, iteraciones=17
// n=838, capicua=5233333325, iteraciones=17
// n=899, capicua=133697796331, iteraciones=17
// n=937, capicua=5233333325, iteraciones=17
// n=998, capicua=133697796331, iteraciones=17
// n=999, capicua=8939779398, iteraciones=16
// n=177, capicua=8836886388, iteraciones=15
// n=276, capicua=8836886388, iteraciones=15
// n=375, capicua=8836886388, iteraciones=15
//
// real    0m0.008s
// user    0m0.001s
// sys     0m0.007s


#include <algorithm>
#include <cstdlib>
#include <limits>
#include <iostream>
#include <vector>

#ifdef HAVE_GMP
#include <gmpxx.h>
#endif // HAVE_GMP


template <typename Integer>
struct CapicuaInfo
{
	Integer n;
	Integer capicua;
	int iteraciones;
};

template <typename T, typename Char, typename Integer>
std::basic_ostream<T, Char> &operator<<(std::basic_ostream<T, Char> &stream, const CapicuaInfo<Integer> &info)
{
	stream << "n=" << info.n << ", capicua=" << info.capicua << ", iteraciones=" << info.iteraciones;
	return stream;
}

template <typename Integer>
Integer reverso(Integer numero)
{
	Integer reverso = 0;
	while (numero) {
		auto digito = numero % 10;
		reverso = reverso * 10 + digito;
		numero /= 10;
	}
	return reverso;
}

template <typename Integer>
inline
bool suma_es_posible(Integer numero, Integer numero_reverso)
{
	return std::numeric_limits<Integer>::max() - numero >= numero_reverso;
}

#ifdef HAVE_GMP
template <>
bool suma_es_posible<mpz_class>(mpz_class numero, mpz_class numero_reverso)
{
	return true;
}
#endif // HAVE_GMP

template <typename Integer>
CapicuaInfo<Integer> capicua_info(Integer numero, int max_iteraciones)
{
	int iteracion = 1;
	Integer numero_original = numero;
	numero = numero + reverso(numero);
	while (iteracion < max_iteraciones) {
		auto numero_reverso = reverso(numero);
		if (numero_reverso == numero) {
			return {numero_original, numero, iteracion};
		}
		if (!suma_es_posible(numero, numero_reverso)) {
			return {numero_original, -1, iteracion};
		}
		numero = numero + numero_reverso;
		iteracion++;
	}
	return {numero_original, -1, iteracion};
}

template <typename Integer>
void imprimir_info_capicuas(Integer primer_numero, int n, int max_iteraciones, int max_resultados)
{
	// Obtenemos primero todos los resultados, luego imprimimos,
	// para aprovechar al maximo el cache de instrucciones de la CPU
	using resultado_t = CapicuaInfo<Integer>;
	std::vector<resultado_t> resultados;
	resultados.reserve(n);
	for (auto numero = primer_numero; numero < primer_numero + n; numero++) {
		auto resultado = capicua_info(numero, max_iteraciones);
		if (resultado.capicua != -1) {
			resultados.emplace_back(resultado);
		}
	}
	std::stable_sort(resultados.begin(), resultados.end(), [](const resultado_t &a, const resultado_t &b) {
		return a.iteraciones > b.iteraciones;
	});
	// Imprimimos los top-20
	for (int i = 0;  i != std::min(max_resultados, int(resultados.size())); i++) {
		std::cout << resultados[i] << '\n';
	}
}

int main(int args, char *argv[])
{
	int primer_numero = 100;
	int ultimo_numero = 1000;
	std::string precision = "i";
	int max_iteraciones = 1000000;
	int max_resultados = 20;
	if (args >= 3) {
		primer_numero = std::atoi(argv[1]);
		ultimo_numero = std::atoi(argv[2]);
	}
	if (args >= 4) {
		precision = argv[3];
	}
	if (args >= 5) {
		max_iteraciones = std::atoi(argv[4]);
	}
	if (args >= 6) {
		max_resultados = std::atoi(argv[5]);
	}
	int n = ultimo_numero - primer_numero + 1;

	if (precision == "l") {
		imprimir_info_capicuas<long>(primer_numero, n, max_iteraciones, max_resultados);
	}
	else if (precision == "ll") {
		imprimir_info_capicuas<long long>(primer_numero, n, max_iteraciones, max_resultados);
	}
#ifdef HAVE_GMP
	else if (precision == "gmp") {
		imprimir_info_capicuas<mpz_class>(primer_numero, n, max_iteraciones, max_resultados);
	}
#endif // HAVE_GMP
	else if (precision == "i") {
		imprimir_info_capicuas<int>(primer_numero, n, max_iteraciones, max_resultados);
	}
	else {
		std::cerr << "precision deconocida: " << precision << '\n';
		return 1;
	}
	return 0;
}

Solucion para https://www.programando.org/blog/2020/01/26/calculando-capicuas.html