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

Ответ 1

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

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

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

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

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

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

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

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

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

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

Немного больше деталей для тех, кто может застрять:

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

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

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

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

Ответ 2

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

Как насчет использования массивов? Например. параллельные векторы или регулярные векторы.

Ответ 3

Ну, для этой конкретной проблемы единственный линейный список или массив - фактически самая простая структура! Ключ должен думать об этих прогонах как пропуски через список с заданным шагом. Если сетка имеет размер 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!

Ответ 4

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

Ответ 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

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