Tukukkk

Imagine the following situation:

It is the year 20XX. You are a prodigious baker, capable of baking cookies at an astonishing rate of 1 cookie per second. Your archnemesis, an equally excellent baker, challenges you to a bake-off.

In this bake-off, you will need to bake 1,000 cookies total as fast as you possibly can, but you will be allowed to purchase several items during the event to aid in your baking.

First, you may buy a Foo machine at a cost of 10 cookies. It will bake 2 cookies per second. You can permanently double the production rate of all Foo machines with an upgrade which costs 100 cookies.

Second, you may buy a Bar machine at a cost of 80 cookies. It will bake 20 cookies per second. You can permanently double the production rate of all Bar machines with an upgrade which costs 400 cookies.

Additionally, machines costs up as you buy more of them, the cost being multiplied by 1.15 every time (and rounded up). For example, while the first Bar machine costs 80 cookies, the next will cost 92, the next 106, the next 122, the next 141, and so on.

How can you beat your archnemesis? What is the best strategy to bake one thousand cookies as quickly as possible? Do you buy Foo machines as soon as you can afford them and let the production rate rise? Or do you throw in some Bar machines to avoid the diminishing returns? To solve this, you turn to the ancient art of mathematics.

How do we model a situation like this mathematically? From one point in time, there are multiple options, each of which lead to more options... Let's start plotting this out. f for Foo, b for Bar, and F or B for the upgraded Foo and Bar.

Now that we can clearly see that we're essentially building a tree structure, we can turn to graph theory to help us get to our target.

As we've just represented each possible state with a vertex, we can represent the time between each state as the edges between the vertices.

For example, if we start with a production rate of 1 cookie per second and a Foo costs 10 cookies, then we can define the edge from start to 1f, 0b as having a weight of 10 seconds.

Note that we neglected to draw in an important part of the graph—the target. Because our target cookie count is cumulative, it is always better to buy something than not.

At a rate of 1C/s, accumulating 1000C would take 1000s. Buying one Foo would cost 10C, taking 10s to afford, but would increase the total production rate to 3C/s. The remaining 990C (1000C − 10C) would only take 330s to accumulate.

Every vertex would have an edge to the target because it's always an option to simply wait until the required amount of cookies is accumulated, but—assuming that no option involves time travel—the only time waiting is optimal is when affording every other option would take more time than simply waiting to bake the required amount of cookies.

Given all of these conditions, we can simply use a pathfinding algorithm—namely, Dijkstra's Algorithm—to find the shortest route from start to finish.

For ease of debugging, each loop in the algorithm will be self-contained. Our entry point essentially boils down to the following:

private const int target_cookies = 1000;



public static async Task MainAsync(string args)

{

    var graph = new Graph(target_cookies);



    while (!graph.Solved)

    {

        graph.Step();

    }



    // Display the output here.



    await Task.Delay(-1);

}

The Graph class is constructed as follows:

public Graph(int targetCookies)

{

    this.TargetCookies = targetCookies;



    this.queue = new FibonacciHeap();



    this.target = new Vertex

    {

        PreviousName = "target"

    };



    var source = new Vertex

    {

        MinimumCost = 0

    };



    source.Node = this.queue.Insert(source, 0);

    this.vertices = new Dictionary<State, Vertex>();

}

First, what's FibonacciHeap? The implementation details are unimportant for this experiment, but a Fibonacci heap is an extremely fast implementation of a priority queue, a type of collection wherein each item has a priority and the highest-priority item can be popped from the collection. the Fibonacci heap is notable for having a time complexity of Θ(1).

In this case, the priority of each vertex in the queue is its tentative cost (Vertex.MinimumCost), where the vertex with the smallest cost is the first to be popped. Use of a priority queue relies on the "no-time-travel" lemma—formally that no edge has a cost that is less than zero.

Next, the source and target are defined. The source is given a tenative cost of 0 (i.e. it takes 0s to get from the starting state to the starting state), while the target is given a name (for output purposes). The source is then added to the queue as a starting point.

