Duplo Railroad Tycoon: Synthesis of a railway network with maximum coverage

Santa Claus brought the Duplo railway to the children. The rail segments are very easily interconnected, and you can build some small, most likely just a closed path, set up the station and watch the train running in a circle. Sometimes he stops and the child has to “fill up” the engine from the column, after which the engine will go again.

Here is an example of the simplest way:



I got bored with this train very quickly, after a third, and I went back to dig into the Thingiverse to try to use a 3D printer for something useful for the hundred thousandth time. And suddenly I find there an arrow segment just for the Duplo engine.

The arrow works like this: it has three inputs and outputs, let's call them first, second and third. If the train enters the first or second node, then it leaves the arrow always through the third. In this case, the arrow switches to the corresponding node (i.e., if it entered through the first, then it switches to the first, if through the second, then to the second). But if he enters the third node, then the exit depends on the state of the arrow and he can leave both through the first and through the second. That is:

'1' -> '3' (the arrow translates to '1')
'2' -> '3' (the arrow translates to '2')
'3' -> if the arrow is to '1', then '1', otherwise '2'

I printed a couple of such arrows, and began to collect a “normal” railway. Only everything turned out somehow sadly - the steam engine traveled only part of the way, sticking on some ring, and did not want to leave it.

Problem one (simple): How many arrow segments should there be in the network so that all nodes are interconnected? The road should be continuous and without dead ends.


But, having worked hard, for the simplest option I solved the problem in a few days. A friend who came to visit decided it in 5 minutes without straining :)

Let each arrow be denoted by a letter, the nodes are the same as in the example above. Those. our network has nodes ['a1', 'a2', 'a3', 'b1', 'b2', 'b3'].


But what if we take more arrows? Hmm, if I thought so much about a simple solution, then I obviously won’t master it anymore. But the computer will master! But how can I get to this task? I struggled for several days, all trying to add some kind of search in depth to this, and almost threw everything away, when suddenly the idea came to me to write a solution on a piece of paper.

I just broke the whole track into steps:

Current state → Transition on the arrow → Transition on the connecting segment → Remember the new state of the arrows

Those. for the solution above, the transitions will be as follows (default arrow state: a3-> a1; b3-> b1):

a1 -> a3 -> b3 (a3-> a1; b3-> b1)
b3 -> b1 -> b2 ( a3-> a1; b3-> b1)
b2 -> b3 -> a3 (a3-> a1; b3-> b2) ## note

The rest is simple:

• We generate all possible road configurations for a given number of arrows
• On each road:
  
  • We drive the train 10 times and count the number of journeys for each node
  • If there are nodes with 0 or 1 passage, then this means the system after entering the mode fell into an infinite loop
  • If there are no such nodes, then the train safely rushes along the entire road, which is what we need!

So simple that I banged my head on the table for two days and eventually went to ask for advice on stackoverflow, where I was given several solutions on a silver platter in a matter of minutes.

Track generator (I will not declare a task and put it in a spoiler - for someone like me this can be a very cruel joke, but try to solve it yourself for the sake of interest):

def getTrack(l):
    # recursion anchor, basic case:
    # when we have 2 nodes only one pair is possible
    if len(l) == 2:
        yield [tuple(l)]
    else:
        # Pair the first node with all the others
        for i in range(1, len(l)):
            # Current pair
            pair1 = [(l[0], l[i])]
            # Combine it with all pairs among the remaining nodes
            remaining = l[1:i] + l[i+1:]
            for otherPairs in getTrack2(remaining, 1):
                yield pair1 + otherPairs

Track lattice:

def solveTrack(track):
    #контейнер для считалки прохода по нодам с инициализацией
    nodeCount = {}
    for n in nodes:
        nodeCount[n] = 0         
    railTr = None
    jointTr = 'a1'
    while True:
        pos = jointTr   #текущая позиция
        nodeCount[pos] += 1 #посчитаем ее
        railTr = getTransition(track, pos) #переход по соединяющим рельсам (зависит только от конфигурации трека)
        nodeCount[railTr] += 1  #посчитаем этот узел тоже
        jointTr = tj[railTr] #переход по стрелке (зависит только от состояния стрелки, которое зависит от предыдущего прохода или начального состояния)
        if railTr[1] in ['1','2']: ##Перевести стрелку
            tj[railTr[0]+'3'] = railTr
        if max(nodeCount.values()) > nodesTrace and min(nodeCount.values()) < 3: #здесь мы просто после определенного числа прогонов nodesTrace смотрим, не осталось ли заброшенных участков. Если остались - значи поезд где-то залип и конфигурация не годится.
            #print "Infinite cycle detected"
            break
        #sol = "{}\t{}\t{}\t{}\t{}".format(pos, railTr, jointTr, tj['a3'], tj['b3'])
        #print sol
        if max(nodeCount.values()) > nodesTrace * 1.5:
            print "-------------------------------------------------------\n"
            print "Simulation complete!"
            print '\nNodes: ', nodeCount, "\n"
            print "Solution: ", track
            break
    return

It remains only to set the list of nodes for the input data, the transitions between the nodes of the arrow and begin the search for a solution! Hurrah!

tj = {} #словарь переходов
nodes = [] #список узлов
##create joints transition table
for jt in range(nJoints):
    tj[idxs[jt]+'1'] = idxs[jt]+'3'
    tj[idxs[jt]+'2'] = idxs[jt]+'3'
    tj[idxs[jt]+'3'] = idxs[jt]+'1'
    nodes.extend((idxs[jt]+'1', idxs[jt]+'2', idxs[jt]+'3'))

Hmm, but there’s no solution to the four-arrow road. And with six (I waited several hours) - not either. That's all. Dream end.

Though. But what if you make only part of the arrows switchable, and freeze the rest? For example, like this:

if railTr[0] in idxs[:nSwitchableJoints]: ## nSwitchableJoints - это количество переключаемых стрелок
            if railTr[1] in ['1','2']: ##Перевести стрелку
                  tj[railTr[0]+'3'] = railTr

And voila - there are many solutions! I tried to choose something prettier :)


Here only the arrow 'a' is switchable, the remaining three are always allowed to one.
This track corresponds to the solution:

[('a1', 'c3'), ('a2', 'f3'), ('a3', 'b3'), ('b1', 'd2'), ('b2', 'e1'), ('c1', 'e2'), ('c2', 'f1'), ('d1', 'f2'), ('d3', 'e3')]
nSwitchableJoints = 1

That's all for now!