Trabajando en un juego en el trabajo y en un punto del juego, el jugador es lanzado a un juego de bonificación. La cantidad que necesitan para ganar está predeterminada, sin embargo, nos gustaría encontrar un algoritmo que use la suma, la multiplicación y la división para llegar a esa cantidad en x cantidad de pasos. La cantidad de pasos también se conocería con anticipación, por lo que el algoritmo solo necesitaría descubrir cómo usar esa cantidad de pasos para alcanzar el número.

Los únicos cálculos que puede usar son +1 a +15, x2, x4, / 2, / 4. Puede exceder el número objetivo durante los pasos, pero debe terminar en el número objetivo en el último paso. La cantidad de pasos es típicamente entre 15 y 30 y siempre comienza en 0.

Por ejemplo: Cantidad: 100, Pasos: 10 == +10, +2, x2, +4, x4, +10, / 2, +15, +15, + 9

Cantidad: 40, Pasos: 12 == +15, +1, +5, +2, +1, / 2, * 4, +6, +6, / 4, +5, * 2

Tengo curiosidad si ya existe algo como esto? Estoy seguro de que podemos encontrar algo, pero no quería reinventar la rueda si hay un algoritmo común que pueda manejar el trabajo.

Update: realizó algunos cambios menores en el código de @ FryGuy para que sea la ruta que se necesita para alcanzar el número objetivo de forma aleatoria. Su solución funcionó muy bien tal cual, pero después de verla funcionar y tomar en cuenta los comentarios de @Argote y @Moron, me di cuenta de que necesitaba tener un nivel de aleatorización para que fuera atractiva para nuestros jugadores. Agregó +1 en 10 pasos para llegar a un número objetivo de 10 funciona muy bien, pero es "aburrido" en términos de cómo lo estaríamos usando. Muchas gracias a todos los que comentaron y respondieron.

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
                );
        }
    }
}