사이버 공간의 폭발물

코드 출현 2016 9일 차

1 부

같은 날, 다른 해

루프에 대한 사양 작성

각 단위 테스트를 실행한 다음 내 퍼즐 입력

같은 날, 다른 해

2017 Day 9은 유사한 주제의 문제인 문자 스트림 처리를 제공했습니다.

이번에 독특한 측면은 다음과 같습니다.

특정 문자의 존재에 따라 처리가 완료되면 스트림 길이가 크게 늘어납니다

.

파트 1에서 요구하는 것은 길이이지 처리된 스트림의 내용이 아닙니다. 그러면 내 알고리즘이 덜 복잡해지고 성능이 향상될 수 있습니다. 문자열 대신 합계를 누적해야 하므로

루프 사양 작성

Set answer to 0
Set pointer to 0
Do as long as pointer is not beyond the length of the input string
  Increment answer and pointer depending on the value at pointer:
    1. Value is (
       Create marker as an empty string
       Append to marker one character at a time for all characters after the ( and before the next )
       Split the resulting string at the x into an array of two strings
         Coerce each string to a number
       Increment answer by the product of both numbers
       Increment pointer by the sum of the length of marker, the first of the two numbers, and 2 
    2. Value is anything else
       Increment answer by 1
       Increment pointer by 1
Return answer

내가 가장 이해하기 힘들었던 방정식:

Increment pointer by the sum of the length of marker, the first of the two numbers, and 2

코드를 약간 수정한 후 코드에서 휴식을 취한 후 내 알고리즘이 작동하는 방식을 고려하여 우승 요소를 발견했습니다.

각 단위 테스트를 실행한 다음 내 퍼즐 입력

이 퍼즐은 6개의 단위 테스트를 제공합니다

.

첫커플 합격했어요

중간에 실패했지만

그런 다음 가운데 하나를 통과했습니다

그러나 일부 초기 제품은 실패했습니다

.

그런 다음 내 알고리즘을 위에 표시된 대로 수정했습니다

.

모든 단위 테스트 통과

그런 다음 내 퍼즐 입력에서 실행합니다.

정답을 생성했습니다!

JavaScript의 핵심 루프:

let answer = 0, pointer = 0
while (pointer < input.length) {
  switch (input[pointer]) {
    case "(":
      let marker = ""
      for (let j = pointer + 1; input[j] !== ')'; j++) {
        marker += input[j]
      }
      let [chars, times] = marker.split('x').map(Number)
      answer += chars * times
      pointer += marker.length + 2 + chars
      break;
    default:
      answer++
      pointer++
  }
}
return answer

2 부

여전히 길이지만 이제...재귀?

재귀를 사용하도록 알고리즘 업데이트 중

각 단위 테스트를 실행한 다음 내 퍼즐 입력

여전히 길이지만 지금은...재귀?

그래서...좋고 나쁜 소식인 것 같아요.

두 번째 예를 더 자세히 연구해야 합니다.

X(8x2)(3x3)ABCY

X는 정상입니다. 합계

에 1를 더합니다.

(8x2) 대상 (3x3)ABC

내 합계에 16를 더하고 Y로 이동하는 대신

그 비트

를 decompress 해야 합니다.

(3x3) 대상 ABC

decompress를 시도하면 3가 됩니다.

따라서 (3x3)ABC 압축해제 길이는 9

8x2 대신 이제 9x2 = 18

합계에 18를 더한 다음 Y로 이동

Y는 정상입니다. 합계

에 1를 더합니다.

최종 합계: 1 + 18 + 1 = 20

흠. 그것은 복잡해 보인다.

하지만 이 작업을 수행하려면 Part 1 알고리즘을 약간만 조정하면 된다는 직감이 있습니다.

재귀를 사용하도록 알고리즘 업데이트

내 전체 알고리즘이 이제 함수가 되어야 합니다

.

answer와 chars의 곱만큼 times를 증가시키는 대신 함수 호출에서 반환된 숫자만큼 answer를 증가시키겠습니다. 바로 뒤의 문자열pointer

그게 다인 것 같아!

각 단위 테스트를 실행한 다음 내 퍼즐 입력에서

이 부분에서는 4개의 단위 테스트를 추가로 제공합니다

.

다 합격했어요!

그런 다음 내 퍼즐 입력에서 실행합니다.

정답을 생성했습니다!

JavaScript의 새로운 핵심 루프:

function decompress(stream) {
  let answer = 0, pointer = 0
  while (pointer < input.length) {
    switch (input[pointer]) {
      case "(":
        let marker = ""
        for (let j = pointer + 1; input[j] !== ')'; j++) {
          marker += input[j]
        }
        let [chars, times] = marker.split('x').map(Number)
        answer += times * decompress(
          stream.slice(
            pointer + marker.length + 2, 
            pointer + marker.length + 2 + chars
          )
        )
        pointer += marker.length + 2 + chars
        break;
      default:
        answer++
        pointer++
    }
  }
  return answer
}

내 재귀 알고리즘이 작동하는 방식에 대한 애니메이션:

해냈어!!

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

또 다른 재귀 알고리즘 퍼즐을 풀었습니다!

나는 길이에 해당하는 합계를 증가시키는 데 집중해야 한다는 것을 현명하게 인식하여 막대한 문자열을 축적하는 함정을 피했습니다!

이 전략 덕분에 파트 2를 위해 전체 알고리즘을 다시 생각하지 않아도 되었습니다!