Abstract Fibonaccii Hack
A Fibonacci algorithm that runs using an abstract parent class.
Introduction
This notebook uses Class definitions, ArrayLists, and Hash Maps. My hypothosis is these data structures are probably the most widely used in the Java language.
Popcorn Hacks
-
Provide some reasons why you agree with my hypothesis?
- class definitions support object oriented programing, which is common in Java
- Arraylists are common in java bcuz they are easily changeable and provide fast access to index items
-
hashmaps are also common in java bcuz they can provide fast lookup times
-
Provide some data structures that you think might rival my hypothesis?
- linked lists are good for dynamic memory allocation and fast insert/delete
- stacks are used in recursion and parsing expressions
-
trees can search/insert/delete
-
Categorize data structure mentioned, tested by college board tested, widely used, fast.
- Class definition: cb tested this and it is widely used and fast
- arraylists: tested by cb, widely used, and fast
- hashmaps: tested by cb, widely used, and fast
- stacks: tested by cb, widely used, and fast
- trees: not with cb, but widely used and fast
/*
* Creator: Nighthawk Coding Society
* Mini Lab Name: Fibonacci sequence, featuring a Stream Algorithm
*
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.stream.Stream;
/* Objective will require changing to abstract class with one or more abstract methods below */
abstract class Fibo {
String name; // name or title of method
int size; // nth sequence
int hashID; // counter for hashIDs in hash map
ArrayList<Long> list; // captures current Fibonacci sequence
HashMap<Integer, Object> hash; // captures each sequence leading to final result
/*
Zero parameter constructor uses Telescoping technique to allow setting of the required value nth
@param: none
*/
public Fibo() {
this(8); // telescope to avoid code duplication, using default as 20
}
/*
Construct the nth fibonacci number
@param: nth number, the value is constrained to 92 because of overflow in a long
*/
public Fibo(int nth) {
this.size = nth;
this.list = new ArrayList<>();
this.hashID = 0;
this.hash = new HashMap<>();
//calculate fibonacci and time mvc
this.calc();
}
/*
This Method should be "abstract"
Leave method as protected, as it is only authorized to extender of the class
Make new class that extends and defines calc()
Inside references within this class would change from this to super
Repeat process using for, while, recursion
*/
protected abstract void calc();
/*
Number is added to fibonacci sequence, current state of "list" is added to hash for hashID "num"
*/
public void setData(long num) {
list.add(num);
hash.put(this.hashID++, list.clone());
}
/*
Custom Getter to return last element in fibonacci sequence
*/
public long getNth() {
return list.get(this.size - 1);
}
/*
Custom Getter to return last fibonacci sequence in HashMap
*/
public Object getNthSeq(int i) {
return hash.get(i);
}
/*
Console/Terminal supported print method
*/
public void print() {
System.out.println("Calculation method = " + this.name);
System.out.println("fibonacci Number " + this.size + " = " + this.getNth());
System.out.println("fibonacci List = " + this.list);
System.out.println("fibonacci Hashmap = " + this.hash);
for (int i=0 ; i<this.size; i++ ) {
System.out.println("fibonacci Sequence " + (i+1) + " = " + this.getNthSeq(i));
}
}
}
public class FiboFor extends Fibo {
public FiboFor() {
super();
}
public FiboFor(int nth) {
super(nth);
}
@Override
protected void calc() {
super.name = "FiboFor extends Fibo";
long limit = this.size;
// for loops are likely the most common iteration structure, all the looping facts are in one line
for (long[] f = new long[]{0, 1}; limit-- > 0; f = new long[]{f[1], f[0] + f[1]})
this.setData(f[0]);
}
/*
Tester class method.
*/
static public void main(int... numbers) {
for (int nth : numbers) {
Fibo fib = new FiboFor(nth);
fib.print();
System.out.println();
}
}
}
FiboFor.main(2, 5, 8);
Calculation method = FiboFor extends Fibo
fibonacci Number 2 = 1
fibonacci List = [0, 1]
fibonacci Hashmap = {0=[0], 1=[0, 1]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
Calculation method = FiboFor extends Fibo
fibonacci Number 5 = 3
fibonacci List = [0, 1, 1, 2, 3]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
Calculation method = FiboFor extends Fibo
fibonacci Number 8 = 13
fibonacci List = [0, 1, 1, 2, 3, 5, 8, 13]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3], 5=[0, 1, 1, 2, 3, 5], 6=[0, 1, 1, 2, 3, 5, 8], 7=[0, 1, 1, 2, 3, 5, 8, 13]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
fibonacci Sequence 6 = [0, 1, 1, 2, 3, 5]
fibonacci Sequence 7 = [0, 1, 1, 2, 3, 5, 8]
fibonacci Sequence 8 = [0, 1, 1, 2, 3, 5, 8, 13]
public class FiboStream extends Fibo {
public FiboStream() {
super();
}
public FiboStream(int nth) {
super(nth);
}
@Override
protected void calc() {
super.name = "FiboStream extends Extends";
// Initial element of stream: new long[]{0, 1}
// Lambda expression calculate the next fibo based on the current: f -> new long[]{f[1], f[0] + f[1]}
Stream.iterate(new long[]{0, 1}, f -> new long[]{f[1], f[0] + f[1]})
.limit(super.size) // stream limit
.forEach(f -> super.setData(f[0]) ); // set data in super class
}
/*
Tester class method.
*/
static public void main(int... numbers) {
for (int nth : numbers) {
Fibo fib = new FiboFor(nth);
fib.print();
System.out.println();
}
}
}
FiboStream.main(2, 5, 8);
Calculation method = FiboFor extends Fibo
fibonacci Number 2 = 1
fibonacci List = [0, 1]
fibonacci Hashmap = {0=[0], 1=[0, 1]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
Calculation method = FiboFor extends Fibo
fibonacci Number 5 = 3
fibonacci List = [0, 1, 1, 2, 3]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
Calculation method = FiboFor extends Fibo
fibonacci Number 8 = 13
fibonacci List = [0, 1, 1, 2, 3, 5, 8, 13]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3], 5=[0, 1, 1, 2, 3, 5], 6=[0, 1, 1, 2, 3, 5, 8], 7=[0, 1, 1, 2, 3, 5, 8, 13]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
fibonacci Sequence 6 = [0, 1, 1, 2, 3, 5]
fibonacci Sequence 7 = [0, 1, 1, 2, 3, 5, 8]
fibonacci Sequence 8 = [0, 1, 1, 2, 3, 5, 8, 13]
Popcorn Hacks
Objectives of these hacks are …
- Understand how to fullfill abstract class requirements using two additional algoritms.
- Use inheritance style of programming to test speed of each algorithm. To test the speed, a.) be aware that the first run is always the slowest b.) to time something, my recommendation is 12 runs on the timed element, through out highest and lowest time in calculations.
- Be sure to make a tester and reporting methods.
.85 basis for text based comparison inside of Jupyter Notebook lesson
Hacks
Assign in each Team to build a Thymeleaf UI for portfolio_2025 using this example https://thymeleaf.nighthawkcodingsociety.com/mvc/fibonacci as basis. Encorporate into Algorithms menu.
Since there are three teams, one team can do Fibo, others Pali and Factorial. Assign this to people that are struggling for contribution and presentation to checkpoints.
.90 basis for FE presentation in Thymmeleaf to BE call in Spring
Abstract class for reporting times and methods
import java.util.ArrayList;
import java.util.HashMap;
/* Abstract Class with Abstract Methods */
abstract class Algorithm {
String name;
int size;
ArrayList<Long> results;
HashMap<Integer, Long> times;
public Algorithm(int size) {
this.size = size;
this.results = new ArrayList<>();
this.times = new HashMap<>();
this.calc();
}
protected abstract void calc();
public void setData(long result, long time) {
results.add(result);
times.put(results.size(), time);
}
public void print() {
System.out.println("\n" + name + " Results:");
System.out.println("Results: " + results);
System.out.println("Execution Times: " + times);
System.out.println("Average Time: " + getAverageTime() + " ns");
}
public long getAverageTime() {
long total = 0;
for (long time : times.values()) {
total += time;
}
return total / times.size();
}
}
/* Fibonacci Using Iteration */
class FiboFor extends Algorithm {
public FiboFor(int size) {
super(size);
this.name = "Fibonacci Using Iteration";
}
@Override
protected void calc() {
long startTime = System.nanoTime();
long a = 0, b = 1;
for (int i = 0; i < size; i++) {
setData(a, System.nanoTime() - startTime);
long temp = a;
a = b;
b = temp + b;
}
}
}
/* Factorial Using Recursion */
class FactorialRec extends Algorithm {
public FactorialRec(int size) {
super(size);
this.name = "Factorial Using Recursion";
}
@Override
protected void calc() {
long startTime = System.nanoTime();
for (int i = 1; i <= size; i++) {
setData(factorial(i), System.nanoTime() - startTime);
}
}
private long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
}
/* Palindrome Checker Using Character Comparison */
class Palindrome extends Algorithm {
public Palindrome(int size) {
super(size);
this.name = "Palindrome Checker";
}
@Override
protected void calc() {
long startTime = System.nanoTime();
for (int i = 0; i < size; i++) {
String sample = "level"; // Sample palindrome to test
boolean isPalindrome = checkPalindrome(sample);
setData(isPalindrome ? 1 : 0, System.nanoTime() - startTime);
}
}
private boolean checkPalindrome(String str) {
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) return false;
left++;
right--;
}
return true;
}
}
/* Tester Class */
public class Tester {
public static void main(String[] args) {
int testSize = 10;
FiboFor fibo = new FiboFor(testSize);
fibo.print();
FactorialRec fact = new FactorialRec(testSize);
fact.print();
Palindrome palindrome = new Palindrome(testSize);
palindrome.print();
}
}
Fibonacci Using Iteration: Results: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] Execution Times (ns): [1773, 801, 533, 763, 773, 696, 610, 1094, 879, 638] Average Time: 856.0 ns
Factorial Using Recursion: Results: [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800] Execution Times (ns): [1986, 1705, 1185, 1943, 1351, 1331, 1170, 2119, 1658, 1958] Average Time: 1640.6 ns
Palindrome Checker: Results: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Execution Times (ns): [2944, 947, 771, 851, 1248, 902, 883, 1909, 1032, 607] Average Time: 1209.4 ns
Recursion
// Recursive method to calculate Fibonacci numbers
public static int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
int count = 12;
System.out.println("First " + count + " Fibonacci numbers (using recursion):");
for (int i = 0; i < count; i++) {
System.out.print(fib(i) + " ");
}
First 12 Fibonacci numbers (using recursion):
0 1 1 2 3 5 8 13 21 34 55 89
Iteration
int count = 12;
long a = 0, b = 1;
System.out.println("First " + count + " Fibonacci numbers (using iteration):");
for (int i = 0; i < count; i++) {
System.out.print(a + " ");
long next = a + b;
a = b;
b = next;
}
First 12 Fibonacci numbers (using iteration):
0 1 1 2 3 5 8 13 21 34 55 89
Palindrome check
// Method to check if a string is a palindrome
public static boolean isPalindrome(String str) {
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
String testString = "tacocat"; // Change this to test other strings
if (isPalindrome(testString)) {
System.out.println(testString + " is a palindrome.");
} else {
System.out.println(testString + " is not a palindrome.");
}
tacocat is a palindrome.