Algorithm to reach a number in a fixed amount of steps using addition, division and multiplication only

Question

Working on a game at work and at one point in the game the player is tossed into a bonus game. The amount they need to win is predetermined, however we'd like to come up with an algorithm which uses addition, multiplication and division to get to that amount in x amount of steps. The amount of steps would be known ahead of time as well, so the algorithm would just need to figure out how to use that amount of steps to reach the number.

The only computations you can use are +1 through +15, x2, x4, /2, /4. You can exceed the target number during the steps, but must end up at the target number on the last step. The step amount is typically between 15 and 30 and you always start at 0.

For example: Amount: 100, Steps: 10 == +10, +2, x2, +4, x4, +10, /2, +15, +15, +9

Amount: 40, Steps: 12 == +15, +1, +5, +2, +1, /2, *4, +6, +6, /4, +5, *2

I'm curious if there something like this might already exist? I'm sure we can come up with something, but I didn't want to re-invent the wheel if there is a common algorithm that could handle the job.

---

Update: Made a few minor changes to @FryGuy's code to make it the route it takes to reach the target number somewhat random. His solution worked great as-is, but after seeing it working and taking into consideration comments by @Argote and @Moron, I realized it needed to have a level of randomization in it to make it appealing to our players. Added +1 over 10 steps to get to a target number of 10 works great, but is 'boring' in terms of how we would be using it. Much thanks to everyone who commented and answered.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CR
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int targetNumber = 20;
                int steps = 13;
                int[] route = null;
                Boolean routeAcceptable = false;

                // Continue choosing routes until we find one that is acceptable (doesn't average above or target win, but does exceed it at least once)
                while(!routeAcceptable)
                {
                    routeAcceptable = CalculateRoute(targetNumber, steps, out route) && route.Average() < targetNumber && route.Max() > targetNumber;
                }

                foreach (int i in route.Reverse())
                {
                    Console.WriteLine(i);
                }
                Console.WriteLine("-----------------------");
                Console.ReadLine();
            }
        }

        static Boolean CalculateRoute(int targetNumber, int numSteps, out int[] route)
        {
            int maxValue = targetNumber * 16;
            bool[,] reachable = new bool[numSteps + 1, maxValue];

            // build up the map
            reachable[0, 0] = true;
            for (int step = 0; step < numSteps; step++)
            {
                for (int n = 0; n < maxValue; n++)
                {
                    if (reachable[step, n])
                    {
                        foreach (int nextNum in ReachableNumbersFrom(n))
                        {
                            if (nextNum < maxValue && nextNum > 0)
                            {
                                reachable[step + 1, nextNum] = true;
                            }
                        }
                    }
                }
            }

            // figure out how we got there
            int[] routeTaken = new int[numSteps + 1];
            int current = targetNumber;
            for (int step = numSteps; step >= 0; step--)
            {
                routeTaken[step] = current;
                bool good = false;

                // Randomize the reachable numbers enumeration to make the route 'interesting'
                foreach (int prev in RandomizedIEnumerbale(ReachableNumbersFromReverse(current)))
                {
                    if (prev < targetNumber * 8)
                    {
                        if (reachable[step, prev])
                        {
                            current = prev;
                            good = true;

                            // Avoid hitting the same number twice, again to make the route 'interesting'
                            for (int c = numSteps; c >= 0; c--)
                            {
                                reachable[c, prev] = false;
                            }
                            break;
                        }
                    }
                }

                if (!good)
                {
                    route = routeTaken;
                    return false;
                }
            }

            route = routeTaken;
            return true;
        }

        static IEnumerable<int> ReachableNumbersFrom(int n)
        {
            // additions
            for (int i = 1; i <= 15; i++)
            {
                yield return n + i;
            }

            // mults/divides
            yield return n / 2;
            yield return n / 4;
            yield return n * 2;
            yield return n * 4;
        }

        static IEnumerable<int> ReachableNumbersFromReverse(int n)
        {
            // additions
            for (int i = 1; i <= 15; i++)
            {
                if (n - i >= 0)
                    yield return n - i;
            }

            // mults/divides
            if (n % 2 == 0)
                yield return n / 2;
            if (n % 4 == 0)
                yield return n / 4;
            yield return n * 2;
            yield return n * 4;
        }

        static IEnumerable<int> RandomizedIEnumerbale(IEnumerable<int> enumerbale)
        {
            Random random = new Random(System.DateTime.Now.Millisecond);
            return (
                from r in
                    (
                        from num in enumerbale
                        select new { Num = num, Order = random.Next() }
                    )
                orderby r.Order
                select r.Num
                );
        }
    }
}

Answer 1

I would use dynamic programming. First, build a map of which numbers are reachable from each step, then backtrack to find out how you could've gotten there:

void CalculateRoute(int targetNumber, int numSteps)
{
    int maxValue = targetNumber * 16;
    bool[,] reachable = new bool[numSteps + 1, maxValue];

    // build up the map
    reachable[0, 0] = true;
    for (int step = 0; step < numSteps; step++)
    {
        for (int n = 0; n < maxValue; n++)
        {
            if (reachable[step, n])
            {
                foreach (int nextNum in ReachableNumbersFrom(n))
                {
                    if (nextNum < maxValue && nextNum >= 0)
                        reachable[step + 1, nextNum] = true;
                }
            }
        }
    }

    // figure out how we got there
    int current = targetNumber;
    for (int step = numSteps; step >= 0; step--)
    {
        Console.WriteLine(current);

        bool good = false;
        foreach (int prev in ReachableNumbersFromReverse(current))
        {
            if (reachable[step, prev])
            {
                current = prev;
                good = true;
                break;
            }
        }

        if (!good)
        {
            Console.WriteLine("Unable to proceed");
            break;
        }
    }
}

IEnumerable<int> ReachableNumbersFrom(int n)
{
    // additions
    for (int i = 1; i <= 15; i++)
        yield return n + i;

    // mults/divides
    yield return n / 2;
    yield return n / 4;
    yield return n * 2;
    yield return n * 4;
}

IEnumerable<int> ReachableNumbersFromReverse(int n)
{
    // additions
    for (int i = 1; i <= 15; i++)
        yield return n - i;

    // mults/divides
    if (n % 2 == 0)
        yield return n / 2;
    if (n % 4 == 0)
        yield return n / 4;
    yield return n * 2;
    yield return n * 4;
}

Answer 2

work backwards from your desired solution
with your division and multiplication only being by 2's and 4's, it makes it easy to know when you can or can't perform those operations
and then, for the last 4-5 steps you can just make it arbitrarily return to 0

To add to this; you can use random operations in the initial phase, checking that you aren't performing illegal operations, and you should also include a check for range. You don't want to end up with a number like 400 and then have to divide it by 4 a bunch of times as your last operations, to get back to 0.

Answer 3

You can brute force it with a search tree that is N levels deep where N is the number of steps. This would be O(m^n) where m is the number of operations allowed.

There is probably a better algorithm but this should work for smaller values of N.

For example, use {Breadth, Depth}-First Search or A*.