package Others;

import java.util.InputMismatchException;
import java.util.Scanner;

/**
 * Class for finding the lowest base in which a given integer is a palindrome. Includes auxiliary
 * methods for converting between bases and reversing strings.
 *
 * <p>NOTE: There is potential for error, see note at line 63.
 *
 * @author RollandMichael
 * @version 2017.09.28
 */
public class LowestBasePalindrome {

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = 0;
    while (true) {
      try {
        System.out.print("Enter number: ");
        n = in.nextInt();
        break;
      } catch (InputMismatchException e) {
        System.out.println("Invalid input!");
        in.next();
      }
    }
    System.out.println(n + " is a palindrome in base " + lowestBasePalindrome(n));
    System.out.println(base2base(Integer.toString(n), 10, lowestBasePalindrome(n)));
    in.close();
  }

  /**
   * Given a number in base 10, returns the lowest base in which the number is represented by a
   * palindrome (read the same left-to-right and right-to-left).
   *
   * @param num A number in base 10.
   * @return The lowest base in which num is a palindrome.
   */
  public static int lowestBasePalindrome(int num) {
    int base, num2 = num;
    int digit;
    char digitC;
    boolean foundBase = false;
    String newNum = "";
    String digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    while (!foundBase) {
      // Try from bases 2 to num-1
      for (base = 2; base < num2; base++) {
        newNum = "";
        while (num > 0) {
          // Obtain the first digit of n in the current base,
          // which is equivalent to the integer remainder of (n/base).
          // The next digit is obtained by dividing n by the base and
          // continuing the process of getting the remainder. This is done
          // until n is <=0 and the number in the new base is obtained.
          digit = (num % base);
          num /= base;
          // If the digit isn't in the set of [0-9][A-Z] (beyond base 36), its character
          // form is just its value in ASCII.

          // NOTE: This may cause problems, as the capital letters are ASCII values
          // 65-90. It may cause false positives when one digit is, for instance 10 and assigned
          // 'A' from the character array and the other is 65 and also assigned 'A'.

          // Regardless, the character is added to the representation of n
          // in the current base.
          if (digit >= digits.length()) {
            digitC = (char) (digit);
            newNum += digitC;
            continue;
          }
          newNum += digits.charAt(digit);
        }
        // Num is assigned back its original value for the next iteration.
        num = num2;
        // Auxiliary method reverses the number.
        String reverse = reverse(newNum);
        // If the number is read the same as its reverse, then it is a palindrome.
        // The current base is returned.
        if (reverse.equals(newNum)) {
          foundBase = true;
          return base;
        }
      }
    }
    // If all else fails, n is always a palindrome in base n-1. ("11")
    return num - 1;
  }

  private static String reverse(String str) {
    String reverse = "";
    for (int i = str.length() - 1; i >= 0; i--) {
      reverse += str.charAt(i);
    }
    return reverse;
  }

  private static String base2base(String n, int b1, int b2) {
    // Declare variables: decimal value of n,
    // character of base b1, character of base b2,
    // and the string that will be returned.
    int decimalValue = 0, charB2;
    char charB1;
    String output = "";
    // Go through every character of n
    for (int i = 0; i < n.length(); i++) {
      // store the character in charB1
      charB1 = n.charAt(i);
      // if it is a non-number, convert it to a decimal value >9 and store it in charB2
      if (charB1 >= 'A' && charB1 <= 'Z') charB2 = 10 + (charB1 - 'A');
      // Else, store the integer value in charB2
      else charB2 = charB1 - '0';
      // Convert the digit to decimal and add it to the
      // decimalValue of n
      decimalValue = decimalValue * b1 + charB2;
    }

    // Converting the decimal value to base b2:
    // A number is converted from decimal to another base
    // by continuously dividing by the base and recording
    // the remainder until the quotient is zero. The number in the
    // new base is the remainders, with the last remainder
    // being the left-most digit.

    // While the quotient is NOT zero:
    while (decimalValue != 0) {
      // If the remainder is a digit < 10, simply add it to
      // the left side of the new number.
      if (decimalValue % b2 < 10) output = Integer.toString(decimalValue % b2) + output;
      // If the remainder is >= 10, add a character with the
      // corresponding value to the new number. (A = 10, B = 11, C = 12, ...)
      else output = (char) ((decimalValue % b2) + 55) + output;
      // Divide by the new base again
      decimalValue /= b2;
    }
    return output;
  }
}