UVa 371. Ackermann Function

The underlying concepts of UVa 371: Ackermann Functions have been discussed in great details in our post of Collatz problem. In this post, we simply outlines an ad-hoc algorithm as a solution to this problem as follows.

	import java.io.PrintWriter;
	import java.util.Scanner;

	public class Main {
	private final Scanner in;
	private final PrintWriter out;

	private final static int _MaxValue = 1000000;
	private final static long[] memo = new long[_MaxValue];

	public Main() {
	in = new Scanner(System.in);
	out = new PrintWriter(System.out, true);
	}

	public Main(Scanner in, PrintWriter out) {
	this.in = in;
	this.out = out;
	}

	private static long[] getInts(String input) {
	String[] ints = input.trim().split(" ");
	long[] rets = new long[2];

	rets[0] = Long.parseLong(ints[0]);
	rets[1] = Long.parseLong(ints[1]);

	return rets;
	}

	private void solveAckermannProblem(long from, long to) {
	long maxValue = from;
	long maxLength = 0;

	for (long i = from; i <= to; i++) {
	long length = computeCycleLength(nextAckermannNumber(i));
	if (maxLength < length) {
	maxValue = i;
	maxLength = length;
	}
	}

	out.println(String
	.format("Between %d and %d, %d generates the longest sequence of %d values.",
	from, to, maxValue, maxLength));
	}

	private static long computeCycleLength(long n) {
	if (n == 0)
	return 0;

	if (n == 1)
	return 1;

	if (n < _MaxValue && memo[(int) n] != 0)
	return memo[(int) n];

	long len = 1 + computeCycleLength(nextAckermannNumber(n));// computing
	// length of
	// Ackermann
	// sequence

	if (n < _MaxValue) // storing it in cache
	memo[(int) n] = len;

	return len;
	}

	public static long nextAckermannNumber(long n) {
	if (n % 2 == 0)
	return n / 2;
	else
	return n * 3 + 1;
	}

	public void run() {
	while (in.hasNextLine()) {
	long[] range = getInts(in.nextLine());

	if ((range[0] == 0) && (range[1] == 0))
	break;

	long from = Math.min(range[0], range[1]);
	long to = Math.max(range[0], range[1]);

	solveAckermannProblem(from, to);
	}
	}

	public static void main(String[] args) {

	Main solver = new Main();
	solver.run();
	}

	}

view raw UVa371.java hosted with ❤ by GitHub

Please leave a comment if you have any question regarding this problem or implementation. Thanks.

UVa 713: Adding Reversed Numbers is a straight-forward problem that can be solved using an ad-hoc algorithm. We have discussed a similar problem in a previous blog-post. However, this problem imposes following additional constraint—numbers will be at most 200 characters long–which necessitates the use of BigInteger. Following Java code shows such an ad-hoc algorithm that solves this problem by considering the stated constraints.

	import java.io.PrintWriter;
	import java.math.BigInteger;
	import java.util.Scanner;

	class Main {

	private final Scanner in;
	private final PrintWriter out;

	public Main(){
	in = new Scanner(System.in);
	out = new PrintWriter(System.out, true);
	}

	public Main(Scanner in, PrintWriter out){
	this.in = in;
	this.out = out;
	}

	private static BigInteger bigIntAfterRemovingTrailingZeros(String num){
	int nonZeroIndex=num.length()-1;
	for (; nonZeroIndex>=0; nonZeroIndex--){
	if (num.charAt(nonZeroIndex) != '0'){
	break;
	}
	}
	return new BigInteger(num.substring(0, nonZeroIndex+1));

	}

	private static BigInteger[] readLineAsBigInts(String input){
	String [] ints = input.trim().split(" ");
	BigInteger [] rets = new BigInteger[2];

	rets[0] = bigIntAfterRemovingTrailingZeros(ints[0]);
	rets[1] = bigIntAfterRemovingTrailingZeros(ints[1]);

	return rets;
	}

	private static BigInteger reversedBigInt(BigInteger num1){
	BigInteger reversedNum = BigInteger.ZERO;
	final int _REM = 1;
	final int _QUOTIENT = 0;

	while (num1.compareTo(BigInteger.ZERO)>0){
	BigInteger [] results = num1.divideAndRemainder(BigInteger.TEN);

	reversedNum = reversedNum.add(results[_REM]);
	if(num1.compareTo(BigInteger.TEN)>=0)
	reversedNum =reversedNum.multiply(BigInteger.TEN);

	num1 = results[_QUOTIENT];
	}

	return reversedNum;
	}

	private static BigInteger getAddRevNumbers(BigInteger num1, BigInteger num2){
	return reversedBigInt(reversedBigInt(num1).add(reversedBigInt(num2)));
	}

	public void run(){
	final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases
	BigInteger [] numbers;

	for (int testCase = 0 ; testCase< T ; testCase++){
	numbers = readLineAsBigInts(in.nextLine());// read input
	out.println(getAddRevNumbers(numbers[0], numbers[1]));// print result
	}
	}

	public static void main(String[] args) {
	Main uva713Solver = new Main();
	uva713Solver.run();
	}

	}

view raw uva713.java hosted with ❤ by GitHub

Please leave a comment if you have any question. Thanks.

