이 디버거 프로그램은 문제가 있다: 메모리 재할당 루틴을 바로잡으려 노력하지만, 계속 무한 루프에 빠지게 된다.
이 영역에는, 열여섯개의 메모리 뱅크가 있다; 각 메모리 뱅크는 임의 개수의 블록들을 가질 수 있다. 재할당 루틴의 목표는 메모리 뱅크들 간의 블록들의 균형을 잡는 것이다.
재할당 루틴은 사이클들로 작동한다. 각 사이클은, 최대 블록 개수를 가진 메모리 뱅크를 찾고(여러 개일 경우 순번이 가장 낮은 뱅크), 뱅크들에게 해당 블록들을 재분배한다. 이걸 하기 위해, 선택된 뱅크에서 모든 블록들을 제거한 뒤, 다음 인덱스인 메모리 뱅크에 그 블록들을 옮기고 하나의 블록을 삽입한다. 이 과정은 옮길 블록이 더 이상 없을 때까지 반복한다; 만약 마지막 메모리 뱅크에 도달하면, 처음 메모리 뱅크로 돌아간다.
디버거는 처음과 같은 뱅크 안 블록 개수들일 때 재분배 발생 횟수를 알고 싶어 한다.
예를 들어, 네 개의 메모리 뱅크들이 있을 때 시나리오를 상상해보자:
- 뱅크들은
0,2,7, 그리고0개의 블록들로 시작한다. 세 번째 뱅크는 가장 많은 개수의 블록들을 가지기 때문에, 재분배를 위해 선택된다. - 다음 뱅크(네 번째 뱅크)로 시작하고 첫 번째 뱅크, 두 번째 뱅크, 이후로 진행하면서
7개의 블록들은 메모리 뱅크들로 퍼져나간다. 네 번째, 첫 번째, 두 번째 뱅크는 각각 두 개의 블록들을 가지고, 그리고 세 번째 뱅크는 한 개의 블록을 돌려 받는다. 최종 결과는 다음과 같다:2 4 1 2. - 다음, 두 번째 뱅크가 최대 블록 개수(
4) 때문에 선정된다. 네 개의 메모리 뱅크가 각각 한 개의 블록을 가진다. 결과는 다음과 같다:3 1 2 3. - 이제, 네 번째 뱅크와 첫 번째 뱅크는 각각 세 개의 블록을 가지는데, 순번이 가장 빠른 첫 번째 뱅크가 선정되어 다른 세 개의 뱅크들에게 분배한다. 결과는 다음과 같다:
0 2 3 4. - 네 번째 뱅크가 선정되고 분배되면 다음과 같다:
1 3 4 1. - 세 번째 뱅크가 선정되고 분배되면 시작할 때와 같이 다음과 같다:
2 4 1 2.
이 시점에서, 처음과 같은 뱅크 안 블록 개수들이 나타난다: 2 4 2 1은 처음과 같다. 다섯 번째 블록 재분배 사이클 이후에 무한 루프가 탐지되었으므로, 이 예제의 답은 5이다.
주어진 퍼즐 인풋의 초기 블록 개수들로, 재분배 사이클의 개수를 구하라.
- 입력 : 뱅크 별 블록 개수들 수열
- 처리 : 재분배하면서 달라지는 수열들을 딕셔너리에 집어넣으면서 이미 나왔던 수열이라면 멈추고 센 횟수를 출력한다.
- 출력 : 재분배 사이클의 개수.
- source
호기심에, 디버거는 루프의 크기도 알고 싶어 한다: 이미 나왔던 상태로부터 시작하여, 다시 해당 상태가 나올 때까지 얼마나 많은 블록 재분배 사이클이 돌아야 하는가?
위 예제에서는, 2 4 1 2는 네 사이클 이후에 다시 나타나므로, 답은 4이다.
무한 루프 안에서 얼마나 많은 사이클이 도는가?
- 입력 : 뱅크 별 블록 개수들 수열
- 처리 : 위 솔루션처럼 재분배하면서 달라지는 수열들을 딕셔너리에 집어넣을 때마다 재분배 반복 횟수를 집어놓고, 이미 나왔던 수열이라면 딕셔너리에 저장되어 있는 재분배 반복 횟수 값과 현재 재분배 반복 횟수 값의 차이를 출력한다.
- 출력 : 딕셔너리에 저장되어 있는 재분배 반복 횟수 값과 현재 재분배 반복 횟수 값의 차이
- source