Из аэропорта в центр
Рассмотрим такую ситуацию. Ваш самолёт только что приземлился в Англии, и у вас арендована машина. В скором времени запланировано совещание, и вам надо добраться из аэропорта Хитроу в Лондон настолько быстро, насколько это возможно (но без риска!).
Существуют две главные дороги из Хитроу в Лондон, а также некоторое количество более мелких дорог, пересекающих главные. Путь от одного перекрёстка до другого занимает чётко определённое время. Выбор оптимального пути возложен на вас: ваша задача – добраться до Лондона самым быстрым способом! Вы начинаете с левой стороны и можете переехать на соседнюю главную дорогу либо ехать прямо.
Как видно по рисунку, самый короткий путь – начать движение по главной дороге B, свернуть на А, проехав немного, вернуться на B и снова ехать прямо. В этом случае дорога занимает 75 минут. Если бы мы выбрали любой другой путь, нам потребовалось бы больше времени.
Наша задача – создать программу, которая примет на вход некоторое представление системы дорог и напечатает кратчайший путь. Вот как может выглядеть входная информация в нашем случае:
50
10
30
5
90
20
40
2
25
10
8
0
Чтобы разобрать входной файл в уме, представьте его в виде дерева и разбейте систему дорог на секции. Каждая секция состоит из дороги A, дороги B и пересекающей дороги. Чтобы представить это в виде дерева, мы предполагаем, что есть последняя замыкающая секция, которую можно проехать за 0 секунд, так как нам неважно, откуда именно мы въедем в город: важно только, что мы в городе.
Будем решать проблему за три шага – так же мы поступали при создании вычислителя выражений в ОПЗ:
1. На минуту забудьте о языке Haskell и подумайте, как бы вы решали эту задачу в уме. При решении предыдущей задачи мы выясняли, что для вычисления в уме нам нужно держать в памяти некоторое подобие стека и проходить выражение по одному элементу за раз.
2. Подумайте, как вы будете представлять данные в языке Haskell. В вычислителе ОПЗ мы решили представлять выражение в виде списка строк.
3. Выясните, как манипулировать данными в языке Haskell так, чтобы получить результат. В прошлом разделе мы воспользовались левой свёрткой списка строк, используя стек в качестве аккумулятора свёртки.