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
Вот мой перевод:
Две комнаты соединены воздуховодом, по которому могут перемещаться роботы-уборщики. Канал узкий, пройти через него может только один робот.
У роботов нет лазера, радара, лидара или чего-либо для обнаружения препятствий. Из всех сенсоров у них есть только датчик прикосновения. Если они встретятся в воздуховоде, они столкнутся друг с другом. После столкновения каждый из них развернется и продолжит движение в противоположном направлении.
Боб считает, что очень интересно наблюдать, как роботы сталкиваются и бегают туда-сюда. Он сделал длинный прозрачный канал и поместил в него много роботов, желая посмотреть последовательность их столкновений и метаний - устроить "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