December 1 Review Ticket

[drewreed2005]

Palette Puzzle

When we thought about what to make for this project, we considered how. some people can mix colors together to create the perfect shade of a certain color just by sight. We wanted to test people's ability to determine how much red, green or blue was in a certain color just by looking at it. Our project ended up with three parts that are described below.

Sorting - Algorithms, Inheritance, Abstraction

Drew was responsible for this part of the project.

Two pages of our project use sorting algorithms, since it's the core of the game we're working on. All four sorting algorithms (bubble, selection, insertion and merge) are fully functional in the backend and accommodate an unlimited number of colors to sort.

Inheritance and Abstraction

Because we were asked to collect certain analytical data on each sort, we decided to use a parent class SortingAlgorithm to accommodate timing the sort, incrementing comparisons and incrementing swaps/insertions.

public class SortingAlgorithm {
    protected int swaps;
    protected int comparisons;
    protected long executionTime;

    public SortingAlgorithm() {
        this.swaps = 0;
        this.comparisons = 0;
        this.executionTime = 0;
    }
    // ... etc.
    public Integer[][] sort(HashMap<Integer, Integer[]> colorValues, int chosenColor) {
        this.swaps = 0; // this method is used to get the execution time
        this.comparisons = 0;
        long startTime = System.nanoTime();
        Integer[][] steps = performSort(colorValues, chosenColor);
        long endTime = System.nanoTime();
        executionTime = endTime - startTime;
        return steps; // we log the steps of the sorting process for one of our pages
    }

    protected Integer[][] performSort(HashMap<Integer, Integer[]> colorValues, int chosenColor) {
        // this method is overwritten by each subclass to be their specific type of sort
        return null;
    }

    protected void swap(Integer[] array, Integer i, Integer j) { // this is used by multiple that swap
        Integer temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        swaps++;
    }

