도적처럼

코드 출현 2016 18일차

1 부

충분히 쉬워보입니다...지금쯤이면

규칙 시각화

상대 좌표에서 trap 또는 safe로 가져오기

행의 초기 상태 생성

안전한 타일 수 세기

내 알고리즘 테스트

충분히 쉬운 것 같습니다...지금쯤

그리드의 행 수N 표시

특정 인접 타일 사용

그리고 일련의 규칙

알 겠어!

규칙 시각화

주어진...

ABC
 1

1는 다음과 같은 경우 트랩입니다.

ABC = T--
ABC = TT-
ABC = -TT
ABC = --T

따라서 1는 다음과 같은 경우에 안전합니다.

ABC = ---
ABC = -T-
ABC = T-T
ABC = TTT

상대 좌표에서 트랩 또는 금고로 이동

이 애니메이션은 내가 계획한 알고리즘을 시각적으로 보여줍니다.


이 의사 코드는 내가 계획한 알고리즘을 더 잘 설명하고 위의 애니메이션에서 힌트를 얻은 것에서 수정된 사전을 통합합니다.

Create an object with eight keys
  Each key is a 3-character representation of the rule to match, and the value is the resulting tile state

Set each tile as safe or trap based on the character returned from the following operations:
   Create a list of three relative coordinates:
     1. [-1,-1]
     2. [-1, 0]
     3. [-1, 1]
   Update each coordinate depending on the value of the cell that distance from the current tile:
     If the value is safe or the cell is outside the bounds of the grid
       Use 0
     Else, it's a trap
       Use 1
   Concatenate all three numbers together to form a 3-character string
   Return the character associated with the 3-character string in the eight-key object

이 JavaScript는 실제 작동하는 알고리즘입니다.

rules = {
    '000': '.',
    '010': '.',
    '101': '.',
    '111': '.',
    '100': '^',
    '110': '^',
    '011': '^',
    '001': '^'
}
// For each col in each row...
tiles[row][col] = rules[
  [[-1,-1],[-1,0],[-1,1]]
    .map(el => {
        let tile = tiles[row + el[0]][col + el[1]]
        switch (typeof tile) {
          case "undefined":
            return 0
            break;
          case "string":
            return tile == "." ? 0 : 1
            break;
        }
      }
    )
    .join('')
]

행의 초기 상태 만들기

위의 JavaScript는 tiles 라는 배열의 배열을 참조합니다.

첫 번째 행에 있는 셀을 제외한 모든 셀을 반복하기 전에 해당 배열은 어떤 모습이어야 합니까?
..^^. 행이 있는 3 입력의 경우:

[
 ['.','.','^','^','.'],
 [ , , , , ]
 [ , , , , ]
]

중첩 배열을 어떻게 구성할 수 있습니까?

let tiles = new Array(3)
  .fill(null)
  .map(
    el => new Array(input.length).fill(null)
  )
tiles[0] = input.split('')

마지막 줄을 제외하고 모두 각 셀의 값

으로 null를 사용하여 중첩된 배열을 만듭니다.

마지막 줄이 첫 번째 배열을 입력 문자열의 각 문자에서 생성된 배열로 바꿉니다

.

안전한 타일 계산

reduce() 구출, 두 번!

안쪽 타일은 각 안전 타일을 한 줄로 세고 있습니다

.

바깥쪽은 각 행의 개수를 계산합니다.

tiles.reduce(
  (sum1, row) => sum1 += row.reduce(
    (sum2, cell) => sum2 += cell == '.' ? 1 : 0, 0)
  , 0)

내 알고리즘 테스트

내 기능을 다음과 같이 호출합니다.

part1(input, rows)

part1('..^^.', 3) : 6

`part1('.^^.^.^^^^', 10): 38

그리고 40행에 대한 내 퍼즐 입력: 1926



그것이 정답입니다!

2 부

그리고 400K 행에 대한 내 퍼즐 입력:
...
...
거의 2천만!

그게 또 정답이야!

당연하게도 실행하는 데 10초 이상 걸렸습니다.

해냈어!!

두 부분 모두 해결했습니다!

이 시점에서 저는 이와 같이 더 간단한 인접한 셀 테마 퍼즐을 사용하여 작업하는 데 매우 자신이 있습니다!

2부의 성능 테스트가 황당하지 않은 한!