in reply to If I had a Free Two Months...

One problem that's a personal curiosity for me has been this:

Given an inventory of train track pieces (my boys love Thomas), figure out what permutations make connecting, valid layouts. Report back any successful layouts, in descending order of complexity.

I've spent some spare cycles thinking about this one, and I've come to the conclusion that I'm just not smart enough. I could probably able to do it with straights, curves and a pot-load of coffee, but once you throw in switches and cross-over bridges -- fuggetaboutit.

Replies are listed 'Best First'.
Re^2: If I had a Free Two Months...
by Anonymous Monk on Jun 22, 2005 at 16:17 UTC
    This sounds essentially like a graph theory problem. Have a track segments be arcs and the places where they connect be nodes. I don't know exactly what the criteria are for a "connecting, valid layout", but I'll assume it's at least planarity (no tracks crossing one another) and that there always exists a non-zero-length path from a node to itself. The presence of cross-over bridges permit a special case of track-crossing, so graphs with a c.o.b. would be allowed to be non-planar only for the c.o.b. arcs. Switches are just two arcs going to/coming from the same node.

    Once you've got the graph designed, you can start tackling the problem of laying it out spatially so that it fits with the pieces.

[reply]

      That's pretty much what I've thought about so far. The place where my brain just starts to smoke is the switches. Not only does a switch have one 'in' and two 'out' paths, but if you flip it over, one 'out' is in the same place and the other 'out' is in a third place.

      I just can't figure out how the recursion would work in that situation. Fortunately, I'm too busy with paying work to figure that out right now.

[reply]
Re^2: If I had a Free Two Months...
by samizdat (Vicar) on Jun 23, 2005 at 16:47 UTC
    Situations like this are already well-solved in EDA tools like gEDA and other schematic capture and physical layout packages. These challenges would be a good place for Higher-Order Perl applications, as they're microworld problems like the 'Blocks World' problem detailed in AI books like Patrick Winston's Artificial Intelligence. What you describe is actually a fairly straightforward 2D+layers situation, and if you limit the allowable turnout designs and curve-piece radii, a recursive try-and-test application becomes very doable. It would work a lot like the Tetris solver used as an example in the Jaguar book, although the solution network would be much more complex and certainly the visualizer would, too.
[reply]
      I didn't think about it, but board layout... yeah, it's got to be very similar. However (at least 10 years ago), I heard stories about those programs running days to get good layouts. I know it's not 10 years ago though :)
[reply]

In Section Meditations