FOOTAlgorithmSimple.java

import java.util.*;

public class FOOTAlgorithmSimple {
    //Constants
    private static final int NUM_OUTCOMES = 10;      //Number of possible outcomes to identify
    private static final int MAX_TESTS = 15;         //Total number of candidate tests generated
    private static final int SELECTED_TESTS = 10;    //Number of best tests selected based on entropy

    public static void main(String[] args) {
        //Generate 15 random binary test vectors (each with 15 true/false bits)
        boolean[][] allTests = generateAllTests();
        
        //Print the generated test candidates
        System.out.println("All " + MAX_TESTS + " test candidates:");
        printTests(allTests);

        //Select the 10 most informative tests (based on entropy of test bits)
        boolean[][] selectedTests = selectTopTests(allTests);
        
        System.out.println("\nSelected " + SELECTED_TESTS + " tests (highest entropy):");
        printTests(selectedTests);

        //Generate a random probability distribution across the 10 outcomes
        double[] probabilities = generateProbabilities();
        
        System.out.println("\nOutcome probabilities:");
        for (int i = 0; i < NUM_OUTCOMES; i++) {
            System.out.printf("Outcome %d: %.4f\n", i+1, probabilities[i]);
        }

        //Calculate the total entropy (uncertainty) of the outcome probabilities
        double entropy = calculateEntropy(probabilities);
        System.out.printf("\nEntropy: %.4f bits\n", entropy);

        //Run FOOT algorithm to find average number of tests needed to identify correct outcome
        double avgTests = runFOOT(selectedTests, probabilities);
        System.out.printf("\nAverage tests needed: %.4f\n", avgTests);

        //Print the ratio of avg tests vs theoretical minimum (entropy)
        System.out.printf("Ratio (avg tests / entropy): %.4f\n", avgTests / entropy);
    }

    //Generates 15 test vectors, each with 15 random true/false values
    private static boolean[][] generateAllTests() {
    boolean[][] tests = new boolean[MAX_TESTS][NUM_OUTCOMES];
    Random rand = new Random();
    Set<String> seenTests = new HashSet<>();

    for (int i = 0; i < MAX_TESTS; i++) {
        boolean[] test = new boolean[NUM_OUTCOMES];
        
        //Assign exactly 5 true and 5 false
        Arrays.fill(test, 0, NUM_OUTCOMES / 2, false);
        Arrays.fill(test, NUM_OUTCOMES / 2, NUM_OUTCOMES, true);
        
        //Shuffle the array to randomize positions
        for (int j = NUM_OUTCOMES - 1; j > 0; j--) {
            int swapIndex = rand.nextInt(j + 1);
            boolean temp = test[j];
            test[j] = test[swapIndex];
            test[swapIndex] = temp;
        }
        
        //Ensure uniqueness
        String testKey = Arrays.toString(test);
        while (seenTests.contains(testKey)) {
            // Reshuffle if duplicate
            for (int j = NUM_OUTCOMES - 1; j > 0; j--) {
                int swapIndex = rand.nextInt(j + 1);
                boolean temp = test[j];
                test[j] = test[swapIndex];
                test[swapIndex] = temp;
            }
            testKey = Arrays.toString(test);
        }
        
        seenTests.add(testKey);
        tests[i] = test;
    }
    return tests;
    }

