SamCG has asked for the wisdom of the Perl Monks concerning the following question:

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.

Replies are listed 'Best First'.
Re: Closed geometry: a train track problem
by Dr. Mu (Hermit) on Jan 03, 2006 at 20:19 UTC
I think I'd treat this as a grammar/parsing problem. First, determine what the simplest closed circuit is. With the set you describe, it would be four quarter circles arranged to form a circle:
```LLLL
```
where L is a quarter circle that "turns left". This assumes that counter-clockwise is the canonical direction of travel. R could then be a quarter circle that turns right. (But RRRR would not be a valid circuit, since it violates the canonical direction of travel.)

Next figure out what transformations you can make to any valid closed circuit to yield another valid closed circuit. For example, in pseudo-regexp terms:

```LL => SLLS
```
i.e. Add straight segments to the ends of any left-turning semi-circle. So LLLL could become LSLLSL, a short oval. Likewise,
```RR => SRRS
```
would also be a valid operation.

Also, some general rules may prove helpful. For instance:

```^xy\$ => yx
```
i.e. commutativity, where x and y are any two sequences which, together, comprise an entire valid closed path. This just says that a valid closed path is valid, regardless of where you start. This means that LSLLSL from the example above can become SLLSLL, perhaps, in preparation for applying another rule.

After you've defined your "transformational grammar", you can design an algorithm to parse potential layouts with it, so you can determine whether a given track arrangement is valid. Parsing with transformational grammars is, in general, not for the faint of heart. But simple Euclidean geometry may come to your rescue, in place of a fancy parsing algorithm. Nonetheless, you may have more fun just applying a random number generator to your transformation rules to see what kinds of layouts you come up with.

Have fun!

In regards to the "grammar" approach, perhaps it's just the Perl background many of us have (regexes do rule!), but that wouldn't address tracks of different radii, which at least exist in the Lionel world. I don't think regexen apply. Maybe they do, but they seem to be one-dimensional. I am thinking (really roughly) that interesting tracks might be built via finite automata... i.e. Conway's game of life on steroids.
At the risk of being pedantic, I should point out that there's an equivalence between regular expressions and finite automata. It's this: Sentences in any regular grammar (i.e. one whose rules consist solely of a regular expression) can be parsed by a finite automaton.

What you're referring to with Conway's Game of Life is a cellular automaton. This is a possibly infinite automaton with local transformation rules that could be (and are in Conway's case) regular.

The grammar I describe is neither a regular grammar, nor a context-free grammar (whose sentences can be parsed by adding a stack to a finite state automaton), but a transformational grammar, which requires the full power of a Turing machine to parse.

As to tracks of different radii, they can indeed be accomodated by the grammar approach by assigning unique symbols to curves of each length and radius.

I need to add that your grammar is really nifty, and it would produce perfectly valid layouts...and on further review the idea of transformations on a basic pattern is exactly what you proposed. Sorry for misinterpreting -- entirely my fault. However I still wonder how you take that grammar and extend it into 2 and 3D, which as I recall requires some notion of state. My Finite Automata class is a bit rusty, so I forget the term... but I think I'm thinking of this being "not well formed" or "non-homogenous" or some other such phrase. Basically indicating transformations and rules that couldn't be reduced into grammars because of notion of state or other conditions. Darn, I hate forgetting college so fast :)
Re: Closed geometry: a train track problem
by pboin (Deacon) on Jan 03, 2006 at 17:55 UTC

Ah, you're peering into The Abyss. (Unless you're a lot smarter than I, which is very possible, maybe even likely.)

I've thought about the same thing, and had some good responses here:

I think I can do 'regular' pieces, but switches that can be flopped over to switch right or left, and valid 'cross-overs' (ie: over-bridges) v. invalid collisions just make my brain start to smoke.

Best of luck. If you make progress, please share it here on PM. This is a *great* problem.

Re: Closed geometry: a train track problem
by samizdat (Vicar) on Jan 03, 2006 at 19:42 UTC
If you think about each piece in terms of adding a delta x and delta y (change of position) and delta angle (change of direction) to your current location and direction, it shouldn't be too difficult to lay pieces end-to-end until you either get a collision or a correct match, or you run out of pieces. Switches are indeed more difficult, especially switches with a numerical frog angle, but I think if you solve the issues in placing a curve to turn left vs a curve to turn right, you'll be well on the way.

As has been stated, this is a graph theory situation, and Winston's AI book is well worth checking out.

