발굽

코드의 출현 2024 10일차

1부

짧은 공포, 그다음에는 설렘

저는 보통 모든 내용을 자세히 읽기 전에 한 페이지를 훑어봅니다.

오늘 본 내용은 다음과 같습니다.

• 그리드
• 그리고 길의 모습

그리고 이것이 또 최단거리 도전이 될까봐 두려웠습니다.

그럼 읽어봤습니다.

그리고 안도의 한숨을 쉬었습니다...적어도 1부에서는.

유효한 경로를 모두 찾아야 합니다.

그건...할 수 있어요!

0부터 시작

0을 모두 찾아야 해요:

input = input
  .split('\n')
  .map(
    line => line.split('').map(char => +char)
  )
let zeros = []
for (let r = 0; r < input.length; r++) {
    for (let c = 0; c < input[0].length; c++) {
        if (input[r][c] == 0) {
            zeros.push([r,c])
        }
    }
}

0초: 찾았습니다!

1씩 이동을 시도합니다.

각 0부터 유효한 경로는 각 숫자가 마지막 숫자보다 1 크고 9에서 끝나는 9단계입니다.

재귀 작업인 것 같습니다.

기본 케이스가 필요합니다:

1. 현재 숫자는 이전 숫자보다 정확히 하나도 크지 않습니다
2. 현재 숫자는 9입니다

내 알고리즘의 작동 방식은 다음과 같습니다.

Input:
1. Originating number
2. Current coordinates

Get current number

If it is not exactly one greater than the originating number
  Return false
Else
  If it is 9
    Return the current coordinates
  If it is not 9
    Continue with the coordinates in each orthogonal direction

지금 작성하고 보니 유효한 최종 좌표 원장을 추적하는 부분이 빠졌네요.

이 문제로 한동안 고생했습니다.

Set 또는 배열을 전달할 수 없다고 잘못 생각하게 만드는 오류가 계속 발생했습니다.

하지만 고맙게도 재귀 함수의 추가 호출에 전달하는 것을 잊어버렸습니다.

작동하는 재귀 알고리즘은 다음과 같습니다.

let dirs = [[-1,0],[0,-1],[0,1],[1,0]]
function pathFinder(num, coord, memo) {
    let current = input[coord[0]][coord[1]]
    if (current - num !== 1) {
        return false
    } else if (current == 9) {
        memo.add(coord.join(','))
        return
    } else {
        dirs.forEach(dir => {
            if (
                coord[0] + dir[0] >= 0 &&
                coord[0] + dir[0] < input.length &&
                coord[1] + dir[1] >= 0 &&
                coord[1] + dir[1] < input[0].length
            ) {
                pathFinder(
                  current, 
                  [coord[0] + dir[0], coord[1] + dir[1]], 
                  memo
                )
            }
        })
    }
}

0의 좌표로 시작해야 하므로 첫 번째 호출에서는 -1을 사용합니다.

pathFinder(-1, zeroCoordinate, matches)

마지막으로 올바른 점수를 얻기 위해 각 0을 반복하여 고유한 대상 9 세트를 생성하고 세트의 크기를 유지하고 합산합니다.

let part1 = zeros.map(z => {
    let matches = new Set()
    pathFinder(-1, z, matches)
    return matches.size
}).reduce((a, c) =>  a + c)

빠른 테스트, 빠른 결과

작은 예시 입력에 대한 정답을 생성했습니다.

더 큰 예제 입력의 경우

그리고...

...내 퍼즐 입력을 위해!!!

우후!!!

파트 2에서는 무엇에 도전하게 될까요?

2부

음, 그건 너무 쉬운 것 같아

1부에서 알고리즘을 작성한 방식에 따르면 정답을 얻으려면 몇 가지 작은 변경만 필요하다는 뜻일까요?

모두 세어보세요!

지금은 유효한 각 9를 세트에 추가합니다.

파트 2의 경우 유효한 9마다 카운터를 증가시키면 될 것 같습니다.

한번 시도해 볼 가치가 있습니다!

Set을 Array로 변경하면 짜잔!

예제의 정답입니다.

내가 입력한 퍼즐의 정답입니다.

와우. 우와. 와.

다음날...훨씬 더 힘들 것 같습니다.

위 내용은 발굽의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!