The following Java code snippet outlines an algorithm using dynamic programming to solve this problem. Notice that the function solveLuggageProblem applies a bottom-up DP to construct dpTable. The boolean value of each dpTable[i][j] implies that whether it is possible to achieve weight j from the weights of 1..i suitcases. In this way, it determines whether halfWeight — the half of the total weights (of the suitcases)– can be derived from using 1..n suitcases, i.e., whether the weights of suitcases can be distributed equally into the boots of two cars.

	import java.io.PrintWriter;
	import java.util.Scanner;

	class Main {

	private final Scanner in;
	private final PrintWriter out;

	public Main(){
	in = new Scanner(System.in);
	out = new PrintWriter(System.out, true);
	}

	public Main(Scanner in, PrintWriter out){
	this.in = in;
	this.out = out;
	}

	private static int[] readLineAsIntegers(String input){
	String [] ints = input.trim().split(" ");
	int [] rets = new int[ints.length];

	for (int i = 0 ;i < ints.length; i++)
	rets[i] = Integer.parseInt(ints[i]);

	return rets;
	}

	private String solveLuggageProblem(int[] weights){
	final String _TRUE = "YES";
	final String _FALSE = "NO";

	int totalWeight = getTotalWeight(weights);

	if (totalWeight%2 != 0)
	return _FALSE;

	int n = weights.length+1;
	int halfWeight = totalWeight/2;

	boolean [][] dpTable = new boolean [n][halfWeight+1];

	// Base case 1: weights = 0 for all n --> True
	for(int i = 0;i<n;i++)
	dpTable[i][0] = true;

	// Base case 2: weights !=0 for all n=0 --> False
	for(int i = 1;i<halfWeight+1;i++)
	dpTable[0][i] = false;

	for (int i = 1; i< n; i++ ){

	for (int j = 1; j< halfWeight+1; j++){

	int w_i = weights[i-1]; // weight of ith item

	if(j<w_i) // this item can't be included since its over the limit:j
	dpTable[i][j] = dpTable[i-1][j];
	else
	dpTable[i][j] = dpTable[i-1][j] \|\| dpTable[i-1][j-w_i];
	}
	}

	return dpTable[n-1][halfWeight]==true?_TRUE:_FALSE;

	}

	private int getTotalWeight(int[] weights) {
	int totalWeight = 0;
	// compute total weight of the bags
	for(int indx =0;indx< weights.length;indx++){
	totalWeight += weights[indx];
	}
	return totalWeight;
	}

	public void run(){
	final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases

	for (int i = 0 ; i< T ; i++){
	int [] weights = readLineAsIntegers(in.nextLine());

	// result:
	out.println(solveLuggageProblem(weights));
	}
	}


	public static void main(String[] args) {

	Main solveLuggageProblem = new Main();
	solveLuggageProblem.run();
	}

	}

view raw uva10664.java hosted with ❤ by GitHub

Please leave a comment if you have any question regarding this problem or implementation. Thanks.

The UVa 102: Ecological Bin Packing can be solved using brute-force search, as outlined in the following Java code snippet. Note that, the primary function getOPTConfiguration iterates over all possible bin arrangements, and determines the arrangement that requires minimum bottle moves for a given problem instance.

	import java.io.PrintWriter;
	import java.util.Scanner;

	class Main {

	private Scanner in = new Scanner(System.in);
	private PrintWriter out = new PrintWriter(System.out, true);

	private char[] types;
	private int[][] permutations;

	private static final int _NO_OF_BINS = 3;
	private static final int _BOTTLE_TYPES = 3;

	private int optMoveCount;
	private String optPermutation;


	public Main(){
	types = new char[]{'B','G','C'};
	permutations = new int[][] {
	{0,1,2},
	{0,2,1},
	{1,0,2},
	{1,2,0},
	{2,0,1},
	{2,1,0}
	};
	}

	private String permutationString(int permutationIndex){
	String retString = "";
	for(int i = 0;i<_NO_OF_BINS;i++){
	retString += types[permutations[permutationIndex][i]];
	}
	return retString;
	}

	private void initState(){
	optMoveCount = -1;
	optPermutation = "";

	}

	/**
	* A brute-force algorithm to determine a bin
	* configuration that yield
	* optimal (minimum) bin movements.
	* @param input
	* @return a String that represents OPT bin
	* configuration that yields minimum movement.
	*/
	String getOPTConfiguration(int[][] input){
	initState();

	for (int pi = 0;pi<permutations.length;pi++){
	int currentMoveCount = 0;

	for (int bno=0;bno<_NO_OF_BINS;bno++){
	int allowedType = permutations[pi][bno];
	for(int btype = 0; btype<_BOTTLE_TYPES;btype++){
	if (allowedType!=btype){
	currentMoveCount += input[bno][btype];
	}
	}
	}

	String currentPermutation = permutationString(pi);

	if ((this.optMoveCount == -1) \|\|
	(currentMoveCount < optMoveCount) \|\|
	((currentMoveCount == optMoveCount) && (currentPermutation.compareTo(optPermutation)<0))){

	this.optMoveCount = currentMoveCount;
	this.optPermutation = currentPermutation;
	}
	}

	return optPermutation+" "+optMoveCount;
	}

	public void solve(){
	int[][] inputBottles = new int[_NO_OF_BINS][_BOTTLE_TYPES];
	while (in.hasNextInt()){
	for(int i = 0;i<_NO_OF_BINS;i++){
	for (int j=0;j<_BOTTLE_TYPES;j++){
	inputBottles[i][j] = in.nextInt();
	}
	}
	out.println(getOPTConfiguration(inputBottles));
	}
	}


	public static void main(String[] args) {
	Main binPackingSolver = new Main();
	binPackingSolver.solve();
	}

	}

view raw uva102.java hosted with ❤ by GitHub

Please leave a comment if you have any question/comment. Happy coding!

Tag: Java

UVa 371. Ackermann Function

See Also

UVa 713. Adding Reversed Numbers

See Also

UVa 10664. Luggage

See Also

UVa 102. Ecological Bin Packing | with Brute-force search