Petando la pila. Problemas y retos usando recursividad.

[eferion]

Otra posible solución al problema de los vampiros.

Visto que mi planteamiento inicial de hacer permutaciones era demasiado lento he cambiado el punto de vista.

Al final, visto lo visto, se parece un poco al resto de soluciones. En mi caso, para llevar el conteo de los dígitos compongo una máscara que me permite saber si los números comparten el mismo grupo de dígitos.

Código C++:

const int _factor[] = { (int)1e0, (int)1e1, (int)1e2,
                        (int)1e3, (int)1e4, (int)1e5,
                        (int)1e6, (int)1e7, (int)1e8,
                        (int)1e9 };
 
 
int Mask( int num )
{
  int digit = num % 10;
 
  if ( num >= 10 )
    return _factor[ digit ] + Mask( num / 10 );
  else
    return _factor[ digit ];
}
 
int es_vampiro( int num, int min, int max, int mask )
{
  if ( num % min == 0 )
  {
    int num2 = num / min;
 
    if ( min % 10 || num2 % 10 )
    {
      if ( Mask( min ) + Mask( num2 ) == mask )
        return 1;
    }
  }
 
  if ( min < max )
    return es_vampiro( num, min + 1, max, mask );
 
  return 0;
}
 
int esVampiro( int num )
{
  int digits = log10( num ) + 1;
 
  if ( digits % 2 )
    return 0;
 
  if ( !(num % 100) && !( num - num / _factor[ digits - 2 ] * _factor[ digits - 2 ] ) )
    return 0;
 
  int mask = Mask( num );
  int min = _factor[ digits / 2 - 1 ] + 1;
  int max = sqrt( 1 + 4.0f * num ) / 2;
 
  return es_vampiro( num, min, max, mask );
}
 
int main(int , char ** )
{
  int counter = 0;
  for ( int i=10000000 ; i<=12000000 ; ++i )
    counter += esVampiro( i );
 
  printf( "%d\n", counter );
}