인쇄 대기열

2024 코드 출현 5일차

1부

질서가 있을 것이다!

이건 정말 굉장한 일이 될 거예요.

업데이트에 포함되지 않은 페이지에 대한 규칙을 고려하면 안 된다는 추가 주의 사항이 마음에 듭니다.

이 퍼즐에 어떻게 접근해야 할지 막연한 생각이 듭니다.

하지만 명확성을 확보하고 실제 코드를 작성할 준비가 되었는지 확인하기 위해 여기에서 전략을 세워야 합니다.

전략에 걸려 넘어지길 바라

재밌네요. 오버체크 방식으로 해결하는 방법을 알 것 같습니다.

제 생각은 이렇습니다.

두 목록 중 첫 번째 목록을 앞에 있어야 하는 모든 페이지의 페이지 번호 카탈로그로 변환합니다.

여기서:

47|53
97|13
97|61
...

이것에:

{
  47: [53],
  97: [13, 61],
  ...
}

그런데 어떻게 사용할 수 있나요?

잠깐. 피벗!!

첫 번째 예제 페이지 업데이트 살펴보기:

75,47,61,53,29

그리고 올바른 순서에 대한 심층 증명을 검토하는 중...

...지나치게 지루한 접근 방식에 대해 생각하게 합니다.

Find all page ordering rules whose two pages are both in the page update list
Find the index of each page
If the first is less than the second
  The order is correct

성능 측면에서 단점:

• 이를 위해서는 각 목록에 대한 전체 페이지 순서 규칙 세트를 살펴봐야 합니다
• 가능한 모든 숫자 쌍을 확인하는 작업에서는 계승처럼 보입니다

그런 접근 방식은 잘 모르겠습니다.

내 키 개체와 '이전' 목록으로 돌아갑니다.

객체를 더욱 포괄적으로 만들면 어떨까요:

47|53
97|13
97|61
...

becomes:

{
  47: [ [53], [] ],
  53: [ [], [47] ],
  97: [ [13, 61], [] ],
  13: [ [], [97] ],
  61: [ [], [97] ]
}

• 첫 번째 중첩 목록은 앞에 와야 하는 숫자를 나열합니다
• 두 번째 중첩 목록은 그 뒤에 와야 하는 숫자를 나열합니다

이론적(및 유사 코드):

For each number in the list
  Create an ordered list of the previous numbers
    Check each one for inclusion in the catalogued list associated with that number
      If they are all in there
        Set a flag to true
  Create an ordered list of the subsequent numbers
    Check each one for inclusion in the catalogued list associated with that number
      If they are all in there
        Set a flag to true
  If both flags are true
    Number is in the correct order

예시 연습:

75

Before: []
After: [47,61,53,29]

Catalog:
{
  75: [ [29, 47, 53, 61, 13], [97] ]
}

Before: Empty - success

After: [True, True, True, True]

All True? Yes - success

Correct Order

이제 최소한 카탈로그 개체를 구축하는 알고리즘을 작성해야 할 때라고 생각합니다.

목록화 알고리즘 구축

업데이트 목록에서 규칙 분리:

let [rules, updates] = input.split('\n\n')

입력을 각 항목이 숫자인 2개 항목 목록으로 구문 분석:

rules = rules.split('\n').map(el => el.split('|').map(Number))

해당 목록을 키와 목록 값으로 가득 찬 객체로 줄이는 방법:

rules = rules.reduce((obj, item) => {
  if (!(item[0] in obj)) {
    obj[item[0]] = []
  }
  obj[item[0]].push(item[1])
  return obj
}, {})

이것이 예상대로 작동합니까?

예, 다음 개체가 출력됩니다.

{
  '29': [ 13 ],
  '47': [ 53, 13, 61, 29 ],
  '53': [ 29, 13 ],
  '61': [ 13, 53, 29 ],
  '75': [ 29, 53, 47, 61, 13 ],
  '97': [ 13, 61, 47, 29, 53, 75 ]
}

주어진 숫자 뒤에 와야 하는 녹음 숫자로만 돌아왔습니다.

그렇다면 굳이 양쪽을 다 확인할 필요는 없을 것 같아요.

제가 틀렸을 수도 있습니다.

하지만 이 가정하에 진행하겠습니다.

각 숫자 뒤의 모든 숫자 확인

올바른 것으로 표시될 첫 번째 예제 업데이트를 작업하겠습니다.

먼저 입력을 숫자 목록으로 구문 분석해야 합니다.

updates = updates.split("\n").map((el) => el.split(",").map(Number));

그런 다음 테스트할 첫 번째 목록을 추출합니다.

let test = updates[0];

이제 실제 작업에 들어갑니다.

첫 번째 시도:

47|53
97|13
97|61
...

5번째 예시 목록 항목에서 시도해 보기 전까지는 작동하는 것 같았습니다.

{
  47: [53],
  97: [13, 61],
  ...
}

