1202 프로그램 알람

코드 출현 2019 2일 차

시뮬레이터를 사용해보십시오!

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

1 부

X = the value left at position 0 after the modified program terminates

2 부

X = the result of an equation combining the noun and verb inputs that modify the program such that it terminates with value 19690720 at position 0

예시 입력

1,9,10,3,2,3,11,0,99,30,40,50

다음을 나타냅니다.

쉼표로 구분된 정수 목록

일부 정수가 opcode를 나타내는 경우 - 1, 2 또는 99

기타 정수는 조회할 위치와 해당 값을 더하거나 곱할지 여부에 대한 지침을 나타냅니다

.

1 부

중첩 조회 프로세스 시각화

작업 알고리즘 작성

알고리즘의 시각적 묘사

중첩 조회 프로세스 시각화

지침에 표시된 대로:

1,9,10,3,2,3,11,0,99,30,40,50

1 = Consider the next three locations
  9 10 3
  1  2 3

Look-up the values in locations 1 and 2
                      9 10
                     30 40

1 = Add them together
                     30+40=70

Store the result in the location referenced by the value in location 3
       3
       3

Resulting in:
       70

Updating the program to:
1,9,10,70,2,3,11,0,99,30,40,50

작동하는 알고리즘 작성

Split the input at each comma to create a list of strings
  Coerce each string to a number
  Change the value of the number at location 1 (the second value) to 12
  Change the value of the number at location 2 (the third value) to 2

Set a starting address at 0

Do as long as address is not equal to or greater than the length of the list of intcodes AND the value at the current address is not 99
  If the value at the current address is a 1
    Update the value at the location specified by the value at the location equal to the current address plus 3 by the sum of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
  Else, if the value at the current address is a 2
    Update the value at the location specified by the value at the location equal to the current address plus 3 by the product of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
  Increment address by 4

Return the new value stored at the first location in the list of intcodes

알고리즘의 시각적 묘사

2 부

무차별 대입 작업 알고리즘 작성

시뮬레이터를 사용하여 패턴 찾기

보다 성능이 뛰어난 작업 알고리즘 작성

무차별 대입 작업 알고리즘 작성

1부에서는 noun와 verb가

로 규정되었다.

파트 2에서 올바른 noun 및 verb를 식별해야 합니다. 주어진 동일한 정수 경계: 0-99

올바른 noun와 verb가 99와 99라고 가정해 보겠습니다.

0과 0으로 시작하여 가능한 모든 조합을 확인하는 알고리즘은 수정된 프로그램을 10,000번 실행해야 합니다.

그것은 끔찍하지 않으며 아마도 두 번째로 끝날 것입니다.

그 알고리즘은 어떻게 생겼습니까?

Create variables for noun and verb
For n as 0 through 99
  For v as 0 through 99
    Split the input at each comma to create a list of strings
      Coerce each string to a number
      Change the value of the number at location 1 (the second value) to n
      Change the value of the number at location 2 (the third value) to v

    Set a starting address at 0

    Do as long as address is not equal to or greater than the length of the list of intcodes AND the value at the current address is not 99
      If the value at the current address is a 1
        Update the value at the location specified by the value at the location equal to the current address plus 3 by the sum of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
      Else, if the value at the current address is a 2
        Update the value at the location specified by the value at the location equal to the current address plus 3 by the product of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
      Increment address by 4

If the new value stored at the first location in the list of intcodes is 19690720
  Set the values of noun and verb respectively to n and v
  Break out of the loop

Return the sum of verb and the product of 100 and noun

시뮬레이터를 사용하여 패턴 찾기

파트 2용 시뮬레이터를 빌드한 후 명사와 동사에 대한 각 정수 0-99의 효과가 분명해집니다.

동사의 정수는 마지막 두 자리를 수정합니다

.

명사의 정수는 앞의 모든 숫자를 수정합니다(4-5)

보다 성능이 뛰어난 작업 알고리즘 작성

각 정수 명사에 대해 각 정수 동사를 확인할 필요가 없습니다

.

대신 각 명사와 동사가 더 큰 출력 번호의 해당 하위 정수와 같아지는 시점을 개별적으로 확인할 수 있습니다

.

두 값이 같지 않은 한 올바른 값을 별도로 증가시킬 수 있습니다.

Sub-routine: Run
- Accept two parameters, noun and verb
Split the input at each comma to create a list of strings
  Coerce each string to a number
  Change the value of the number at location 1 (the second value) to noun
  Change the value of the number at location 2 (the third value) to verb
Set a starting address at 0
Do as long as address is not equal to or greater than the length of the list of intcodes AND the value at the current address is not 99
  If the value at the current address is a 1
    Update the value at the location specified by the value at the location equal to the current address plus 3 by the sum of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
  Else, if the value at the current address is a 2
    Update the value at the location specified by the value at the location equal to the current address plus 3 by the product of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
  Increment address by 4
Return the value stored at location 1

Main loop:
Set noun and verb each to 0
Call Run once, passing in noun and verb
  Store the result as a variable, output
Do as long as output does not store the value 19690720
  Create an integer from all but the last two digits of the value stored in output
  Create an integer from the last two digits of the value stored in output
  If the first integer is not equal to 196907
    Increment noun by 1
  If the second integer is not equal to 20
    Increment verb by 1
  Call Run again, passing in noun and verb
    Store the result in output

Return the sum of verb and the product of 100 and noun

시뮬레이터의 이 애니메이션에서 볼 수 있듯이 내 퍼즐 입력에는 이전 무차별 대입 알고리즘을 사용하는 5,121번의 반복 대신 72번의 반복만 필요합니다.
( https://aoc1202programalarm.rmion.repl.co/ )


입력에 대한 올바른 명사와 동사를 찾기 위해 이진 검색을 사용하여 알고리즘을 훨씬 더 효율적으로 만들고 싶었습니다.

이는 반복 횟수를 10-15 사이의 숫자로 줄일 수 있습니다.

오 잘. 나는 여전히 다음을 자랑스럽게 생각합니다.

두 부분 모두 풀었습니다

무차별 대입

보다 더 성능이 뛰어난 알고리즘으로 파트 2를 해결했습니다.

특히 내 시뮬레이터를 사용하여 숨겨진 패턴을 발견한 후!