Railroad switch network Introduction

Suppose we have a network of railroads.
Each junction in the network is controlled by a switch, which determines whether an incoming train turns left or right.
The switches are configured so that each time a train passes, the switch changes direction: if it was pointing left, it now points right, and vice versa.
Given the structure of the network and the initial positions of the switches, your task is to determine whether a train can eventually pass through it.

This challenge was inspired by this article.

Input

Your input is a non-empty list S of pairs S[i] = (L, R), where each of L and R is an index of S (either 0-based or 1-based), in any reasonable format.
This includes a 2 &times; N matrix, an N &times; 2 matrix, two lists of length N, or a list of length 2N.

Each pair represents a junction of the network, and L and R point to the junctions that are reached by turning left and right from the junction.
They may be equal and/or point back to the junction i.
All junctions initially point left.

Output

A train is placed on the first junction S[0].
On each "tick", it travels to the junction that its current switch points to, and that switch is then flipped to point to the other direction.
Your output shall be a truthy value if the train eventually reaches the last junction S[length(S)-1], and a falsy value if is doesn't.

Example

Consider this network:



This corresponds to the input [(1,2),(0,3),(2,0),(2,0)]
The train travels the following route:

[0] -L-&gt; [1] -L-&gt; [0] -R-&gt; [2] -L-&gt; [2] -R-&gt; [0] -L-&gt; [1] -R-&gt; [3]


Since the train reached its destination, the last junction, the correct output is truthy.

For the input [(1,2),(0,3),(2,2),(2,0)] we have the following route:

[0] -L-&gt; [1] -L-&gt; [0] -R-&gt; [2] -L-&gt; [2] -R-&gt; [2] -L-&gt; [2] -R-&gt; ...


This time, the train got stuck in the junction 2, and will never reach the destination.
The correct output is thus falsy.

Rules and scoring

You can write a full program or a function, and the lowest byte count wins.
Consider skimming the article, as it may contain useful info for writing a solution.

Test cases

These have 0-based indexing.

[(0,0)] -&gt; True
[(0,1),(0,0)] -&gt; True
[(0,0),(1,0)] -&gt; False
[(1,2),(0,3),(2,0),(1,2)] -&gt; True
[(1,2),(0,3),(2,2),(1,2)] -&gt; False
[(1,2),(3,0),(2,2),(1,2)] -&gt; True
[(1,2),(2,0),(0,2),(1,2)] -&gt; False
[(0,2),(4,3),(0,4),(1,2),(4,1)] -&gt; True
[(4,0),(3,0),(4,0),(2,0),(0,4)] -&gt; True
[(1,4),(3,2),(1,4),(5,3),(1,0),(5,2)] -&gt; True
[(3,1),(3,2),(1,5),(5,4),(1,5),(3,2)] -&gt; True
[(1,2),(5,0),(3,2),(2,4),(2,3),(1,6),(1,2)] -&gt; False
[(4,9),(7,3),(5,2),(6,4),(6,5),(5,4),(3,2),(6,8),(8,9),(9,1)] -&gt; False
[(2,7),(1,5),(0,8),(9,7),(5,2),(0,4),(7,6),(8,3),(7,0),(4,2)] -&gt; True
[(4,9),(7,3),(3,2),(8,3),(1,2),(1,1),(7,7),(1,1),(7,3),(1,9)] -&gt; False
[(0,13),(3,6),(9,11),(6,12),(14,11),(11,13),(3,8),(8,9),(12,1),(5,7),(2,12),(9,0),(2,1),(5,2),(6,4)] -&gt; False
[(6,0),(1,2),(14,1),(13,14),(8,7),(6,4),(6,10),(9,10),(10,5),(10,9),(8,12),(14,9),(4,6),(11,10),(2,6)] -&gt; False
[(1,3),(9,17),(5,1),(13,6),(2,11),(17,16),(6,12),(0,8),(13,8),(10,2),(0,3),(12,0),(3,5),(4,19),(0,15),(9,2),(9,14),(13,3),(16,11),(16,19)] -&gt; True
CJam, 30 29 bytes

0l~_,m!{_2$=(@@2$+3$\t}*,(])&amp;


Uses 0-based inputs and prints the index of the terminal node if the terminal node is ever reached.

This is super inefficient. You wouldn't want to test this on inputs with more than 10 nodes. The test link below uses 2\# instead of m! which isn't quite enough for all possible inputs, but it passes all test cases in a few seconds (and one would have try fairly hard to find a test case that doesn't pass).

Try it online!

Explanation

This doesn't have any loop or terminal detection. Instead we simply iterate the system often enough that we know we've hit a loop, recording the history, and then we check whether we've reached the terminal node at any point.

If we don't visit the terminal node, we only modify the states of N-1 nodes (if N is the total number of nodes). Each of the nodes has two different states, and the train can be on any one of those nodes (thanks to ais523 for pointing this out), so there are 2(N-1)*(N-1) different states we can visit before entering a loop or reaching the terminal node. Since we start from one of these states we know that after 2(N-1)*(N-1) transitions, we've either entered a loop or reached the terminal node.

That's a fairly lengthy expression. However, N! is almost never less than 2(N-1)*(N-1). In fact, the only N for which that's the case is 3, where the number of possible states is 8 and N! gives only 6. That said, it's not necessarily the case that it's possible to reach all theoretical states in any of the possible inputs. It's fairly easy to check this exhaustively: the neighbours of the last node are always irrelevant, so we can simply consider all inputs of the form [[a b] [c d] [0 0]] where at least one of abcd contains 2 (otherwise, the terminal state is guaranteed to be unreachable). There are only 65 of these states, and I ran them through a slightly modified program, which finds the first transition after which the terminal state is reached (or -1 if it's unreachable). As it turns out, it's impossible to construct an input which requires more than 6 transitions to reach the terminal state, just what we need. Hence, I'm using N! as the upper bound of iterations.

0      e# Push a zero. This is the initial node index of the train.
l~     e# Read and evaluate the input.
_,m!   e# Compute the factorial of N.
{      e# Run this block N! times.
  _    e#   Copy the list of LR pairs.
  2$=  e#   Copy the current node index and extract the corresponding pair.
  (    e#   Pull off the first neighbour - this is where the train moves next.
  @@   e#   Pull list of pairs and the list with the other neighbour on top.
  2$+  e#   Copy the first neighbour and append it. This effectively, reverses
       e#   the pair so that next time the other destination from the current
       e#   node is picked.
  3$   e#   Copy the current node again.
  \    e#   Swap it with the reversed pair.
  t    e#   Write the reversed pair back into the full list of pairs.
       e#   In summary, one iteration extracts the first neighbour of the
       e#   current node and leaves it on the stack, and swaps the neighbours
       e#   of that node for future visits.
}*     e# At the end, we've got all the reachable nodes on the stack, and
       e# the list of all pairs still on top.
,(     e# Compute N-1 from the list of pairs.
])     e# Wrap everything in a list and remove N-1 from it.
&amp;      e# Compute the set intersection all reachable nodes with N-1.