Don Wilde
"There's more than one level to any answer."
Oh yes, delta x,y,alfa is the clever sight, but, it cannot describe possibility of track crossing (without some special crossing piece), for instance.
"an exercise for the reader"... :)

Okay, how about this: calculate some intermediate points, and store them in an x-y array. If a new piece tries to add points that are too close to an old point, it's a collision.

Actually, I like Dr. Mu's concept of transforming successful closed layouts, although I wouldn't necessarily do it as a 'parsing problem' because that gets trickier as pieces become more varied in length, angle and radius. Either the programmer or the program need to figure out what transformations work geometrically, and I'd much rather it be the program. Heesh's right to focus on successful layouts rather than random ones, because that will give you more solutions more quickly. Won't be as entertaining to watch, though! :D

Don Wilde
"There's more than one level to any answer."
If the only crossings permitted are bridges, then this is easily solved. A bridge needs:
• an ascending section of track;
• a raised but level section of track;
• a descending section of track
Presumably you have a set number of support pieces for these, so if you allow any piece of track to alter the z co-ordinate if necessary, you just need to keep track of how many times you've changed z (ie how many ascents and descents you have) and how many times z has remained constant but non-zero (ie how many raised level sections you have). Detecting when you need a bridge to cross over another piece of track is easy.

If you can have flat cross-overs, then you need to model the crossover as a special case.

Re: Closed geometry: a train track problem
by abcde (Scribe) on Jan 03, 2006 at 18:10 UTC

I just typed up a nice algorithm here (which was essentially brute force) when I thought of a much better one. Damn. This one should be better, and you can apply it in real life as well.

1. Begin by placing 7->8 "marker" pieces of track at various points around the floor. Make sure they're spaced well apart from each other.
2. For each marker track that you haven't already used:
1. Find the marker track nearest to it.
2. Lay track down in such a pattern that it joins the two marker tracks together.
3. Put some trains on it and make "choo choo!" noises.

This seems boring, but it's much, much faster than trying a brute-force method, and it still produces interesting tracks.

One of the interesting things (that I just thought of) about this design is the pathfinding - if you're laying down a track, but there's another piece of track in the way, don't remove the bit of track, but use one of the circle pieces to divert it around that bit of track. This makes the rails run together, as rails tend to do!

If you're really looking for a challenge, try making the algorithm recursive by using it again while doing step 2.2. And well done for thinking of such an interesting puzzle!

~abseed
Re: Closed geometry: a train track problem
by InfiniteSilence (Curate) on Jan 04, 2006 at 00:40 UTC
You know, starting out with a finite number of pieces should mean that there is a finite number of connecting track sequences. If you are choosing from N pieces you can produce a series of subsets which can be viewed using n-choose-k.

N-choose-k only gives us a certain number of distinct subsets. It answers the question, "How many ways can I pick k pieces from the box?" For instance, if the set was {1,2,3} we and we want sets of two we wind up with ({1,2}, {1,3}, {2,3}) or 3!/2!(3-2)! == 6/2(1)= 3 distinct sets. Running through this process iteratively should reveal all of the possible subsets (e.g. 4, 5, 6...N - 1).

Any given subset is going to have N! orderings or permutations. Going back to our above example of {1,2,3} a subset of {1,2} has two permutations: {1,2} and {2,1}. A set of three elements (i.e. {a,b,c}) will have 6 because 3! == 3*2*1 == 6.

Armed with the permutations for each k-subset we can start the process of eliminating those that cannot form a complete circuit by graphing out the connections somehow. It is fair to say that any less than four pieces will not produce the desired result, so k < 4 cases should be ignored.

In order to discover whether your graph is undirected or not, you would probably need to build an adjacency matrix and check to see if it is symmetric.

Celebrate Intellectual Diversity