내 알고리즘은 각 번호가 카탈로그에 키로 존재하는지 확인하고 일치하는 항목이 있는지 관련 목록의 모든 번호를 확인합니다.

하지만 카탈로그에는 13이 없습니다. 내 알고리즘이 올바른 판단을 잘못 가정하고 있습니다.

그리고 29가 되면 더 이상 숫자가 없으므로 역시 정답이라고 가정합니다.

그래서 전략을 조정해야 합니다.

두 번째 시도:

75,47,61,53,29

이렇게 하면 모든 예시 목록에 대한 정답이 생성됩니다!

확인 중인 숫자(하위 목록 바로 앞에 있는 숫자)가 포함되어 있는지 각 숫자 뒤에 나타나는 숫자의 하위 목록에서 각 숫자를 올바르게 확인합니다.

따라서 다음의 경우:

Find all page ordering rules whose two pages are both in the page update list
Find the index of each page
If the first is less than the second
  The order is correct

13을 만나면 29를 찾아 13을 보게 되는데, 이는 순서가 잘못되었음을 의미합니다.

이것을 감소에 연결하고 중간 숫자를 합산합니다.

생각보다 힘들지 않았어요:

47|53
97|13
97|61
...

becomes:

{
  47: [ [53], [] ],
  53: [ [], [47] ],
  97: [ [13, 61], [] ],
  13: [ [], [97] ],
  61: [ [], [97] ]
}

예제 입력에 대한 정답을 생성합니다!

내가 입력한 퍼즐은 어떻게 될까요???

또 정답이 나왔습니다!!!

우후!!!

한동안 너무 과하게 생각했던 것 같아요. 그러다가 뭐가 안 되는 걸 보니 답이 명확해졌네요.

재미있는 것들!

파트2는 어떤 새로운 도전을 불러일으킬지...?

2부

정렬 연습

이런 걸 봤어야 했는데.

다행히 내 알고리즘이 이 작업에 적합하다고 생각합니다.

목록별로 정리해야겠네요.

두 가지 값을 비교하고 세 가지 결과 중 하나에 따라 두 가지 중 하나를 수행하여 작업을 정렬합니다.

• 정렬 함수에서 -1이 반환되면 첫 번째 값이 두 번째 값 앞에 옵니다
• 1이 반환되는 경우 두 번째 값이 첫 번째 값 앞에 와야 합니다
• 0이 반환되면 값이 동일하므로 이동되지 않습니다

내 알고리즘은 부울 값 목록을 생성합니다.

모든 부울 값이 true인 경우 이를 올바르게 생성한 숫자가 모든 부울 값 앞에 옵니다.

그러나 부울 값이 false인 경우 해당 숫자 중 하나가 현재 숫자 앞에 와야 합니다.

그러나 두 숫자를 비교했는데 두 숫자 모두 잘못된 값을 갖고 있다면 어느 것이 먼저 와야 하는지 어떻게 알 수 있나요?

한 목록이 모두 참이고 다른 목록은 그렇지 않거나 둘 다 모두 참인 경우에만 해결할 수 있는 방법이 있습니다.

흠.

숫자 목록 대신 두 개의 숫자를 동시에 테스트해야 할 것 같습니다.

정렬 작동 방식과 정확히 같습니다: a 대 b

1대다 대신 1대1 전투에 맞게 알고리즘을 조정합니다.

몇 차례 머리를 긁고, 삼항을 확인하고, 추측한 끝에 작동하는 알고리즘에 도달했습니다.

47|53
97|13
97|61
...

잘못된 순서의 각 예제 업데이트에 대해 이를 실행하면 올바른 순서의 목록이 생성됩니다!

두 입력의 모든 목록에서 실행하게 되어 기쁩니다. 오늘은 두 개의 금별을 획득하여 마무리할 수 있기를 바랍니다!

거대한...사소한 세부 사항을 내려다보고 있습니다.

예제 입력에 대해 알고리즘을 실행했는데 표시된 것보다 더 큰 숫자를 얻었습니다.

이유는 전혀 몰랐습니다. 올바르게 정렬된 각 목록을 인쇄하면 해당 요소가 올바른 순서로 되어 있음이 입증되었습니다.

그런 다음 지침을 다시 읽었습니다.

잘못 순서의 업데이트만

그렇군요! 모든 목록의 중간값을 더하고 있었어요!

이 문제를 해결하려면 목록을 복제하기 위한 약간의 슬라이스() 작업이 필요하며 문자열화된 버전을 비교해야 합니다.

{
  47: [53],
  97: [13, 61],
  ...
}

비올라! 예시 입력에 대한 정답을 얻었습니다.

손가락이 교차했습니다. 퍼즐 입력으로 알겠습니다!

그렇죠!!!

멋지네요!!

금별 2개. 다 내꺼야!

또 다른 재미있는 퍼즐이군요.

몇 가지 전략을 고민하고 도출하는 데 며칠이 걸렸습니다.

그런데 결국 안개 속에서 길을 찾았어요.

6일차를 향해!

위 내용은 인쇄 대기열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!