import java.util.*;
//=========================
// Custom Timeout Exception
//=========================
class TimeoutException extends Exception {
public TimeoutException() {
super();
}
public TimeoutException(String message) {
super(message);
}
}
//=====================================
// Utility that Adds, Counts, and Times
//=====================================
class Util {
public static Integer timeLimitMs = 500;
public static Long count = 0L;
private static Long t0 = 0L;
public static Long add(Long a, Long b)
throws TimeoutException {
count++;
if (count % 10000 == 0) {
checkTime();
}
return Math.addExact(a, b);
}
public static void start() {
count = 0L;
t0 = System.nanoTime();
}
public static Double stop() {
return elapsedMs();
}
private static Double elapsedMs() {
return (System.nanoTime() - t0)/1000000d;
}
private static void checkTime()
throws TimeoutException {
if (elapsedMs() > timeLimitMs) {
throw new TimeoutException(timeLimitMs + " ms limit exceeded.");
}
}
}
//==========================
// Generic Abstract Function
//==========================
abstract class Func<In, Out> {
public abstract Out call(Func<In, Out> self, In x)
throws TimeoutException;
public Out call(In x)
throws TimeoutException {
return this.call(this, x);
}
}
//==========================
// Generic Memoized Function
//==========================
class MemoizedFunc<In, Out> extends Func<In, Out> {
private Map<In, Out> cache = new HashMap<In, Out>();
private Func<In, Out> otherFunc;
public MemoizedFunc(Func<In, Out> func) {
this.otherFunc = func;
}
public Out call(Func<In, Out> self, In x)
throws TimeoutException {
if (!cache.containsKey(x)) {
cache.put(x, otherFunc.call(self, x));
}
return cache.get(x);
}
}
//============================
// Abstract Fibonacci Function
//============================
abstract class Fib extends Func<Integer, Long> {
}
//============================
// Memoized Fibonacci Function
//============================
class MemoizedFib extends MemoizedFunc<Integer, Long> {
MemoizedFib(Fib func) {
super(func);
}
}
//===========================
// Amnesic Fibonacci Function
//===========================
class AmnesicFib extends Fib {
public Long call(Func<Integer, Long> self, Integer i)
throws TimeoutException {
if (i == 0) { // return first Fibonacci number
return 0L;
}
else if (i == 1) { // return second Fibonacci number
return 1L;
}
else if (i > 0) { // return ith Fibonacci number
return Util.add(
self.call(self, i-2),
self.call(self, i-1));
}
else { // return ith "negafibonacci" number
return Util.add(
self.call(self, i+2),
-1 * self.call(self, i+1));
}
}
}
//===========================
// Eidetic Fibonacci Function
//===========================
class EideticFib extends MemoizedFib {
EideticFib() {
super(new AmnesicFib());
}
}
//===========================
// Grinder Fibonacci Function
//===========================
class GrinderFib extends Fib {
public Long call(Func<Integer, Long> self, Integer i)
throws TimeoutException {
//----------------------------------------
// 1 multiplier => Fibonacci number
// -1 multiplier => "negafibonacci" number
// 0 is the "bipolafibonacci" number
//----------------------------------------
Integer multiplier = i < 0 ? -1 : 1;
Integer magnitude = multiplier * i;
Long f2 = -1L;
Long f1 = 1L;
Long f0 = 0L;
for (Integer j = 0; j < magnitude; j++) {
f2 = f1;
f1 = f0;
f0 = Util.add(f2, (multiplier * f1));
}
return f0;
}
}
//===========================
// Unitary Fibonacci Function
//===========================
class UnitaryFib extends MemoizedFib {
UnitaryFib() {
super(new GrinderFib());
}
}
//===========================
// Lacunar Fibonacci Function
//===========================
class LacunarFib extends Fib {
public Long call(Func<Integer, Long> self, Integer i)
throws TimeoutException {
Double sqrt5 = Math.sqrt(5);
Double phi = (1 + sqrt5)/2;
Double phiHat = -1/phi;
Double phiPowI = Math.pow(phi, i);
Double phiHatPowI = Math.pow(phiHat, i);
Double fib = (phiPowI - phiHatPowI)/sqrt5;
return Math.round(fib);
}
}
//=======
// Report
//=======
public class FunkyFibs {
private final static int STACK_OVERFLOW = 1;
private final static int DATATYPE_OVERFLOW = 2;
private final static int TIMEOUT = 3;
private final static String[] PRTF = { "%5s", "%55s", "%12d", "%12.3f" };
private final static String[] PRTH = { "%5s", "%55s", "%12s", "%12s" };
private static void printData(Func<Integer, Long> F, String[] seqNums, int i0) {
String nm = F.getClass().getName();
Integer n;
Long Fn = null; // nth Fibonacci number
Double dt = 0d; // delta (change in) time in ms
Double sumTm = 0d; // sum of times
Long sumCt = 0L; // sum of counts (number of operations)
Integer err; // error code
//---------------------------------------
// print one data row per sequence number
//---------------------------------------
for (Integer i = i0; i < seqNums.length; i++) {
err = 0;
n = Integer.parseInt(seqNums[i]);
Util.start();
try {
Fn = F.call(n);
}
catch(StackOverflowError soe) {
Fn = null;
err = STACK_OVERFLOW;
}
catch(TimeoutException toe) {
Fn = null;
err = TIMEOUT;
}
catch(Exception e) {
Fn = null;
err = DATATYPE_OVERFLOW;
}
dt = Util.stop();
sumTm += dt;
sumCt += Util.count;
printDataRow(n, Fn, Util.count, dt, nm, err);
}
//----------------------------------------------------
// if more than one sequence number, print summary row
//----------------------------------------------------
if (seqNums.length - i0 > 1) {
printDataRow(null, null, sumCt, sumTm, "TOTALS", 0);
System.out.println();
}
}
private static void printHeaderRow() {
System.out.println("FunkyFibs: " + (new Date()).toString());
System.out.println();
System.out.printf(PRTH[0], "i");
System.out.printf(PRTH[1], "Fib(i)");
System.out.printf(PRTH[2], "operations");
System.out.printf(PRTH[3], "time (ms)");
System.out.println();
System.out.printf(PRTH[0], "-----");
System.out.printf(PRTH[1], "------------------------------------------------------");
System.out.printf(PRTH[2], "-----------");
System.out.printf(PRTH[3], "-----------");
System.out.println();
}
private static void printDataRow
(Integer n, Long Fn, Long ct, Double dt, String name, Integer err) {
if (n != null) {
System.out.printf(PRTF[0], n.toString());
}
else {
System.out.printf(PRTF[0], "");
}
if (Fn == null && err == 0) {
System.out.printf(PRTF[1], "");
}
else {
switch(err) {
case 0:
System.out.printf(PRTF[1], Fn);
break;
case STACK_OVERFLOW:
System.out.printf(PRTF[1], "STACK_OVERFLOW");
break;
case DATATYPE_OVERFLOW:
System.out.printf(PRTF[1], "DATATYPE_OVERFLOW");
break;
case TIMEOUT:
System.out.printf(PRTF[1], "TIMEOUT");
break;
default:
System.out.printf(PRTF[1], "UNEXPECTED_ERROR");
break;
}
}
System.out.printf(PRTF[2], ct);
System.out.printf(PRTF[3], dt);
System.out.print(' ');
System.out.print(name);
System.out.println();
}
public static void unoReport(Func<Integer, Long> fib, String[] args, int i0) {
printHeaderRow();
printData(fib, args, i0);
if (args.length == 1) {
System.out.println();
}
}
public static void comboReport(String[] args, int i0) {
printHeaderRow();
printData(new AmnesicFib(), args, i0);
printData(new EideticFib(), args, i0);
printData(new GrinderFib(), args, i0);
printData(new UnitaryFib(), args, i0);
printData(new LacunarFib(), args, i0);
if (args.length == 1) {
System.out.println();
}
}
public static void main(String[] args) {
if (args.length == 0) {
return;
}
switch(args[0].toLowerCase()) {
case "amnesic":
unoReport(new AmnesicFib(), args, 1);
break;
case "eidetic":
unoReport(new EideticFib(), args, 1);
break;
case "grinder":
unoReport(new GrinderFib(), args, 1);
break;
case "unitary":
unoReport(new UnitaryFib(), args, 1);
break;
case "lacunar":
unoReport(new LacunarFib(), args, 1);
break;
default:
comboReport(args, 0);
break;
}
}
}
