Умножение чисел по горизонтальным, вертикальным и диагональным линиям

Question

В настоящее время я работаю над проектом Euler problem (www.projecteuler.net) для удовольствия, но попал в камнем преткновения. Одна из проблем дает 20х20 сетку чисел и запрашивает наибольший продукт из 4 чисел по прямой. Эта линия может быть горизонтальной, вертикальной или диагональной.

Использование процедурного языка У меня не было бы проблем с этим, но часть моей мотивации для решения этих проблем в первую очередь заключается в том, чтобы получить больше опыта и узнать больше Haskell.
Как раз сейчас я читаю в сетке и преобразую ее в список списка int, например - [[Int]]. Это делает тривиальное горизонтальное умножение, и, перенося эту сетку, вертикаль также становится тривиальной.

Диагональ - это то, что дает мне проблемы. Я подумал о нескольких путях, когда я мог бы использовать явную сортировку или индексирование массива, чтобы получить решение, но он кажется слишком сложным и взломанным. Я считаю, что здесь, вероятно, есть элегантное функциональное решение, и мне бы хотелось услышать, что могут придумать другие.

Answer 1

Я не согласен с достойным доном Стюартом. Учитывая комбинаторный характер проблемы и тот факт, что размер проблемы составляет всего 20х20, списки списков будут достаточно быстрыми. И последнее вещь, которую вы хотите, это futz вокруг с индексированием массива. Вместо этого я предлагаю вам расширить методы, разработанные Ричардом Бердом в его знаменитом знаменитом sudoku solver. Чтобы быть более конкретным, я хотел бы предложить следующее:

• Написать функцию, которая задана последовательность, возвращает все смежные подпоследовательности длины 4.

• Написать функцию, которая данную сетку, возвращает все строк.

• Напишите функцию, которая задает сетку, возвращает все столбцы.

• Напишите функцию, которая задает сетку, возвращает все диагонали.

С этими функциями в руках ваше решение будет легким. Но, как вы говорите, диагональ не так очевидна. Что такое диагональ? Давайте посмотрим на пример:

X . . . . . 
. X . . . . 
. . X . . . 
. . . X . . 
. . . . X . 
. . . . . X 

Предположим на минуту, что вы используете функцию drop и упаду 0 элементы из ряда 0, 1 элемент из строки 1, и так далее. Вот то, что вы завершаете с:

X . . . . . 
X . . . . 
X . . . 
X . . 
X . 
X 

Элементы диагонали теперь формируют первый столбец треугольной, что вы уехали.Еще лучше, каждый столбец - это диагональ исходной матрицы. Бросьте несколько преобразований симметрии, и вы легко сможете перечислить все диагоналями квадратной матрицы любого размера. Удалите каждого из них с помощью вашей «непрерывной последовательности с длиной 4», а Боб - ваш дядя!

---

Чуть более подробно для тех, кто может быть застрял:

Ключ к этой проблеме состав. Диагонали входят в четыре группы. Мой пример дает одну группу. Чтобы получить остальные три, примените ту же функцию к зеркальному изображению, транспонированию и зеркальному отображению транспонирования.

• Transpose - это однострочная функция, и в любом случае вам это нужно, чтобы восстановить столбцы.

• Зеркальное изображение еще проще, чем транспонирование — подумайте о том, какие функции вы можете использовать из Prelude.

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

Answer 2

Вы можете использовать функцию !! для извлечения элементов в списке по индексу. То, что с фиксированным шагом увеличивает или уменьшает индекс, вы получаете диагональ.

Answer 3

Списки неправильной структуры данных для этой проблемы, поскольку они не обеспечивают случайную индексацию в постоянное время - они смещаются в сторону линейных обходов. Таким образом, ваши диагонали всегда будут более раздражать/замедлять списки.

Как насчет использования массивов? Например. parallel vectors или regular vectors.

Answer 4

Ну, для этой конкретной проблемы единственный линейный список или массив на самом деле является самой легкой структурой! Ключ должен думать об этих прогонах как пропуски через список с заданным шагом. Если сетка ш × ч по размеру, а затем

• горизонтальный прогон имеет большой шаг
• вертикальный прогон имеет большой шаг ш
• одной диагонали перспективы имеет шаг 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!

Answer 5

Так у вас есть сетки NxN, и вы хотите, чтобы извлечь все горизонтальные , вертикальные и диагональные линии длины M, затем найти максимальный продукт. Проиллюстрируем некоторые методы Haskell на примере сетке 4х4, с длиной линии равно 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. Ага, 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 

Является ли этот код максимально элегантным и эффективным? Черт, нет, но он работает и иллюстрирует некоторые модели мышления функционального программирования. Сначала вам нужно написать код, который просто работает, а затем итеративно реорганизовать его, пока вы не придете к решению, которое легко читать и вообще.