어댑터 어레이

코드 출현 2020 10일차

NullDev의 알고리즘을 사용하여 Part 2의 시뮬레이터를 사용해 보십시오.

작업: X에 대해 풀기 여기서 X =

정렬된 충격 측정값 간의 1개 및 3개 정수 차이 카운트의 곱

어댑터를 정렬할 수 있는 고유한 방법의 총 수

예시 입력

16
10
15
5
1
11
7
19
6
12
4

다음을 나타냅니다.

어댑터 모음

각각의 출력 흔들림

1 부

혼란, 그 다음 명확성, 그 다음 자신감

작업 알고리즘 작성

혼란, 그 다음 명료성, 그 다음 자신감

혼란: 이 퍼즐의 소개 문장 때문에 어디서부터 시작해야 할지 모르겠다는 생각이 들었습니다

.

명료성: 예제 입력을 사용한 연습은 이 퍼즐의 규칙이 무엇인지 이해하는 데 도움이 되었습니다

.

자신감: 알고리즘 방식으로 문제를 해결하는 방법을 즉시 알았고 다행히 알고리즘이 작동했습니다!

작동하는 알고리즘 작성

Process the input into a sorted array of numbers

Insert two values: one at the beginning and another at the end

Accumulate a 3-element array representing tallies for each 1-, 2- and 3-integer difference between each subsequent value

Return the product of the integers tallying all 1- and 3-integer differences

내 알고리즘의 시각화는 다음과 같습니다.

2 부

그게 오는 걸 봤어야 했는데

알아낸 줄 알았는데

그렇게 간단할 줄 알았어!

작동 방식을 확인해야 했습니다

.

나는 그것이 오는 것을 보았어야 했다

파트 1이 쉽게 느껴질 때 - 나에게! - 파트 2가 속도 테스트라는 신호인 경우가 많습니다...제가 풀 수 없는 경우가 많습니다

.

1, 2 및 3 정수 차이를 감안할 때 파트 2는 '얼마나 많은 배열이 가능한가?'에 대한 테스트가 되어야 합니다.

내가 알아냈다고 생각했어

첫 번째 예제 입력을 참조로 사용하여 순서대로 번호는 다음과 같습니다.

1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19

내 잘못된 논리는 해결책을 향한 다음 경로를 따랐습니다.

Legend:
0 numbers in-between = 1
1 number in-between  = 2
2 numbers in-between = 4

1 - 4:   0 -> 1
4 - 7:   2 -> 4
7 - 10:  0 -> 1
10 - 12: 1 -> 2
12 - 15: 0 -> 1
15 - 16: 0 -> 1
16 - 19: 0 -> 1

1 * 4 * 1 * 2 * 1 * 1 * 1
4 * 2
8

안타깝게도 두 번째 예에서 이 공식을 사용하면 19208이 아닌 ~2000이 생성됩니다.

나는 그것이 그렇게 간단하다는 것을 알고 있었다!

고맙게도 제가 즐겨 사용하는 JavaScript 솔버인 NullDev는 시뮬레이션을 사용하여 완전히 이해해야 한다고 느꼈던 우아한 하위 5줄 솔루션을 작성했습니다!

Create step, a 1-element array containing the value 1
For i from 0 to the maximum value in the sorted array of numbers from the input
  Set j to i + 1
  While the number at location j in the sorted array is less than or equal to i + 3
    Set the item at location j in step equal to the sum of the item at location i in step and either the item at location j in step or 0
    Increment j
Return the last value in step

NullDev의 알고리즘이 어떻게 작동하는지 머릿속으로 추리할 때 혼란스러웠습니다.

마지막에 console.log를 사용하여 채워진 step 배열을 표시한 후에도 여전히 각 반복에서 수행하는 작업을 보지 못했습니다.

각 반복을 시뮬레이션해야 한다는 것을 알았습니다.

나는 그것이 어떻게 작동하는지 봐야했다

NullDev의 코드를 if...else 및 for 루프 조합 대신 while 절로 리팩토링하는 것이 그리 어렵지 않았습니다

.

그 결과 목록을 렌더링하는 시뮬레이터가 더 길어지고 항상 맨 위에 마지막 값을 표시합니다

.

마침내 NullDev의 알고리즘이 각 값을 계속해서 두 배로 늘리는 방식으로 '3단계 전진, 2단계 후퇴'하는 방식을 이해하는 데 도움이 되었습니다

.

Try the simulator for Part 2 using NullDev's algorithm


NullDev의 솔루션을 보면 내가 1-2-4 배가 논리에서 '무언가'에 있음을 알 수 있습니다. 하지만 분명히 내 접근 방식이 너무 얕았습니다.

파트 2를 풀지 못했을 수도 있지만 이 퍼즐을 풀고 다른 솔버의 알고리즘을 시뮬레이트하는 것이 즐거웠습니다.