Traversing an infinite graph using Dijkstra's algorithm to maximize cookie production speed

Question

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.

How can I reduce the memory usage of this algorithm?

---

• 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.

Answer 1

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

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 2^x. With it, it is x + 1. The memory savings increase with the number of parameters in an exponential fashion.

I don't fully understand what you're doing here, but I think you need to revisit the design of the heap. It's far too interconnected. The Graph class shouldn't know about the internals of the heap. My implementation uses some generic code:

public interface PriorityQueue<K, V>
    where V : IComparable<V>
{
    int Count { get; }
    bool ContainsKey(K key);
    void Add(K key, V priority);
    void Update(K key, V priority);
    V this[K key] { get; }
    KeyValuePair<K, V> Pop();
}

public interface IWeightedGraph<TVertex, TWeight>
{
    IEnumerable<(TVertex, TWeight)> Edges(TVertex vertex);
}

public static TWeight ShortestPath<TVertex, TWeight>(this IWeightedGraph<TVertex, TWeight> g, TVertex source, TVertex sink, Func<TWeight, TWeight, TWeight> add)
    where TWeight : IComparable<TWeight>
{
    // Simple Dijkstra implementation.
    PriorityQueue<TVertex, TWeight> q = new BinaryHeap<TVertex, TWeight>();
    var closed = new HashSet<TVertex>();

    q.Add(source, default(TWeight)); // Assume that default(TWeight) is zero
    while (true)
    {
        (var u, var w) = q.Pop();
        if (Equals(u, sink)) return w;

        closed.Add(u);

        foreach ((var v, var x) in g.Edges(u))
        {
            if (closed.Contains(v)) continue;

            var relaxed = add(w, x);

            if (!q.ContainsKey(v)) q.Add(v, relaxed);
            else if (relaxed.CompareTo(q[v]) < 0) q.Update(v, relaxed);
        }
    }
}

class CookieCutterGraph : IWeightedGraph<CookieCutterState, double>
{
    ...
}

var soln = g.ShortestPath(emptyState, targetState, (a, b) => a + b);

To use a Fibonacci heap, I would just have to change one line. Also, the heap maintains the mapping from states to whatever internal representation it needs to implement ContainsKey and Update. There's only one instance of each state because the only hard reference is kept inside the heap, and when the heap finishes with it it removes it from its internal structures.

It's true that my ShortestPath method only finds the weight and not the path. The fully general way to find the path is to have a list of popped vertices to their costs, and then run it backwards looking for vertices which have a suitable edge to the current start of the partial path. This still guarantees keeping only one instance of each vertex live (two if it's a struct, because you have a copy in closed as well) without having a class-level cache which leaks memory.

On the bright side, as far as I can tell Vertex.Node is never cleared, so is keeping unnecessary FibonacciHeapNode instances around; and having references from both Vertex to FibonacciHeapNode and vice versa costs an extra 8 bytes for a reference on a 64-bit machine.

For further memory saving around the heap, you could look at using a pairing heap, which uses less state per node but is claimed to be typically at least as fast as a Fibonacci heap.

Answer 2

You can reduce the memory footprint by using BitVector32 instead of bool. A bool in .NET occupies a full word in memory. A BitVector32 allows you to store the equivalent of 32 bools the same memory space.

By replacing all of the bool fields in State with a single BitVector32, I was able to reduce State's memory footprint from 68 bytes to 12 (as measured by Marshal.SizeOf<State>()). Since State is the key in the dictionary, that adds up to a decent reduction in memory usage overall.

After applying my changes to your master branch and running for 1,000,000 steps, the memory usage of the state dictionary dropped from ~215 MB to ~167 MB (as measured by the Visual Studio profiler). After 5,000,000 steps, it dropped from ~864 MB to ~671 MB.

You could push this technique even further by packing numeric values into bit vectors. There are some examples of doing so in the docs.

Here's a sample of the code that I used. All of the changes happened within State. I opted for the most convenient refactoring path... there might be a more efficient/performant way to code all this.

BitVector32 bits;

private const int ReinforcedIndexFingerMask = 1 << 0;
private const int CarpalTunnelPreventionCreamMask = 1 << 1;

public bool ReinforcedIndexFinger
{
    get => bits[ReinforcedIndexFingerMask];
    set => bits[ReinforcedIndexFingerMask] = value;
}

public bool CarpalTunnelPreventionCream
{
    get => bits[CarpalTunnelPreventionCreamMask];
    set => bits[CarpalTunnelPreventionCreamMask] = value;
}

As an added bonus, I think you could simplify the GetHashCode() and Equals() implementations by comparing the bit vector directly, rather than comparing every value individually.

Answer 3

I will try to tackle your problem a bit differently. Your main question is:

How can I reduce the memory usage of this algorithm?

Regardless, I would first have a closer look into other path finding algorithms, such as

• A* (or IDA*) with a decent heuristic function

• Floyd Warshall Algorithm

Compare the algorithms and evaluate the right one:

• How long does each algorithm take (Time Complexity)?
• How much space do each algorithm use (Space Complexity)?
• Does it have to be optimal or is an approximation good enough?

Regarding your question, the space complexity is relevant. For example, if one vertex takes up 1KB and your algorithm uses 100'000'000 vertices, then even if you can optimize your vertex down to 0.5KB, it's still bad.

---

Another option is to improve your current Dijkstra implementation:

• Only keep a subset of the vertices in the memory (e.g. the highest promising ones). You can serialize the others on your hard disk (e.g. with Protocol Buffers).
• Still minimize your vertex' size as suggested by others (just because you can)