    // Print all test vectors to console as 0s and 1s
    private static void printTests(boolean[][] tests) {
        for (int i = 0; i < tests.length; i++) {
            System.out.print("Test " + (i+1) + ": ");
            for (int j = 0; j < tests[i].length; j++) {
                if (tests[i][j]) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
    }

    //Select the 10 tests with the highest entropy scores
    private static boolean[][] selectTopTests(boolean[][] allTests) {
        double[] scores = new double[MAX_TESTS];

        //Calculate entropy score for each test
        for (int i = 0; i < MAX_TESTS; i++) {
            scores[i] = calculateTestScore(allTests[i]);
        }

        //Sort tests by entropy score in descending order using bubble sort
        for (int i = 0; i < MAX_TESTS - 1; i++) {
            for (int j = 0; j < MAX_TESTS - i - 1; j++) {
                if (scores[j] < scores[j + 1]) {
                    //Swap the scores
                    double tempScore = scores[j];
                    scores[j] = scores[j + 1];
                    scores[j + 1] = tempScore;
                    
                    //Swap the test vectors accordingly
                    boolean[] tempTest = allTests[j];
                    allTests[j] = allTests[j + 1];
                    allTests[j + 1] = tempTest;
                }
            }
        }

        //Return the best 10 tests
        boolean[][] topTests = new boolean[SELECTED_TESTS][NUM_OUTCOMES];
        for (int i = 0; i < SELECTED_TESTS; i++) {
            for (int j = 0; j < NUM_OUTCOMES; j++) {
                topTests[i][j] = allTests[i][j];
            }
        }
        return topTests;
    }

    //Compute entropy of a test vector based on how many true or false values it contains
    private static double calculateTestScore(boolean[] test) {
        int countTrue = 0;
        for (boolean b : test) {
            if (b) countTrue++;
        }
        int countFalse = NUM_OUTCOMES - countTrue;
        
        double pTrue = countTrue / (double) NUM_OUTCOMES;
        double pFalse = countFalse / (double) NUM_OUTCOMES;
        
        double entropy = 0;
        if (pTrue > 0) entropy -= pTrue * Math.log(pTrue) / Math.log(2);
        if (pFalse > 0) entropy -= pFalse * Math.log(pFalse) / Math.log(2);
        
        return entropy;
    }

    //Generate a random probability distribution for the 10 outcomes
    private static double[] generateProbabilities() {
        double[] probs = new double[NUM_OUTCOMES];
        Random rand = new Random();
        double sum = 0;
        
        //Fill array with random values
        for (int i = 0; i < NUM_OUTCOMES; i++) {
            probs[i] = rand.nextDouble();
            sum += probs[i];
        }
        
        //Normalize it so the total sum equals to 1
        for (int i = 0; i < NUM_OUTCOMES; i++) {
            probs[i] /= sum;
        }
        
        return probs;
    }

    //Calculate the Shannon entropy of the full outcome distribution
    private static double calculateEntropy(double[] probs) {
        double entropy = 0;
        for (double p : probs) {
            if (p > 0) {
                entropy -= p * Math.log(p) / Math.log(2);
            }
        }
        return entropy;
    }

    //Run FOOT algorithm on all outcomes and return average number of tests used
    private static double runFOOT(boolean[][] tests, double[] probs) {
        double totalTests = 0;
        
        //Try every possible true outcome from 0 to 9
        for (int target = 0; target < NUM_OUTCOMES; target++) {
            int testsUsed = simulateFOOT(tests, probs, target);
            totalTests += testsUsed;
        }

        //Average number of tests used to identify outcome
        return totalTests / NUM_OUTCOMES;
    }

    //Simulate FOOT algorithm for a single true outcome
    private static int simulateFOOT(boolean[][] tests, double[] probs, int target) {
        boolean[] possible = new boolean[NUM_OUTCOMES]; //Tracks remaining valid outcomes
        for (int i = 0; i < NUM_OUTCOMES; i++) {
            possible[i] = true;
        }

        int testsUsed = 0;
        int remaining = NUM_OUTCOMES;

        //Continue testing while more than 1 outcome remains
        while (remaining > 1) {
            //Find the best test to split remaining outcomes
            int bestTest = findBestTest(tests, possible, probs);
            boolean targetResult = tests[bestTest][target]; //Result of the test on the true outcome

            //Eliminate outcomes that produce a different test result
            for (int i = 0; i < NUM_OUTCOMES; i++) {
                if (possible[i] && tests[bestTest][i] != targetResult) {
                    possible[i] = false;
                    remaining--;
                }
            }

            testsUsed++; //Count the test
        }

        return testsUsed;
    }

    //Find the test that gives the highest information gain among remaining outcomes
    private static int findBestTest(boolean[][] tests, boolean[] possible, double[] probs) {
        int bestTest = 0;
        double maxGain = -1;

        for (int i = 0; i < tests.length; i++) {
            double gain = calculateInfoGain(tests[i], possible, probs);
            if (gain > maxGain) {
                maxGain = gain;
                bestTest = i;
            }
        }

        return bestTest;
    }

    //Calculate information gain of a test given remaining possible outcomes
    private static double calculateInfoGain(boolean[] test, boolean[] possible, double[] probs) {
        double pTrue = 0, pFalse = 0;

        //Split probabilities based on test result (true/false)
        for (int i = 0; i < NUM_OUTCOMES; i++) {
            if (possible[i]) {
                if (test[i]) pTrue += probs[i];
                else pFalse += probs[i];
            }
        }

        //Calculate entropy of the "true" group
        double hTrue = 0;
        if (pTrue > 0) {
            for (int i = 0; i < NUM_OUTCOMES; i++) {
                if (possible[i] && test[i]) {
                    double p = probs[i] / pTrue;
                    hTrue -= p * Math.log(p) / Math.log(2);
                }
            }
        }

        //Calculate entropy of the "false" group
        double hFalse = 0;
        if (pFalse > 0) {
            for (int i = 0; i < NUM_OUTCOMES; i++) {
                if (possible[i] && !test[i]) {
                    double p = probs[i] / pFalse;
                    hFalse -= p * Math.log(p) / Math.log(2);
                }
            }
        }

        //Calculate current total entropy of remaining outcomes
        double currentEntropy = 0;
        for (int i = 0; i < NUM_OUTCOMES; i++) {
            if (possible[i]) {
                double p = probs[i] / (pTrue + pFalse);
                if (p > 0) currentEntropy -= p * Math.log(p) / Math.log(2);
            }
        }

        //Return how much the test reduces the current entropy
        return currentEntropy - (pTrue * hTrue + pFalse * hFalse);
    }
}