LLLL

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

RR => SRRS

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

^xy$ => yx

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 :)

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:

Re: If I had a Free Two Months...

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.

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.

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!

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.

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.

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";
[download]

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

Good luck!
Marcel

200604 Janitored by Corion: Added formatting

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.