Background
The platform I'm coding for is an esoteric scripting engine coded some time ago that only has limited capabilities. Because I cannot produce a version of the engine that can be run on its own (it needs to attach to a running instance of a game), I have translated the code into C# with limitations to mimic the scripting environment.
Task
Given a blackbox function, find the secret in the blackbox using the following limitations:
- You can only declare variables of the decimal type
- You have access to the elementary operators (+, -, /, *, ==, != ...etc) except for modulo (%)
- You cannot use library functions (Math.Floor() ...etc)
The function is as follows:
//the function returns the result of the operation between the secret and the input
//available operations are: >=, >, <=, <, ==, !=
public static bool BlackBox(decimal num, string operation)
{
//the secret is always an integer greater than or equal to 1
//you can assume a maximum value the secret cannot exceed, if it helps
//in this example, the maximum is 400000
decimal secret = 317810;
if (operation == ">=" && secret >= num)
return true;
else if (operation == ">" && secret > num)
return true;
else if (operation == "<=" && secret <= num)
return true;
else if (operation == "<" && secret < num)
return true;
else if (operation == "==" && secret == num)
return true;
else if (operation == "!=" && secret != num)
return true;
else
return false;
}
Implementation
My first thought was to try a binary search but was stumped because I can't use floor/ceil. I settled on using a Fibonacci search to get to the ballpark and follow with a linear search to find the exact value:
public static void Main()
{
decimal num1 = 0;
decimal num2 = 1;
//use fibonacci sequence to get close to ballpark
while (BlackBox(num2, ">="))
{
decimal temp = num1;
temp += num2;
num1 = num2;
num2 = temp;
}
//use linear search for the last mile
while (BlackBox(num1, "!="))
{
num1++;
}
Console.WriteLine("The number is " + num1.ToString());
}
This works well for small numbers but as the range of the secret grows the linear portion can get quite time consuming (I chose a worst-case example for this implementation for this reason) because the scripting engine is no where near as efficient as C#. My question is how can I improve this algorithm in terms of performance? Or, is there another algorithm that can perform better than Fibonacci search (maybe a binary search implementation is possible)?