STUDIO HAZE · atlas
Topaz source
Open by house policy. Topaz is our own language.
Topaz 6.0 · 5 files
Topaz 6.0 source.
Publication edits are limited to explanatory comments. Executable code is unchanged.
Rights and source notices · Source manifest
core/topaz/linebreak/최적분할.tpz
Topaz · 14382 B · Published file
1
// 아틀라스 최적분할. 전체 비용이 가장 낮은 줄 분할을 고르는 고정소수 정수 DP 명세다(optimal-fit integer DP).2
// 통합 줄바꿈기 `줄바꿈.tpz`의 4단계(정수 동적계획법)를 따로3
// 떼어 적었다.4
// 범위는 드롭캡 OFF(단일 버킷), 첫줄=목표, 정렬=없음이다. 1·2·4단계(금칙분류·나쁨도·정수 DP)를 한 파일에 인라인한다.5
// 드롭캡·첫줄목표·정렬을 더한 2차원 (분할점, 버킷) 전체 DP는 통합본 `줄바꿈.tpz`에 있다.6
// 입출력. 표준입력으로 "<목표너비mpt>\n<진행mpt>\t<텍스트>\n..."를 받아 "<시작> <끝배타> <줄나쁨도B>\n...TOTAL <B>"를 낸다.8
import std.io10
let R = 10000000011
let B = 100000013
// ── 금칙분류 ──14
function 첫코드포인트(텍스트: string) -> int { 텍스트.codePointAt(0) ?? -1 }15
function 단일스칼라(텍스트: string) -> bool { 텍스트.scalars().length == 1 }16
function 한글분할문자인가(코드: int) -> bool {17
(코드 >= 4352 && 코드 <= 4607) || (코드 >= 12592 && 코드 <= 12687) || (코드 >= 44032 && 코드 <= 55215)18
|| (코드 >= 13312 && 코드 <= 19903) || (코드 >= 19968 && 코드 <= 40959) || (코드 >= 63744 && 코드 <= 64255)19
|| 코드 == 65292 || 코드 == 12289 || 코드 == 12290 || 코드 == 65307 || 코드 == 6530620
}21
function 줄머리금지인가(코드: int) -> bool {22
코드 == 41 || 코드 == 93 || 코드 == 125 || 코드 == 12301 || 코드 == 12303 || 코드 == 12299 || 코드 == 1229723
|| 코드 == 44 || 코드 == 46 || 코드 == 59 || 코드 == 58 || 코드 == 33 || 코드 == 63 || 코드 == 12289 || 코드 == 1229024
|| 코드 == 8217 || 코드 == 8230 || 코드 == 65289 || 코드 == 12305 || 코드 == 65341 || 코드 == 65373 || 코드 == 65292 || 코드 == 65294 || 코드 == 65307 || 코드 == 65306 || 코드 == 65281 || 코드 == 65311 || 코드 == 187 || 코드 == 825025
}26
function 줄끝금지인가(코드: int) -> bool {27
코드 == 40 || 코드 == 91 || 코드 == 123 || 코드 == 12300 || 코드 == 12302 || 코드 == 12298 || 코드 == 1229628
|| 코드 == 65288 || 코드 == 12304 || 코드 == 65339 || 코드 == 65371 || 코드 == 171 || 코드 == 824929
}30
function 모두한글분할(텍스트: string) -> bool {31
텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 한글분할문자인가(첫코드포인트(스칼라)))32
}33
function 모두줄머리금지(텍스트: string) -> bool {34
텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 줄머리금지인가(첫코드포인트(스칼라)))35
}36
function 일부줄머리금지(텍스트: string) -> bool {37
텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 줄머리금지인가(첫코드포인트(스칼라)))38
}39
function 일부줄끝금지(텍스트: string) -> bool {40
텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 줄끝금지인가(첫코드포인트(스칼라)))41
}42
function 분할가능라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }43
function 라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160) }44
function 비분할공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 160 || 첫코드포인트(텍스트) == 8239) }45
function 라틴붙임표인가(텍스트: string) -> bool {46
단일스칼라(텍스트) && (첫코드포인트(텍스트) == 45 || 첫코드포인트(텍스트) == 8208 || 첫코드포인트(텍스트) == 8209 || 첫코드포인트(텍스트) == 8211)47
}48
function 쉼표마침표콜론인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 44 || 첫코드포인트(텍스트) == 46 || 첫코드포인트(텍스트) == 58) }49
function 아스키숫자인가(텍스트: string) -> bool { 텍스트.byteLength() == 1 && 첫코드포인트(텍스트) >= 48 && 첫코드포인트(텍스트) <= 57 }50
function 다음은라틴공백아님(다음: Option<string>) -> bool {51
match (다음) {52
case Some(텍스트) => !라틴공백인가(텍스트)53
case None() => true54
}55
}56
function 다음은줄머리금지없음(다음: Option<string>) -> bool {57
match (다음) {58
case Some(텍스트) => !일부줄머리금지(텍스트)59
case None() => true60
}61
}62
function 다음은라틴공백(다음: Option<string>) -> bool {63
match (다음) {64
case Some(텍스트) => 라틴공백인가(텍스트)65
case None() => false66
}67
}68
function 다음은일부줄머리금지(다음: Option<string>) -> bool {69
match (다음) {70
case Some(텍스트) => 일부줄머리금지(텍스트)71
case None() => false72
}73
}74
function 옵션아스키숫자인가(옵션: Option<string>) -> bool {75
match (옵션) {76
case Some(텍스트) => 아스키숫자인가(텍스트)77
case None() => false78
}79
}80
function 숫자구분자인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {81
쉼표마침표콜론인가(현재) && 옵션아스키숫자인가(이전) && 옵션아스키숫자인가(다음)82
}83
function 닫음부호허용인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {84
모두줄머리금지(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !숫자구분자인가(현재, 이전, 다음)85
}86
function 한글분할허용인가(현재: string, 다음: Option<string>) -> bool {87
모두한글분할(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !일부줄끝금지(현재)88
}90
// ── 나쁨도 (정렬=없음 경로) ──91
function 반올림나눗셈(분자: int, 분모: int) -> int {92
let 몫 = 분자 / 분모93
let 나머지 = 분자 % 분모94
if (나머지 >= (분모 + 1) / 2) { 몫 + 1 } else { 몫 }95
}96
function 절댓값(값: int) -> int { if (값 < 0) { -값 } else { 값 } }97
function 나쁨도(너비: int, 목표너비: int, 글자수: int, 공백수: int, 분할종류: string, 마지막인가: bool) -> int {98
let 여유 = 목표너비 - 너비99
let 절대여유 = 절댓값(여유)100
let 원시R = if (절대여유 >= 4 * 목표너비) { 4 * R } else { 절대여유 * R / 목표너비 }101
let 조정상한센티 = if (여유 >= 0) { 100 + 공백수 * 45 } else { 100 + 공백수 * 25 }102
let 비례R = 반올림나눗셈(원시R * 100, 조정상한센티)103
let 제곱 = 비례R * 비례R104
let 몫 = 반올림나눗셈(제곱, R)105
let mut 기본B = 반올림나눗셈(몫 * (1000 * B), R)106
if (마지막인가) {107
기본B = 반올림나눗셈(기본B * 2, 5)108
if (너비 * 100 < 목표너비 * 52 && 글자수 > 0) { 기본B += 500 * B }109
}110
if (여유 < 0) { 기본B += 20000 * B + 반올림나눗셈(20000 * B * 비례R, R) }111
if (분할종류 == "latin_hyphen") { 기본B += 65 * B }112
if (분할종류 == "hard_fallback") { 기본B += 50000 * B }113
if (글자수 <= 2) { 기본B += 275 * B }114
기본B += 10 * B115
기본B116
}118
// ── 분할점(단위 + 종류), 인덱스 0에 센티넬 ──119
// 모든 후보에 적용하는 원문 문맥 금칙. 공백 뒤의 부호도 앞 낱말에 붙인다.120
function 공백코드인가(코드: int) -> bool {121
(코드 >= 9 && 코드 <= 13) || 코드 == 32 || 코드 == 133 || 코드 == 160 || 코드 == 5760122
|| (코드 >= 8192 && 코드 <= 8202) || 코드 == 8232 || 코드 == 8233 || 코드 == 8239 || 코드 == 8287 || 코드 == 12288123
}124
function 여는직선따옴표인가(글자들: Array<string>, 위치: int) -> bool {125
let 코드 = 첫코드포인트(글자들[위치])126
if (코드 != 34 && 코드 != 39) { return false }127
if (위치 == 0) { return true }128
let 앞 = 첫코드포인트(글자들[위치 - 1])129
공백코드인가(앞) || 줄끝금지인가(앞)130
}131
function 라틴낱말코드인가(코드: int) -> bool {132
(코드 >= 65 && 코드 <= 90) || (코드 >= 97 && 코드 <= 122)133
|| (코드 >= 192 && 코드 <= 591) || (코드 >= 7680 && 코드 <= 7935)134
}135
function 문맥경계허용인가(글자들: Array<string>, 경계: int) -> bool {136
let mut 왼쪽 = 경계 - 1137
while (왼쪽 >= 0) {138
if (!공백코드인가(첫코드포인트(글자들[왼쪽]))) { break }139
왼쪽 -= 1140
}141
if (왼쪽 > 0 && 왼쪽 + 1 < 글자들.length) {142
let 코드 = 첫코드포인트(글자들[왼쪽])143
if ((코드 == 8217 || 코드 == 39) && 라틴낱말코드인가(첫코드포인트(글자들[왼쪽 - 1])) && 라틴낱말코드인가(첫코드포인트(글자들[왼쪽 + 1]))) { return false }144
}145
if (왼쪽 >= 0) {146
if (줄끝금지인가(첫코드포인트(글자들[왼쪽])) || 여는직선따옴표인가(글자들, 왼쪽)) { return false }147
}148
let mut 오른쪽 = 경계149
while (오른쪽 < 글자들.length) {150
if (!공백코드인가(첫코드포인트(글자들[오른쪽]))) { break }151
오른쪽 += 1152
}153
if (오른쪽 < 글자들.length) {154
let 코드 = 첫코드포인트(글자들[오른쪽])155
if (줄머리금지인가(코드)) { return false }156
if ((코드 == 34 || 코드 == 39) && !여는직선따옴표인가(글자들, 오른쪽)) { return false }157
if (코드 == 8212) {158
if (오른쪽 > 0 && 줄머리금지인가(첫코드포인트(글자들[오른쪽 - 1]))) { return false }159
if (오른쪽 + 1 < 글자들.length && 줄머리금지인가(첫코드포인트(글자들[오른쪽 + 1]))) { return false }160
}161
}162
true163
}165
function 분할점생성(클러스터들: Array<string>) -> { 단위들: Array<int>, 종류들: Array<string> } {166
let 개수 = 클러스터들.length167
let mut 전체텍스트 = ""168
for 단위 in (클러스터들) { 전체텍스트 = 전체텍스트 + 단위 }169
let 글자들 = 전체텍스트.scalars()170
let mut 글자끝 = 0171
let mut 단위들 = [0]172
let mut 종류들 = ["forced_end"]173
for i in (0..<개수) {174
let 단위 = 클러스터들[i]175
let 단위끝 = i + 1176
글자끝 += 단위.scalars().length177
let 이전: Option<string> = 클러스터들.get(i - 1)178
let 다음 = 클러스터들.get(단위끝)179
let 결과: { 종류: string, 내보냄: bool } = match (true) {180
case _ if (단위끝 == 개수) => { 종류: "forced_end", 내보냄: true }181
case _ if (!문맥경계허용인가(글자들, 글자끝)) => { 종류: "", 내보냄: false }182
case _ if (분할가능라틴공백인가(단위)) => { 종류: "latin_space", 내보냄: true }183
case _ if (라틴붙임표인가(단위)) => { 종류: "latin_hyphen", 내보냄: true }184
case _ if (닫음부호허용인가(단위, 이전, 다음)) => { 종류: "closing_punctuation", 내보냄: true }185
case _ if (한글분할허용인가(단위, 다음)) => { 종류: "korean_cluster", 내보냄: true }186
case _ if (다음은라틴공백(다음) || 비분할공백인가(단위) || 다음은일부줄머리금지(다음)) => { 종류: "", 내보냄: false }187
case _ => { 종류: "hard_fallback", 내보냄: true }188
}189
if (결과.내보냄) {190
단위들.push(단위끝)191
종류들.push(결과.종류)192
}193
}194
{ 단위들: 단위들, 종류들: 종류들 }195
}197
function 처리(입력: string) -> string {198
let 줄들 = 입력.split("\n")199
let 목표 = 줄들[0].toInt() ?? 0200
if (목표 <= 0 || 목표 > 23000000000) { return "OUT_OF_BOUNDS" }201
let mut 클러스터들: Array<string> = []202
let mut 진행: Array<int> = []203
for li in (1..<줄들.length) {204
let 부분들 = 줄들[li].split("\t")205
진행.push(부분들[0].toInt() ?? 0)206
클러스터들.push(if (부분들.length >= 2) { 부분들[1] } else { "" })207
}208
let 개수 = 클러스터들.length209
// 접두합210
let mut 너비접두 = [0]211
let mut 글자접두 = [0]212
for i in (0..<개수) {213
너비접두.push(너비접두[i] + 진행[i])214
글자접두.push(글자접두[i] + 클러스터들[i].scalars().length)215
}216
let 분할점 = 분할점생성(클러스터들)217
let 분할점단위 = 분할점.단위들218
let 분할점종류 = 분할점.종류들219
let 분할점수 = 분할점단위.length220
// DP 상태(병렬 배열, endIndex 순으로 push)221
let mut 상태들: Array<{ 있음: bool, 비용: int, 이전: int, 줄나쁨: int }> = [222
{ 있음: true, 비용: 0, 이전: 0, 줄나쁨: 0 }223
]224
for ei in (1..<분할점수) {225
let 끝단위 = 분할점단위[ei]226
let 끝종류 = 분할점종류[ei]227
let 이전시작 = if (ei > 80) { ei - 80 } else { 0 }228
let 마지막인가 = 끝단위 == 개수229
let mut 최선 = { 있음: false, 비용: 0, 이전: 0, 줄나쁨: 0 }230
for pi in (이전시작..<ei) {231
if (상태들[pi].있음) {232
let 시작 = 분할점단위[pi]233
if (시작 < 끝단위) {234
let 너비 = 너비접두[끝단위] - 너비접두[시작]235
if (!(너비 > 목표 + 1 && 끝단위 > 시작 + 1)) {236
let 공백수 = (시작..<끝단위).filter((i: int) => 분할가능라틴공백인가(클러스터들[i])).length237
let 줄비용 = 나쁨도(너비, 목표, 글자접두[끝단위] - 글자접두[시작], 공백수, 끝종류, 마지막인가)238
let 후보비용 = 상태들[pi].비용 + 줄비용239
if (!최선.있음 || 후보비용 < 최선.비용) {240
최선 = { 있음: true, 비용: 후보비용, 이전: pi, 줄나쁨: 줄비용 }241
}242
}243
}244
}245
}246
상태들.push(최선)247
}248
let 마지막 = 분할점수 - 1249
if (!상태들[마지막].있음) { return "NO_PLAN" }250
// 역추적(reversed 수집)251
let mut 역줄들: Array<{ 시작: int, 끝: int, 줄나쁨: int }> = []252
let mut wi = 마지막253
while (wi > 0) {254
let 상태 = 상태들[wi]255
역줄들.push({ 시작: 분할점단위[상태.이전], 끝: 분할점단위[wi], 줄나쁨: 상태.줄나쁨 })256
wi = 상태.이전257
}258
let mut 출력 = ""259
let mut 총비용 = 0260
let mut k = 역줄들.length - 1261
while (k >= 0) {262
let 줄 = 역줄들[k]263
let 시작 = 줄.시작264
let 끝 = 줄.끝265
let 줄나쁨 = 줄.줄나쁨266
출력 = if (출력 == "") { "{시작} {끝} {줄나쁨}" } else { "{출력}\n{시작} {끝} {줄나쁨}" }267
총비용 += 줄나쁨268
k -= 1269
}270
"{출력}\nTOTAL {총비용}"271
}273
io.writeLine(처리(io.readStdin()))SHA256 dd4f0cc59bc877e36d93ef173cb2d9ea27a8420edbb75a3a8c6315c9648553dd