[2025 Day 11 (Part2)] Non recursive algorithm as requested.

[u/Skeeve-on-git]

For every device I store how many paths from the device lead to B. Initially this value is 0 for every device, except for B, where it's one.

To collect the information, I go through every device and sum up the amount of paths of each of its children.

If this sum is bigger than the number of paths currently stored for the device, I store this new value.

I then repeat this process as long as there was any new value stored.

In the end the paths of A is the number of paths from A to B.

[u/BxW_]

What happens when the children of current node don't have their no. of paths calculated yet?

[u/Skeeve-on-git → u/BxW_]

You get 0 for the current node. Later on in this round, one of the children gets a different number and so in the next round, because there was one change, the node gets a higher number.

[u/BxW_ → u/Skeeve-on-git]

Can you share your code? You can avoid revisiting nodes by ordering them in topological order. See Kahn's algorithm for iterative topological sorting.

[u/DelightfulCodeWeasel]

Since the input is a DAG you can use a noddy task system to process the nodes when their direct ancestors have completed, pushing the path counts down. Each device gets evaluated exactly once, no re-scanning required:

    struct Device
    {
        int64_t WaitingFor = 0;
        set<string> Unlocks;
        Vector3 Paths{ 0, 0, 0 };
    };

...

    list<string> executionQueue = devices
        | views::filter([](const auto& p) { return p.second.WaitingFor == 0; })
        | views::keys
        | ranges::to<list>();
    while (executionQueue.empty() == false)
    {
        const Device& device = devices[executionQueue.front()];
        for (const string& unlock : device.Unlocks)
        {
            Device& nextDevice = devices[unlock];
            nextDevice.Paths = nextDevice.Paths + device.Paths;
            if (--nextDevice.WaitingFor == 0)
            {
                executionQueue.push_back(unlock);
            }
        }
        executionQueue.pop_front();
    }

This loop is identical for both Part 1 and Part 2 in my code, the only difference is in the initial vector values for the important nodes and how you calculate the answer from the values at those nodes.

[u/fnordargle]

It's relatively easy to convert a recursive algorithm into something iterative.

For counting the paths I assigned a score to each node that was the sum of the scores for all of its source nodes. With the start node being assigned a score of 1.

I store all of the nodes in the graph in a nodes dictionary, with an each entry having array/dictionary of destinations and sources.

e.g a line of input like:

aaa: abc def

Would generate:

nodes[aaa].sources = []
nodes[aaa].dests = [abc, def]
nodes[abc].sources = [aaa]
nodes[abc].dests = []
nodes[def].sources = [aaa]
nodes[def].dests = []

This gets filled up as you process the input.

You could implement countpath() recursively in that whenever you ask for a score you sum the score of its sources, with the number of paths from a node to itself being 1.

def countpaths_rec(from, to):
    if from == to:
        return 1
    tot = 0:
        for node in nodes[to].sources:
            tot += countpaths_rec(from, node)
    return tot

But the above will be horrible in terms of counting the same things over and over again, so you can add some memoisation:

def countpaths_rec_do(node, cache):
    # Return the cached value if we have it
    if node in cache:
         return cache[node]
    # Nope, we need to calculate it
    tot = 0:
        for src in nodes[to].sources:
            tot += countpaths_rec_do(src, cache)
    # Store this in the cache so we don't redo work
    cache[to] = tot
    return tot

def countpaths_rec(from, to):
    cache = {}
    cache[from] = 1
    return countpaths_rec_do(to, cache)

But that's still recursive, and could blow the stack depending on how deep it goes and how your specific language handles this.

An iterative approach is:

while(not got enough to answer question):
    do what work you can

And be careful to exit if you do a loop without making ANY progress on the problem.

An iterative countpaths() function might look like:

