#include <fstream.h>  // For file output
#include <stdio.h>    // For sprintf()
#include <string.h>   // For strcmp()

#define MAX(a,b) (a>b ? a : b)

class vampire_number_with_fangs
{
public:
  long vampire_number;
  long fang1;
  long fang2;
  int operator<(const vampire_number_with_fangs&) const;
  int operator==(const vampire_number_with_fangs&) const;
  friend ostream& operator<<(ostream&,const vampire_number_with_fangs&);
};

int vampire_number_with_fangs::operator<(const vampire_number_with_fangs& rhs) const
{
  return vampire_number<rhs.vampire_number;
}

int vampire_number_with_fangs::operator==(const vampire_number_with_fangs& rhs) const
{
  return vampire_number==rhs.vampire_number;
}

ostream& operator<<(ostream& out, const vampire_number_with_fangs& in)
{
  out << in.fang1 << " * " << in.fang2 << " = " << in.vampire_number;
  return out;
}

void sort(char* in)
{
  int i,j,k,t;

  i=0;
  while(in[i]!=0)
  {
    k=i;
    j=i+1;
    while (in[j]!=0)
    {
      if (in[j]<in[k]) k=j;
      j++;
    }
    if (k>i)
    {
      t=in[k];
      in[k]=in[i];
      in[i]=t;
    }
    i++;
  }
}

void sort(vampire_number_with_fangs* in, int l)
{
  int i,j,k;
  vampire_number_with_fangs t;

  for(i=0; i<l; i++)
  {
    k=i;
    for(j=i+1; j<l; j++)
      if (in[j]<in[k]) k=j;
    if (k>i)
    {
      t=in[k];
      in[k]=in[i];
      in[i]=t;
    }
  }
}

void main()
{
  long vampire_length=4;
  long fang_length=vampire_length>>1;

  long i,j,count,true;
  long min_vampire,vampire,first,last,f1,f2,f2_min;
  long vampire_number;
  char f1timesf2[100], f1f2[100];
  ofstream f("vampires.txt");
  vampire_number_with_fangs list[5000];

  // Initialize count, the total number of vampire numbers
  count=0;

  // Calculate first possible fang:  10^(fang_length-1) + 1
  // Calculate last possible fang: 10^(fang_length) - 1
  first=10;
  for(i=2; i<fang_length; i++)
    first*=10;
  last=first;
  last*=10;
  last-=1;
  first+=1;

  // Calculate the smallest possible vampire number: 10^(vampire_length-1) + 1
  min_vampire=10;
  for(i=2; i<vampire_length; i++)
    min_vampire*=10;
  min_vampire+=1;

  cout << "first       = " << first << endl;
  cout << "last        = " << last << endl;
  cout << "min_vampire = " << min_vampire << endl;

  // Find vampire numbers.  fang1 is the smaller of the two fangs.  This
  // will generate a list ordered by the smaller fang.
  f << "Sorted by smallest fang:\n\n";
  cout << "\nFound this many so far: 0...";
  for (f1=first; f1<last; f1++)
  {
    f2_min=MAX(f1,min_vampire/f1+1);
    for(f2=f2_min; f2<=last; f2+=1)
    {
      vampire_number=f1*f2;
      sprintf(f1f2,"%d%d",f1,f2);
      sort(f1f2);
      sprintf(f1timesf2,"%d",vampire_number);
      sort(f1timesf2);

      if (!strcmp(f1f2,f1timesf2))
      {

        if (f1%10 || f2%10)
        {
          f << f1 << " * " << f2 << " = " << vampire_number << endl;
          list[count].vampire_number=vampire_number;
          list[count].fang1=f1;
          list[count].fang2=f2;
          count++;
          cout << count << "...";
        }
      }
    }
  }
  f << endl << "Sorted by vampire number:\n\n";
  sort(list,count);
  true=count;
  for(i=0; i<count; i++)
  {
    f << list[i];
    if (i && list[i]==list[i-1])
    {
      f << " duplicate";
      true--;
    }
    f << endl;
  }
  f << endl << "There are " << true << " true " << vampire_length;
  f << " digit vampire numbers.\n";
}