The algorithm you currently use will call the classifier 65 times, once for every element you remove from the original array (and maybe insert back into it). So the aim is to lower that number.
Theoretical minimum number of classifier-calls in worst case
A theoretical minimum for the worst case is 35 times:
When starting with an array of 65, it might be that there is indeed only one set of 9 elements that are of the same color, all other elements being of a different color and occurring 8 times each. In that case those 9 elements can be positioned in C(9 of 65) ways (ignoring order), i.e. 65!/(56!9!) = 31 966 749 880.
Since a call of the classifier has 2 possible outcomes, it divides the number of configurations that were still considered possible into two: one group is still possible, the other no longer is. The most efficient use of the classifier will aim to make that split such that 50% of the configurations is eliminated, whichever the return value (false/true).
In order to get that number of possible configurations to 1 (the final solution) you would need to perform 35 divisions by 2. Or otherwise put, 235 is the first power of 2 that is greater than that 31 billion.
So even if we would know how to use the classifier in the most optimal way, we would still need 35 calls in the worst case.
To be honest, I don't know an algorithm that would be that efficient, but with some randomness and reducing the array size with some bigger steps, you can get a better number on average than 65.
Idea for a guessing strategy
There is approximately 50% chance that a random array of 42 objects will have 9 of the same color. You can verify this by running a large number of simulations.
So why not start with a call to the classifier with only 42 of the 65 objects you have initially picked? With a bit of luck you know after one call that your 9 objects are hidden in an array of 42 instead of 65, which would really trim the number of calls you will make in total. And if not, you just "lost" one call.
In that latter case you could try again with a new selection of 42 objects from that array. You would now certainly include the 23 other objects, as those objects would individually have a tiny bit more likelihood to be among the 9 searched elements. Maybe the classifier returns false again. That's bad luck, but you would continue using different sets of 42 until you get success. On average you will have success after 2.7 calls.
After success on an array of 42, you obviously discard the remaining 23 other objects. Now take 38 as the number of objects you will try with, following the same principle as above.
For driving the selection of the objects in each iteration, add credit to the objects that were not part of the previous selection, and sort all objects by descending credit. The added credit should be higher when the number of non-selected objects is small. Where the credit is the same, use a random order.
An additional precaution can be taken by logging all subsets for which the classifier returned false. If ever you're about to call the classifier again, first check whether it is a subset of one of those earlier made calls. If that is true, then it makes no sense to call the classifier, as it is certain it will return false. This will on average save one call to the classifier.
Implementation
Here is a JavaScript implementation of that idea. This implementation also includes the "bank" (get method) and the classifier. It effectively hides the color from the algorithm.
This code will clear the job for 1000 random test cases and then output the minimum, average and maximum number of times it needed to call the classifier before finding the answer.
I used the BigInt primitive, so this will only run on JS engines that support BigInt.
// This is an implementation of the bank & classifier (not part of the solution)
const {get, classify} = (function () {
const colors = new WeakMap; // Private to this closure
return {
get(length) {
return Array.from({length}, () => {
const obj = {};
colors.set(obj, Math.floor(Math.random()*8)); // assign random color (0..7)
return obj; // Only return the (empty) object: its color is secret
});
},
classify(arr) {
const counts = Array(8).fill(9); // counter for 8 different colors
return !arr.every(obj => --counts[colors.get(obj)]);
}
}
})();
function shuffle(a) {
var j, x, i;
for (i = a.length - 1; i > 0; i--) {
j = Math.floor(Math.random() * (i + 1));
x = a[i];
a[i] = a[j];
a[j] = x;
}
return a;
}
// Solution:
function randomReduce(get, classify) {
// Get 65 objects from the bank, so we are sure there are 9 with the same type
const arr = get(65);
// Track some extra information per object:
const objData = new Map(arr.map((obj, i) => [obj, { rank: 0, bit: 1n << BigInt(i) } ]));
// Keep track of all subsets that the classifier returned false for
const failures = [];
let numClassifierCalls = 0;
function myClassify(arr) {
const pattern = arr.reduce((pattern, obj) => pattern | objData.get(obj).bit, 0n);
if (failures.some(failed => (failed & pattern) === pattern)) {
// This would be a redundant call, as we already called the classifier on a superset
// of this array, and it returned false; so don't make the call. Just return false
return false;
}
numClassifierCalls++;
const result = classify(arr);
if (!result) failures.push(pattern);
return result;
}
for (let length of [42,38,35,32,29,27,25,23,21,19,18,17,16,15,14,13,12,11,10,9]) {
while (!myClassify(arr.slice(0, length))) {
// Give the omited entries an increased likelihood of being seleced in the future
let addRank = 1/(arr.length - length - 1); // Could be Infinity: then MUST use
for (let i = length; i < arr.length; i++) {
objData.get(arr[i]).rank += addRank;
}
// Randomise the array, but ensure that the most promising objects are put first
shuffle(arr).sort((a,b) => objData.get(b).rank - objData.get(a).rank);
}
arr.length = length; // Discard the non-selected objects
}
// At this point arr.length is 9, and the classifier returned true. So we have the 9 elements.
return numClassifierCalls;
}
let total = 0, min = Infinity, max = 0;
let numTests = 1000;
for (let i = 0; i < numTests; i++) {
const numClassifierCalls = randomReduce(get, classify);
total += numClassifierCalls;
if (numClassifierCalls < min) min = numClassifierCalls;
if (numClassifierCalls > max) max = numClassifierCalls;
}
console.log("Number of classifier calls:");
console.log("- least: ", min);
console.log("- most: ", max);
console.log("- average: ", total/numTests);
Performance statistics
The above algorithm needs an average of 35 classifier-calls to solve the problem. In the best case its calls to the classifier always return true, and then 20 calls will have been made. The downside is that the worst case is really bad and can go to 170 or more. But such cases are rare.
Here is a graph of the probability distribution:
In 99% of the cases the algorithm will find the solution in at most 50 classifier calls.
