가로, 세로 및 대각선에 숫자 곱하기

Question

현재 재미있는 프로젝트 오일러 문제 (www.projecteuler.net)를 작업하고 있지만 걸림돌이되었습니다. 이 문제 중 하나는 20x20 격자의 숫자를 제공하고 직선에 4 개의 숫자로 구성된 가장 큰 곱셈을 요구합니다. 이 선은 가로, 세로 또는 대각선이 될 수 있습니다.

절차 언어를 사용하면 문제를 해결할 수 있지만 처음부터 이러한 문제를 해결하려는 동기 중 하나는 더 많은 경험을 얻고 더 많은 하스켈을 배우는 것입니다.
지금 당장 그리드를 읽고 int 목록 (예 : [Int]) 목록으로 변환합니다. 이것은 수평 곱셈을 하찮게 만들고,이 격자를 조 변경하여 수직도 또한 사소 해집니다.

대각선은 나를 괴롭히는 것입니다. 몇 가지 방법을 생각해 봤지만 명시 적 배열 슬라이싱 또는 인덱싱을 사용하여 솔루션을 얻을 수 있지만 지나치게 복잡하고 해킹 된 것처럼 보입니다. 아마도 여기에는 우아하고 기능적인 해결책이있을 것이라고 생각합니다. 다른 사람들이 생각해 낼 수있는 것을 듣고 싶습니다.

Answer 1

나는 Don Stewart와 의견이 맞지 않습니다. 문제의 조합 적 특성과 문제 크기가 20x20이라는 사실을 감안할 때 목록의 목록은 충분히 빠르지 않을 것입니다. 그리고 마지막으로 원하는 것은 배열 인덱싱을 사용하는 것입니다. 대신 리차드 버드 (Richard Bird)가 개발 한 기술을 자신의 정당한 이름 인 sudoku solver에서 연장하는 것이 좋습니다.

• 그리드를 주어진 함수를 작성 길이 4

• 의 모든 연속 서브 시퀀스를 반환 시퀀스를 주어진 함수를 작성, 모든 반환 구체적으로, 나는이 다음 좋을 것 행.

• 표를 제공하는 함수를 작성하여 모든 열을 반환합니다.

• 그리드를 지정하면 모든 대각선을 반환하는 함수를 작성하십시오.

이러한 기능을 사용하면 쉽게 해결할 수 있습니다. 그러나 대각선은 그리 명백하지 않습니다. 어쨌든 대각선이란 무엇입니까? 의 예를 살펴 보자 :

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

당신이 drop 기능을 사용하고 행 0 0 요소 등 1 개 행 1 요소 및 드롭 잠시 가정 해 보자. 여기에 다음과 같은 내용이 있습니다.

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

대각선 요소는 이제 남긴 삼각형의 첫 번째 열을 형성합니다.심지어 더 좋게도, 모든 왼쪽에있는 항목의 열은 원래 행렬의 대각선입니다. 몇 가지 대칭 변환을 수행하면 모두 모든 크기의 정사각형 행렬을 쉽게 열거 할 수 있습니다. "길이 4의 연속적인 서브 시퀀스"기능으로 각각 하나씩 놀리십시오, 그리고 Bob은 당신의 삼촌입니다!

---

붙어있을 수 있습니다 사람들을 위해 조금 더 자세히 :

는

이 문제의 핵심은 구성입니다. 대각선은 네 그룹으로 나뉩니다. 내 예제는 하나의 그룹을 제공합니다. 나머지 세 개를 얻으려면, 대칭의 대칭 이미지, 대칭 및 대칭 이미지에 동일한 기능을 적용하십시오.

• 트랜스 포즈는 한 줄 기능이며 열을 깨끗하게 복구하려면 필요합니다.

• 거울 이미지는 조옮김보다 훨씬 간단합니다. — 서곡에서 사용할 수있는 기능에 대해 생각해보십시오.

대칭법은 각 주요 대각선을 두 번 나타냅니다. 다행히도 문제는 대각선을 반복하는 것이 좋습니다.

Answer 2

함수를 사용하여 목록의 요소를 색인으로 검색 할 수 있습니다. 색인을 증가 시키거나 감소시키는 고정 단계를 통해 대각선이됩니다.

Answer 3

목록은 일정 시간에 임의의 색인 생성을 제공하지 않으므로이 문제에 대한 잘못된 데이터 구조입니다. 선형 순회를 지향합니다. 따라서 대각선은 항상 목록과 함께 더 성가 시거나 느려질 것입니다.

