2001. Автомобиль-робот

К 2020 году многие автокомпании планируют создать автомобили, которые могут самостоятельно доставить пассажиров из точки А в точку Б.

Чтобы понять трудности, стоящие перед разработчиками программного обеспечения для автомобиля-робота, напишите программу для управления роботом в следующей задаче. Роботу нужно проехать по двухполосной дороге с односторонним движением длиной 10 единиц, на которой припаркованы несколько машин (см. рис.). Машины могут стоять на любой полосе, но путь по дороге всегда существует. Первоначально робот находится в начале дороги на левой полосе. Робот может выполнять следующие команды: ^ – ехать вперед, < – сдвинуться в полосу, расположенную левее текущей полосы движения, > – сдвинуться в полосу, расположенную правее. После команды можно указать число – количество повторений этой команды. Например, ^5 – ехать вперед 5 единиц. Несколько команд можно соединить в группу с помощью круглых скобок, тогда число после закрывающейся скобки будет показывать количество повторений этой группы, например, (^>^<)3. Для проверки возможности движения в каком-то направлении используется команда ?, после которой указывается команда движения ^, <, >. Если движение в этом направлении возможно, то команда выполняется. Иначе в программе ищется символ | (вертикальная черта) и выполняется команда после него. Например, ?^|< – пытаемся ехать вперед, если нельзя, то сдвигаемся влево. Можно соединить несколько проверок в последовательность, например, ?^|?<|>.

Робот должен из начального положения проехать в любую клетку на другой стороне дороге и там остановиться. При этом нельзя врезаться в припаркованные машины и выезжать за пределы дороги. Например, для левого рисунка решением является следующая программа: ^5>^4.

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

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

В качестве решения вы должны выслать одну строку, содержащую программу для робота.