6
\$\begingroup\$

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:

  1. You can only declare variables of the decimal type
  2. You have access to the elementary operators (+, -, /, *, ==, != ...etc) except for modulo (%)
  3. 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)?

\$\endgroup\$
3
  • 3
    \$\begingroup\$ What stops you from using a Fibonacci search in the second round (and third, etc)? \$\endgroup\$ – vnp Jul 11 '20 at 20:11
  • \$\begingroup\$ @vnp Interesting idea! Would definitely beat a linear search \$\endgroup\$ – Setsu Jul 11 '20 at 22:42
  • \$\begingroup\$ this implementation uses 121419 iterations to reach the answer \$\endgroup\$ – Setsu Jul 12 '20 at 18:58
4
\$\begingroup\$

My first thought was to try a binary search but was stumped because I can't use floor/ceil.

I'm not sure why you thought that would matter. Once you have a maximum number, all you need is to divide the difference between max and min in half and add it to min on each iteration. Here's a simple example that works for your test case. It might need tweaking for some edge cases.

const int MAX_SECRET = 400000;
public static decimal Find()
{
    decimal max = MAX_SECRET;
    decimal min = 0;
    while(max - min > 0)
    {
        decimal temp = ((max - min) / 2) + min;
        if(BlackBox(temp,"=="))
        {
            return temp;
        }
        if(BlackBox(temp, "<"))
        {
            max = temp;
        }
        else
        {
            min = temp;
        }
    }
    return max;
}

EDIT

Did some more thinking on the efficiency of this algorithm. The problem mainly stems from using a decimal to represent an int. A decimal doesn't want to do integer math. One way around this is, to use the rounding functionality when the maximum precision is exceeded, to make a floor function. This greatly reduces the iterations to find the target number.

Here's one way that uses the max precision of C#:

const int MAX_SECRET = 400000;
public static decimal Find()
{
    decimal max = MAX_SECRET;
    decimal min = 0;
    decimal count = 0;
    while(max - min > 0)
    {
        decimal temp = floor((max - min) / 2) + min;
        if(BlackBox(temp,"=="))
        {
            return temp;
        }
        if(BlackBox(temp, "<"))
        {
            max = temp;
        }
        else
        {
            min = temp;
        }
    }
    return max;
}
const decimal MAX_PRECISION = 10000000000000000000000000000M;
static decimal floor(decimal num)
{
    decimal temp = (num / MAX_PRECISION) * MAX_PRECISION;
    if(temp > num)
    {
        --temp;
    }
    return temp;
}

This cuts the iterations down to the same level as using int's instead of decimal's. To use this in a different language the MAX_PRECISION constant may need to adjusted.

\$\endgroup\$
8
  • \$\begingroup\$ Wow, I had originally thought that because dividing will eventually yield non-integers it would cause problems...looks like I was wrong. Great job! \$\endgroup\$ – Setsu Jul 12 '20 at 16:01
  • \$\begingroup\$ Actually, upon further investigation this answer is quite suboptimal. If you print out the value of temp at each iteration you will see it bounce between two values close to the secret before finally reaching the answer. It's about 50% as efficient as a true binary search. \$\endgroup\$ – Setsu Jul 12 '20 at 18:22
  • \$\begingroup\$ Like my post said it might need some tweaking. Either way this algorithm is a definite improvement in performance, over the fibonacci and the linear search. \$\endgroup\$ – tinstaafl Jul 12 '20 at 18:43
  • \$\begingroup\$ True. This implementation uses 89 iterations to reach the answer \$\endgroup\$ – Setsu Jul 12 '20 at 18:59
  • 1
    \$\begingroup\$ @Setsu - I've added a more efficient algorithm for you to consider. \$\endgroup\$ – tinstaafl Jul 13 '20 at 17:05
1
\$\begingroup\$

I know this was not your concern. But let me point out anyway that the BlackBox implementation can be simplified quite a bit.

if (operation == ">=") return secret >= num;
if (operation == ">") return secret > num;
// ...
return false;
\$\endgroup\$
0
\$\begingroup\$

Using @vnp hint I've implemented a dual loop fibonacci to avoid a linear search:

public static void Main()
{
    decimal num1 = 1;
    decimal num2 = 1;
    decimal num3 = 0;
    decimal num4 = 0;
    decimal min = 0;
    int count = 0;
    
    while (BlackBox(num4, "!="))
    {
        do 
        {
            num3 = num1;
            num3 += num2;
            num1 = num2;
            num2 = num3;
            num3 += min;
            num4 = num1 + min;
            count++;
            Console.WriteLine(num4.ToString());
        }
        while (BlackBox(num3, ">="));
        
        min += num1;
        num1 = 1;
        num2 = 1;
    }
    
    Console.WriteLine("The number is " + num4.ToString() + " in iterations " + count.ToString());
}

This version uses only 182 iterations to find the answer; vastly improved over the original but still loses to the binary search.

\$\endgroup\$
0
\$\begingroup\$

You can indeed solve this using a binary search. In my solution i implemented a recursive method to solve the problem, although a non-recursive version could easily be implemented as well. This solves the problem within O(log n) iterations. It uses 19 iterations to find the secret number of 317810

private static void Main(string[] args)
    {
        int max = 400000;
        int min = 1;
        int current = max / 2;
        binarySearch(max, min, current);
    }

    private static int binarySearch(int max, int min, int current)
    {
        if (BlackBox(current, ">"))
        {
            return binarySearch(max, current, (max + current) / 2);
        }

        if (BlackBox(current, "<"))
        {
            return binarySearch(current, min, (current + min) / 2);
        }

        if (BlackBox(current, "=="))
        {
            return current;
        }

        // secret number is not within range of max/min 
        return -1;
    }
\$\endgroup\$
2
  • \$\begingroup\$ The OP stated that only decimal types may be used, and a binary search using decimal types has already been submitted. \$\endgroup\$ – tinstaafl Jul 15 '20 at 0:26
  • \$\begingroup\$ Unfortunately this implementation relies on the fact that int truncates the fraction portion towards 0. Dealing with the type limitation is what complicates this problem. \$\endgroup\$ – Setsu Jul 17 '20 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.