세레스 검색

2024 코드 출현 4일차

1부

X는 (수백 개의?) 지점을 표시합니다.

지금까지 이런 문자 그대로 단어 검색 퍼즐이 없었다는 사실에 놀랐습니다.

어려운 일 같지만 내 전략은 다음과 같습니다.

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

예를 통해 이 전략을 확인해 보니 이것이 성공적인 접근 방식이라고 믿게 되었습니다.

이제 흥미로운 부분입니다. 이 모든 것을 처음부터 코딩하세요!

결국 그리드에서 각 X의 인덱스를 찾습니다.

먼저 입력을 2D 문자 배열로 구문 분석해야 합니다.

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

그리드 퍼즐에서 제가 자주 직면하는 장애물은 범위를 벗어난 지수를 설명하는 것입니다.

경계 셀(또는 경계에 가까운 셀)에서 시작하여 가장자리 방향으로 지금까지 걸어가면 결국 경계를 벗어난 행이나 열을 만나게 됩니다.

이 문제를 해결하기 위한 두 가지 전략이 있습니다.

1. 존재하지 않는 행이나 열에 대한 조건에 검사 추가
2. 경계를 벗어날 위험이 없도록 충분한 행과 열로 그리드를 채우세요

이번 챌린지는 #2를 선택합니다.

3셀 두께의 테두리로 그리드를 채우면 다음과 같습니다.

grid = grid.map(line => ['.','.','.',...line,'.','.','.'])
grid = [
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  ...grid,
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.')
]

이제 그리드 예시는 다음과 같습니다.

................
................
................
...MMMSXXMASM...
...MSAMXMSMSA...
...AMXSXMAAMM...
...MSAMASMSMX...
...XMASAMXAMM...
...XXAMMXXAMA...
...SMSMSASXSS...
...SAXAMASAAA...
...MAMMMXMMMM...
...MXMXAXMASX...
................
................
................

이제 패딩된 그리드에 있는 각 X의 좌표를 목록화할 준비가 되었습니다.

let Xs = []
for (let row = 0; row < grid.length; row++) {
  for (let col = 0; col < grid[0].length; col++) {
    if (grid[row][col] == "X") {
      Xs.push([row, col])
    }
  }
}

성공: 예제 그리드에서 19개의 X를 모두 찾았습니다!

각 X에서 8방향으로 3걸음 걷기

8개의 상대 좌표는 모두 8개 요소 배열로 코딩됩니다.

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

이제 주요 알고리즘은 다음과 같습니다.

For each X
  For each direction
    Create an array that starts with X
    Do 3 times
      Move one cell in this direction
      Add the value of that cell to the array
    Check whether the concatenation of all four values is "XMAS"
      If it is, increment a tally

그리고 JavaScript에서는:

Xs.reduce((total, coord) => {
  dirs.forEach((dir) => {
    let [row, col] = coord;
    let [y, x] = dir;
    let word = ["X"];
    for (let i = 0; i < 3; i++) {
      row += y;
      col += x;
      word.push(grid[row][col]);
    }
    if (word.join("") == "XMAS") {
      total++;
    }
  });
  return total;
}, 0);

예제 입력에 대한 정답을 생성합니다!

퍼즐 입력으로 실행하면 어떻게 될까요??!!

숫자를 얻습니다: 수천 개의 'XMAS'

정답인가요?

그렇습니다!!!

우우우우!!!

파트 2의 내용이 너무 기대됩니다...

2부

아아아아. 좀 더 복잡해졌습니다. 하지만 가능합니다!

1부에서는 X를 찾고 있었어요.

지금 저는 Ms.를 찾고 있습니다.

1부에서는 단어를 만들기 위해 글자를 직선으로 적어봤습니다.

이제 5셀 문구의 네 가지 구성을 찾고 있습니다.

M S   M M   S M   S S
 A     A     A     A
M S   S S   S M   M M

하나의 M은 여러 X-MAS의 일부가 될 수 있습니다.

M을 하나하나 확인하다 보면 여러 번 만날 가능성이 높습니다.

각 일치 항목에 대해 문자열화된 좌표의 Set()을 구축해야 합니다. 이렇게 하면 X-MAS 인스턴스를 한 번만 설명합니다.

갑자기 - 훌륭해! - 아이디어

M마다 확인하지는 않겠습니다.

A 하나하나 확인해보겠습니다.

그리고 시계방향으로 대각선으로 인접한 4개의 셀을 확인해보겠습니다.

X-MAS 경기는 다음 네 가지 패턴 중 하나에 적합합니다.

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

`

휴! 이것은 내 원래 아이디어보다 훨씬 덜 지루할 것입니다.

그리고 대부분의 Part 1 코드를 재활용할 수 있을 것입니다!

복사-붙여넣기-조정

그리드에서 모두 As 찾기:
js
As = [];
for (let row = 0; row for (let col = 0; col if (grid[row][col] == "A") {
As.push([행, 열]);
}
}
}

확인할 상대좌표 순서 정하기:
js
Adirs = [
하자 [-1, -1],
[-1, 1],
[1, 1],
[1, -1],
];

경기 집계 추가:
js
let part2 = As.reduce((total, coord) => {
시계 방향 = Adirs.map((dir) => {
let [행, 열] = coord;
let [y, x] = dir;
그리드[행 y][열 x];
반환 });
if (["MSSM", "MMSS", "SMMS", "SSMM"].includes(clockwise.join(""))) {
전체 ;
}
총액 반환;
}, 0);

예제 입력에 대한 정답을 생성합니다!

이제 내 퍼즐 입력을 확인하겠습니다...

그렇죠!!! 정답!!!

Ms 대신 As를 사용하게 되어 정말 기쁩니다.

두려운 문제를 해결하는 데 드는 시간을 절약할 수 있었습니다.

또 하나의 재미있고 접근하기 쉬운 퍼즐이었습니다!

5일차에는 어떤 일이 있을지 궁금합니다.

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