Así que hay una rejilla de NxN y quiere extraer todo horizontal , líneas verticales y diagonales de longitud M, luego para encontrar el producto máximo. Vamos a ilustrar algunas de las técnicas de Haskell en la parrilla ejemplo 4x4, siendo la longitud de la línea 2:
[[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9,10,11,12],
[13,14,15,16]]
horizontal y vertical es fácil, todo lo que necesita es una función que extraer trozos de longitud M de una lista:
chunks 2 [1,2,3,4] == [[1,2],[2,3],[3,4]]
El tipo de dicha función es [a] -> [[a]].Esta es una función relacionada con la lista, así que antes de reinventar la rueda, veamos si hay algo similar en Data.List. Aha, tails es similar, devuelve las listas con más y más elementos desde el principio de la lista eliminado:
tails [1,2,3,4] == [[1,2,3,4],[2,3,4],[3,4],[4],[]]
Si tan sólo pudiéramos acortar las listas secundarias para que sean de longitud 2. Pero podemos, mediante el uso de map función, que aplica una función a cada elemento de la lista y devuelve una nueva lista:
map (take n) (tails xs) -- [[1,2],[2,3],[3,4],[4],[]]
yo no me preocuparía por líneas más pequeñas, como la tarea original es para encontrar el producto más grande, y el producto de [15, N] ≥ producto de [15], N ≥ 1. Pero si desea deshacerse de ellos, parece th en una lista de longitud N contiene N-M + 1 trozos de longitud M, por lo que podría aplicar take (4-2+1) a la lista resultante. Alternativamente, usted podría simplemente filter la lista:
chunks n xs = filter ((==n) . length) $ map (take n) (tails xs)
-- [[1,2],[2,3],[3,4]]
Ok, podemos extraer una lista de trozos de una lista, pero tenemos una en 2D de la red, no una lista plana! map nos rescata de nuevo:
map (chunks 2) grid -- [[[1,2],[2,3],[3,4]],[[5,6],[6,7],[7,8]],...]
Pero aquí es la cosa, el código resultante pone trozos en listas separadas, y que complica las cosas, ya que en realidad no importa, a partir del cual se origina la línea del trozo. Así que nos gustaría para aplanar un nivel la lista resultante por concat . map o equivalente concatMap:
concatMap (chunks 2) grid -- [[1,2],[2,3],[3,4],[5,6],[6,7],[7,8],...]
Ahora, ¿cómo consigo trozos verticales de una red? Suena de miedo al principio, hasta que se da cuenta de que puede transpose toda la red, es decir, a su vez filas en columnas y columnas en filas, y luego aplicar el mismo código:
concatMap (chunks 2) (transpose grid) -- [[1,5],[5,9],[9,13],[2,6],[6,10],...]
Ahora la parte difícil: las líneas diagonales. Norman Ramsey da una idea: ¿y si pudiera eliminar 0 elementos de la línea 0, 1 elementos de la línea 1, etc.? La línea diagonal se convertiría en una línea vertical, que es fácil de extraer. Recuerde que para aplicar una función a cada elemento de una lista utiliza map, pero aquí debe aplicar diferentes funciones a cada elemento, a saber, drop 0, drop 1, drop 2, etc. map no sería adecuado. Pero mire, el primer argumento para drop forma un patrón de números sucesivos, que pueden representarse como una lista infinita [0..]. Ahora, ¿qué pasaría si pudiéramos tomar un elemento de [0..] Lo que necesitamos es una función que toma un número de una lista infinita [0..] y una fila de la cuadrícula, y aplica drop con este número a la fila. zipWith es lo que necesita:
zipWith drop [0..] grid -- [[1,2,3,4],[6,7,8],[11,12],[16]]
map head $ zipWith drop [0..] grid -- [1,6,11,16]
Pero quiero que todos diagonales de longitud 2, no sólo la mayor diagonal. Así que mira la cuadrícula y piensa, ¿qué líneas diagonales ves con elementos en la fila 0? [1,6],[2,7],[3,8]. Así que está claro que es necesario tomar sólo 2 primeras filas y la transposición elementos:
transpose $ zipWith drop [0,1] grid -- [[1,6],[2,7],[3,8],[4]]
ahora cómo consigo diagonales a partir de otras filas, así? ¿Recuerdas nuestro truco tails?Podemos obtener todas las diagonales proporcionando nuestra nueva función a un concatMap y aplicándolo a tails grid:
concatMap (transpose . zipWith drop [0,1]) (tails g)
-- [[1,6],[2,7],[3,8],[5,10],[6,11],...]
Pero estos son sólo diagonales que van desde la parte superior izquierda a la inferior derecha. ¿Y los que van de arriba a la derecha a abajo a la izquierda? Es más fácil sólo para revertir las filas de la cuadrícula:
concatMap (transpose . zipWith drop [0,1]) (tails $ reverse g)
-- [[13,10],[14,11],[15,12],[9,6],[10,7],...]
Por último, es necesario encontrar productos de todas las líneas y elegir el más grande. El código final se ve así:
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
¿Este código es al máximo elegante y eficiente? Diablos, no, pero funciona e ilustra ciertos patrones de pensamiento de la programación funcional. Al principio, necesita escribir un código que simplemente funcione, luego refactorizarlo iterativamente, hasta que llegue a una solución que sea fácil de leer y general.
por favor especifique el número de problema de Euler también. algunas personas ya lo han resuelto y pueden desear mirar su propia solución, y tal vez darle una respuesta útil basada en él – yairchu
Es problema # 11 – MtnViewMark