디지털 배관공

코드 출현 2017 12일차

1 부

일대다...다시

사전 만들기

작업 알고리즘 작성 및 테스트

일대다...다시

그것들이 생각난다 Handy Haversacks

그리고 또 다른 퍼즐인데 이름이나 날짜가 기억나지 않습니다

여하튼, 이것은 사전을 구축하고 내가 모두 파악할 때까지 반복하는 또 다른 재미있는 연습이 될 것입니다!

사전 만들기

패턴은 일대다입니다.

2 <-> 0, 3, 4
3 <-> 2, 4
5 <-> 6

추출해야 할 부분은 숫자뿐입니다. 이는 간단한 정규식을 만듭니다.

/\d+/g

그러면 한 줄의 각 숫자가 표시됩니다.

지침에 따라 다음과 같은 줄입니다.

2 <-> 0, 3, 4

다음을 의미하는 것 같습니다.

2는 0, 3, 4와 통신할 수 있습니다.

0은 2, 3, 4와 통신할 수 있습니다.

3은 0, 2, 4

와 통신할 수 있습니다.

4는 0, 2, 3과 통신할 수 있습니다.

따라서:

For each number in the line
  Create or add to a set of unique values it can communicate with each of the other numbers

예제 입력을 어떻게 찾습니까?

0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5

이와 같이?

0: 2, 3, 4
2: 0, 3, 4, 6
1: 1
3: 0, 2, 4, 6
4: 0, 2, 3, 6, 5
6: 2, 3, 4, 5
5: 6, 4

0를 작성하려면 또 다른 반복이 필요합니다. 여기에서 0의 각 숫자와 연결된 각 집합에서 찾은 각 숫자를 추가하려고 시도합니다.

0: 2 (+6), 3, 4 (+5)

아마도 내 알고리즘은 모든 숫자에 대해 0를 되돌아보고 0에 숫자가 있으면 해당 숫자와 현재 줄에 저장된 숫자도 추가할 수 있습니까?

조회 시 많은 숫자가 사전에 추가되지 않았기 때문에 까다로워집니다.

이 정규식과 사전 데이터 구조를 구현하는 알고리즘 작성을 시도하기에 충분한 이해가 있다고 생각합니다.

작업 알고리즘 작성 및 테스트

Split the input at each newline character into an array of strings

For each string, populate a dictionary
  Use the regular expression to extract all the digits
  For each digit as i
    For each digit as j
      As long as i is not j
        If the digit is not yet a key in the dictionary
          Create a key for it and set the value to a unique Set
        Add the digit j to the unique set if not already part of the Set

Create a counter to track the size of the Set associated with the key, 0
  Initialize it to the current size, after the dictionary is done being constructed

Do at least once, and as long as counter is less than the new size of the Set associated with the key, 0
  For each number in the Set associated with 0
    Attempt to add each number in the Sets associated with the current number to the Set associated with 0

결과 테스트:

예제 입력에서 작동했습니다!

내 퍼즐 입력에 효과가 있었습니다!

2 부

일대다... 또?!

작업 알고리즘 작성 및 테스트

일대다... 또?!

이것은 문자 그대로 키를 제거하는 재미있는 과정이어야 합니다.

내 계획:

Run the algorithm from Part 1 to identify all members in a group shared by `0`
  Delete each of those keys from the dictionary
Run the algorithm from Part 1 on the next key in the dictionary
  Delete each of the keys identified as part of that dictionary
Go until there are no other keys to evaluate
Count the number of keys remaining in the dictionary

작업 알고리즘 작성 및 테스트

내가 계획한 알고리즘 때문에 중요한 부분을 너무 빨리 수행하게 되었고 또 다른 중요한 부분을 놓쳤습니다.

이것은 작동하는 알고리즘입니다.

Split the input at each newline character into an array of strings

For each string, populate a dictionary
  Use the regular expression to extract all the digits
  For each digit as i
    For each digit as j
      As long as i is not j
        If the digit is not yet a key in the dictionary
          Create a key for it and set the value to a unique Set
        Add the digit j to the unique set if not already part of the Set

Create a counter to track the number of groups identified

For each key in the dictionary
  Create a counter to track the size of the Set associated with the key
    Initialize it to the current size
  Do at least once, and as long as counter is less than the new size of the Set associated with the key
    For each number in the Set associated with the key
      Attempt to add each number in the Sets associated with the current number to the Set associated with the key
  Remove the number in its Set that is equal to the key
  Delete each key in the dictionary bearing the same alias as each number in this key's set of values
  Increment the group counter by 1

Return the group counter's value

이 GIF는 파트 1과 2에 대한 알고리즘이 어떻게 작동하는지 보여줍니다.


결과 테스트:

예제 입력에서 작동했습니다!

내 퍼즐 입력에 효과가 있었습니다!

해냈어!!

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

내 알고리즘이 두 부분을 어떻게 해결하는지 보여주는 GIF를 만들었습니다!

GIF를 만든 후 Part 2 알고리즘에서 몇 가지 중복 루프를 제거하여 훨씬 빠르게 실행됩니다!