codingame easy puzzle

Наткнулся на задачу на codingame - https://www.codingame.com/training/easy/robot-show

Вот мой перевод:

Две комнаты соединены воздуховодом, по которому могут перемещаться роботы-уборщики. Канал узкий, пройти через него может только один робот.

У роботов нет лазера, радара, лидара или чего-либо для обнаружения препятствий. Из всех сенсоров у них есть только датчик прикосновения. Если они встретятся в воздуховоде, они столкнутся друг с другом. После столкновения каждый из них развернется и продолжит движение в противоположном направлении.

Боб считает, что очень интересно наблюдать, как роботы сталкиваются и бегают туда-сюда. Он сделал длинный прозрачный канал и поместил в него много роботов, желая посмотреть последовательность их столкновений и метаний - устроить "robot show". Он расставил роботов на стартовые позиции, а затем включил их всех одновременно.

- предположим, что роботы движутся с постоянной скоростью 1 метр в секунду,
- предположим, что роботы имеют достаточно малый размер, чтобы им можно было пренебречь при расчете пройденного расстояния,
- предположим, что во время robot show дополнительных роботов в служебном канале не появится,
- предположим, что Боб может расположить каждого робота лицом либо влево, либо вправо перед началом шоу ...

Какое самое долгое время, в течение которого роботы могут бегать по воздуховоду, пока все не выйдут?

Пример: в десятиметровом воздуховоде два робота расположены лицом друг к другу.

    >       <
+-+-+-+-+-+-+-+-+-+-+  init state
0 1 2 3 4 5 6 7 8 9 10

        X              after 2 sec
+-+-+-+-+-+-+-+-+-+-+  bump at 4, bounce
0 1 2 3 4 5 6 7 8 9 10

<               >      after 4 sec
+-+-+-+-+-+-+-+-+-+-+  the L bot is exiting
0 1 2 3 4 5 6 7 8 9 10

                    >  after 2 sec
+-+-+-+-+-+-+-+-+-+-+  the R bot is exiting
0 1 2 3 4 5 6 7 8 9 10

Время шоу - 8 секунд

Изюминка этой задачи - то, что непонятно, куда смотрят роботы, налево или направо. И вроде бы можно все возможные случаи ориентации роботов перебрать, сделать на каждый из них симуляцию и посмотреть, для какого варианта время шоу будет максимальным.

Я сначала полез делать таким способом, но потом бросил - при увеличении роботов количество вариантов растет экспоненциально!

К счастью, есть простое наблюдение, которое поможет решить задачу за O(n) от количества роботов. В этом случае решение задачи - несколько строк. Но допереть до него сложновато. Возможно, именно поэтому у этой задачи сложности easy процент успешно решивших всего 67%

Ниже - мое решение. Ключ к решению - в комментарии перед классом, начиная со слов "Ключ к решению"

https://gist.github.com/Manjago/584444337ab9c2cceffd841190da91e2