So, I mused in my previous post about whether or not it would be more efficient to change directions every time you returned to the starting car, and after more thinking/exploration I determined that it is, it's actually MUCH more efficient to change directions every time you return to the starting room. Here's the basic idea (also, I'm generally going to use right and left to refer to the directions because it just made the most sense to me to think about it that way):

So if every time you re-traverse the train you always start going right, all those steps you take to get back to the last car you checked are all wasted. You already know the entire path to that train car, so you aren't gathering any new information. However, if you change from right to left every time you return to the first car you can actually gather some information on the trip back out. If I start going right, don't find the end, but then go left instead, I now get to see the two cars to the left of start, which is new information. Then, when I don't find it on the left and head back right, even while traversing back to the furthest car I'm still gathering information, as I might've actually changed a light on that side now.

I'm not sure if I explained that well enough

but here's some data I gathered on the total amount of steps that it takes to confirm the car numbers to prove that it's actually a lot more efficient:

Only moving one way:

Only Right, Case 1 : 2 steps

Only Right, Case 2 : 6 steps

Only Right, Case 3 : 12 steps

Only Right, Case 4 : 20 steps

Only Right, Case 5 : 30 steps

Only Right, Case 6 : 42 steps

Only Right, Case 7 : 56 steps

Only Right, Case 8 : 72 steps

Only Right, Case 9 : 90 steps

Only Right, Case 10 : 110 steps

Only Right, Case 11 : 132 steps

Only Right, Case 12 : 156 steps

Only Right, Case 13 : 182 steps

Only Right, Case 14 : 210 steps

Only Right, Case 15 : 240 steps

Only Right, Case 16 : 272 steps

Only Right, Case 17 : 306 steps

Only Right, Case 18 : 342 steps

Only Right, Case 19 : 380 steps

Only Right, Case 20 : 420 steps

Switching directions:

Left/Right, Case 1 : 2 steps

Left/Right, Case 2 : 6 steps

Left/Right, Case 3 : 7 steps

Left/Right, Case 4 : 13 steps

Left/Right, Case 5 : 14 steps

Left/Right, Case 6 : 22 steps

Left/Right, Case 7 : 23 steps

Left/Right, Case 8 : 33 steps

Left/Right, Case 9 : 34 steps

Left/Right, Case 10 : 46 steps

Left/Right, Case 11 : 47 steps

Left/Right, Case 12 : 61 steps

Left/Right, Case 13 : 62 steps

Left/Right, Case 14 : 78 steps

Left/Right, Case 15 : 79 steps

Left/Right, Case 16 : 97 steps

Left/Right, Case 17 : 98 steps

Left/Right, Case 18 : 118 steps

Left/Right, Case 19 : 119 steps

Left/Right, Case 20 : 141 steps

Only moving one direction will always take Σ2n (0 to n) steps to 'solve', whereas changing directions takes...Okay, so, I'm not really sure to be honest. Maybe someone better at math can determine that. The nice thing, though, is that for odd number n the number of steps to 'solve' will always just be the number of steps to solve n-1, plus 1 (because as soon as you enter the next car you will have noticed it changed)

EDIT: Looked into the numbers a little bit, best approximation I can find for the number of steps for each is this (I think):

Σi (for i=1 to n/2) + (3n/2) + 1 (or +2 for odd numbers)

(n/2 is floored for odd numbers as well)

I don't really understand the pattern but...I think this should be accurate?

I also made a quick python script for testing this, for anyone curious. Feel free to check my work/modify the search functions/judge my coding:

`#!/usr/bin/python`

import random

######################

# Search Functions #

######################

# Traverse the train always starting to the right

def forwardSearch(train):

totalSteps = 0

stepsToTake = 0

startingLight = train[0]

# Break at 100 in case I'm bad at coding

while stepsToTake < 100:

stepsToTake += 1

# Move to the last car

totalSteps += stepsToTake

# Change the light

train[stepsToTake%len(train)] = not train[stepsToTake%len(train)]

# Walk back to starting car

totalSteps += stepsToTake

# Check the light

if train[0] != startingLight:

# We changed the first car, we know how many cars

return (stepsToTake, totalSteps)

# Traverse the train both left and right

def swingSearch(train):

totalSteps = 0

stepsToTake = 0

startingLight = train[0]

observedRight = []

observedLeft = []

polarity = -1

# Break at 100 in case I'm bad at coding

while stepsToTake < 100:

stepsToTake += 1

polarity *= -1

lights = observedRight if polarity > 0 else observedLeft

# Walk the car

for i in range(1, stepsToTake+1):

totalSteps += 1

curLight = train[polarity * i%len(train)] # Don't access imaginary cars

if i > len(lights):

lights.append(curLight)

elif curLight != lights[i-1]:

# Light changed, log

return (i + stepsToTake-1, totalSteps)

# Change the last light, as well as our observed version

lastCar = polarity * stepsToTake%len(train)

train[lastCar] = not train[lastCar]

lights[stepsToTake-1] = not lights[stepsToTake-1]

# Walk back to starting car

totalSteps += stepsToTake

# Check the light

if train[0] != startingLight:

# We changed the starting car, we know how many cars

return (stepsToTake, totalSteps)

################

# Run Trials #

################

def makeTrain(size):

train = []

for i in range(0, size):

train.append(random.randint(0,1) == 1)

return train

NUM_TIRALS = 20

for i in range(1, NUM_TIRALS+1):

# Make a train

train = makeTrain(i)

# One direction search

guess = forwardSearch(train)

if guess[0] == i:

print 'Only Right, Case', guess[0], ':', guess[1], 'steps'

else:

print '!!! BAD ANSWER !!!'

# Switch direction search

guess = swingSearch(train)

if guess[0] == i:

print 'Left/Right, Case', guess[0], ':', guess[1], 'steps'

else:

print '!!! BAD ANSWER !!!'

(EDIT: apologies, it doesn't seem to like my code in a spoiler tag)

I assume this same theory should work for the more complex ways of traversing the train as well, I just did the simple case because it was the easiest.