import java.io.*;
import java.math.*;   // Needed for BigInteger
import java.util.*;   // Needed for Vector and/or ArrayList

/****************************************************************\
 * Program Name: TBD                                            *
 * Author: Steve Palmer                                         *
 * Date: 2/11/7                                                 *
 *                                                              *
 * Purpose:                                                     *
 * Mostly for play.                                             *
 *                                                              *
 * A set of functions to demonstrate some observed methods for  *
 * performing integer base conversion.  The first functions,    *
 * implemented 2/11/7 and before, perform base conversion when  *
 * one base is a multiple of another.                           *
 *                                                              *
 * To convert from base B to base B/F, the conversion is done   *
 * as follows. (ignore variable/parameter names for now)        *
 * B0 <- Source base.                                           *
 * B1 <- Target base.                                           *
 * F <- Factor which gives B0 when multiplied by B1             *
 * N <- Numeral                                                 *
 * {d_k, d_k-1, ... d_1, d_0} <- Digits of N.                   *
 * m_i in {m_k, m_k-1, ... m_1, m_0} <- F^i (i -> k...0)        *
 * C <- {d_k(m_k), d_k-1(m_k-1),... ,d_0(m_0)}                  *
 *                                                              *
 * At that point, C contains coefficients for a polynomial,     *
 * equivalent to N, but in terms of (X/F).                      *
 *                                                              *
 * Digit normalization utilizes borrowing and carrying to       *
 * convert a polynomial into a legal numeral in base B1.        *
 *                                                              *
 * Converting from base B to base B(F) is a little trickier.    *
 * The method is something like this:                           *
 * B0 <- Source base                                            *
 * B1 <- Target base                                            *
 * F  <- Integer that gives B1 when multiplied by B0.           *
 * N  <- Numeral.                                               *
 * {d_k, d_k-1, ... d_1, d_0} <- Digits of N.                   *
 * m_i in {m_k, m_k-1, ... m_1, m_0} <- F^(i)                   *
 * C0 <- { d_k(m_0), d_k-1(m_1), ..., d_k-1(m_k-1), d_0(m_k) }  *
 * C  <- for d_i in C0 (i->k,k-1,...0)                          *
 *    d1_i <- d_i/m_k                                           *
 *    d1_i-1 <- (d_i-1 + B1(d_i % m_k))/m_i-1                   *
 *                                                              *
 * Like before, C contains coefficients for a polynomial in     *
 * terms of B(F).  Digit normalization (borrowing/carrying)     *
 * makes it a legal numeral.                                    *
 *                                                              *
 * Revision History:                                            *
 *   2/10/7 - Base conversion methods written and string I/O    *
 *            enabled.                                          *
 *   2/16/7 - Modified to handle positive integers with         *
 *            negative bases.                                   *
 *   2/26/7 - Working on Pascal's Triangle conversion for       *
 *            non-multiple bases.                               *
 *            ^^^ Needs to be compiled with PascalT.java now ^^^*
 *   3/4/7  - It's not pretty, but I think it's working for     *
 *            both offsets and multiples.  If one base is a     *
 *            multiple of another, it uses the appropriate      *
 *            multiple routine.  Otherwise it uses powers of    *
 *            Pascal's Triangle matrices.                       *
 *   3/5/7  - Removed debugging print-outs.                     *
 *                                                              *
 * To compile and execute:                                      *
 * > javac normalize.java Pascal.java                           *
 * > java normalize                                             *
 * {Follow prompts.}                                            *
 *                                                              *
 * Known Problems:                                              *
 *   - Weak data validation.                                    *
 *   - Pass integer by reference kludge should be fixed,        *
 *     probably by a custom data type.  I kludged it because    *
 *     Vector.size() and Vector.remove*() seem not to do quite  *
 *     what I expected.  I had to manually track the number of  *
 *     digits/coefficients in the Vector.                       *
 *                                                              *
 * To-Do list:                                                  *
 *   - Add conversion between any two bases using matrix        *
 *     multiplication by Pascal's Triangle.                     *
 *   - Head-start on Pascal's Triangle for offsets B+/-6, B+/-8 *
 *     (up6, down6, up8, down8 for 10 <-> 16 or 10 <-> 2).      *
\***************************************************************/