배열 사용은 어떻습니까? 예 : parallel vectors 또는 regular vectors입니다.

Answer 4

글쎄,이 특별한 문제 때문에, 하나의 선형 목록이나 배열이 실제로 가장 쉬운 구조입니다! 열쇠는 주어진 뛰기를 가진 명부를 건너 뛰기 것과 같이이 뛰기에 대하여 생각하기위한 것이다. 그리드는 다음의 크기 × w H,

• 경우 수평 런 수직 런
• 한 대각선 실행 w 의 보폭을 가지고 1
• 의 보폭을 가지고 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] 

, 효율적인 구현, 당신은 그래서 es!

Answer 5

와 Data.Array Int a 및 es!! 같은과 [a]을 대체 할 거라고는되는 N × N 그리드를 가지고 모든 수평을 추출 할 , 길이 M의 수직선과 대각선을 긋고 최대 곱을 구하십시오. 라인 길이가 2 인 상태의 예를 4x4 그리드에 대한 몇 가지 하스켈 기술을 설명하자

chunks 2 [1,2,3,4] == [[1,2],[2,3],[3,4]] 

:

이

[[ 1, 2, 3, 4], 
[ 5, 6, 7, 8], 
[ 9,10,11,12], 
[13,14,15,16]] 

수평 및 수직 쉽게, 당신이 필요로하는 모든이 목록에서 길이 M의 덩어리를 추출하는 기능입니다

해당 기능의 유형은 [a] -> [[a]]입니다.이것은 목록과 관련된 함수이므로 휠을 다시 만들기 전에 Data.List과 비슷한 내용이 있는지 살펴 보겠습니다. 아하, tails는 제거 목록의 시작 부분에서 더 많은 요소 목록을 반환 유사하다 : 단지 우리가 길이 2의를 만들기 위해 하위 목록을 단축 할 수 있다면

tails [1,2,3,4] == [[1,2,3,4],[2,3,4],[3,4],[4],[]] 

하지만 우리가 할 수있는, map를 사용하여 원래 작업이 가장 큰 제품을 찾을 수 있으며, [15, N] ≥의 제품으로 난 작은 라인에 대해 걱정하지 것이다

map (take n) (tails xs) -- [[1,2],[2,3],[3,4],[4],[]] 

:리스트의 모든 원소에 함수를 적용하고 새로운 목록을 반환 기능, [15]의 제품, N ≥ 1. 그러나 당신이 그 (것)들을 제거하고 싶은 경우에, th 길이 N의 목록에는 길이 M의 N-M + 1 청크가 포함되어 있으므로 take (4-2+1)을 결과 목록에 적용 할 수 있습니다. 또는 당신이 할 수 단순히 filter 목록 :

chunks n xs = filter ((==n) . length) $ map (take n) (tails xs) 
-- [[1,2],[2,3],[3,4]] 

좋아, 우리는 목록에서 덩어리의 목록을 추출 할 수 있지만, 우리는 2D 그리드가 아닌 단순 목록을 가지고! 결과 코드는 별도의 목록에 덩어리를두고, 우리는 실제로 상관하지 않는 선에서 덩어리가 시작된 않는 한 그것은 일을 복잡하게

map (chunks 2) grid -- [[[1,2],[2,3],[3,4]],[[5,6],[6,7],[7,8]],...] 

을하지만, 여기에 일이 : map 다시 우리를 구출. 그래서 우리는 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 (transpose . zipWith drop [0,1]) (tails g) 
-- [[1,6],[2,7],[3,8],[5,10],[6,11],...] 

을하지만 이들은에서 이동에만 대각선입니다 왼쪽 상단 오른쪽 아래에 : 우리는 concatMap에 새로운 기능을 제공하고 tails grid에 적용하여 모든 대각선을 얻을 수 있습니다. 오른쪽 상단에서 왼쪽 하단으로 이동하는 것은 어떻습니까? 그것은 쉬운 그냥 그리드의 행을 반대합니다 :

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 

이 코드는 최대한 우아하고 효율적입니까? 지옥 아니,하지만 작동 및 함수 프로그래밍의 생각의 특정 패턴을 보여줍니다. 처음에는 읽기 쉽고 일반적인 솔루션에 도달 할 때까지 작동하는 코드를 작성한 다음 반복적으로 리팩터링해야합니다.