Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


Ooh, 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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: