UVa371: Ackermann Function

UVa371.java

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();
	}

}