엘프는 보고 엘프는 말한다

코드 출현 2015 10일 차

1 부

세는 가장 좋은 방법은 무엇입니까?

Map()의 첫 번째 사용 ?

새로운 접근법: 워킹 더 라인

계산하는 가장 좋은 방법은 무엇입니까?

이제 저는 주어진 문자가 문자열에 나타나는 횟수를 계산하도록 잘 훈련되었습니다

.

그러나 종종 순서는 중요하지 않습니다

.

그랬을 때 알파벳 순서에 의존할 수 있었습니다

.

하지만 여기에는 알파벳이 없고... 순서가 매우 중요합니다

여전히 개체를 사용하여 각 숫자를 집계할 수 있습니까?

Map() 을 처음 사용합니까?

MDN의 페이지에 따라:

The Map object holds key-value pairs and remembers the original insertion order of the keys

그게 내가 원하는거야, 그렇지?

예 중 하나를 사용하여:

1211

Map() 를 사용하여 다음 개체를 만들 수 있습니다.

{ '1': 1 }
{ '1': 1, '2': 1 }
{ '1': 2, '2': 1 }
{ '1': 3, '2': 1 }

그리고 순서대로 새 시퀀스를 생성합니다.

1321

어 오. 그건 내가 원한 게 아니야.

나는 원했다:

1 1 1 2 2 1

흠, 다른 접근법이 필요한 것 같습니다.

새로운 접근법: 선을 따라 걷기

이 예제로 돌아가서:

1211

의사 코드로서의 내 알고리즘 :

Do 40 times
  Set next as an empty string
  Set i as 0
  Do as long as i is less than the length of the sequence
    Set count to 1
    Set j to one more than i
    Do as long as j is less than the length of the sequence and the character at j is the same as the character at i
      Increment count by 1
      Increment j by 1
    Concatenate next with count and the character at i
    Set i to j
  Set sequence to next

Return the length of sequence

내 알고리즘, 애니메이션:


내 알고리즘을 40번 실행하면 정답이 거의 즉시 생성되었습니다!

2 부

정답을 맞히다...결국

훨씬 빠르게 정답을 얻음

정답을 맞히다...결국

40를 50로 업데이트했습니다.

내 프로그램 재실행

몇 초 대기 중

그러면 정답이 생성되었습니다!

훨씬 더 빠르게 정답을 얻습니다.

문자열 대신 배열을 사용하도록 알고리즘을 업데이트했습니다

.

내 프로그램 재실행

잠시만 기다려주세요

그런 다음 동일한 정답을 생성했습니다!

JavaScript에서 내 최적화된 알고리즘:

function lookAndSay(digits, times) {
  let sequence = digits.split('')
  for (let times = 0; times < 50; times++) {
    let next = [], i = 0
    while (i < sequence.length) {
      let count = 1, j = i + 1
      while (j < sequence.length && sequence[j] == sequence[i]) {
        count++
        j++
      }
      next.push(count, sequence[i])
      i = j
    }
    sequence = next
  }
  return sequence.length
}
// Part 1
lookAndSay(input, 40)
// Part 2
lookAndSay(input, 50)

해냈어!!

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

알고리즘을 작성함으로써...며칠 만에 처음으로!

그런 다음 문자열 대신 배열을 사용하는 더 빠른 알고리즘을 작성합니다!

파트 2에 링크된 비디오 덕분에 이 퍼즐의 주제가 수학적으로 얼마나 흥미로운지 배웠습니다!

2015년은 지금까지 정말 재미있는 퍼즐의 해였습니다!