public class normalize
{
    /*
     * Convert between bases where the target is a multiple of the source.
     */
    public static void bGrow (Vector <BigInteger> numeral,
                              int rFactor,
                              int Base,
                              int termSize[])
    {
	BigInteger multBy=BigInteger.ONE;
	BigInteger Factor=new BigInteger (Integer.toString(rFactor));
	BigInteger Holder;

	/*
	 * Multiply digits, right to left, by
	 * increasing consecutive powers of rFactor.
	 */
	for ( int lcv=termSize[0]-1; lcv > -1; lcv-- ) {
	    Holder = numeral.elementAt(lcv);
	    numeral.removeElementAt(lcv);
	    numeral.add(lcv, Holder.multiply(multBy));
	    multBy = multBy.multiply(Factor);
	    /*
	     * Show steps if desired.
	     */
	    //	    showList(numeral, termSize);
	}
	multBy = multBy.divide(Factor);

	// Now we have a number that's multBy times too big.
	// Divide multBy out again.
	BigInteger Remnant = BigInteger.ZERO;
	for (int lcv=termSize[0]-1;lcv>-1; lcv--) {
	    Holder = numeral.elementAt(lcv);
	    numeral.remove(lcv);

	    Holder = Holder.add(Remnant);
	    Remnant =
               Holder.remainder(multBy).multiply(BigInteger.valueOf(Base));
	    Holder = Holder.divide(multBy);

	    numeral.add(lcv,Holder);
	    /*
	     * Show steps if desired.
	     */
	    // showList(numeral, termSize);
	}
    }

    /*
     * Convert between bases where the source is a multiple of the target.
     */
    public static void bReduce (Vector <BigInteger> numeral, int rFactor, int Base, int termSize[])
    {
	BigInteger multBy=BigInteger.ONE;
	BigInteger Factor=new BigInteger (Integer.toString(rFactor));
	BigInteger Holder;

	for ( int lcv=0; lcv < termSize[0]; lcv++ ) {
	    Holder = numeral.elementAt(lcv);
	    numeral.removeElementAt(lcv);
	    numeral.add(lcv, Holder.multiply(multBy));
	    multBy = multBy.multiply(Factor);
	    /*
	     * Show steps if desired.
	     */
	    //	    showList(numeral, termSize);
	}
    }

    public static boolean isNormal( BigInteger Curr,
                                 BigInteger Prev, 
				 int base,
                                 int pass,
                                 int size)
    {
	BigInteger NormalBase = BigInteger.valueOf(base);

	if (
	    (Curr.abs().compareTo(NormalBase.abs()) >= 0) ||
	    (Prev.abs().compareTo(NormalBase.abs()) >= 0) ||
	    (Curr.compareTo(BigInteger.ZERO) < 0) ||
	    (Prev.compareTo(BigInteger.ZERO) < 0 ) ||
	    (pass < size)
	    ) {
	    return false;
	} else {
	    return true;
	}
    }

