Re: Closed geometry: a train track problem

[Dr. Mu]

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!

[Anonymous Monk]

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.

[Dr. Mu]

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.

[Anonymous Monk]

See my post below, I briefly had my terminology totally blown and was confusing the grammar you proposed (totally valid) and what I proposed (the exact same thing) with the idea of a regular expression solution ... which was the result of skimming your post waaaay too fast. We are talking about the same thing, I agree -- as I said below, my fault!

[Anonymous Monk]

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

[Anonymous Monk]

I in-fact meant "context-free" as you used above. I really should register an account so I can edit things. The idea of building things from transformations does make sense now, especially if you forget coordinates... it would be a fun project.