Умножая числа на горизонтали, vertial, и диагональные строки
Я в настоящее время работаю над Euler проблемой проекта (www.projecteuler.net) для забавы, но поразил камень преткновения. Одна из проблемы обеспечивает 20x20 сетка чисел и просит самый большой продукт 4 чисел на прямой линии. Эта строка может быть или горизонтальной, вертикальной, или диагональной.
Используя процедурный язык у меня не было бы проблемы при решении этого, но часть моей мотивации для того, чтобы сделать эти проблемы во-первых должна получить больше опыта и узнать больше Haskell.
С прямо сейчас я читаю в сетке и преобразовываю ее в список списка ints, например, - [[Интервал]]. Это делает горизонтальное умножение тривиальным, и путем перемещения этой сетки, вертикаль также становится тривиальной.
Диагональ - то, что дает мне проблему. Я думал о нескольких путях, где я мог использовать явное разрезание массива или индексацию, для получения решения, но это кажется чрезмерно сложным и hackey. Я полагаю, что здесь существует, вероятно, изящное, функциональное решение, и я хотел бы услышать то, что могут придумать другие.
4 ответа
Я не согласен с уважаемым Доном Стюартом. Учитывая комбинаторную природу проблемы и тот факт, что размер задачи всего 20x20, списки списков будут достаточно быстрыми. И последнее, чего вы хотите, это возиться с индексацией массивов. Вместо этого я предлагаю вам расширить методы, разработанные Ричардом Бердом в его знаменитом решателе судоку. Чтобы быть более конкретным, я бы предложил следующее:
Напишите функцию, которая, учитывая последовательность, возвращает все непрерывные подпоследовательности длины 4.
Напишите функцию, которая, учитывая сетку, возвращает все строки.
Напишите функцию, которая, учитывая сетку, возвращает все столбцы.
Напишите функцию, которая, учитывая сетку, возвращает все диагонали.
С этими функциями в руках решение будет простым. Но, как вы упомянули, диагональ не так очевидна. Что такое диагональ вообще? Давайте рассмотрим пример:
X . . . . .
. X . . . .
. . X . . .
. . . X . .
. . . . X .
. . . . . X
Предположим на минуту, что вы используете функцию drop и отбрасываете 0 элементов из строки 0, 1 элемент из строки 1 и так далее. Вот что получается в итоге:
X . . . . .
X . . . .
X . . .
X . .
X .
X
Элементы диагонали теперь образуют первый столбец треугольника, который у вас остался. Еще лучше то, что каждый столбец оставшейся у вас вещи является диагональю исходной матрицы. Добавьте несколько преобразований симметрии, и вы легко сможете перечислить все диагонали квадратной матрицы любого размера. Перечислите каждую из них с помощью функции "смежные подпоследовательности длины 4", и Боб - ваш дядя!
Немного больше деталей для тех, кто может застрять:
Ключ к этой проблеме - композиция. Диагонали бывают четырех групп. В моем примере дана одна группа. Чтобы получить остальные три, примените ту же функцию к зеркальному изображению, транспонированию и зеркальному изображению транспонирования.
Транспонирование - это однострочная функция, и она нужна в любом случае для чистого восстановления столбцов.
Зеркальное изображение еще проще, чем транспонирование - подумайте о том, какие функции вы можете использовать из Прелюдии.
Метод симметрии даст каждую главную диагональ дважды; к счастью, для указанной задачи повторение диагонали - это нормально.
Списки - неправильная структура данных для этой проблемы, поскольку они не обеспечивают случайную индексацию за постоянное время - они склоняются к линейному обходу. Так что ваши диагонали всегда будут больше раздражать / медленнее со списками.
Как насчет использования массивов? Например. параллельных векторов или регулярных векторов .
Ну, для этой конкретной задачи одиночный линейный список или массив на самом деле является самой простой структурой! Главное - думать об этих прогонах как о прохождении по списку с заданным шагом. Если решетка имеет размер w × h, то
- горизонтальный прогон имеет ширину 1
- вертикальный прогон имеет ширину w
- диагональный прогон имеет ширину w-1
- диагональный прогон имеет ширину w+1
Теперь для каждого из четырех видов прогонов нужно просто вычислить возможные начальные точки. Что-то вроде этого:
allRuns :: Int -> Int -> Int -> [a] -> [[a]]
allRuns n w h es = horiz ++ vert ++ acute ++ grave
where horiz = runs [0..w-n] [0..h-1] 1
vert = runs [0..w-1] [0..h-n] w
acute = runs [n-1..w-1] [0..h-n] (w-1)
grave = runs [0..w-n] [0..h-n] (w+1)
runs xs ys s = [run (x+y*w) s | x <- xs, y <- ys]
run i s = map (es!!) [i,i+s..i+(n-1)*s]
Конечно, в эффективной реализации вы замените [a] на что-то вроде Data.Array Int a и es!!! с es!
Вы можете использовать !!! функцию для получения элементов списка по индексу. Это с фиксированным шагом либо увеличения, либо уменьшения индекса позволяет получить диагональ.