언제부터 깨졌나 — 64판을 여섯 번에 좁힌다

목표

좋다·나쁘다·판정 불가를 가르는 기계 판정기를 만들고, 그것으로 빌드 이력 64판과 입력 자료 4096행을 각각 반씩 잘라 경계를 찾는다. 판정 불가를 비켜 가는 길과 경계를 전수로 검증하는 길까지 붙이고, 순차 탐색이었다면 몇 번이었을지를 함께 기록한다.

왜 중요한가

"지난주까지는 됐는데요" 와 "어제 파일에서만 죽어요" 는 같은 모양의 문제다. 경계가 하나 있고 앞뒤가 갈린다. 앞에서부터 하나씩 보면 64번과 4096번이지만, 반씩 자르면 여섯 번과 열두 번이다.
이 차이를 만드는 것은 도구가 아니라 판정기다. 사람이 화면을 보고 판단하는 절차가 섞이면 열 번을 반복할 수 없고, 다섯 번째쯤에서 자기가 어느 쪽을 좋다고 했는지 잊는다.
어려운 것은 반으로 자르는 코드가 아니라 경계 조건이다. 기동하지 않는 판을 나쁨으로 셈하면 범인이 앞으로 밀리고, 조각에서 머리글을 떼면 모든 조각이 실패해 1행을 가리키고, 중간에 고쳤다가 다시 깨진 이력에서는 답 자체가 틀린다.
채점기는 여러분의 문구를 믿지 않는다. 채점기가 만든 이력과 자료를 임시 디렉터리에 차려 놓고 여러분의 도구를 실제로 실행해, 경계가 맞는지와 몇 번 만에 찾았는지를 함께 잰다. 경계는 실행할 때마다 다른 자리에 있으므로 값을 외워 넣을 수 없다.

단계

1. /root/bisect/gen_history.py 를 만들어 실행해 빌드 이력 64판과 /root/bisect/ref.csv, /root/bisect/rows.csv, /root/bisect/loader.py 를 만드세요.
2. /root/bisect/judge.py 를 만들어 한 판을 good·bad·unknown 으로 가르게 하세요. 종료 코드는 각각 0, 1, 125 입니다.
3. /root/bisect/bisect_run.py 로 이력을 반씩 잘라 처음 나빠진 판을 찾고 /root/bisect/bisect_result.json 에 남기세요. 후보 63개는 여섯 번이면 끝납니다.
4. bisect_run.py 가 판정 불가를 만나면 이웃 판으로 비켜 다시 묻게 하고, 구간이 통째로 판정 불가면 한 판을 지목하지 않게 하세요.
5. /root/bisect/row_bisect.py 로 적재기를 죽이는 행을 찾아 /root/bisect/row_result.json 에 남기세요. 조각에는 머리글을 항상 붙입니다.
6. /root/bisect/probe_count.json 에 순차 탐색과 이분 탐색의 최악 횟수, 그리고 실제로 든 횟수를 나란히 적으세요.
7. /root/bisect/verify_bisect.py 로 경계를 전수 검증해 /root/bisect/verify_result.json 을 만드세요. 단조가 아닌 이력을 만나면 반례를 이름으로 적어야 합니다.
8. /root/bisect/summary.json 과 /root/bisect/bisect_report.md 에 네 절로 보고하세요.

참고

• 판정 계약: python3 /root/bisect/judge.py --rev <판 디렉터리> --input <csv> --expect <정수> 는 good·bad·unknown 중 한 낱말을 표준출력에 내고 종료 코드 0·1·125 로 끝납니다.
• 파이프라인 계약: python3 <판>/pipeline.py --in <csv> 는 total=<정수> 한 줄을 내고 0 으로 끝납니다. 기동하지 않는 판은 0 이 아닌 코드로 끝납니다.
• 탐색 계약: python3 /root/bisect/bisect_run.py --hist <이력 디렉터리> --input <csv> --expect <정수> --out <json> 은 first_bad·last_good·probe_count·probes·undecided 를 담은 JSON 한 덩어리를 냅니다. 판 이름은 디렉터리 이름 그대로(예: r41)입니다.
• 행 탐색 계약: python3 /root/bisect/row_bisect.py --csv <파일> --loader <적재기> --out <json> 은 bad_row(머리글을 뺀 1부터 세는 행 번호)·probe_count·rows 를 냅니다. 적재기는 python3 <적재기> <csv> 로 부르고 0 이 아닌 코드면 그 조각에 범인이 있습니다.
• 검증 계약: python3 /root/bisect/verify_bisect.py --hist <디렉터리> --input <csv> --expect <정수> --boundary <판 이름> --out <json> 은 boundary_bad·prev_good·monotone·contradictions·checked 를 냅니다.
• 횟수 계산: 후보 n 개의 순차 탐색 최악은 n 번, 이분 탐색 최악은 올림한 log2(n) 번입니다. 이력의 후보 수는 판의 수에서 하나를 뺀 값(첫 판은 좋다고 보고 시작하므로)이고, 자료의 후보 수는 행 수입니다.
• 흔한 실수: 판정 불가를 나쁨으로 접기, 조각에서 머리글 떼기, 경계를 찾고 검증하지 않기, 판정기를 만들기 전에 눈으로 탐색하기.
• 이 실습의 가정: 종료 코드 125 를 판정 불가로 쓰는 것은 git bisect run 의 규약을 그대로 빌린 것입니다. 표준이 정한 값은 아닙니다.
• 부하 시험을 만들지 마세요. 채점 하나의 예산은 60초이고 파드는 2코어입니다.

단계 8개

1. 빌드 이력과 새 입력 손에 쥐기
2. 좋다와 나쁘다를 기계가 가르게 하기
3. 이력을 반씩 잘라 경계 찾기
4. 기동하지 않는 판 비켜 가기
5. 적재기를 죽이는 행 찾기
6. 몇 번 만에 끝났는지 세기
7. 경계가 정말 경계인지 전수로 확인하기
8. 두 경계를 한 장으로 보고하기