초콜릿 차트

코드 출현 2018 14일차



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



1 부




X = the scores of the ten recipes immediately after N number of recipes, where N is my puzzle input


2 부




X = the number of recipes that appear on the scoreboard to the left of N, where N is the score sequence in my puzzle input


예시 입력




9


다음을 나타냅니다.
  • 두 명의 엘프가 만든 레시피의 수

  • 1 부


  • 또 다른 어레이 퍼즐이 증가하고 있습니까?
  • 이 퍼즐의 산술 논리 이해하기
  • 알고리즘을 작성하기 전에 부하를 생각함
  • 내 작업 알고리즘에 대한 서면 설명
  • 현재 레시피 변경의 시각적 묘사

  • 성장하는 또 다른 어레이 퍼즐?


  • 이 퍼즐과 예시는 2021 Day 6: Lanternfish을 생각나게 합니다.
  • 길이가 변경되지 않는 배열을 사용하는 퍼즐을 푸는 매우 우아하고 효과적인 방법을 다른 솔버의 솔루션을 조사하면서 배웠습니다
  • .
  • 언뜻 보기에 이 퍼즐에 대해 유사한 솔루션을 고안할 수 있을지 확신이 서지 않습니다
  • .
  • 대신 간단한 솔루션을 시도하고 배열 크기를 2개 값에서 거의 100만 개로 늘려야 하는 압력으로 알고리즘이 불안정해지지 않기를 바랍니다
  • .

    이 퍼즐의 산술 기반 논리 이해하기


  • 투 엘프
  • 레시피를 만드는 각자
  • 각 레시피
  • 의 점수0-9를 기록하는 스코어보드 추적

    초기 상태는 다음과 같습니다.

    scoreboard = [3,7]
    elf1 = scoreboard[0] -> 3
    elf2 = scoreboard[1] -> 7
    


    하나 또는 두 개의 새 레시피가 생성됩니다.

    new_score = elf1 + elf2
                   3 +    7
    -----------------------
                         10
    
    new recipes = 1,0
    scoreboard = [3,7,1,0]
    


    Elf 1의 새로운current 레시피:

    steps_forward = 1 + elf1 -> 1 + 3 -> 4
    
    [3,7,1,0]
     *
    
    [3,7,1,0]
       1 2 3
    
    [3,7,1,0]
     4
    
    elf1 = scoreboard[0] -> 3
    


    Elf 2의 새로운 current 레시피:

    steps_forward = 1 + elf2 -> 1 + 7 -> 8
    
    [3,7,1,0]
       *
    
    [3,7,1,0]
         1 2
    
    [3,7,1,0]
     3 4 5 6
    
    [3,7,1,0]
     7 8
    
    elf1 = scoreboard[1] -> 8
    


    알고리즘을 작성하기 전에 크게 생각하기



    N + 10 번 실행되는 for 루프 내부에 알고리즘을 작성하기에 충분히 이해하고 있다고 생각합니다. 여기서 N은 거의 백만 개의 퍼즐 입력입니다.

    또한 루프가 완료되는 데 몇 초(몇 분은 아니더라도)가 걸릴 수 있다고 생각합니다. 특히 점점 더 커지는 배열을 위해 지속적으로 메모리를 재할당해야 하는 경우에는 더욱 그렇습니다.

    배열의 길이가 어떻게 될지 정확히 알고 있으므로 인덱스 0과 1에서 초기 값 3과 7을 사용하여 그렇게 큰 배열을 만들 수 있습니다.

    그러나 주어진 지점에 포함된 값의 수를 추적하고 이를 시뮬레이션length으로 사용하지 않는 한 앞으로 단계를 추적하는 방법이 엉망이 됩니다.

    그 알고리즘이 작동하는지 궁금합니다.
    만약에... 내가 쓰려고 했다면?
    해보자!

    내 작업 알고리즘에 대한 서면 설명


  • 가장 어려운 부분은 각 엘프
  • 에 대한 current recipe 업데이트 방정식을 식별하는 것이었습니다.
  • 머릿속으로 해결하기 위해 강아지와 함께 긴 산책을 했지만 결국 작동하는 알고리즘을 생각했습니다.

  • Set several variables:
      1. My puzzle input as an integer
      2. The scoreboard as an array containing as many empty slots as the sum of my puzzle input and 10
      3. Elf 1's current recipe as 0
      4. Elf 2's current recipe as 1
      5. The number of scores on the scoreboard as 2
    
    Set 3 and 7 as the first two values in scoreboard
    
    Do as many times as the sum of my puzzle input and 10
      Set new_recipe as the sum of the values in scoreboard at the positions indicated by both Elves current recipes
      For each digit in new_recipe
        Insert the digit at the next empty slot in scoreboard
      Update the number of scores to reflect the sum of the current value of scores and the number of digits in new_recipe
      Update both Elves' current recipes to the result of the following equation:
        The remainder after dividing these two values
          1. The sum of: a) the current position of this Elf; b) 1; c) the value in scoreboard at the current position of this Elf;
          2. The number of scores on the scoreboard
    
    Return as a 10-digit integer the 10 scores after the score at  the location indicated by my puzzle input
    

    그것은 효과가 있었다!

    그리고 그것은 1초도 안되어 실행되었습니다!

    현재 레시피 변경의 시각적 묘사



    공식:

    (current + (1 + score of current)) % number of scores
    




    2 부


  • 재미있는 트위스트
  • 나의 전략적 접근 방식
  • 내 작업 알고리즘에 대한 서면 설명

  • 흥미로운 트위스트


  • 1부에서 레시피 생성을 위한 반복 횟수를 지시하는 것 같습니다
  • .
  • 파트 2는 레시피 점수를 생성하는 동안 찾아야 하는 순서가 지정된 점수 목록으로 퍼즐 입력을 처리하는 청소부 찾기에 가깝습니다
  • .

    나의 전략적 접근


  • 점수판에 N개의 점수가 있는 한 점수판에서 마지막 N개의 점수를 확인합니다. 여기서 N은 내 퍼즐 입력의 자릿수입니다
  • .
  • 확인을 시작한 위치를 추적하기 위해 추가 변수가 필요했습니다. 점수 수가 1 또는 2씩 증가할 수 있고 점수를 건너뛰는 위험을 감수하고 싶지 않았기 때문입니다
  • .

    내 작업 알고리즘에 대한 서면 설명




    Set several variables:
      1. My puzzle input as a string
      2. The scoreboard as an array containing as many empty slots as my puzzle input as an integer
      3. Elf 1's current recipe as 0
      4. Elf 2's current recipe as 1
      5. The number of scores on the scoreboard as 2
      6. The address of the first score to check as 0
    
    Set 3 and 7 as the first two values in scoreboard
    
    Do until manually escaped
      If there are more than 5 scores in scoreboard
        If the N scores starting from the score at address - when combined - are equivalent to my puzzle input
          Break out of the loop
        Else
          Increment address by 1
      Set new_recipe as the sum of the values in scoreboard at the positions indicated by both Elves current recipes
      For each digit in new_recipe
        Insert the digit at the next empty slot in scoreboard
      Update the number of scores to reflect the sum of the current value of scores and the number of digits in new_recipe
      Update both Elves' current recipes to the result of the following equation:
        The remainder after dividing these two values
          1. The sum of: a) the current position of this Elf; b) 1; c) the value in scoreboard at the current position of this Elf;
          2. The number of scores on the scoreboard
    
    Return address
    


    내 알고리즘을 실행하는 데 몇 초가 걸렸습니다.

    점수판 배열이 결국 내가 만든 것보다 크기가 더 커졌기 때문일 수 있습니다.

    오, 글쎄요. 정답을 생성했습니다!

    해냈어!!


  • 두 부분 모두 해결했습니다!
  • 적어도 1부에서는 처음부터 필요한 정확한 길이의 어레이를 사용하여
  • 성능을 설명했다고 생각합니다.
  • 현재 레시피를 업데이트하는 방법을 묘사하는 GIF를 만들었습니다
  • .

    좋은 웹페이지 즐겨찾기