I think you're on the right track (get it?) as far as permutations. The problem I've had (and it's probably me being short-sighted) is that certain pieces (switches) not only have three endpoints instead of two, but they also can have that offshoot node either left or right-handed, depending on which side is up. So, do they take two positions in the permutation matrix?

Some of you will now be thinking of my omission: the other direction. That same switch piece can not only be flopped left-to-right, but also end-over-end. So, when we get involved with tracking male and female connectors, there's really *four* states for a switch piece, and two for more regular pieces.

I'm no mathemetician, but this seems to be the most difficult part of the problem, followed closely by differentiating acceptable collisions from unacceptable ones.

Re: Closed geometry: a train track problem
by Anonymous Monk on Jan 04, 2006 at 10:16 UTC

Hi
You might want to take a look at the code of a game called "MAZE". It works with a 2 dimentional map, keeps track of your current position and gives you valid directions to make it through the MAZE. Maybe this gives you a good insperation.

Here is a copy of it:

```#!/usr/bin/perl -w
use strict;

my @maze=(
[ qw( e   swe we ws  ) ],
[ qw( se new sw ns ) ],
[ qw( ns  -      ns n  ) ],
[ qw( ne w     ne w   ) ],
);

my %direction=( n=> [ -1, 0], s=> [1,  0],
e=> [  0, 1], w=> [0, -1]);
my %full=( e => 'East', n => 'North', w=>'West', s=>'South');
my(\$curr_x, \$curr_y, \$x, \$y)=(0,0,3,3);
my \$move;

sub disp_location {
my(\$cx, \$cy)=@_;
print "You may move ";
while(\$maze[\$cx][\$cy]=~/([nsew])/g) {
print "\$full{\$1} ";
}

print "(\$maze[\$cx][\$cy])\n";
}

sub move_to {
my(\$new, \$xref, \$yref)=@_;
\$new=substr(lc(\$new),0,1);
if (\$maze[\$\$xref][\$\$yref]!~/\$new/) {
print "Invalid direction, \$new.\n";
return;
}
\$\$xref += \$direction{\$new}[0];
\$\$yref += \$direction{\$new}[1];
}

until ( \$curr_x == \$x and \$curr_y == \$y ) {
disp_location(\$curr_x, \$curr_y);
print "Which way? ";
\$move=<STDIN>; chomp \$move;
exit if (\$move=~/^q/);
move_to(\$move, \\$curr_x, \\$curr_y);
}

print "You made it through the maze!\n";

(Provided by "SAMS Teach yourself Perl in 24 Hours")

Good luck!
Marcel

200604 Janitored by Corion: Added formatting

Re: Closed geometry: a train track problem
by dragonchild (Archbishop) on Jan 04, 2006 at 15:06 UTC
For simple tracks, there's a number of options. You can do grammars, but I'd prefer vectors (I'm a math major, not a linguistics major). You have some starting point and a set of vectors (your track pieces). Each vector modifies the current position by providing a new position based on the old one in a relative fashion. Then, using basic vector math, you can determine if a given layout is closed or not.

My criteria for good software:
1. Does it work?
2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
Re: Closed geometry: a train track problem
by DungeonKeeper (Novice) on Jan 04, 2006 at 15:59 UTC
I can't help but notice the family resemblance this has to the Travelling Salesman Problem. One imperfect but nevertheless useful approach to that type of problem is the neural network. I'd start by defining the trackset as a set of vectors (x,y) and use Math::Combinatorics to generate the permutations. Then generate a target shape starting with a thin long oblong layout (meant to represent only an approximation to the flattest possible) of target circumference, and generate track solutions for which the sum of distances between the endpoints of the track pieces and the target shape approximates to a target value (+ or - a tolerance value). Change both the target value and tolerance to iterate (working with the same permutation until it succeeds for the iterated targets or the iteration exhausts and then getting the next permutation), using 1/4 unit steps. Permutations can be eliminated as soon the distance sum goes out of tolerance or if pieces run out before connecting back to the first piece (*update: can eliminate also if the distance from the nearest point on the target shape to the home point is already too great to get home for the remaining pieces). Overachievers are thus eliminated early and no solutions will need to exhaust the pieces to underachieve the target provided the target deviance is iterated in ascending order, making elimination relatively fast. A maximum total deviation of say three times the template circumference of the starting target shape would also assist the elimination speed and is anyway essential to prevent impossible permutations from being tried out for an infinite number of trial deviations.

Update: *could pre-compute the scalar value of each piece (using Pythagorus: sqr. root of the sum of the two components of the vector) and store them alongside the shapes rather than compute them every time the piece is used.

Re: Closed geometry: a train track problem
by pajout (Curate) on Jan 04, 2006 at 13:22 UTC
I see the square grid as playboard, where the smallest square is the unit of real track pieces. For instance, the straight piece takes 1x8 inches, curve takes 8x8 inches, it defines 1x1 inch square as the unit. (I guess that all real pieces have this character.) One square on the playboard can be occupied by 1 piece, maximally. Every piece has 2 or more endpoints. The endpoints are the edges of occupied square units. When some piece is put on the playground, the sum of not coupled endpoints is recalculated. The goal is sum == 0.
Update: the sum of endpoints -> the sum of not coupled endpoints