경비병 갈리반트

2024 코드 출현 6일차

1부

매우 친숙한 종류의 퍼즐

• 2D 그리드
• 전반적인 장애물
• 경로 추적
• 방문한 고유 타일 수를 세어보세요

가져가자!

한 번에 한 걸음씩

그리드 구문 분석:

let grid = input.split('\n').map(el => el.split(''))

경비원의 시작 위치를 식별하고 빈 타일로 교체:

let guard = null;
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

가드의 현재 회전을 추적하는 개체 만들기:

let facing = [
  [-1,0],
  [0,1],
  [1,0],
  [0,-1]
]

• 경비원은 북쪽을 향하기 시작하므로 후속 이동에는 더 작은 인덱스 행을 방문해야 합니다
• 장애물이 있을 때마다 경비원은 우회전해야 합니다
• 그렇게 하면 얼굴이 동쪽으로 변하게 되므로 이후의 움직임에는 더 큰 지수의 열을 방문해야 합니다
• 다음 셀이 장애물이 될 때마다 내 알고리즘은 목록에서 첫 번째 항목을 가져와서 뒤로 이동합니다

방문한 셀 추적:

let visited = new Set()

이동할 때마다 이 Set()에 문자열화된 좌표를 추가하려고 합니다.

경비원 이동:

while (true) {
  visited.add(guard.join(","));
  let next = [guard[0] + facing[0][0], guard[1] + facing[0][1]];
  if (
    next[0] >= 0 &&
    next[0] < grid.length &&
    next[1] >= 0 &&
    next[1] < grid[0].length
  ) {
    if (grid[next[0]][next[1]] == ".") {
      guard = next;
      console.log(guard);
    } else if (grid[next[0]][next[1]] == "#") {
      let oldDirection = facing.shift();
      facing.push(oldDirection);
    }
  } else {
    break;
  }
}

설명:

Keep going until manually broken out of
  Add the current coordinate to the tracked list
  Record the next location to visit
  If it is within the grid
    If it is empty cell
      Move the guard
    Else If it is an obstacle
      Rotate the guard
  Else
    Break out of the loop

이 알고리즘은 예제 입력에 대해 41개의 방문 셀 목록을 성공적으로 생성했습니다!

내가 입력한 퍼즐에 대한 정답이 생성되나요?

그렇습니다!!!

멋져요.

2부로!

2부

나는 이것이 오는 것을 어느 정도 보았고, 그것을 두려워하고 있었다

올바른 퍼즐을 위해 가능한 모든 옵션을 확인하세요.

읽을 때 제가 가장 궁금해하는 점은 다음과 같습니다.

• 경비원이 루프에 진입하면 어떻게 식별할 수 있나요?

하지만 저는 다음을 알고 있다고 생각합니다:

• 좌표뿐만 아니라 향한 방향도 추적해보겠습니다
• 목록에 추가되는 다음 항목의 복사본이 포함되어 있으면 루프가 시작됩니다

일을 훨씬 더 복잡하게 만들 시간입니다!

모든 루프를 찾기 위해 각 셀을 반복합니다.

먼저 경비원의 시작 셀을 제외하고 .가 있는 모든 셀의 목록을 생성하고 싶습니다.

let empties = [];
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == ".") {
      empties.push([r, c]);
    }
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

그런 다음 축소를 사용하여 각 . 그리드에서 그리드와 원래 가드 위치를 복사하고, 축소 내부에서 원본 코드를 많이 이동하고, 현재 상태의 인스턴스가 있는 추적된 좌표 및 회전 목록에 대한 조건을 포함하도록 while 루프를 확장합니다.

let part2 = empties.reduce((count, coord) => {
    let guardCopy = guard.slice()
    let gridCopy = grid.map(row => row.slice())
    gridCopy[coord[0]][coord[1]] = "#"
    let facing = [
        [-1,0],
        [0,1],
        [1,0],
        [0,-1]
      ]
    let visited = new Set()
    while (true) {
        let stamp = guardCopy.join(',') + facing[0].join(',')
        if (visited.has(stamp)) {
            count++
            break;
        } else {
            visited.add(stamp);
            let next = [guardCopy[0] + facing[0][0], guardCopy[1] + facing[0][1]]
            if (
              next[0] >= 0 &&
              next[0] < gridCopy.length &&
              next[1] >= 0 &&
              next[1] < gridCopy[0].length
            ) {
              if (gridCopy[next[0]][next[1]] == ".") {
                guardCopy = next;
              } else if (gridCopy[next[0]][next[1]] == "#") {
                let oldDirection = facing.shift();
                facing.push(oldDirection);
              }
            } else {
              break;
            }
        }
    }
    return count
}, 0)

많습니다.

하지만 효과가 있어요! 최소한 예시 입력에서는요.

그래도 나한테는 먹힐까???

음...실행하는데 30초 걸렸네요.

하지만...답이 나왔습니다!

그리고 그것은...

정답!!!

우후!!!

1부는 간단했습니다. 그리고 파트 2는 힘들었지만 규모가 커지는 것을 환영했습니다.

가방에 금별이 2개 더!

7일차까지.

위 내용은 경비병 갈리반트의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!