The objective here is framed as "I want to find a cheapest path that visits a sequence of nodes with specific goal weights [W_1, ..., W_n], in ascending order". This is a bit like a spatial path-finding problem where the objective is to find a path through a fixed sequence of waypoints, except harder, as we're not specifying specific waypoint nodes to visit but only that we visit nodes with some desired characteristic (total weight).
Consider how the state space is encoded -- it isn't valid to model each node in the graph by total weight, as that erases the detail of which plates are currently equipped, which we need to determine the edge costs. That's shown in the diagrams, where each node is represented as a multiset of plate weights.
Another part of the state space encoding is subtler: it's only valid to visit a node with goal weight W if we have previously visited all goal weights W' with W' < W. This constraint is implicitly encoded by the nodes and edges considered in the transition graph, and the ordering of the nodes from left to right. For this problem there's no need to augment the state space with an extra state variable to track how many goals or which goals we've already achieved, that's implicitly tracked through the total weight and the construction of the transition graph. Nodes and edges that violate this have been excluded from the transition graph, e.g. there's no edge drawn from node {0} to node {10, 25} -- as that transition causes the path to fail to visit a node with total weight 15 and total weight 25.
Suppose we were to change the objective from "visit a sequence of nodes with these specific goal weights [W_1, ..., W_n] in ascending order" to "visit a sequence of nodes with these specific goal weights in _any_ order". The problem becomes _much_ harder, a variation of the traveling salesman problem, and starts to resemble some industrial problems, e.g. some kind of resource constrained vehicle routing delivery problem.
This nuance is correct, and handled correctly by the code and diagrams, although the text is unclear. (Although a random ordering of the weights would not make sense for the problem setting, which is warmup sets in the gym.)
> This can be done efficiently via, eg, Dijkstra’s algorithm, but since this is such a small graph, we can also easily enumerate all 36 paths and sort for efficiency.
Brute force enumeration for small problem instances is pragmatic. For larger problems, Dijkstra's algorithm would certainly work, and would also work for more general problems where we're given a graph containing cycles.
For this barbell plate problem we could also exploit the acyclic structure and use bottom-up dynamic programming: maintain a table tracking the cost of the cheapest path to each node, and an auxiliary table tracking the predecessor node or incoming edge per node where the cheapest path was attained, then fill out the tables "bottom up" (or left to right per the diagrams). Less general, but it dodges the need to do a bunch of work maintaining a priority queue of partial paths.
Another fun connection is to the Viterbi algorithm - a completely different real world application to barbell plate optimization - decoding a sequence of noisy observations and trying to reconstruct the most probable trajectory of unobserved states - but the abstract mathematical model & way to attack it computationally is very similar -- construct a DAG, a solution is a least-cost path through the DAG (ignoring all the problem-specific details going into the definition of state spaces, transition graphs, edge costs, etc). c.f. "The Viterbi Algorithm at 50 (2017)" from a couple of months ago: https://news.ycombinator.com/item?id=35897851
edit: i guess another connection is the knapsack problem mentioned in this post -- it can also be framed as a least-cost path through a DAG, and computed bottom-up.
For this barbell plate optimisation problem, the acyclic structure comes from the monotonic increasing sequence of goal weights. For the Viterbi algorithm's problem of inferring a most probable sequence, the acyclic structure comes from each observation being ordered by the observation time. For the knapsack problem, there isn't really a natural problem defined ordering of item take/leave decisions, but the decisions can be sequenced in any arbitrary fixed order.
Consider how the state space is encoded -- it isn't valid to model each node in the graph by total weight, as that erases the detail of which plates are currently equipped, which we need to determine the edge costs. That's shown in the diagrams, where each node is represented as a multiset of plate weights.
Another part of the state space encoding is subtler: it's only valid to visit a node with goal weight W if we have previously visited all goal weights W' with W' < W. This constraint is implicitly encoded by the nodes and edges considered in the transition graph, and the ordering of the nodes from left to right. For this problem there's no need to augment the state space with an extra state variable to track how many goals or which goals we've already achieved, that's implicitly tracked through the total weight and the construction of the transition graph. Nodes and edges that violate this have been excluded from the transition graph, e.g. there's no edge drawn from node {0} to node {10, 25} -- as that transition causes the path to fail to visit a node with total weight 15 and total weight 25.
Suppose we were to change the objective from "visit a sequence of nodes with these specific goal weights [W_1, ..., W_n] in ascending order" to "visit a sequence of nodes with these specific goal weights in _any_ order". The problem becomes _much_ harder, a variation of the traveling salesman problem, and starts to resemble some industrial problems, e.g. some kind of resource constrained vehicle routing delivery problem.