디스크 조각

2024 코드의 출현 9일차

1부

3단계 건틀렛입니다. 신나는!??

제가 보는 단계는 다음과 같습니다.

1. 기억을 리스트로 표현
2. 값을 끝에서 처음으로 이동
3. 선을 따라 체크섬을 계산하세요

특별히 어렵게 느껴지지는 않습니다.

그리고 그 중 일부는 실제로 또 다른 재미있는 알고리즘 챌린지처럼 보입니다!

목록 만들기

이것을 뒤집고 싶습니다:

12345

이것에 대해:

0..111....22222

고려해야 할 사항:

• 루프 사용
• 짝수 및 홀수 인덱스 확인
• 0부터 시작하여 1씩 값 증가

내 디스크 생성 알고리즘은 다음과 같습니다.

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

매력처럼 작동합니다!

끝에서 처음으로 값 이동

이를 더 쉽게 만드는 방법은 디스크의 모든 빈 공간 목록을 만드는 것입니다.

다음 두 곳에서 알고리즘을 업데이트해야 합니다.

1. 새 변수: 공백 = []
2. .을 삽입한 후의 새로운 작업:empty.push(disk.length - 1)

예제에서 테스트해 보면 각 .!의 예상 인덱스 번호가 표시됩니다.

이것은 목록 끝에서 처음으로 값을 이동하면서 반복할 목록입니다.

하지만 기다려 보세요.

생각보다 어려울 수도 있겠네요.

가치 이동을 중단해야 하는 시기를 어떻게 알 수 있나요?

• 빈 인덱스 목록을 반복합니까? 언제 멈춰야 할까요?
• 디스크를 거꾸로 반복합니까? 언제 멈춰야 할까요?

깨달음: 마법의 숫자 10

짧은 예시의 마지막 상태는 다음과 같습니다.

022111222......

첫 번째 예:

0099811188827773336446555566..............

즉, 모든 ID가 왼쪽에 있고 모든 빈 공간이 오른쪽에 있는 지점이 있다는 의미입니다.

그 상태를 어떻게 확인하나요?

입력: 숫자 10.

연속되는 빈 공간의 양은 9개를 넘을 수 없습니다.

그래서 빈 공간을 발견하고 9개의 공간(또는 디스크 목록의 끝까지)을 찾아 빈 공간을 모두 보면 조각화가 완료된 것입니다.

이 알고리즘의 나머지 부분을 작성하는 방법을 알 것 같아요!

조각화 알고리즘 작성

작동 알고리즘은 다음과 같습니다.

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

작동 방식:

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

다행히 두 예시와 동일한 출력이 표시됩니다!

체크섬 계산

매우 쉽고 간단해 보입니다.

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

의사 코드:

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

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

퍼즐 입력에도 동일하게 적용되나요?

...

그렇습니다!!!

우후!!!

2부에는 어떤 반전이 있을까요? 약간의 규칙 조정 또는 규모의 문제가 있습니까?

2부

흥미로운 반전

부분이었습니다. 이제 전체입니다.

이렇게 하려면 내 알고리즘을 약간 조정해야 합니다.

간극 및 블록 크기를 더욱 강력하게 추적할 수 있습니다.

첫 번째 전략을 실행 중입니다.

저는 각각의 빈 위치를 추적했습니다.

각 빈 공간이 어디에 있고 얼마나 큰지 추적해야 할 것 같아요.

어떤 모습일까요?

스크래치하세요. 어쩌면 새로운 전략일 수도 있습니다.

첫 번째 예 사용:

12345

파일 블록 크기는 홀수입니다.

0..111....22222

빈 셀 크기는 짝수입니다.

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

홀수의 끝과 짝수의 시작부터 시작하여 홀수보다 크거나 같은 짝수를 찾습니다.

022111222......

즉시 일치하는 항목을 찾습니다.

결과:

• 홀수가 움직입니다
• 짝수가 감소합니다
• 그런데 이제 두 개의 홀수에는 간격이 없습니다
• 그리고 두 번째 2s 아이디를 잃어버렸어요

0099811188827773336446555566..............

이 전략은 절대 먹히지 않습니다.

두 번째 전략을 실행 중입니다.

이 기능이 성능에 미치는 영향이 마음에 들지 않습니다.

하지만 실행이 끝나는 한...효과가 있을 것이라고 믿습니다.

디스크 입력의 각 숫자에 대해 목록 항목으로 기록하겠습니다.

1. 파일 블록 또는 빈 셀
2. 길이
3. 아이디

예:

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

다음과 같이 됩니다:

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

으, 정리하자:

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

데이터 유형에 따라 파일 블록과의 간격을 구분하겠습니다.

파일 블록 이동은 변경된 예제 입력에서 다음과 같습니다.

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

이 작업은 100,000회 반복마다 수행됩니다.

• 큰 배열의 항목 검색
• 배열을 내부에서 변경

둘 다 비용이 많이 드는 작업입니다.

하지만 이것이 이 퍼즐을 풀 수 있는 유일한 방법이라고 생각합니다.

그래서 이것이 나의 접근 방식입니다.

내 전략을 체계화하기

위의 데이터 아키텍처를 제공하는 JavaScript는 다음과 같습니다.

2333133121414131402

메인 루프를 어떻게 시작하고 종료하나요?

파일 ID 번호가 가장 높은 파일부터 시작하여 파일 ID 번호가 감소하는 순서로 각 파일을 정확히 한 번씩 이동해 보세요.

뒤에서 앞으로 이동하면 원하는 대로 작동할 것 같습니다.

이 for 루프 뼈대가 작동해야 합니다.

[2,4,1,4,2,5,5,3,5,2]

찾기, 이동 및 바꾸기

[3,3,3,1,1,1,1,1,0]

if의 두 번째 절이 마지막 디버그였습니다. 가장 낮은 ID를 너무 일찍 넣었네요.

디스크 프린터 코딩

내 디스크가 거의 실시간으로 조각화되는 것을 확인해야 한다는 것을 깨달았습니다. 예제 연습에서와 같이 최소한 이에 대한 로그입니다.

다행히 코딩은 어렵지 않았습니다. 두 개의 인덱스를 혼합하여 정말 이상한 출력을 본 부분:

12345

• 끈을 쌓는다
• 디스크에 있는 항목 유형에 따라
• 어느 쪽이든 배열을 만들고 .s 또는 블록 ID로 채웁니다.

잘 작동합니다! 파일이 이동된 위치를 확인할 수 있었고 코드 문제를 훨씬 쉽게 해결할 수 있었습니다!

내가 보는 것을 좋아한다

0..111....22222

제 파일 이동 알고리즘이 작동하는 것 같아요!

마지막 단계는 새 체크섬을 계산하는 것입니다.

마지막으로 더 많은 수학

두 배로 줄이는 방법:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

• 첫 번째 축소에서는 ID와 .s의 광범위한 배열을 얻습니다
• 두 번째 축소는 항목이 id일 때 적절한 계산을 수행하고 .

작동합니까?

예제 퍼즐 입력에? 네!

내 퍼즐 입력에?

...

으으으으으아아앙!

와우. 나는 놀랐다. 2부에 제출한 숫자가 1부와 거의 동일합니다. 더 높을 줄 알았습니다.

추가 조사에는 관심이 없습니다.

저는 힘들게 얻은 두 개의 금별을 가지고 10일차까지 걸어가는 것이 낫습니다.

안녕아아아아 9일차!

위 내용은 디스크 조각의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!