Okay, my question this morning is inspired by trying to solve a problem for my sons (5, and 2.5 years old).
Over the course of the last several years, we've collected several sets of toy train tracks. Some are "Thomas the Train", some are Tomy, and some are GeoTrax. Toy tracks are generally built in a similar fashion -- several pieces of varying lengths and curvatures. There are generally straight, curved (usually either an eighth or quarter circle), split curved (a straight track with a curved bifurcation), and bridges (these tend to differ from set to set, but the simplest is a straight up and straight down, with a tunnel to support the middle). For an example of Geotrax, see http://www.fisher-price.com/us/geotrax/default_flash.asp
Arranging these tracks can involve a lot of trial and error. Although I'd be happy to let my sons engage in this work (heck, that should be the fun of it), I end up doing quite a bit of it (and I find it a bit tedious setting up and rearranging tracks all the time). What I'd like is to be able to have a program that would give me workable (i.e., closed) arrangements. I'm not really sure even what sort of algorithm I'd use. I'd need to start with the number of pieces of each type.
As a "simple" example (I hope simple, anyway):
- Imagine 4 pieces, curved quarter-circles A, B, C, D, with corresponding ends 1,2, 3, 4, 5, 6, 7, 8.
- Imagine 2 more straight pieces, E and F, with ends 9, 10, 11, and 12.
- 1, 2, 9, 10, 3, 4, 5, 6, 11, 12, 7, 8 should work as an elongated circle
- 1, 2, 9, 10, 3, 4, 11, 12, 5, 6, 7, 8 should not, since the 8 and 1 won't be able to connect.
I'm sure there must be some algorithm for this. I've also considered trying to create track objects (with length, curvature, endpoint properties) and then laying them on a virtual grid and simply trying to determine by coordinate whether the figure is closed or not. In a way, this is as much an exercise to expand my knowledge of perl/programming, so any pointers as to direction would be appreciated.
If not, it's not a hugely important problem, though it would let me lay out designs for my children without spending an hour shifting track around.