Railroad switch network

Question

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 × N matrix, an N × 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-> [1] -L-> [0] -R-> [2] -L-> [2] -R-> [0] -L-> [1] -R-> [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-> [1] -L-> [0] -R-> [2] -L-> [2] -R-> [2] -L-> [2] -R-> ...

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)] -> True
[(0,1),(0,0)] -> True
[(0,0),(1,0)] -> False
[(1,2),(0,3),(2,0),(1,2)] -> True
[(1,2),(0,3),(2,2),(1,2)] -> False
[(1,2),(3,0),(2,2),(1,2)] -> True
[(1,2),(2,0),(0,2),(1,2)] -> False
[(0,2),(4,3),(0,4),(1,2),(4,1)] -> True
[(4,0),(3,0),(4,0),(2,0),(0,4)] -> True
[(1,4),(3,2),(1,4),(5,3),(1,0),(5,2)] -> True
[(3,1),(3,2),(1,5),(5,4),(1,5),(3,2)] -> True
[(1,2),(5,0),(3,2),(2,4),(2,3),(1,6),(1,2)] -> False
[(4,9),(7,3),(5,2),(6,4),(6,5),(5,4),(3,2),(6,8),(8,9),(9,1)] -> False
[(2,7),(1,5),(0,8),(9,7),(5,2),(0,4),(7,6),(8,3),(7,0),(4,2)] -> True
[(4,9),(7,3),(3,2),(8,3),(1,2),(1,1),(7,7),(1,1),(7,3),(1,9)] -> 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)] -> 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)] -> 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)] -> True

Answer 1

CJam, 30 29 bytes

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

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.
&      e# Compute the set intersection all reachable nodes with N-1.

Answer 2

Perl, 52 + 2 = 54 bytes

$F[$1/($@++<@F<<@F)]=~s/(.+),(.+)/$2,$1/ while$1<$#F

Run with -ap (2 byte penalty). Input is a single line in the format 1,2 0,3 2,2 2,0.

Prints a copy of the input (which is truthy in Perl, as it's a string more than one byte long) to standard output on success, or crashes via dividing by zero (producing nothing on standard output; the null string is falsey) on failure.

The algorithm is very simple; we simply simulate the movement of the train, remembering its current location in $1 (whose initial value is zero when seen as an integer, and which automatically updates to hold the first capture group every time a regex is run), and the current states of the track by overriding @F (which holds the input array, and is input via the -a option on the command line). In order to detect that we've got stuck in a loop, we use $@ to count the number of steps taken; if this exceeds the number of switches times 2 to the power of the number of switches (a formula that can be conveniently written in Perl as @F<<@F and which is only slightly higher than the actual upper bound), we're necessarily stuck in a loop, because seeing the same (track, train) state twice will cause an infinite loop in this problem, and we've already been through more states than there are distinct states (so by the pigeonhole principle, we must have seen at least one twice).

Answer 3

Haskell, 114 95 88 84 bytes

(o%h)g|elem(o,g)h=1<0|(a,(l,r):b)<-splitAt o g=null b||(l%((o,g):h)$a++(r,l):b)
0%[]

Keeps a history of visited (location, network) pairs to be able to decide a failure. Junctions tuples are swapped when visited.

Usage:

0%[]<$>[[(0,0)] ,[(0,1),(0,0)] ,[(0,0),(1,0)] ,[(1,2),(0,3),(2,0),(1,2)] ,[(1,2),(0,3),(2,2),(1,2)] ,[(1,2),(3,0),(2,2),(1,2)] ,[(1,2),(2,0),(0,2),(1,2)] ,[(0,2),(4,3),(0,4),(1,2),(4,1)] ,[(4,0),(3,0),(4,0),  (2,0),(0,4)] ,[(1,4),(3,2),(1,4),(5,3),(1,0),(5,2)] ,[(3,1),(3,2),(1,5),(5,4),(1,5),(3,2)] ,[(1,2),(5,0),(3,2),(2,4),(2,3),(1,6),(1,2)] ,[(4,9),(7,3),(5,2),(6,4),(6,5),(5,4),(3,2),(6,8),(8,9),(9,1)] ,[(2,7),(1,  5),(0,8),(9,7),(5,2),(0,4),(7,6),(8,3),(7,0),(4,2)] ,[(4,9),(7,3),(3,2),(8,3),(1,2),(1,1),(7,7),(1,1),(7,3),(1,9)] ,[(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)] ,[(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)] ,[(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)]]
[True,True,False,True,False,True,False,True,True,True,True,False,False,True,False,False,False,True]

Ungolfed:

rails location history network
  | elem state history = False                         --We are stuck in a loop
  | otherwise = null b || (rails l newHistory swapped) --b is empty when location is last element in list
  where
  (a, (left, right):b) = splitAt location network
  swapped            = a ++ (right, left):b
  state              = (location, network)
  newHistory         = state:history

Thanks @Zgarb for saving 4 bytes

Answer 4

Python 135 133 bytes

-1 byte thanks to Angs (l>len(c)-2 rather than l==len(c)-1)

def f(c,p=0,l=0,h=[]):j=len(c);p=p or[0]*j;s=p[:],l;r=2*(l>j-2)or(s in h);n=c[l][p[l]];p[l]=1-p[l];return r-1if r else f(c,p,n,h+[s])

repl.it

Returns 1 (truthy) if the goal is reached; or 0 (falsey) if a state is reached that has been reached before. Otherwise recurses updating the state.

c is the network. p is the current state of each switch (initialised to all left as [0]*len(c) on the first run). l is the current location. h is the state history, to which s, a tuple of a copy of p and l, is added.