slow.monster

STUDIO HAZE · jeniapp

Topaz source

Open by house policy. Topaz is our own language.

Topaz 5.20.2 · 63 files

apps/layout/layout.tpz

Topaz · 15513 B · Original file

1// 제약 기반 레이아웃 계산. 한 줄에 하나씩 적은 선형 등식을 가우스-조던 소거로 풀고 상자 배치를 그립니다.
2// 입력은 줄마다 `좌변 = 우변` 이고 항은 정수, 변수, `정수 * 변수` 를 + 와 - 로 잇습니다. 빈 줄과 # 으로 시작하는 줄은 건너뜁니다.
3// 출력은 변수별 값 목록과, `<이름>.x` 와 `<이름>.폭` 이 함께 있는 상자를 가로 막대로 그린 SVG 를 담은 HTML 조각입니다.
4// 같은 입력이면 인터프리터와 웹 빌드에서 바이트까지 같은 해와 같은 SVG 를 냅니다.
5// 부등식, 제약 강도, 편집 변수, 2차원 자동 배치, 소수 계수, 절댓값이 10000 을 넘는 계수와 상수는 다루지 않습니다.
6// Constraint layout: solves one linear equation per line by Gauss-Jordan elimination and draws the resulting boxes.
8record 이름항 { 이름: string, 계수: float }
9record 한변 { 이름항들: Array<이름항>, 상수: float }
10record 방정식 { 이름들: Array<string>, 계수합: Map<string, float>, 우변: float }
11enum 풀이상태 { 유일, 모순, 부족 }
12record 풀이 { 상태: 풀이상태, 값들: Array<float>, 피벗있음: Array<bool> }
13record 상자 { 이름: string, x: float, 폭: float }
15// 계수가 사실상 0 인지와 잔차가 진짜 모순인지는 다른 질문이라 값이 같아도 따로 둡니다.
16// 계수와 상수를 ±10000 으로 묶었으므로 진짜 모순의 잔차는 약 1e-4 이상이고 실수 잡음은 약 1e-12 라 고정 임계로 가릅니다.
17let 엡실론 = 0.000001
18let 모순엡실론 = 0.000001
19// 이 범위 밖은 실수 정밀도를 보장할 수 없어 잘못 풀기보다 거절합니다.
20let 계수한도 = 10000.0
21let 모순문구 = "모순된 제약입니다. 해가 없습니다."
22let 빈입력안내 = "<div class=\"meta\">제약(예: 상자1.x = 0)을 한 줄에 하나씩 입력하세요.</div>"
23let 부족안내 = "<div class=\"bad\">제약이 부족합니다. 자유 변수는 0으로 둔 한 가지 해입니다.</div>"
25// 공용 도우미 시작 (이스케이프 숫자인가 오류알림 결과풀기 오류바꾸기)
26// 여러 도구가 같은 원본을 씁니다. 여기서 고치지 않고 원본에서 고친 뒤 다시 생성합니다.
28// 사용자 입력을 HTML 에 넣기 전에 반드시 거칩니다.
29function 이스케이프(원문: string) -> string {
30 원문.replace("&", "&amp;").replace("<", "&lt;").replace(">", "&gt;").replace("\"", "&quot;")
33function 숫자인가(글자: string) -> bool {
34 let 코드 = 글자.codePointAt(0) ?? 0
35 코드 >= 48 && 코드 <= 57
38// 문구는 고정 문장이거나 이미 이스케이프한 값이어야 합니다.
39function 오류알림(문구: string) -> string {
40 "<div class=\"err\">{문구}</div>"
43// 성공 값과 안내가 모두 바로 보여 줄 HTML 조각일 때 진입점에서 한 번 풉니다. 토파즈 과제 'Result 오류 쪽 변환과 풀기' 의 우회입니다.
44function 결과풀기(값: Result<string, string>) -> string {
45 match 값 {
46 case Ok(결과) => 결과
47 case Err(안내) => 안내
48 }
51// 성공 값은 그대로 두고 오류만 문구로 바꿉니다. 토파즈 과제 'Result 오류 쪽 변환과 풀기' 의 우회입니다.
52function 오류바꾸기<T, E>(결과: Result<T, E>, 바꾸기: (E) -> string) -> Result<T, string> {
53 match 결과 {
54 case Ok(값) => Ok(값)
55 case Err(오류) => Err(바꾸기(오류))
56 }
59// 공용 도우미 끝
61// 변수 이름에 쓰는 글자입니다. 영문, 숫자, 밑줄, 점, 한글 음절, 자모, 호환 자모 순입니다.
62// 코드포인트를 10진수로 적습니다. 토파즈 과제 '16진 정수 리터럴' 의 우회입니다.
63function 이름글자인가(글자: string) -> bool {
64 let 코드 = 글자.codePointAt(0) ?? 0
65 (코드 >= 48 && 코드 <= 57) || (코드 >= 65 && 코드 <= 90) || (코드 >= 97 && 코드 <= 122)
66 || 코드 == 95 || 코드 == 46
67 || (코드 >= 44032 && 코드 <= 55203) || (코드 >= 4352 && 코드 <= 4607)
68 || (코드 >= 12592 && 코드 <= 12687)
71// 숫자로 시작하지 않아야 정수 상수와 갈립니다.
72function 변수이름인가(토큰: string) -> bool {
73 let 글자들 = 토큰.scalars()
74 글자들.length > 0 && !숫자인가(글자들[0]) && 글자들.filter(글자 => !이름글자인가(글자)).length == 0
77// 붙여 쓴 `x+y=3` 도 띄어 쓴 입력처럼 토큰으로 나뉘게 합니다. 점은 변수 이름의 일부라 그대로 둡니다.
78function 연산자띄우기(입력줄: string) -> string {
79 입력줄.replace("+", " + ").replace("-", " - ").replace("*", " * ").replace("=", " = ")
82// 모든 항에 기본부호를 곱하므로 우변은 -1 을 받아 좌변 - 우변 꼴로 모입니다.
83function 한변읽기(식: string, 기본부호: float) -> Result<한변, string> {
84 let 토큰들 = 식.trim().split(" ").filter(토큰 => 토큰 != "")
85 if 토큰들.length == 0 { return Err("빈 식입니다") }
86 let mut 이름항들: Array<이름항> = []
87 let mut 상수 = 0.0
88 let mut 부호 = 기본부호
89 // 부호 뒤에 아직 항이 오지 않았는지입니다. 끝까지 남으면 매달린 부호입니다.
90 let mut 부호대기 = false
91 let mut 위치 = 0
92 while 위치 < 토큰들.length {
93 let 토큰 = 토큰들[위치]
94 if 토큰 == "+" || 토큰 == "-" {
95 if 부호대기 { return Err("부호가 연달아 올 수 없습니다") }
96 부호 = if 토큰 == "+" { 기본부호 } else { -기본부호 }
97 부호대기 = true
98 위치 += 1
99 } else if 토큰 == "*" {
100 return Err("'*'의 위치가 잘못되었습니다")
101 } else {
102 match toInt(토큰) {
103 case Some(수) => {
104 if 위치 + 1 < 토큰들.length && 토큰들[위치 + 1] == "*" {
105 if !(위치 + 2 < 토큰들.length && 변수이름인가(토큰들[위치 + 2])) { return Err("'*' 뒤에 변수가 필요합니다") }
106 이름항들.push(이름항 { 이름: 토큰들[위치 + 2], 계수: 부호 * toFloat(수) })
107 위치 += 3
108 } else {
109 상수 += 부호 * toFloat(수)
110 위치 += 1
111 }
112 }
113 case None => {
114 if !변수이름인가(토큰) { return Err("알 수 없는 토큰: '{토큰}'") }
115 이름항들.push(이름항 { 이름: 토큰, 계수: 부호 })
116 위치 += 1
117 }
118 }
119 부호 = 기본부호
120 부호대기 = false
121 }
122 }
123 if 부호대기 { return Err("부호 뒤에 항이 필요합니다") }
124 Ok(한변 { 이름항들: 이름항들, 상수: 상수 })
127// 같은 변수의 계수는 항 순서대로 0.0 에 더합니다. 행렬의 칸과 한도 검사가 이 합을 함께 씁니다.
128function 계수합구하기(항들: Array<이름항>) -> Map<string, float> {
129 let mut 합: Map<string, float> = Map.new()
130 for 항 in 항들 { 합.insert(항.이름, 합.getOr(항.이름, 0.0) + 항.계수) }
131 합
134// 합친 뒤의 계수에 한도를 겁니다. `10000 * x + x` 는 10001 이 되기 때문입니다.
135function 방정식읽기(다듬은줄: string, 줄번호: int) -> Result<방정식, string> {
136 let 양변 = 연산자띄우기(다듬은줄).split("=")
137 if 양변.length != 2 { return Err(오류알림("{줄번호}번째 줄: 등호(=)가 정확히 하나여야 합니다.")) }
138 let 왼쪽 = 오류바꾸기(한변읽기(양변[0], 1.0), 문구 => 오류알림("{줄번호}번째 줄: {이스케이프(문구)}"))?
139 let 오른쪽 = 오류바꾸기(한변읽기(양변[1], -1.0), 문구 => 오류알림("{줄번호}번째 줄: {이스케이프(문구)}"))?
140 let 항들 = [for 변 in [왼쪽, 오른쪽] for 항 in 변.이름항들 => 항]
141 let 우변 = -(왼쪽.상수 + 오른쪽.상수)
142 let 계수합 = 계수합구하기(항들)
143 let 한도넘음 = 계수합.keys.reduce(Math.abs(우변) > 계수한도, (넘음, 이름) => 넘음 || Math.abs(계수합.getOr(이름, 0.0)) > 계수한도)
144 if 한도넘음 { return Err(오류알림("{줄번호}번째 줄: 계수와 상수는 ±10000 이내여야 합니다.")) }
145 Ok(방정식 { 이름들: 항들.map(항 => 항.이름), 계수합: 계수합, 우변: 우변 })
148function 제약읽기(입력: string) -> Result<Array<방정식>, string> {
149 let 줄목록 = 입력.split("\n")
150 let mut 방정식들: Array<방정식> = []
151 for i in 0..<줄목록.length {
152 let 다듬은줄 = 줄목록[i].trim()
153 if 다듬은줄 != "" && !다듬은줄.startsWith("#") { 방정식들.push(방정식읽기(다듬은줄, i + 1)?) }
154 }
155 Ok(방정식들)
158// 변수 색인은 첫 등장 순서이고 값 목록과 상자 순서가 이 순서를 따릅니다.
159function 변수모으기(방정식들: Array<방정식>) -> Array<string> {
160 let mut 변수들: Array<string> = []
161 let mut 본이름: Set<string> = Set.of()
162 for 방 in 방정식들 {
163 for 이름 in 방.이름들 {
164 if !(이름 in 본이름) {
165 본이름.add(이름)
166 변수들.push(이름)
167 }
168 }
169 }
170 변수들
173// 마지막 칸은 우변입니다.
174function 행만들기(방: 방정식, 변수들: Array<string>) -> Array<float> {
175 [for 열 in 0..<(변수들.length + 1) => if 열 == 변수들.length { 방.우변 } else { 방.계수합.getOr(변수들[열], 0.0) }]
178function 소거한행(대상행: Array<float>, 기준행: Array<float>, 열: int) -> Array<float> {
179 let 배수 = 대상행[열]
180 map(0..<대상행.length, 자리 => 대상행[자리] - 배수 * 기준행[자리])
183// 부분 피벗팅을 하는 가우스-조던 소거입니다. 자유 변수는 0 으로 둔 한 가지 해를 냅니다.
184function 풀기(방정식들: Array<방정식>, 변수들: Array<string>) -> 풀이 {
185 let 변수수 = 변수들.length
186 let mut 행렬 = 방정식들.map(방 => 행만들기(방, 변수들))
187 let 행수 = 행렬.length
188 let mut 피벗있음 = [for 열 in 0..<변수수 => false]
189 let mut 피벗의행 = [for 열 in 0..<변수수 => 0]
190 let mut 피벗행 = 0
191 let mut 열 = 0
192 while 열 < 변수수 && 피벗행 < 행수 {
193 // 같은 절댓값이면 먼저 본 행을 지켜야 출력이 바뀌지 않습니다.
194 let mut 최대행 = 피벗행
195 let mut 최댓값 = Math.abs(행렬[피벗행][열])
196 for 행 in (피벗행 + 1)..<행수 {
197 if Math.abs(행렬[행][열]) > 최댓값 {
198 최댓값 = Math.abs(행렬[행][열])
199 최대행 = 행
200 }
201 }
202 // NaN 이 된 열도 피벗으로 다뤄야 출력이 바뀌지 않으므로 `>=` 로 뒤집지 않습니다.
203 if !(최댓값 < 엡실론) {
204 let 임시 = 행렬[피벗행]
205 행렬[피벗행] = 행렬[최대행]
206 행렬[최대행] = 임시
207 let 피벗값 = 행렬[피벗행][열]
208 행렬[피벗행] = 행렬[피벗행].map(값 => 값 / 피벗값)
209 let 기준행 = 행렬[피벗행]
210 for 대상 in 0..<행수 {
211 if 대상 != 피벗행 { 행렬[대상] = 소거한행(행렬[대상], 기준행, 열) }
212 }
213 피벗있음[열] = true
214 피벗의행[열] = 피벗행
215 피벗행 += 1
216 }
217 열 += 1
218 }
219 // 뒤의 소거가 앞 행의 우변을 다시 바꾸므로 값은 소거가 모두 끝난 뒤에 읽습니다.
220 let 값들 = [for 열 in 0..<변수수 => if 피벗있음[열] { 행렬[피벗의행[열]][변수수] } else { 0.0 }]
221 let 모순 = 행렬.filter(행 => 행.slice(0, 변수수).reduce(0.0, (합, 값) => 합 + Math.abs(값)) < 엡실론 && Math.abs(행[변수수]) > 모순엡실론).length > 0
222 let 상태: 풀이상태 = if 모순 { 풀이상태.모순 } else if 피벗행 < 변수수 { 풀이상태.부족 } else { 풀이상태.유일 }
223 풀이 { 상태: 상태, 값들: 값들, 피벗있음: 피벗있음 }
226// 음의 0 같은 미세한 값을 0 으로 보여 줍니다. SVG 좌표에는 쓰지 않습니다.
227function 표시값(값: float) -> float {
228 if Math.abs(값) < 엡실론 { 0.0 } else { 값 }
231function 값줄(이름: string, 값: float, 피벗있음: bool) -> string {
232 let 자유표시 = if 피벗있음 { "" } else { " (자유)" }
233 "{이스케이프(이름)} = {표시값(값)}{자유표시}<br>"
236function 값목록(변수들: Array<string>, 결과: 풀이) -> string {
237 let 줄들 = map(0..<변수들.length, i => 값줄(변수들[i], 결과.값들[i], 결과.피벗있음[i]))
238 "<div class=\"out\">" + 줄들.join("") + "</div>"
241// `<바탕>.x` 이고 `<바탕>.폭` 도 변수이면 바탕 이름을 돌려줍니다.
242function 상자바탕(이름: string, 변수들: Array<string>) -> Option<string> {
243 let 마디들 = 이름.split(".")
244 if 마디들.length < 2 || 마디들[마디들.length - 1] != "x" { return None }
245 let 바탕 = 마디들.slice(0, 마디들.length - 1).join(".")
246 if (바탕 + ".폭") in 변수들 { Some(바탕) } else { None }
249function 상자모으기(변수들: Array<string>, 값들: Array<float>) -> Array<상자> {
250 let mut 값맵: Map<string, float> = Map.new()
251 for i in 0..<변수들.length { 값맵.insert(변수들[i], 값들[i]) }
252 let mut 상자들: Array<상자> = []
253 for i in 0..<변수들.length {
254 match 상자바탕(변수들[i], 변수들) {
255 case Some(바탕) => 상자들.push(상자 { 이름: 바탕, x: 값들[i], 폭: 값맵.getOr(바탕 + ".폭", 0.0) })
256 case None => {}
257 }
258 }
259 상자들
262function 상자도형(대상: 상자, y: float) -> string {
263 let 테두리 = "<rect x=\"{대상.x}\" y=\"{y}\" width=\"{대상.폭}\" height=\"24\" fill=\"none\" stroke=\"#111\" />"
264 테두리 + "<text x=\"{대상.x + 4.0}\" y=\"{y + 16.0}\" font-size=\"12\" font-family=\"monospace\" fill=\"#111\">{이스케이프(대상.이름)}</text>"
267// 좌표는 표시값으로 다듬지 않은 해 그대로입니다. viewBox 너비는 가장 오른쪽 끝과 10 중 큰 값에 여백 10 을 더합니다.
268function 상자그림(변수들: Array<string>, 값들: Array<float>) -> string {
269 let 상자들 = 상자모으기(변수들, 값들)
270 if 상자들.length == 0 { return "" }
271 let 오른끝 = 상자들.map(대상 => 대상.x + 대상.폭).reduce(10.0, (최대, 끝) => Math.max(끝, 최대))
272 let 높이 = toFloat(상자들.length * 34 + 10)
273 let 도형들 = map(0..<상자들.length, 번호 => 상자도형(상자들[번호], toFloat(번호 * 34 + 8)))
274 "<svg viewBox=\"0 0 {오른끝 + 10.0} {높이}\" width=\"100%\" style=\"border:1px solid #e3e3e3;margin-top:12px\">" + 도형들.join("") + "</svg>"
277function 풀이그리기(변수들: Array<string>, 결과: 풀이) -> string {
278 match 결과.상태 {
279 case 모순 => 오류알림(모순문구)
280 case 부족 => 부족안내 + 값목록(변수들, 결과) + 상자그림(변수들, 결과.값들)
281 case 유일 => 값목록(변수들, 결과) + 상자그림(변수들, 결과.값들)
282 }
285function 레이아웃계산(입력: string) -> Result<string, string> {
286 let 방정식들 = 제약읽기(입력)?
287 if 방정식들.length == 0 { return Err(빈입력안내) }
288 let 변수들 = 변수모으기(방정식들)
289 if 변수들.length == 0 {
290 // 변수가 없으면 소거할 것이 없어 우변이 0 이 아닌 식 하나가 곧 모순입니다.
291 let 모순 = 방정식들.filter(방 => Math.abs(방.우변) > 엡실론).length > 0
292 return Ok(if 모순 { 오류알림(모순문구) } else { "<div class=\"out\">제약을 모두 만족합니다. 변수가 없습니다.</div>" })
293 }
294 Ok(풀이그리기(변수들, 풀기(방정식들, 변수들)))
297input() |> 레이아웃계산 |> 결과풀기 |> print

SHA256 bde8b27c79b188f078f4c2e671621291db23ee05a8fe24c7379b6278e2d7e6ae