Finally, a dictionary of (State, Vertex) is created. Let's come back to that.

For now, let's look at Vertex:

public class Vertex

{

    public FibonacciHeapNode Node { get; set; }

    public State State { get; set; }

    public float MinimumCost { get; set; } = Single.PositiveInfinity;



    public Vertex Previous { get; set; }

    public string PreviousName { get; set; }



    public Vertex(FibonacciHeapNode node = null, State state = default(State))

    {

        this.Node = node;

        this.State = state;

    }

}

Of note:
- The default tentative cost is infinite, such that literally any value is better than infinity when evaluating.
- Each vertex keeps track of its node in the queue. This is so that priorities can be updated when a better MinimumCost is found.
- The name of the path taken to get to each vertex is stored for human readability when a solution is found.

Now, State:

public struct State

{

    private const float cost_foo = 10;

    private const float cost_bar = 80;



    public const int COST_FOO_UPGRADE = 100;

    public const int COST_BAR_UPGRADE = 400;



    public byte Foos;

    public int FooCost => Cost(cost_foo, this.Foos);



    public bool FooUpgrade;

    public bool FooUpgradeAvailable => !(this.FooUpgrade || this.Foos < 1);



    public byte Bars;

    public int BarCost => Cost(cost_bar, this.Bars);



    public bool BarUpgrade;

    public bool BarUpgradeAvailable => !(this.BarUpgrade || this.Bars < 1);



    public float ProductionRate

    {

        get

        {

            float baseProduction = 1;



            float fooProduction = 2 * this.Foos;

            float barProduction = 20 * this.Bars;



            if (this.FooUpgrade)

            {

                fooProduction *= 2;

            }

            if (this.BarUpgrade)

            {

                barProduction *= 2;

            }



            return baseProduction + fooProduction + barProduction;

        }

    }



    public int AlreadySpent

    {

        get

        {

            int fooCost = Sum(cost_foo, this.Foos);

            int barCost = Sum(cost_bar, this.Bars);



            int totalCookies = fooCost + barCost;



            totalCookies += this.FooUpgrade ? COST_FOO_UPGRADE : 0;

            totalCookies += this.BarUpgrade ? COST_BAR_UPGRADE : 0;



            return totalCookies;

        }

    }



    private static int Cost(float baseCost, int ownedCount)

        => (int)Math.Ceiling(baseCost * Math.Pow(1.15, ownedCount));



    private static int Sum(float baseCost, int count)

    {

        int sum = 0;



        for (int i = 0; i < count; i++)

        {

            sum += Cost(baseCost, i);

        }



        return sum;

    }



    public State(State other)

    {

        this.Foos = other.Foos;

        this.FooUpgrade = other.FooUpgrade;

        this.Bars = other.Bars;

        this.BarUpgrade = other.BarUpgrade;

    }



    public override int GetHashCode()

    {

        unchecked

        {

            int hash = 17;

            hash = (hash * 23) + this.Foos.GetHashCode();

            hash = (hash * 23) + this.FooUpgrade.GetHashCode();

            hash = (hash * 23) + this.Bars.GetHashCode();

            hash = (hash * 23) + this.BarUpgrade.GetHashCode();

            return hash;

        }

    }



    public override bool Equals(object obj)

    {

        return

            obj != null &&

            obj is State other &&

            this.Foos == other.Foos &&

            this.FooUpgrade == other.FooUpgrade &&

            this.Bars == other.Bars &&

            this.BarUpgrade == other.BarUpgrade;

    }



    public static bool operator ==(State lhs, State rhs)

        => lhs.Equals(rhs);



    public static bool operator !=(State lhs, State rhs)

        => !lhs.Equals(rhs);

}

Beautiful, isn't it? 🤢 All of that code, while dreadful to look at, just captures the basic information about a state how many Foos are owned, how many Bars are owned, and if each is upgraded. For utility, State also provides the calculation for the current cost of Foo and Bar, the production rate of the state, and the total number of cookies already spent to reach that state.

