스핀록

코드 출현 2017 17일차

1 부

익숙한 것 같군요...

상당히 간단해 보입니다...

이것은 친숙한 것 같습니다 ...

이전에 원형 삽입 퍼즐을 본 적이 있습니까?

2017년 25일에는 무한히 긴 수평 목록이 표시되었습니다

.

2018년 9일차에 유사한 퍼즐이 등장했습니다

.

2018 Day 14에도 비슷한 퍼즐이 있습니다

.

그것은 내가 최근에 이 퍼즐 유형을 더 많이 본 것을 기억하는 내 직감을 확인시켜줍니다.

이것은 상당히 간단해 보인다...

Start with an array containing the value 0
For i from 1 to 2018 and current starting at 0
  Without deleting anything...
  ...insert i at the location in the array...
  ...equivalent to:
    - the remainder after dividing the sum of
    - current and the puzzle input integer
    - by the length of the array
    - then adding 1
  Then, update current to the location in the array of i

Return the integer at the location one greater than the location of the integer 2017

이 알고리즘은 3의 예제 입력과 내 퍼즐 입력 모두에 대해 정답을 생성합니다!

그러나 나는 그것을 작성하는 과정에서 몇 가지 버그와 겉보기에 운이 좋은 우연의 일치를 경험했습니다.

원래 루프를 사용하여 업데이트했습니다current.

뿐만 아니라 해당 루프

의 각 반복에서 current를 i씩 잘못 증가시켰습니다.

놀랍게도 3의 예제 입력을 사용하여 정답을 생성하고 있었습니다!

퍼즐 입력으로 생성한 숫자가 왜 too high인지 의문이 들었습니다.

고맙게도 그 문제들을 해결했습니다.

그리고 알고리즘을 5줄이 조금 넘는 코드로 단순화, 축소 및 압축했습니다!

Part 1을 해결하기 위해 작성한 JavaScript는 다음과 같습니다.

const part1 = () => {
  let input = 3, RA = [0]
  for (let i = 1, curr = 0; i < 2018; i++) {
    RA.splice((curr + 376) % i + 1, 0, i)
    curr = RA.indexOf(i)
  }
  return RA[RA.indexOf(2017) + 1]
}

2 부

오 그래, 오는 걸 봤어

게시 후 업데이트

오 그래, 그게 오는 걸 봤어

5천만 번, 어?

다시 한 번 말씀드리지만 연결 목록에 익숙하지 않아서 문제를 풀지 못했습니다. 연결 목록은 이 문제에 대해 배열보다 성능이 훨씬 뛰어난 데이터 구조입니다

.

바라건대 곧 연결 목록을 사용하는 방법을 배우게 될 것입니다.

그런 다음 위에서 언급한 몇 가지 퍼즐로 돌아가서 이를 필요로 하는 파트 2를 해결하려고 시도합니다.

게시 후 업데이트

연결 목록 사용

npm library that provides a doubly linked list data structure을 찾았습니다.

설명서를 읽고 연결된 목록

을 사용하여 파트 1의 솔루션을 다시 만들기 위해 노력했습니다.

내 연결 목록 메인 루프는 다음과 같습니다.

for (let i = 1, curr = 0; i < 2018; i++) {
  let index = (curr + input) % i + 1
  if (index > i - 1) {
    list.insert(i)
    curr = i - 1
  } else {
    list.insertAt(index, i)
    curr = index
  }
}

그런 다음 2018을 50M로, 2017을 0으로 바꾸고 다시 실행했습니다

.

그것도 영원히 계속되는 것 같았어요

안타깝다.

패턴 사냥

어쩌면 내가 50M로 추정할 수 있는 0 바로 오른쪽에 있는 정수에 대한 패턴이 있을까요?

0 오른쪽에 있는 정수가 변경될 때마다 추적하는 코드를 추가했습니다

.

새 숫자를 기록했습니다: 명백한 패턴 없음

새 숫자와 이전 숫자 간의 차이를 기록했습니다. 명확한 패턴 없음

안타깝다.

해냈어!

1부 풀었습니다!

내 코드를 거의 5줄로 통합했습니다!

연결 목록을 사용하여 배우고 연습해야 할 또 다른 이유를 얻었습니다!

업데이트: 첫 번째linked list library를 사용하여 파트 1의 답변을 다시 만들었습니다!