    protected int compare(HashMap<Integer, Integer[]> colorValues, int i, int j, int chosenColor) {
        comparisons++; // this is used in all sorting algorithm subclasses
        return Integer.compare(colorValues.get(i)[chosenColor], colorValues.get(j)[chosenColor]);
    }

Algorithms

Rather than paste the code here, see the table below for all sorting algorithms in full.

Sort Type	Link
Bubble	Click here
Selection	Click here
Insertion	Click here
Merge	Click here

We would like to highlight some usage of the parent attributes and methods in these sorting algorithms.

// bubble sort
  for (int i = 0; i < colorValues.size(); i++) {
      boolean swapped = false; // flag to track whether any swaps were made in this pass
      for (int j = 0; j < colorValues.size() - i - 1; j++) {
          if (compare(colorValues, indices[j], indices[j + 1], chosenColor) > 0) {
              swap(indices, j, j + 1);
              swapped = true;
          }
      }

// selection sort
    for (int i = 0; i < colorValues.size() - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < colorValues.size(); j++) {
            if (compare(colorValues, indices[j], indices[minIndex], chosenColor) < 0) {
                minIndex = j;
            }
        }
        swap(indices, i, minIndex);

Implementation

At the time of writing this, we haven't been able to deploy our backend, but it works locally for use in the live demonstration. Click here for the 5000-color sorting page.

The actual Palette Puzzle sorting game was second priority, since it did not incorporate the important analysis data like the big sort did. However, because the backend works identically between the two pages, all that is missing is the remaining frontend work for this page.

Fibonacci

Haseeb was responsible for most of this portion of the project.

For our two additional fibonacci sequence algorithms, we decided to use the Golden Ratio Formula and Matrix Exponentiation. Other methods are finished in notes but not yet implemented into the backend, since these two were the first priority. Both of them are now fully implemented on the backend, each using the parent class Fibonacci to its advantage.

Fibonacci Method	Link
Golden Ratio	Click here
Matrix Exponentiation	Click here

Inheritance and Abstraction

Like the sorting algorithms, the fibonacci methods make use of an overarching parent class. It is show below:

public class Fibonacci {
    protected long executionTime;

    public Fibonacci() {
        this.executionTime = 0;
    }

    public long getExecutionTime() {
        return executionTime;
    }

    public long calculate(Integer num) {
        long startTime = System.nanoTime();
        long result = performCalculation(num);
        long endTime = System.nanoTime();
        executionTime = endTime - startTime;
        return result;
    }

    protected long performCalculation(Integer num) {
        // to be implemented by each fibonacci algorithm
        return 0;
    }
}

Once again, this allows us to time all methods in the same manner.

Implementation

Click here for the fronted site that works locally and will be universally functional after deployment.

Analysis - Calculations and Measurements

AJ was largely responsible for assisting with frontend-to-backend connections, which included formatting the sort data on the big sort simulation page.

On the big sort page, data on execution time, comparisons and swaps are collected in a table below as the sorting process is visualized. Since 5000 different colors are being sorted, we met expectations with the size of the sort.

Fibonacci timing stats from the parent class work perfectly with the currently finished methods (see image below) and, because of the use of inheritance, all future methods will continue to function.

Individual: Key Commits

Drew

The commit I wanted to highlight the most is this one. This was my initial attempt at putting all of the sorting algorithms I had created separately in a Jupyter Notebook into the Springboot repository and connecting it to an API Controller. I was very excited to discover that, aside from a minor problem with comparisons and swaps not resetting when occurring in multiple sorts, everything worked extremely well.

Aside from fully-functional and consistent sorting algorithms, which I touched on earlier, I wanted to point out some efficient use of class declarations in the API Controller page. I created an array of all of the different subclass Objects, but declared it as an array of SortingAlgorithms. If I hadn't done this, I wouldn't have been able to iterate through with the for loop below and use class methods, since using a more general declaration like Object would make the method unrecognizable.

      SortingAlgorithm[] algorithmArray = {bigBubbleSort, bigSelectionSort, bigInsertionSort, bigMergeSort};
      long[] averageTimes = {0, 0, 0, 0}; // indexes: 0 = bubble, 1 = selection, 2 = insertion, 3 = merge
      // 100 sorts
      for (int i = 0; i < 100; i++) {
          for (int j = 0; j < 4; j++) {
              algorithmArray[j].sort(data, chosenColor);
              averageTimes[j] += (algorithmArray[j].getExecutionTime() * 0.01);
          }
      }

I also added a boolean big to the SortRequest mapping object that allowed for this one API to be used for both the smaller-scale Palette Puzzle game and the large-scale demonstration. Using the big boolean, many different runs of the sorts can be used to get a more accurate average runtime for the sorts. This is implemented on the big sort page shown earlier.

Haseeb

There's two major commits I would like to highlight in lieu of this project. The first being this one, which pertains to Palette Puzzle.

function colorBoxes(){
        var totalSlots = [_0, _1, _2, _3, _4, _5, _6, _7];
        for(let i = 0; i < 8; i++){
            rgbGen();
            RGB = [`${r}`, `${g}`, `${b}`];
            console.log(RGB);
            totalSlots[i].style.backgroundColor = `rgb(${r}, ${g}, ${b})`;
        }
    }

This commit was important as it helped me clean up the code for efficiency purposes. Previously, I had super rough frontend code that was super messy, as there were a lot of things just repeated/copy-pasted. I realized I could just use recursion by putting all the slots in an array and applying changes on all of them using a for loop.

The second commit I would like to highlight is [this one](), which is related to the addition of the Fibonacci methods.

        public static void main(String[] args) {
            Instant timerStart = Instant.now();
            int n = 20; 
            double goldenRatio = (1 + Math.sqrt(5)) / 2;
            long fibonacciNumber = calculateFibonacciWithGoldenRatio(n, goldenRatio);
            System.out.println("Fibonacci number at position " + n + ": " + fibonacciNumber);
            Instant timerStop = Instant.now();
            Duration elapsedTime = Duration.between(timerStart, timerStop);
            System.out.println("elapsed time: " + elapsedTime.toNanosPart() + " nanoseconds");
        }

        private static long calculateFibonacciWithGoldenRatio(int n, double goldenRatio) {
            double phiToN = Math.pow(goldenRatio, n);
            double negativePhiToMinusN = Math.pow(-goldenRatio, -n);
            double result = (phiToN - negativePhiToMinusN) / Math.sqrt(5);
            return Math.round(result);
        }

This code is for the first extra method I coded for the Fibonacci requirements, in which I utilized the Golden Ratio formula to calculate the specific number at the specified index of the Fibonacci Sequence. I also added a timer, which shows how long the process takes, this was implemented for the second method too.

AJ

AJ was not present on December 1 to add comments about his commits.

What's Left

There are a few things that remain to be done.

First priority is implementing the other fibonacci methods into the backend. We have methods that work, but they haven't been brought over yet. We also plan to make the frontend page a bit nicer.

We had some trouble with deployment due to issues with the backend, but we plan to have it deployed by the end of the day.

The frontend for the Palette Puzzle game itself is another priority, since it adds another layer to the sorting algorithm by explaining it step-by-step.

[Ekamjot-Kaire]

Everything looks close to being done. Some possible improvements could be to include more of a visual aspect to the fibonacci part of the project, if there is time (ill add more comments later)