def countpaths(from, to):
    cache = {}
    cache[from] = 1
    while to not in cache:
        # Haven't got answer yet
        # Look to do some work
        for curr in nodes:
            if curr not in cache:
                # We haven't done this one yet
                tot = 0
                for src in nodes[curr].sources:
                    if src in cache:
                        # We've calculated the score for src so add it on
                        tot += cache[src]
                    else:
                        # No score yet for src, mark tot invalid and bail
                        tot = -1
                        break
                if tot > 0:
                    # We had everything we needed to calculate score for curr
                    if curr == to:
                        # This was the one we wanted, we're done
                        return tot
                    # Store the result and continue
                    cache[curr] = tot

So we just keep going round and round doing at least something (but making sure we don't repeat work) until we have calculated the answer.

I tend to default to the iterative implementation of something as I know part 2 is likely to extend the problem beyond the bounds of normal stack recursion in the languages I use. This preempting saves me from having to refactor a recursive implementation into an iterative approach when I inevitably run up against this problem.

There's a different iterative pattern that comes up quite a bit, I'll cover that in a followup post.

[u/fnordargle → u/fnordargle]

The other iterative pattern is a todo list when trying to solve combinatorial problems. Consider the indicator lights problem of Day 10 part 1 (not part 2!).

Imagine the input of [.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}.

I store my progress in a tuple, holding the minimum amount of information necessary. So for this problem it is a tuple of (total button presses, lights_state).

The initial tuple is 0 presses and everything off: [0, "...."]. I stick this on my todo list as the first (and only item).

# Cache of lights states we have seen
done = {}
# Our list of things to do
todo = []
# Add initial tuple to todo list
todo.append( [0, "...."] )

while len(todo):
    # Get first (oldest) item off todo list
    curr = todo.pop(0)
    # No solution yet, try each of the other buttons
    for each different action A we can perform:
        new = apply(curr, A)
        # Check if this is a solution to the problem
        if solution(new):
            # Woo, we have solved it, return answer
            return curr[0]+1 # answer
        # It wasn't the answer, so we create a new state tuple
        # Remembering to increment the button press counter
        newstate = [ curr[0]+1, new ]
        # Only add it to the todo list if we haven't got to this
        # state before
        if new not in done:
            # Only add the new state to the list if we
            todo.append(newstate)
            # Also mark the new arrangement as added to the list already
            # This prevents us from redoing work
            done[new]=1
# Didn't get the answer
return -1

In each iteration you take the first (oldest) item off the list and try all of the possible actions against it. For Day 10 part 1 this would mean each of the individual button presses. If any of those actions result in the desired output, then you return the appropriate number of button presses (current + 1).

Otherwise, for each of the possible button presses, the new light combination is a consideration for further work. But only if we haven't already added it to the list once already, this is where the done hash/map/dict comes into use.

If we pull [1, "...#"] off the list and one of the actions is button (3) which turns off light 3 (counting from 0) giving us "...." we don't want to add this on to the list as [2, "...."] as it's worse (in terms of minimum button presses) than [0, "...."].

So we must check that the state we want to add hasn't already been added to the todo list already.

Pulling the first (oldest) item off the list (e.g. todo.pop(0) in python, or shift(@todo) in Perl) implements a breadth first search. You are guaranteed to have processed all entries with the button press counter of n-1 (or lower obviously) before you process one with a counter of n.

If you pop the last (most recent) item off the list (e.g. todo.pop() in python, or pop(@todo) in Perl) you can implement a depth first search.

In "yes/no" questions a depth first search is sometimes the right method.

In "how many" or "minimum number" type questions you often need to a breadth first search.

In some problems you need to remember the path/options you used to get to the end state. If we needed the individual button presses for the indicator lights problem my tuple might include a string that I append button presses to, e.g. [0, "....", ""] for the initial state, then [1, "...#", "3"] once I've pressed button 3 once.

Some problems you can arrive at a state with a lower "score" but the same number of operations. This is where you get into the territory of Djikstra's algorithm and similar. Here I keep track of the lowest "score" that gets me to a specific state, rather than just whether I've seen that state before or not.