Re:Playing with model trains and calling it graph theory
by mpettitt on Friday May 03, 2019 @11:59AM
(#19819548)
It is surprisingly difficult to build train tracks given a set of parts, even without taking junctions into account - there is a challenge about it on Stack Overflow's Programming Puzzle site (https://codegolf.stackexchange.com/q/116607/66060) and there is only one answer in the two years it's been there. In some ways, real life engineers have it easier - they don't have to plan routes based on the parts in the box!
[ Parent
| on HN ]
Re:Playing with model trains and calling it graph theory
by Someone on Friday May 03, 2019 @02:36PM
(#19821050)
Having only one answer in two years doesn’t imply the problem is hard.
I would think all ‘large enough’ puzzles of this kind are easy. You build a rectangle (needs four corners. If you don’t have those, no closed curve is possible), and use pairs of left-over curves to add detours to the straight ends, possibly compensating for an odd number of straight edges. I would guess there is an analog to Euler’s formula (https://en.wikipedia.org/wiki/Euler%27s_formula) that describes what number of small corners, large corners, and straight ends can form a large closed curve.
I also suspect ‘large enough’ isn’t that large, probably everything over 16 pieces or so (Smaller problems may be non-standard because they require effort to avoid overlap)