Мегамозг - посчитать вагоны

Есть несколько вагонов, сцепленные между собой по кругу. Внутри ходит Мегамозг, он должен посчитать количество вагонов. Мегамозг может только включать или выключать свет в вагонах. Как ему это сделать? Вначале свет горит случайным образом. (Количество вагонов может быть ну очень большим).

Ниже обсуждение с админом, верный ответ был в первом моем сообщении, но все равно любопытно.



Zmeyk
ОТВЕТ: поскольку времени у ММ много, можно поступить таким образом - идем по часов стрелке и выключаем свет, двигаемся до ближайшего вагона с выключенным светом, на этой точке разворачиваемся и идем против часовой стрелки, включая свет и так до ближайшего вагона с включенным сетом. Каждый проход считаем пройденные вагоны и остановиться можно в том случае, когда кол-во пройденных челночным способом вагонов перестанет увеличиваться. Понятно, что в начале свет можно не выключать, а включать, в зависимости от стартового состояния освещенности (главное состояние изменить).

Mr.KIR
Ситуация: Вы прошли 10 вагонов по часовой стрелке(соответственно выключили свет) и 10 вагонов против(включили свет), далее по часовой стрелке идут вагоны только с выключенным светом(так случайно получилось), а против с включенным. Как мы поймём, что пора остановиться?

Zmeyk
Эта ситуация предусмотрена описанным алгоритмом.
По часовой стрелке мы ВЫКЛЮЧАЕМ свет до ближайшего вагона с ВЫКЛЮЧЕННЫМ светом.
Против часовой - ВКЛЮЧАЕМ свет до ближайшего вагона с ВКЛЮЧЕННЫМ светом.
Таким образом мы меняем состояние всех вагонов последовательно, челночным способом. Считаем вагоны каждый раз при развороте, останавливаемся в том случае, когда кол-во вагонов в точке разворота перестанет увеличиваться (т.е. когда мы дойдем до вагона, у которого сами изменили состояние).

Mr.KIR
Если изначально во всех вагонах свет включен, вы можете до бесконечности ходить сначала выключая их, а потом включая.
Вы мыслите в верном направлении, надо просто додумать алгоритм.
Не предусмотрена. По вашему алгоритму вы по часовой стрелке выключаете свет до ближайшего выключенного, против - наоборот.
А дальше ситуация не описана. Получится что у вас ММ натолкнувшись на вагон(который он не трогал) с выключенным светом, пойдет обратно, натолкнувшись там на вагон с включенным светом(который он не трогал) снова развернётся и зациклится.

Zmeyk
Нет, в вагоне, на который от "натолкнулся" происходит следующее.
В этой точке он должен развернуться обратно, начиная с этой точки он будет вести отсвет вагонов, в этой точке необходимо изменить состояние света на обратное. Казалось, этот набор шагов подразумевается, но явным образом его не указал.

Mr.KIR
/ начиная с этой точки он будет вести отсвет вагонов/
Верная мысль, попробуйте пожалуйста её развить, тем самым оптимизировать ваш алгоритм и довести его до ума.

Zmeyk
Ну есть момент, который трогать не хотелось изначально. Если не переключать свет в каждом вагоне а дать указание, например, выключить свет во всех вагонах.
В этом случае идем до ближайшего включенного, оставляем в нем свет, далее начиная с этого вагона считаем, идем до следующего включенного, выключаем в нем свет и идем обратно, снова считая вагоны, когда счет сравняется с первым - остановиться и смотреть что с этим вагоном случилось, если свет по прежнему включен - значит нужно повторить процедуру "туда-обратно", если выключен - значит вагоны закончились.
Фактической оптимизации я не ощущаю, кроме отсутствия потребности выключать свет в одну сторону и включать в другую. Кол-во проходов такое же, только ходить будет скучнее. :)