인코딩 오류

코드 출현 2020 9일차

다음은 예제 입력을 사용한 두 알고리즘의 시각화입니다.

과제: X에 대해 풀기 여기서...

1 부:

X = the first number that is not the sum of two of the N numbers before it

및 N = 25

2 부:

X = the sum of the smallest and largest numbers included in a list of contiguous numbers from the puzzle input that sum to the number identified in Part 1

N = 5인 입력 예

35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576

다음을 나타냅니다.

일련의 숫자

1 부

'하강 계단' 알고리즘 시각화

그 알고리즘을 쓰려고 하다가...중지

훨씬 간단하고 작동하는 알고리즘

'내림차순 계단' 알고리즘 시각화

숫자 그룹 중에서 가능한 모든 합을 추적해야 하는 것 같습니다.

그 숫자가 1-5라고 가정 해 봅시다.

   1 2 3 4 5

1  2 3 4 5 6
2  3 4 5 6 7
3  4 5 6 7 8
4  5 6 7 8 9
5  6 7 8 9 10

다음으로, 같은 숫자를 두 번 더하는 것에서 합계를 제외해야 합니다.

   1 2 3 4 5

1    3 4 5 6
2  3   5 6 7
3  4 5   7 8
4  5 6 7   9
5  6 7 8 9  

그리고 우리는 합계를 얻었습니다.

공식은 다음과 같을 수 있습니다.

Where N = the size of the group
N * (N - 1) = the amount of sums to track

N = 5
5 * (5 - 1) = 20 sums to track

N = 25
25 * (25 - 1) = 225 sums to track

포함된 합계로 확인할 첫 번째 숫자가 6이라고 가정합니다.

   1 2 3 4 5

1    3 4 5 6
2  3   5 6 7
3  4 5   7 8  <-- 6?
4  5 6 7   9
5  6 7 8 9  

예! 거기에 있습니다.

합계 그룹은 어떻게 조정해야 합니까?

정확히 보여주기 위해 만든 비주얼은 다음과 같습니다.


매 턴:

가장 빠른 숫자의 모든 합계가 제거됩니다.

가장 앞선 숫자와 다음 숫자를 사용하여 형성된 합계는 제거됩니다.

해당 숫자와 그룹

에 포함하기 위해 방금 확인한 숫자의 합계를 포함하는 각 후속 숫자의 하위 집합에 요소가 추가됩니다.

끝에 새 하위 집합이 추가되고 새로 추가된 숫자와 끊임없이 변화하는 목록의 미리 합산된 각 숫자의 합계를 포함하는 값으로 채워집니다(앞에 있던 숫자 빼기)

해당 알고리즘을 작성하려고 시도하다가 중지합니다.

중첩 루프로 시작: 각 숫자

에서 합계 그리드 생성

그런 다음 모든 종류의 잘못된 느낌을 주는 일련의 배열 조회, 삭제 및 삽입 단계로 빠르게 발전했습니다.

증분 카운터 값보다 하나 더 큰 위치에 요소를 삽입하는 방법을 알 수 없을 때 알고리즘 작성을 중단했습니다. 그 시점에서 내 노력이 헛된 것이라고 느꼈기 때문입니다.

훨씬 간단하고 작동하는 알고리즘

나는 잠자리에 들었고 대답이 나를 때렸습니다!

Forget about storing and updating a list of sums

Store the puzzle input as an array of numbers

Create and store the preamble subset

Check as many numbers needed in the preamble until a match is found for the inclusion of the number that equals the next number in the input list minus the number being checked
  If a match is found
    Escape the loop immediately with an indication that a match was found

Update the preamble subset such that the first number is removed and the next number in the input list is added
  Else, if no match is found
    Return the next number in the input list

다음은 해당 알고리즘의 시각화입니다.

2 부

어디서부터 시작할까요, 시작인가요 끝인가요?

작업 알고리즘 작성

어디에서 시작할 것인가, 시작인가 끝인가?

예시된 예에서 첫 번째 유효하지 않은 숫자에 합산되는 연속 숫자 집합은 목록의 시작 부분에 더 가깝습니다.

하지만 내 퍼즐 입력의 첫 번째 잘못된 숫자는 목록의 끝에 더 가깝습니다

그래서 처음부터 시작하는 알고리즘을 만들 수 있습니다

하지만 목록의 길이, 처음에 훨씬 더 작은 숫자에서 누적해야 하는 연속 목록의 길이를 고려할 때 성능이 떨어지는 것 같습니다. 목록

의 시작보다 잘못된 숫자입니다.

결정됨: 유효하지 않은 숫자 앞의 1부터 시작하여 입력 목록의 처음부터가 아니라 역방향으로 작업하고 앞으로 작업

작동하는 알고리즘 작성

Run Part 1's algorithm to identify the first invalid number
Store the location of that number in the puzzle input list
Initialize an incrementing value i to 1
Create an empty array, nums
Do as long as the numbers stored in nums do not sum to the invalid number
  Set an incrementing value j to i
  Do as long as the numbers stored in nums sum to a value less than the invalid number
    Insert in nums the value from the puzzle input at the location equivalent to the location of the invalid number minus the value stored in j
    Increment j by 1
  If, by now, nums is empty or the numbers stored in nums sum to a value greater than the invalid number
    Reset nums to an empty array
    Increment i by 1
Return the sum of the highest and lowest numbers in nums

위치 650 근처의 유효하지 않은 숫자부터 시작하는 것이 현명했던 것 같습니다. 퍼즐 입력의 경우 위치 500 주변에서 시작된 17개의 연속된 숫자 목록이 있기 때문입니다.

다음은 예제 입력을 사용한 두 알고리즘의 시각화입니다.