With that out of the way, everything we need to understand the logic is defined. So, back to Graph:

public void Step()

{

    var current = this.queue.Pop();



    if (current.Vertex == this.target)

    {

        this.Solved = true;

        return;

    }



    foreach (Path neighbor in this.GetNeighborsOf(current.Vertex))

    {

        float alt = current.Vertex.MinimumCost + neighbor.Cost;

        if (alt < neighbor.To.MinimumCost)

        {

            neighbor.To.MinimumCost = alt;

            neighbor.To.Previous = current.Vertex;

            neighbor.To.PreviousName = neighbor.Name;

            if (neighbor.To.Node == null)

            {

                neighbor.To.Node = this.queue.Insert(neighbor.To, alt);

            }

            else

            {

                this.queue.DecreaseCost(neighbor.To.Node, alt);

            }

        }

    }

}

First, the node with the highest priority is popped from the queue. By definition, this is the vertex with the lowest tentative cost. If the vertex in question is the target, that means that any other option is slower than simply waiting, and thus the solution is found.

Otherwise, the neighbors of the vertex are evaluated and processed. Path is a tiny utility struct:

public struct Path

{

    public Vertex To;

    public float Cost;

    public string Name;



    public Path(Vertex to, float distance, string name)

    {

        this.To = to;

        this.Cost = distance;

        this.Name = name;

    }

}

The next section of code is the entirety of Dijkstra's Algorithm—simply evaluate each neighbor, see if the cost to the neighbor through the current vertex is less than the stored cost (Single.PositiveInfinity by default) and either update the existing queue node or create it if it doesn't already exist.

And now, we get to the final cursed method: GetNeighborsOf.

public IEnumerable<Path> GetNeighborsOf(Vertex from)

{

    State state = from.State;



    var possibilities = new List<Possibility>

    {

        new Possibility("buy foo", state.FooCost, new State(state) { Foos = (byte)(state.Foos + 1) }),

        new Possibility("buy bar", state.BarCost, new State(state) { Bars = (byte)(state.Bars + 1) }),

    };



    if (state.FooUpgradeAvailable)

    {

        possibilities.Add(new Possibility(

            "buy foo upgrade", 

            State.COST_FOO_UPGRADE,

            new State(state) { FooUpgrade = true }));

    }

    if (state.BarUpgradeAvailable)

    {

        possibilities.Add(new Possibility(

            "buy bar upgrade",

            State.COST_BAR_UPGRADE,

            new State(state) { BarUpgrade = true }));

    }



    float production = state.ProductionRate;

    foreach (Possibility possibility in possibilities)

    {

        if (!this.vertices.TryGetValue(possibility.State, out Vertex to))

        {

            to = new Vertex(null, possibility.State);

            this.vertices[possibility.State] = to;

        }



        yield return new Path(to, possibility.Cost / production, possibility.Name);

    }



    yield return new Path(this.target, (this.TargetCookies - state.AlreadySpent) / production, "target");

}

Really worthy of focus here is the last bit, in which the the vertices dictionary created in the constructor is queried. If a State already has a vertex associated with it, then use that; otherwise, create a new vertex to represent the state. As far as I can tell, this is all but necessary. Without it, the "space complexity" for a State with 2 constant parameters would be 2x. With it, it is x + 1. The memory savings increase with the number of parameters in an exponential fashion.

Despite this massive memory save, the Dictionary itself provides an incredible amount of overhead, typically composing well over 75% of the memory allocated for the task. Try as I might, I have been unable to save more than a nominal amount of memory without fundamentally reworking how the dictionary system is used.

In a tiny microcosmic case like this, memory doesn't appear to matter at all. But in a full-scale application of this experiment, State has not 2 constant parameters and 2 dependent parameters, but 5 constant parameters and 12 dependent parameters searching towards 1,000,000 cookies.

• The simplified example given here can be found on this branch.


• The project with full scope can be found on the master branch.


• The original idea to use graph theory to solve this problem was suggested here.