/* Problem 1--Egyptian Multiplication
   The trick to this problem was to convert the Egyptian numbers to
   ints, do all the arithmetic with the ints, and convert them back to
   Egyptian numbers.  In other words, it would be much more tedious
   actually to define string manipulation functions to perform the
   doubling and addition routines. */

#include <fstream>
#include <cstring>
using namespace std;

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

ifstream in ("prob1.in");
ofstream out ("prob1.out");

int main (int argc, char **argv);
int e2i (char *e);
char *i2e (int i);
void append (char *e, int &l, char ch, int s);
void mult (int a, int b);

int main (int argc, char **argv) {

 char a[50], b[50];  //The numbers a and b.
 while (true) {
  in.getline (a,sizeof a);  //Read in the numbers.
  if (strcmp (a,"END")==0) break;
  in.getline (b,sizeof b);
  mult (e2i(a),e2i(b));  //Multiply them.
 }
 return 0;
}

/* e2i converts an Egyptian number to an integer. */

int e2i (char *e) {

 int i = 0;
 for (int c=0; e[c]!=0;c++)
  switch (e[c]) { // Just add the appropriate value to the integer
   case '|': {i++; break;}
   case 'n': {i+=10; break;}
   case '9': {i+=100; break;}
   case '8': {i+=1000; break;}
   case 'r': {i+=10000; break;}
  }
 return i;
}

//i2e converts an integer to an Egyptian number.

char *i2e (int i) {

 char *e = new char[50];  //Allocate a new string.
 int l = 0;  //length of string so far
 append (e,l,'|',i%10); //Add the appropriate number of symbols to the
 i/= 10;                //string for each digit in the number.
 append (e,l,'n',i%10);
 i/= 10;
 append (e,l,'9',i%10);
 i/= 10;
 append (e,l,'8',i%10);
 i/= 10;
 append (e,l,'r',i%10);
 e[MAX(l-1,0)]=0; //Strip off the final trailing space.
 return e;
}

/* append accepts a string, its current length, the character to add and
   the number of these characters to be added, and appends these
   characters to the string. */

void append (char *e, int &l, char ch, int s) {

 if (s==0) return; //If none are to be added, just skip.
 for (int c=0; c<s;c++) e[l++]=ch; //Add the characters.
 e[l++]=' '; //Add the trailing space.
}

/* mult takes the two integers and prints out the steps of Egyptian
   multiplication.  Notice that the rows with asterisks correspond to
   the one digits in the binary representation of b */

void mult (int a, int b) {

 char *e;
 int c = 1, p = a*b; //c is the left column; p is the final product.
 while (b > 0) {
  out << (b%2==1 ? "* " : "  "); //Check whether the rightmost digit of
                                 //this binary number is 1; if so, print
                                 //asterisk.
  out.width (50); out.setf (ios::left); //Set formatting.
  out << (e=i2e(c)); //Print left column.
  delete[] e; //Deallocate string.
  out.width(0); //Set formatting.
  out << (e=i2e(a)) << endl; //Print right column.
  delete[] e; //Deallocate string.
  c *= 2; a *= 2; b /= 2; //Double left and right columns, halve b.
 }
 out << "The solution is: "<< (e = i2e(p)) << endl << endl;
 delete[] e;
}