Автор оригинала: Arun Ravindran.
На прошлой неделе я попытался сделать то, что давно планировал. Перенос программы Python в Haskell. Если вы не знали, Haskell – это чисто функциональный язык программирования, который в последнее время стал популярным. В нем много передовых идей из академического мира, особенно из-за лени и строгой типизации. У него есть интересный способ решить «проблему с несколькими процессорами».
Mars Rover – это известная программная проблема, которую Thoughtworks используют при приеме на работу. Сначала я решил проблему на Python, а затем попытался решить то же самое на Haskell. Не могу сказать, что я портировал его с Python, потому что подход, который я использовал, совершенно другой.
Проблема
Отряд роботов-вездеходов должен высадиться NASA на плато на Марсе.
Это плато, имеющее любопытную форму прямоугольника, должно перемещаться марсоходами, чтобы их бортовые камеры могли получить полный обзор окружающей местности для отправки обратно на Землю.
Положение марсохода и его местоположение представлены комбинацией координат x и y и буквой, представляющей одну из четырех основных точек компаса. Плато разделено на сетку для упрощения навигации. Примерное положение может быть 0, 0, N, что означает, что ровер находится в нижнем левом углу и смотрит на север.
Чтобы управлять марсоходом, НАСА отправляет простую строку букв. Возможные буквы – «L», «R» и «M». «L» и «R» заставляют марсоход вращаться на 90 градусов влево или вправо соответственно, не двигаясь с текущего места. «M» означает перемещение вперед на одну точку сетки с сохранением того же курса.
Предположим, что квадрат непосредственно к северу от (x, y) равен (x, y + 1).
ВХОД:
Первая строка ввода – это верхние правые координаты плато, нижние левые координаты предполагаются равными 0,0.
Остальная часть входных данных – это информация, относящаяся к развернутым роверам. У каждого ровера есть две линии ввода. В первой строке указано положение марсохода, а во второй строке – серия инструкций, указывающих марсоходу, как исследовать плато.
Позиция состоит из двух целых чисел и буквы, разделенных пробелами, соответствующих координатам x и y и ориентации марсохода.
Каждый марсоход будет завершен последовательно, а это означает, что второй марсоход не начнет двигаться, пока первый не закончит движение.
ВЫХОД
Выходными данными для каждого ровера должны быть его окончательные координаты и курс.
ВХОД И ВЫХОД
Тестовый ввод:
5 5
1 2 N
LMLMLMLMM
3 3 E
MMRMMRMRRM
Ожидаемый результат:
1 3 N
5 1 E
Решение Python
Решение Python на самом деле меньше, чем сама проблема. Читаемость не так уж велика, но она вполне расширяема. Фактически, для добавления новой инструкции, такой как B (ackward) , потребуется всего одна дополнительная строка. Вы также можете расширить четыре основных направления до восьми с минимальными изменениями кода.
dirs "NESW" # Notations for directions
shifts[(0,1),(1,0),(0,-1),(-1,0)] # delta vector for each direction
# One letter function names corresponding to each robot instruction
r lambda x, y, a: (x, y, (a + 1) % 4)
l lambda x, y, a: (x, y, (a - 1 + 4) % 4)
m lambda x, y, a: (x + shifts[a][0], y + shifts[a][1], a)
raw_input() # Ignore the grid size
while 1:
# parse initial position triplet
x, y, dir raw_input().split()
pos (int(x),int(y),dirs.find(dir))
# parse instructions
instrns raw_input().lower()
# Invoke the corresponding functions passing prev position
for i in instrns: pos eval('%s%s' % (i, str(pos)))
print pos[0], pos[1], dirs[pos[2]]
Решение Haskell
Я новичок в Haskell, поэтому приношу свои извинения за плохие методы программирования. Вы могли заметить, что вместо использования Reflection, как в коде Python, я использовал определение типа для вызова правильной функции для каждой инструкции. Опять же, это хорошо масштабируется при добавлении новых инструкций.
import Data.List
dirs "NESW"
shifts 0 (0, 1)
shifts 1 (1, 0)
shifts 2 (0, -1)
shifts 3 (-1, 0)
instrn (x, y, a) 'R' (x, y, mod (a + 1) 4)
instrn (x, y, a) 'L' (x, y, mod (a - 1 + 4) 4)
instrn (x, y, a) 'M' (x+fst (shifts a), y+snd (shifts a), a)
showpos (x, y, a) show x ++ " " ++ show y ++ " " ++ [dirs !! a]
finddir dirchar
case elemIndex dirchar dirs of
Nothing -> error "invalid direction"
Just position -> position
readpos line (x, y, a)
where a finddir $ head $ drop 1 line3
[(y,line3)] reads line2 :: [(Integer, String)]
[(x,line2)] reads line :: [(Integer, String)]
robo do
posn <- getLine
instrns <- getLine
putStrLn (showpos (foldl instrn (readpos posn) instrns))
robo
main do
skip <- getLine -- Skip reading the grid size
robo
Ключевые выводы
Поскольку некоторых из вас может заинтересовать Haskell, я попытался обобщить свой опыт программирования на Haskell.
- Конструкций цикла нет. Так что все нужно делать с помощью рекурсии!
- Ввод-вывод Haskell очень сложен. Это из-за того, что я мало знаю Монады. На самом деле я довольно быстро решил логику. Мне потребовалось время, чтобы разобраться в синтаксическом анализе ввода.
- Вывод типа выявляет множество ошибок. Это очень удобно, но сообщения об ошибках иногда сбивают с толку.
- Я мог бы использовать абстрактные типы данных для указаний, но это сделало бы код более длинным.
Короче говоря, программирование на Haskell – это невероятное упражнение. Настоятельно рекомендуется!