4 ms·
I am in a problem solving mood. Termination can be proved for finite graph with sink as: For every grain, compute its distance to the sink along the shortest ro
by im2w1l 12y ago
I am in a problem solving mood. Termination can be proved for finite graph with sink as:
For every grain, compute its distance to the sink along the shortest route. For grains that entered the sink, use 0. Sort the values and put them in a vector. Note that there are finitely many possible vectors for a given number of grains and a given graph. Compare vectors lexicographically. With every topple at least one grain comes closer to the sink. This means that the vector decreases for every topple.
- Sniffnoy 12y agoOoh, that's more elegant than the direction I was going with (which I'm not sure would have worked). Note that the "sort, put in vector, order lexicographically" can be rephrased as "keep a vector of how many grains are at each distance, compare lexicographically". I think that makes it a little clearer.