4 ms·
Playing with model trains and calling it graph theory
- vibrio 8y agoThanks 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.
- astazangasta 8y agoDitto. 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.
- grimjack00 8y agoYou may want to search for "shunting puzzles", such as those here: https://www.transum.org/Software/Shunting/Puzzles.asp 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.
- deleted 8y ago[deleted]
- d_j_b 8y agoI'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.
- Someone 8y agoThat 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.
- travisjungroth 8y agoI 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?
- desertrider12 8y agoBidirectional without backing up. To turn a train around, you need a closed loop at the end of the line or a triangle (wye).
- hakfoo 8y agoOne 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.
- jpfed 8y agoI 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.
- inciampati 8y agoTrain 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!
- dekhn 8y agoThe book Hackers has an entire chapter on the TMRC https://en.wikipedia.org/wiki/Tech_Model_Railroad_Club 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.
- petemcc 8y ago* https://en.wikipedia.org/wiki/Tech_Model_Railroad_Club https://en.wikipedia.org/wiki/Tech_Model_Railroad_Club (above breaks with the bracket included)
- jpmattia 8y agoWhile 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. https://www.youtube.com/playlist?list=PLUl4u3cNGP62in17jH_DiJMkCGNM6Xni- https://www.youtube.com/playlist?list=PLUl4u3cNGP62in17jH_Di...
- dekhn 8y agoThanks, 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.
- mpettitt 8y agoIt 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 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!
- TomK32 8y agoIt'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.
- Someone 8y agoHaving 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 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)
- new4thaccount 8y agoWow ...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.
- mkagenius 8y agoOfftopic: I read it as model trains and calling it machine learning.. meh!
- elygre 8y agoI 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.
- KineticLensman 8y agoI 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
- martinlofgren 8y agoI 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.
- dblohm7 8y agoThis 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."
- Sniffnoy 8y agoOh 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 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...
- sand500 8y agoReminds 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: http://engineering.armstrong.edu/tom/engr2031/engr2031trainassignment.pdf http://engineering.armstrong.edu/tom/engr2031/engr2031traina...
- dllthomas 8y agoI call it group theory when I play with my Rubik's cube.
- elsurudo 8y agoAt 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.