    /*
     * Normalize digits in a base.  Make sure all coefficients are legal digits
     * in the base.
     */
    public static void normalDigs(Vector <BigInteger> C, int Base, int termSize[])
    {
	int lcv = 0, lastInd=termSize[0]-1, lSize=lastInd+1;

	BigInteger Holder = C.elementAt(lcv);
	BigInteger Predecessor;
	if (lcv < lastInd) {
	    Predecessor = C.elementAt(lcv+1);
	} else {
	    Predecessor = BigInteger.ZERO;
	}

	while ( isNormal (Holder, Predecessor, Base, lcv, lSize) == false) {

	    if ( Holder.compareTo(BigInteger.ZERO) < 0) {

		// Borrowing to get digit above 0.
		Predecessor = Predecessor.add (Holder.divide(BigInteger.valueOf(Base)));
		Holder = Holder.remainder(BigInteger.valueOf(Base));
		if ( Base > 0 ) {
		    if ( Holder.compareTo(BigInteger.ZERO) < 0) {
			Holder = Holder.add(BigInteger.valueOf(Base));
			Predecessor = Predecessor.subtract(BigInteger.ONE);
		    }
		} else {
		    Holder = Holder.subtract(BigInteger.valueOf(Base));
		    Predecessor = Predecessor.add(BigInteger.ONE);
		}

	    } else if ( Holder.compareTo(BigInteger.valueOf(Base)) >= 0) {
		// Carrying to get digit below <Base>

		Predecessor = Predecessor.add (Holder.divide(BigInteger.valueOf(Base)));
		Holder = Holder.remainder(BigInteger.valueOf(Base));
	    }

	    C.removeElementAt(lcv);
	    C.add(lcv, Holder);
	    if (lcv < lastInd) {
		C.removeElementAt(lcv+1);
	    }
	    C.add(lcv+1, Predecessor);

	    lcv++;
	    Holder = Predecessor;
	    if (lcv < lastInd ) {
		Predecessor = C.elementAt(lcv+1);
	    } else {
		Predecessor = BigInteger.ZERO;
	    }
	}
	if (Holder.compareTo(BigInteger.ZERO) != 0)
	    lcv++;

	termSize[0] = lcv;
    }

    public static BigInteger[][] stuffMat(Vector<BigInteger> Cset, int lSize[]) {
	BigInteger[][] LocalDigits = new BigInteger[1][lSize[0]];
	for (int lcv=0; lcv<lSize[0]; lcv++)
	    LocalDigits[0][lcv] = Cset.elementAt(lSize[0] - lcv - 1);
	return LocalDigits;
    }

    public static Vector<BigInteger> dumpMat(BigInteger[][] HeldMat, int lSize[]) {
	Vector<BigInteger> LocalDigits = new Vector<BigInteger> ();

	for (int lcv=0; lcv<lSize[0]; lcv++) {
	    LocalDigits.add(lcv, HeldMat[0][lSize[0] - lcv - 1]);
	}

	return LocalDigits;
    }

    /*
     * Display a list of coefficients and/or digits.
     */
    public static void showList( Vector <BigInteger> Cset, int lSize[])
    {
	System.out.print("[");
	for (int lcv=lSize[0]-1; lcv>-1; lcv--) {
	    System.out.print(Cset.elementAt(lcv));
	    if (lcv > 0)
		System.out.print (" ");
	}
	System.out.println("]");
    }

    public static String Digits()
    {
	return ("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
                "abcdefghijklmnopqrstuvwxyz" +
		"`~!@#$%^&*()-_=+[]{}\\|;:,.<>/?\'\"");
    }

    public static String listToNum (Vector <BigInteger> L, int Size[]) {
	String tempStr="", DL=Digits();
	int fnum=0;

        for (int lcv=Size[0]-1; lcv>-1; lcv--) {
	    if ( L.elementAt(lcv).compareTo(BigInteger.ZERO) == 0 ) {
		fnum++;
	    } else {
		break;
	    }
	}

	for (int lcv=Size[0]-fnum-1;lcv>-1;lcv--) {
	    int spos=L.elementAt(lcv).intValue();
	    int epos=spos+1;
	    if (epos > DL.length()) {
		System.err.println("I don't have that many digits");
		System.exit(-1);
	    }
	    tempStr = tempStr + DL.substring(spos,epos);
	}
	System.out.print(tempStr);
        return DL;
    }

    public static void printRuler()
    {
	int nextTen = 1;
	for (int lcv=0;lcv<94;lcv++) {
	    if ((lcv % 10) == 0) {
		if (lcv != 0) {
		    System.out.print(nextTen++);
		} else {
		    System.out.print(" ");
		}
	    } else {
		System.out.print(" ");
	    }
	}
	System.out.println("");

	for (int lcv=0;lcv<94;lcv++)
	    System.out.print(lcv%10);

	System.out.println("");
	System.out.println(Digits());
	System.out.println("");
    }
		
    public static Vector<BigInteger> strToList (String Numeral)
    {
	String DL = Digits();
	Vector<BigInteger> digitList = new Vector<BigInteger>();

	// for (int lcv = Numeral.length(); lcv > -1; lcv--)
	for (int lcv=0; lcv<Numeral.length(); lcv++ )
	    for (int lcv1=0; lcv1<DL.length(); lcv1++) {
		int left=Numeral.length() - lcv - 1;
		int right = left+1;
		if (DL.substring(lcv1,lcv1+1).equals(Numeral.substring(left, right))) {
		    digitList.add(lcv, BigInteger.valueOf(lcv1));
		}
	    }
	return (digitList);
    }

    /*
     * Begin main()
     */
    public static void main (String args[])
    {
	Vector <BigInteger> CoeffList = new Vector<BigInteger>();
	Integer inBase, outBase;
	String buf;
	String tokens[];

	InputStreamReader stdin =
	    new InputStreamReader (System.in);
        BufferedReader MyTTY =
	    new BufferedReader(stdin);

	printRuler();
	System.out.print ("Enter a numeral: ");

	try {
	    // Get list of coefficients and dplit into a Vector of BigIntegers.
	    buf = MyTTY.readLine();
	    while ( buf.length() != 0 ) {
		CoeffList = strToList(buf);

		// This is stupid.  Can't pass integer by reference.  Can't keep track of the size of
		// CoeffList between functions.  Array of int effectively passes by reference.  Stupid!
		int numParams[] = new int[1];
		numParams[0] = buf.length();

		// Get bases for normalization and conversion
		System.out.print ("Enter an input base: ");
		buf = MyTTY.readLine();
		inBase = Integer.parseInt(buf);

		System.out.print ("Enter an output base: ");
		buf = MyTTY.readLine();
		outBase = Integer.parseInt(buf);

		/*
		 * Convert base, reducing from base inBase to outBase
		 *   inBae is a multiple of outBase.
		 */
		if ((( inBase / outBase ) * outBase) == inBase ) {
		    System.out.println
			("Input base is a multiple of output base");
		    bReduce (CoeffList, inBase/outBase, outBase, numParams);

		/*
		 * Convert base from base inBase to outBase.
		 *   outBase is a multiple of inBase.
		 */
		} else if ((( outBase / inBase ) * inBase) == outBase ) {
		    System.out.println
			("Output base is a multiple of input base");
		    bGrow (CoeffList, outBase/inBase, outBase, numParams);

		/*
		 * Convert base from base inBase to outBase.
		 *   inBase and outBase are not multiples of each other.
		 */
		} else {
		    System.out.println
			("Bases are not multiples.  Using Pascal's Triangle.");

		    int Power;
		    if ( inBase < outBase ) {
			Power = outBase - inBase;
		    } else {
			Power = inBase - outBase;
		    }

		    int size = numParams[0];
		    BigInteger[][] PasMat = PascalT.initMat(numParams[0]);
		    BigInteger[][] ProdMat;
		    if ( Power > 1 ) {
			ProdMat =
                           PascalT.multMat
                              (PasMat, PasMat, size, size, size, size);
			for (int lcv=2; lcv<Power; lcv++)
			    ProdMat = PascalT.multMat
                               (PasMat, ProdMat, size, size, size, size);
		    } else {
			ProdMat = PascalT.initMat(numParams[0]);
		    }

		    BigInteger DigitMat[][] = stuffMat(CoeffList, numParams);
		    if ( outBase > inBase ) {
			ProdMat = PascalT.negPascal(ProdMat,size);
		    }
		    BigInteger ResultMat[][] =
                       PascalT.multMat
                          (DigitMat, ProdMat, 1, size, size, size );
		    CoeffList = dumpMat(ResultMat,numParams);
		}

		/*
		 * Show coefficient before normalization if desired.
		 */
		normalDigs(CoeffList, outBase, numParams);

		// Print the result.
		System.out.print("Converts to: ");
		listToNum(CoeffList, numParams);
		System.out.println(" base " + outBase);
		System.out.print ("\n\nEnter a numeral: ");
		buf = MyTTY.readLine();
	    }
	} catch (Exception e) {
	    System.err.println("Error in input block: " + e + "\n");
	    System.exit(-1);
	}
    }
}