В настоящее время я работаю над проектом Euler (www.projecteuler.net) для удовольствия, но попал в камнем преткновения. Одна из проблем дает 20х20 сетку чисел и запрашивает наибольший продукт из 4 чисел по прямой. Эта линия может быть горизонтальной, вертикальной или диагональной.
Используя процедурный язык, у меня не было бы проблем с этим, но часть моей мотивации для решения этих проблем в первую очередь заключается в том, чтобы получить больше опыта и узнать больше Haskell.
На данный момент я читаю в сетке и преобразую ее в список списка int, например - [[Int]]. Это делает тривиальное горизонтальное умножение, и, перенося эту сетку, вертикаль также становится тривиальной.
Диагональ - это то, что вызывает у меня проблемы. Я подумал о нескольких путях, когда я мог бы использовать явную сортировку или индексирование массива, чтобы получить решение, но он кажется слишком сложным и взломанным. Я считаю, что здесь, вероятно, есть элегантное функциональное решение, и мне бы хотелось услышать, что другие могут придумать.
Ответ 5
Итак, у вас есть сетка NxN, и вы хотите извлечь все горизонтальные, вертикальные и диагональные линии длины M, а затем найти максимальный продукт. Давайте проиллюстрируем некоторые методы Haskell на примере сетки 4x4 с длиной линии 2:
[[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9,10,11,12],
[13,14,15,16]]
Горизонтальная и вертикальная легко, все, что вам нужно, это функция, которая извлекает куски длины M из списка:
chunks 2 [1,2,3,4] == [[1,2],[2,3],[3,4]]
Тип такой функции [a] -> [[a]]. Это функция, связанная с списком, поэтому, прежде чем изобретать колесо, посмотрим, есть ли что-то подобное в Data.List. Aha, tails аналогичен, он возвращает списки с большим количеством элементов с самого начала списка:
tails [1,2,3,4] == [[1,2,3,4],[2,3,4],[3,4],[4],[]]
Если бы мы могли сократить узлы, чтобы сделать их длиной 2. Но мы можем, используя map функцию, которая применяется функция для каждого элемента списка и возвращает новый список:
map (take n) (tails xs) -- [[1,2],[2,3],[3,4],[4],[]]
Я бы не стал беспокоиться о более мелких строках, поскольку первоначальная задача - найти самый большой продукт и продукт [15, N] ≥ продукта [15], N ≥ 1. Но если вы хотите избавиться от них, кажется, что список длины N содержит N-M + 1 кусков длины M, поэтому вы можете применить take (4-2+1) к результирующему списку. В качестве альтернативы вы можете просто filter список:
chunks n xs = filter ((==n) . length) $ map (take n) (tails xs)
-- [[1,2],[2,3],[3,4]]
Хорошо, мы можем извлечь список кусков из списка, но у нас есть 2D-сетка, а не плоский список! map снова спасает нас:
map (chunks 2) grid -- [[[1,2],[2,3],[3,4]],[[5,6],[6,7],[7,8]],...]
Но вот эта вещь, полученный код помещает куски в отдельные списки, и это усложняет ситуацию, так как нам на самом деле неинтересно, из какой строки возникает кусок. Таким образом, мы хотели бы сгладить на один уровень полученный список на concat . map или эквивалентный concatMap:
concatMap (chunks 2) grid -- [[1,2],[2,3],[3,4],[5,6],[6,7],[7,8],...]
Теперь, как мне получить вертикальные куски из сетки? Сначала звучит страшно, пока вы не поймете, что можете transpose всю сетку, то есть превратить строки в столбцы и столбцы в строки, а затем примените тот же код:
concatMap (chunks 2) (transpose grid) -- [[1,5],[5,9],[9,13],[2,6],[6,10],...]
Теперь сложная часть: диагональные линии. Norman Ramsey дает представление: что, если вы могли бы сбросить 0 элементов из строки 0, 1 элементов из строки 1 и т.д.? Диагональная линия станет вертикальной линией, которую легко извлечь. Вы помните, что для применения функции к каждому элементу списка вы используете map, но здесь вам нужно применить различные функции к каждому элементу, а именно drop 0, drop 1, drop 2 и т.д. map не устраивает. Но посмотрите, первый аргумент drop формирует шаблон последовательных чисел, который может быть представлен как бесконечный список [0..]. Теперь, если бы мы могли взять один элемент из [0..] Нам нужна функция, которая берет число из бесконечного списка [0..] и строку из сетки и применяет drop к этому номеру в строке. zipWith - это то, что вам нужно:
zipWith drop [0..] grid -- [[1,2,3,4],[6,7,8],[11,12],[16]]
map head $ zipWith drop [0..] grid -- [1,6,11,16]
Но мне нужны все диагонали длины 2, а не только самая большая диагональ. Итак, посмотрите на сетку и подумайте, какие диагональные линии вы видите с элементами в строке 0? [1,6],[2,7],[3,8]. Поэтому ясно, что вам нужно взять только первые 2 строки и транспонировать элементы:
transpose $ zipWith drop [0,1] grid -- [[1,6],[2,7],[3,8],[4]]
Теперь, как мне получить диагонали, начиная с других строк? Помните наш трюк tails? Мы можем получить все диагонали, предоставив нашу новую функцию concatMap и применив ее к tails grid:
concatMap (transpose . zipWith drop [0,1]) (tails g)
-- [[1,6],[2,7],[3,8],[5,10],[6,11],...]
Но это только диагонали, которые идут от верхнего левого до нижнего правого. Как насчет тех, кто идет сверху вниз справа налево? Легче всего просто изменить строки сетки:
concatMap (transpose . zipWith drop [0,1]) (tails $ reverse g)
-- [[13,10],[14,11],[15,12],[9,6],[10,7],...]
Наконец, вам нужно найти продукты всех линий и выбрать самый большой. Окончательный код выглядит следующим образом:
grid = [[1..4],[5..8],[9..12],[13..16]]
chunks n xs = map (take n) (tails xs)
horizontal = concatMap (chunks 2) grid
vertical = concatMap (chunks 2) (transpose grid)
grave = concatMap (transpose . zipWith drop [0,1]) (tails grid)
acute = concatMap (transpose . zipWith drop [0,1]) (tails $ reverse grid)
maxProduct = maximum $ map product $ horizontal ++ vertical ++ grave ++ acute
-- answer: 240
Является ли этот код максимально элегантным и эффективным? Черт, нет, но он работает и иллюстрирует некоторые модели мышления функционального программирования. Сначала вам нужно написать код, который просто работает, а затем итеративно реорганизовать его, пока вы не придете к решению, которое легко читать и вообще.
