Hacker News new | past | comments | ask | show | jobs | submit login
Playing with model trains and calling it graph theory (11011110.github.io)
145 points by zdw 18 days ago | hide | past | web | favorite | 29 comments

The book Hackers has an entire chapter on the TMRC https://en.wikipedia.org/wiki/Tech_Model_Railroad_Club engineers (students) build early track switching systems using relays and mainframes (later I think it was transistors and later microcomputers). This let them experiment with all sorts of train routing algorithms and those students often went on to influential positions in the telecom and computing industries.

While we're on the subject of ancient history, Prof Jim Roberge's course on feedback systems (6.302) famously included a final lecture incorporating his love of model trains.

The goal of the lecture was that the train should have a constant speed despite hills introduced into the track. In order to measure the speed of the train, he noticed that there was a small glitch that would occur as the motor's armature switched polarity, and so a time measurement of the glitches was proportional to the speed of the engine.

[I took the course in 85 and still remember it, so he left something of an impression. A couple of generations learned analog feedback from this course. RIP Prof Roberge.]

Edit: By some lesser miracle, his lectures are on youtube. The train lecture was last.


Thanks, that's pretty cool. When I was a kid I could never get my model train to go very fast. It wasn't until about 30 years later that I learned enough EE to understand the problem. Eventually I learned enough to build a self-balancing robot using PID control but I'm always amazed at college students who can do this stuff easily.

* https://en.wikipedia.org/wiki/Tech_Model_Railroad_Club

(above breaks with the bracket included)

Thanks for this, I've been obsessing about track layouts while playing trains with my kid, how to avoid getting stuck in permanent loops, having bi-drectional routes on all parts of the track etc. As I'm not a math person, I've not had a logical framework with which to think about it. my kid doesn't care but laying out tracks been a surprisingly fun mind game for me.

You may want to search for "shunting puzzles", such as those here: https://www.transum.org/Software/Shunting/Puzzles.asp

Every time my model train interest rises, I consider setting up a small layout for puzzles like these.

I've wanted to make timesaver for quite some time now.

Those look fun, thanks for the tip!

Ditto. The ideal track layout should allow trains to go in either direction across every segment. Bonus for going under a bridge. I also haven't really worked out the graph theory (something involving the +/- orientation of junction splits) but the temptation is immanent.

I also play trains with my kid, and I might be thinking about the same stuff. When I build a track, I think "given a position and direction, could I reach every other (position,direction) pair from here?". There's a certain minimum complexity required for a track to have that property, but I haven't really broken it down in a principled way.

I've been doing this too, with mine! A recent discovery is that if you keep all the Y pieces pointing in the same compass direction you seem to end up with a track which is always 100% traversable in either forward or reverse.

That can’t be true, can it?

Traversable doesn’t change if you bend parts of a track, and that can change the compass direction the switches point at.

For example, if part of the track containing a switch has an S shape, moving the switch from the center horizontal to the top or bottom one turns it by 180 degrees without affecting traversability.

I know nothing about train tracks past my BRIO days, but a bit about graphs. Can you explain how a track would not be bidirectional except for a permanent loop?

Bidirectional without backing up. To turn a train around, you need a closed loop at the end of the line or a triangle (wye).

One of the things that makes it more interesting in practice is that most electric model trains* use a "one rail is hot, one is return" electrical design-- so adding a wye or reversing loop to the design is asking for all sorts of electrical gimmicry to prevent it from shorting, while still maintaining usability.

*classic Lionel and Marklin designs used a third conductor in the centre. Since the outer rails are wired together, reversing designs are trivial.

It is surprisingly difficult to build train tracks given a set of parts, even without taking junctions into account - there is a challenge about it on Stack Overflow's Programming Puzzle site (https://codegolf.stackexchange.com/q/116607/66060) and there is only one answer in the two years it's been there. In some ways, real life engineers have it easier - they don't have to plan routes based on the parts in the box!

Having only one answer in two years doesn’t imply the problem is hard.

I would think all ‘large enough’ puzzles of this kind are easy. You build a rectangle (needs four corners. If you don’t have those, no closed curve is possible), and use pairs of left-over curves to add detours to the straight ends, possibly compensating for an odd number of straight edges. I would guess there is an analog to Euler’s formula (https://en.wikipedia.org/wiki/Euler%27s_formula) that describes what number of small corners, large corners, and straight ends can form a large closed curve.

I also suspect ‘large enough’ isn’t that large, probably everything over 16 pieces or so (Smaller problems may be non-standard because they require effort to avoid overlap)

It's so easy to monkey-patch a set of tracks, especially when you have different lengths of track, lots of them and a saw or router.

Reminds me of the lab I TA'ed college where we had to implement a track with 2 trains on it as a state machine and make it impossible for the two trains to collide. We had to eventually implement this state machine in vhdl which was then run on a fpga where we could simulate and control the trains:


Train track graphs have applications in genomics, where they are used to build pangenomic models in which the graph has two strands (like DNA). It's great to see work on them is ongoing!

Oh man, so I'd actually been thinking about the question of what happens when you actually play the game of Snake on an arbitrary graph: https://hjaltman.github.io/snake.html

Very interesting to see these results about the more basic model, where we leave out the game part and just focus on movement! I may have to contact the authors about this...

At UW (University of Waterloo), our Real-time OS class projects used physical trains. Walking the halls of the Math & CS building, you could see kids "playing with trains" all through the night quite routinely.

It had the reputation of being one of the hardest CS classes in the undergrad curriculum.

I seem to remember an Alistair MacLean book where the secret messages (spy business) were coded in a model train setup. It was then disguised in a set of time tables that, when run, would end up with the train cars in a particular order, and where the cars were encoded letters.

I think you are thinking of The Enemy by Desmond Bagley. It’s on a book shelf at home and I’m away so I can’t check. I recall that the murdered industrialist actually uses a train set to encode an algorithm rather than a code. Will have to check when I get back

This brings up fond memories of Waterloo's CS 452: Real-time Programming.

"Here, we've got this model train set hooked up to a PC with nothing on it. Here are some specs. Write an RTOS and control program to make the trains do something interesting."

I thought a lot about this a few years ago when my son was very much into building train tracks. I had just taken a first course in linear algebra and started to work out a mathematical solution to this very problem. It is still one of those projects I wish to complete... someday when there is more time. Guess it will be when I have grandchildren.

Wow ...I was building tracks with my toddler yesterday and wondering how to not run into so many problems with not being able to complete an interconnection. I had a feeling it was an open math problem.

I call it group theory when I play with my Rubik's cube.

Offtopic: I read it as model trains and calling it machine learning.. meh!

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact