Code Day n Golang의 출현: XMAS 및 X-MAS 검색

소개

4일차로 넘어가면 우리 앞에 그리드 문제가 있습니다. 그리드 형태의 숫자, 즉 대문자가 포함된 행과 열이 주어집니다. 우리가 해야 할 일은 모든 방향(위, 왼쪽, 아래, 오른쪽, 대각선)에서 XMAS라는 단어를 찾는 것이고, 두 번째 부분에서는 X를 형성하는 MAS라는 단어를 찾아야 합니다.

그럼 golang에서 어떻게 접근하고 해결할 수 있는지 살펴보겠습니다.

여기 GitHub에서 제 솔루션을 확인하실 수 있습니다.

미스터 파괴자 / 출현_코드

코드의 출현

그리드 구성

문제의 가장 근본적인 부분은 실제로 텍스트를 그리드나 행렬 형태로 변환하는 것입니다. 행을 개별 행으로 분할하고 각 문자를 목록의 요소로 추가할 수 있으며, 이렇게 하면 행렬 또는 격자형(2차원) 구조인 문자열 목록을 가질 수 있습니다.

아래는 퍼즐에 대한 입력입니다.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

이런 식으로 변환해야 합니다

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

이것은 문자열 목록입니다. golang에서는 [][]string 이라고 말할 수 있습니다. 다음과 같은 함수를 만들어서 그렇게 할 수 있습니다:

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

위 함수는 문자열 목록을 가져와 그리드의 개별 문자인 문자열 목록을 반환합니다.

파일 바이트를 읽고 개행 문자로 바이트를 분할한 다음 이것이 이 함수의 입력으로 사용됩니다.

따라서 입력이 그리드로 구문 분석되면 XMAS라는 단어를 찾는 실제 논리에 대해 생각해 볼 수 있습니다.

1부

첫 번째 부분에서는 매트릭스에서 나타날 수 있는 XMAS라는 단어를 찾아야 합니다.

• 전달(XMAS로)

• 뒤로(SAMX로)

• 위로
  

            S
            A
            M
            X

• 아래쪽으로

            X
            M
            A
            S    

• 대각선 위쪽(오른쪽 또는 왼쪽 위)

            S
              A
                M
                  X

            OR
                  S
                A
              M 
            X

• 아래쪽 대각선(오른쪽 또는 왼쪽)

                     X
                   M
                 A
               S

            OR

            X
              M
                A
                  S

따라서 XMAS가 그리드에 나타날 수 있는 방향은 8개이며 이러한 XMAS는 n개 있을 수 있습니다. 그리드에서 이들의 개수를 찾아야 합니다.

이 문제에 접근하려면 XMAS라는 단어의 첫 번째 문자를 찾은 다음 모든 방향에서 하나씩 검색하여 M을 찾았는지 확인하고 어느 방향에서든 M을 찾았으면 계속해서 앞으로 나아갈 수 있습니다. 그 방향에 A, S가 있는지 확인해보세요.

접근 방식은 다음과 같습니다.

• 카운터를 0으로 초기화

• 각 라인을 반복

  • 줄의 각 문자를 반복합니다

    • 문자가 X와 같은지 확인하세요.

    • 캐릭터가 X인 경우→

      • 모든 방향(위, 아래, 오른쪽, 왼쪽, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래)을 반복합니다

        • M이라는 캐릭터를 찾으면 그 방향으로
        • 같은 방향으로 계속 이동하여 A와 S를 유사하게 찾습니다. 모든 문자 XMAS를 찾았으면 카운터를 증가시킵니다
        • 그렇지 않으면 루프에서 다른 방향을 선택하세요

복잡하고 커 보이지만 간단합니다. 한 번에 하나씩 집중하면 쉽게 해결할 수 있습니다.

이를 구현하려면 먼저 몇 가지 사항을 정의해야 합니다.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

그래서 우리는 원하는 위치에 도달하기 위해 더하거나 빼야 하는 x 및 y 좌표 방향의 정수 목록을 정의했습니다. 이는 기본적으로 단위 벡터와 같으며 거리가 1이고 방향이 또는 -로 표시되어 x 좌표는 왼쪽이나 오른쪽으로, y 좌표는 위아래로 이동함을 나타냅니다.

좀 더 명확하게 설명하자면, 제가 4x4 차원의 그리드에서 (1,2)에 있다고 가정하겠습니다.

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

2,1에는 G가 있으므로 이에 대한 몇 가지 지침을 확인합니다

up → 0,-1 → 2 0, 1-1 → 2,0, C로 이동했습니다

오른쪽 → 1,0 → 2 1, 1 0 → 3,1, H로 이동했습니다

아래, 왼쪽 → -1,1 → 2-1, 1 1 → 1, 2, J로 이동했습니다

그러면 우리가 이 좌표를 사용하여 어떤 방향으로 움직이고 있다는 것을 알 수 있습니다.

이 요소를 사용하여 해당 요소에 검색 중인 단어에 다음 문자가 있는지 확인하려는 다음 방향 점프를 얻을 수 있습니다.

이 작업을 먼저 수행하는 함수를 작성하고 그리드에서 단어를 찾았는지 확인하는 함수를 추상화하겠습니다.

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

위 함수는 그리드를 입력받아 점수가 될 정수, 즉 그리드/행렬에서 발견된 XMAS 단어의 개수를 반환합니다.

먼저 그리드의 각 행을 반복해야 합니다. 각 행에 대해 문자를 반복하므로 x 및 y 좌표를 그리드의 인덱스로 갖게 됩니다. 그런 다음 현재 문자가 X 또는 wordList[0]인지 확인해야 합니다. 그렇다면 모든 방향을 반복하고 해당 방향에서 XMAS, 즉 MAS를 찾을 수 있는지 확인하고, 그렇다면 카운터를 증가시킵니다. FindXMAS 함수는 무엇입니까? 이를 추상화하고 현재 단어의 좌표인 x, y를 전달하고 XMAS의 단어 위치가 될 1을 전달합니다. 이 경우 필요한 X를 이미 찾았습니다. 그 방향으로 MAS를 찾으세요. 그리드와 방향을 전달하므로 해당 방향에 MAS가 있으면 이 함수는 true 또는 false를 반환합니다.

반복하자면:

• 그리드를 반복하여 행과 x를 문자열 목록으로 가져오고 현재 행의 인덱스를 얻습니다.

• 각 행, 즉 문자열 목록에 대해 문자열 목록을 반복하여 char 및 y를 문자(문자열)로 가져오고 문자열 목록에서 해당 문자의 인덱스를 가져옵니다.

• 현재 문자가 wordList의 0번째 인덱스인 X와 같다면

  • 모든 방향을 반복하고 FindXMAS 함수를 호출하여 해당 방향에 나머지 단어 MAS가 있는지 확인합니다
  • 모든 단어를 찾으면 카운터를 증가시킵니다.

• 그래서 그리드/행렬의 XMAS 단어 수를 세면서 카운터를 반환합니다.

이제 x, y 좌표, 단어 위치, 방향 및 그리드를 입력받아 단어가 발견되면 반환하는 FindXMAS 함수를 구현할 수 있습니다.

• 먼저 현재 x 좌표를 가져와 방향의 x 구성요소(0번째 인덱스 또는 첫 번째 요소)를 추가합니다

• 현재 y 좌표를 방향의 y 구성요소(첫 번째 인덱스 또는 두 번째 요소)에 추가

• 단어 위치, 즉 단어 인덱스나 현재 함수에 있는 단어 자체가 wordList와 동일하다면, 원하는 단어를 완전히 찾았다는 뜻입니다

• x와 y 좌표에 방향을 추가하여 확인해야 합니다. 그리드의 너비와 높이를 초과하지 않으므로 그렇게 하면 false를 반환합니다

• 마지막 if는 현재 문자가 찾고 있는 단어와 동일한지 확인하기 위한 것으로 M, A 또는 S가 될 수 있습니다. 그렇다면 업데이트된 x 및 y 좌표와 wordList의 다음 단어를 전달하여 FindXMAS 함수를 재귀적으로 호출하고 방향을 동일하게 유지하고 전체 그리드를 전달합니다.
  

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

그래서 우리는 FindXMAS 함수를 구현했습니다. 이는 좌표를 업데이트하고 격자의 해당 위치에 있는 단어가 MAS의 다음 단어인지 확인하여 특정 방향으로 이동하여 MAS 단어를 찾았는지 반환합니다. 목록.

전체 첫 번째 부분은 다음과 같습니다.

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

행을 문자열 목록으로 가져와 ConstructGrid에 전달하고 그리드를 얻습니다. 마지막으로 그리드를 전달하고 그리드에 있는 XMAS 단어 수로 점수를 얻어 TraverseGrid를 호출합니다.

1부에서 나온 내용입니다.

2부

2부에서는 아래와 같이 십자 모양의 MAS를 찾아야 합니다.

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

이 문제를 해결하려면 비슷한 접근 방식을 사용할 수 있지만 훨씬 간단합니다. 중앙에 항상 MAS라는 단어가 있으므로 A를 찾으면 됩니다. 따라서 A가 있는지 확인하고 왼쪽 상단에 , 오른쪽 상단 또는 오른쪽 하단, 왼쪽 하단에는 M 또는 S가 있습니다.

1을 더하고 빼서 오른쪽 위, 왼쪽 위 위치, 오른쪽 아래, 왼쪽 아래 위치의 좌표를 얻습니다. 그리드의 경계를 초과하지 않는지 기본적인 점검을 합니다. 경계를 초과하면 MAS를 찾을 수 없습니다

그러나 그리드 내에 있는 경우 이제 4개 위치에 문자를 가져오고 왼쪽 상단과 오른쪽 하단에 M, S 또는 S 또는 M이 있는지 확인합니다. 마찬가지로 오른쪽 상단과 왼쪽 하단도 마찬가지입니다. 각각 M과 S 또는 S 또는 M을 갖습니다. 문자 A 위와 아래의 M과 S에 대한 대각선 검색입니다.

따라서 두 대각선이 모두 일치하면 true를 반환합니다.

            S
            A
            M
            X

이것이 MAS 대각선을 찾는 간단한 구현입니다.

이제 TraverseGrid를 약간 변경해야 합니다. 그리드를 반복하고 행의 문자에 A가 있는지 확인하기만 하면 됩니다(예: wordList[2]). 이제 A가 있으면 현재 좌표와 그리드를 사용하여 FindMAS 함수를 호출해야 합니다. 해당 함수가 true를 반환하면 카운터를 증가시킵니다.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

이것이 파트 2의 최종 구현입니다. 교차 방향의 MAS 수를 구합니다.

여기 GitHub에서 제 솔루션을 확인하실 수 있습니다.

결론

이것이 Advent of Code in Golang 4일차의 내용입니다. 제안 사항과 이에 접근한 방법이 있으면 알려주세요. 더 나은 솔루션이 있나요?

행복한 코딩하세요 :)

위 내용은 Code Day n Golang의 출현: XMAS 및 X-MAS 검색의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!