slow.monster

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>"를 낸다.
8import std.io
10let R = 100000000
11let B = 1000000
13// ── 금칙분류 ──
14function 첫코드포인트(텍스트: string) -> int { 텍스트.codePointAt(0) ?? -1 }
15function 단일스칼라(텍스트: string) -> bool { 텍스트.scalars().length == 1 }
16function 한글분할문자인가(코드: int) -> bool {
17 (코드 >= 4352 && 코드 <= 4607) || (코드 >= 12592 && 코드 <= 12687) || (코드 >= 44032 && 코드 <= 55215)
18 || (코드 >= 13312 && 코드 <= 19903) || (코드 >= 19968 && 코드 <= 40959) || (코드 >= 63744 && 코드 <= 64255)
19 || 코드 == 65292 || 코드 == 12289 || 코드 == 12290 || 코드 == 65307 || 코드 == 65306
21function 줄머리금지인가(코드: int) -> bool {
22 코드 == 41 || 코드 == 93 || 코드 == 125 || 코드 == 12301 || 코드 == 12303 || 코드 == 12299 || 코드 == 12297
23 || 코드 == 44 || 코드 == 46 || 코드 == 59 || 코드 == 58 || 코드 == 33 || 코드 == 63 || 코드 == 12289 || 코드 == 12290
24 || 코드 == 8217 || 코드 == 8230 || 코드 == 65289 || 코드 == 12305 || 코드 == 65341 || 코드 == 65373 || 코드 == 65292 || 코드 == 65294 || 코드 == 65307 || 코드 == 65306 || 코드 == 65281 || 코드 == 65311 || 코드 == 187 || 코드 == 8250
26function 줄끝금지인가(코드: int) -> bool {
27 코드 == 40 || 코드 == 91 || 코드 == 123 || 코드 == 12300 || 코드 == 12302 || 코드 == 12298 || 코드 == 12296
28 || 코드 == 65288 || 코드 == 12304 || 코드 == 65339 || 코드 == 65371 || 코드 == 171 || 코드 == 8249
30function 모두한글분할(텍스트: string) -> bool {
31 텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 한글분할문자인가(첫코드포인트(스칼라)))
33function 모두줄머리금지(텍스트: string) -> bool {
34 텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 줄머리금지인가(첫코드포인트(스칼라)))
36function 일부줄머리금지(텍스트: string) -> bool {
37 텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 줄머리금지인가(첫코드포인트(스칼라)))
39function 일부줄끝금지(텍스트: string) -> bool {
40 텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 줄끝금지인가(첫코드포인트(스칼라)))
42function 분할가능라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }
43function 라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160) }
44function 비분할공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 160 || 첫코드포인트(텍스트) == 8239) }
45function 라틴붙임표인가(텍스트: string) -> bool {
46 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 45 || 첫코드포인트(텍스트) == 8208 || 첫코드포인트(텍스트) == 8209 || 첫코드포인트(텍스트) == 8211)
48function 쉼표마침표콜론인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 44 || 첫코드포인트(텍스트) == 46 || 첫코드포인트(텍스트) == 58) }
49function 아스키숫자인가(텍스트: string) -> bool { 텍스트.byteLength() == 1 && 첫코드포인트(텍스트) >= 48 && 첫코드포인트(텍스트) <= 57 }
50function 다음은라틴공백아님(다음: Option<string>) -> bool {
51 match (다음) {
52 case Some(텍스트) => !라틴공백인가(텍스트)
53 case None() => true
54 }
56function 다음은줄머리금지없음(다음: Option<string>) -> bool {
57 match (다음) {
58 case Some(텍스트) => !일부줄머리금지(텍스트)
59 case None() => true
60 }
62function 다음은라틴공백(다음: Option<string>) -> bool {
63 match (다음) {
64 case Some(텍스트) => 라틴공백인가(텍스트)
65 case None() => false
66 }
68function 다음은일부줄머리금지(다음: Option<string>) -> bool {
69 match (다음) {
70 case Some(텍스트) => 일부줄머리금지(텍스트)
71 case None() => false
72 }
74function 옵션아스키숫자인가(옵션: Option<string>) -> bool {
75 match (옵션) {
76 case Some(텍스트) => 아스키숫자인가(텍스트)
77 case None() => false
78 }
80function 숫자구분자인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {
81 쉼표마침표콜론인가(현재) && 옵션아스키숫자인가(이전) && 옵션아스키숫자인가(다음)
83function 닫음부호허용인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {
84 모두줄머리금지(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !숫자구분자인가(현재, 이전, 다음)
86function 한글분할허용인가(현재: string, 다음: Option<string>) -> bool {
87 모두한글분할(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !일부줄끝금지(현재)
90// ── 나쁨도 (정렬=없음 경로) ──
91function 반올림나눗셈(분자: int, 분모: int) -> int {
92 let 몫 = 분자 / 분모
93 let 나머지 = 분자 % 분모
94 if (나머지 >= (분모 + 1) / 2) { 몫 + 1 } else { 몫 }
96function 절댓값(값: int) -> int { if (값 < 0) { -값 } else { 값 } }
97function 나쁨도(너비: 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 * 비례R
104 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 * B
115 기본B
118// ── 분할점(단위 + 종류), 인덱스 0에 센티넬 ──
119// 모든 후보에 적용하는 원문 문맥 금칙. 공백 뒤의 부호도 앞 낱말에 붙인다.
120function 공백코드인가(코드: int) -> bool {
121 (코드 >= 9 && 코드 <= 13) || 코드 == 32 || 코드 == 133 || 코드 == 160 || 코드 == 5760
122 || (코드 >= 8192 && 코드 <= 8202) || 코드 == 8232 || 코드 == 8233 || 코드 == 8239 || 코드 == 8287 || 코드 == 12288
124function 여는직선따옴표인가(글자들: Array<string>, 위치: int) -> bool {
125 let 코드 = 첫코드포인트(글자들[위치])
126 if (코드 != 34 && 코드 != 39) { return false }
127 if (위치 == 0) { return true }
128 let 앞 = 첫코드포인트(글자들[위치 - 1])
129 공백코드인가(앞) || 줄끝금지인가(앞)
131function 라틴낱말코드인가(코드: int) -> bool {
132 (코드 >= 65 && 코드 <= 90) || (코드 >= 97 && 코드 <= 122)
133 || (코드 >= 192 && 코드 <= 591) || (코드 >= 7680 && 코드 <= 7935)
135function 문맥경계허용인가(글자들: Array<string>, 경계: int) -> bool {
136 let mut 왼쪽 = 경계 - 1
137 while (왼쪽 >= 0) {
138 if (!공백코드인가(첫코드포인트(글자들[왼쪽]))) { break }
139 왼쪽 -= 1
140 }
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 오른쪽 += 1
152 }
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 true
165function 분할점생성(클러스터들: Array<string>) -> { 단위들: Array<int>, 종류들: Array<string> } {
166 let 개수 = 클러스터들.length
167 let mut 전체텍스트 = ""
168 for 단위 in (클러스터들) { 전체텍스트 = 전체텍스트 + 단위 }
169 let 글자들 = 전체텍스트.scalars()
170 let mut 글자끝 = 0
171 let mut 단위들 = [0]
172 let mut 종류들 = ["forced_end"]
173 for i in (0..<개수) {
174 let 단위 = 클러스터들[i]
175 let 단위끝 = i + 1
176 글자끝 += 단위.scalars().length
177 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 { 단위들: 단위들, 종류들: 종류들 }
197function 처리(입력: string) -> string {
198 let 줄들 = 입력.split("\n")
199 let 목표 = 줄들[0].toInt() ?? 0
200 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 개수 = 클러스터들.length
209 // 접두합
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 분할점수 = 분할점단위.length
220 // 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])).length
237 let 줄비용 = 나쁨도(너비, 목표, 글자접두[끝단위] - 글자접두[시작], 공백수, 끝종류, 마지막인가)
238 let 후보비용 = 상태들[pi].비용 + 줄비용
239 if (!최선.있음 || 후보비용 < 최선.비용) {
240 최선 = { 있음: true, 비용: 후보비용, 이전: pi, 줄나쁨: 줄비용 }
241 }
242 }
243 }
244 }
245 }
246 상태들.push(최선)
247 }
248 let 마지막 = 분할점수 - 1
249 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 총비용 = 0
260 let mut k = 역줄들.length - 1
261 while (k >= 0) {
262 let 줄 = 역줄들[k]
263 let 시작 = 줄.시작
264 let 끝 = 줄.끝
265 let 줄나쁨 = 줄.줄나쁨
266 출력 = if (출력 == "") { "{시작} {끝} {줄나쁨}" } else { "{출력}\n{시작} {끝} {줄나쁨}" }
267 총비용 += 줄나쁨
268 k -= 1
269 }
270 "{출력}\nTOTAL {총비용}"
273io.writeLine(처리(io.readStdin()))

SHA256 dd4f0cc59bc877e36d93ef173cb2d9ea27a8420edbb75a3a8c6315c9648553dd