Get the latest tech news
Possibly all the ways to get loop-finding in graphs wrong
[Simon Tatham, 2024-09-09] In my puzzle collection, there are many games in which you have to connect points together by edges, making a graph, and the puzzle rules say you must avoid making any loop in the graph. Examples are Net, Slant, and some configurations of Bridges (although not the default one).
So I thought I’d write up all my mistakes, as a case study in all the ways you can solve this particular problem wrongly – and also in how much effort you can waste by not managing to find the existing solution in the literature. A solved Net puzzle in wrapping modeA torus has a property that makes it fundamentally different from a plane or a sphere, known in algebraic topology as a ‘nontrivial H 1 homology group’. You can walk from above this loop to below it by wrapping round the edges of the grid.So the face dsf loop-finding algorithm wouldn’t detect it at all!This incident is the current holder of my personal record for ‘most esoteric mathematical concept that I’ve ever seen cause a real software bug’.
Or read this on Hacker News
