layout.tpz
// 제약 기반 레이아웃 솔버. 한 줄에 선형 등식 하나(좌변 = 우변)를 받아 가우스-조던 소거로 푼다.
// Constraint layout solver. One linear equation per line (left = right); solved by Gauss-Jordan.
// Key identifiers: 항=term, 이름=name, 계수=coeff, 한변결과=sideResult, 이름항들=nameTerms,
// 상수=constant, 방정식=equation, 우변=rhs, 변수들=variables, 행렬=matrix, 행=row, 값들=values,
// 열피벗=isPivotColumn, 피벗의행=pivotRowOfColumn, 상태=status, 풀이=solution, 절댓값=abs,
// 이스케이프=escape, 유효변수=isValidName, 변수글/숫자글=isNameChar/isDigit, 한변파싱=parseSide,
// 풀기=solve, 렌더=render, 상자그림=boxSVG, 폭=width, 칸=cell, 번호=index, 세로=y
//
// 결정적이다. 같은 제약이면 인터프리터와 네이티브/wasm 빌드에서 같은 해와 같은 SVG가 나온다.
// Deterministic. Same constraints yield the same solution and SVG across interpreter and builds.
// 안 하는 것: 부등식, Cassowary 강도/편집 변수, 2차원 자동 배치.
// Won't do: inequalities, Cassowary strengths/edit-vars, 2D auto-layout.
// float 계산은 새 toFloat(int)->float 빌트인을 쓴다(이 앱이 견인한 기능).
// Float math uses the new toFloat(int)->float builtin (the compiler feature this app drove).
record 항 { 이름: string, 계수: float }
record 한변결과 { 이름항들: Array<항>, 상수: float }
record 방정식 { 이름항들: Array<항>, 우변: float }
// 닫힌 풀이 상태. 변수 이름과 오류 메시지는 입력 경계라 string으로 둔다.
// Closed solution status. Variable names and error messages stay string at the input boundary.
enum 풀이상태 { 유일, 모순, 부족 }
record 풀이 { 상태: 풀이상태, 값들: Array<float>, 열피벗: Array<bool> }
let 엡실론 = 0.000001
// 모순 판정 임계값. 엡실론과 값은 같지만 다른 질문에 답한다. 엡실론은 계수가 사실상 0인지 보고,
// 모순엡실론은 잔차가 진짜 모순인지 본다. 계수·상수를 ±10000으로 제한하므로(처리) 고정 임계로
// 충분하다. 진짜 모순의 잔차는 약 1e-4 이상, float 잡음은 약 1e-12라 1e-6이 둘을 안전하게 가른다.
// Conflict threshold. Same value as 엡실론 but a different question: 엡실론 tests whether a coefficient
// is effectively zero, 모순엡실론 tests whether a residual is a real contradiction. Coefficients and
// constants are capped at +/-10000 (처리), so a fixed threshold suffices: a real contradiction's
// residual is >= ~1e-4 and float noise is ~1e-12, so 1e-6 separates them.
let 모순엡실론 = 0.000001
// 절댓값. 수학 stdlib가 없어 비교로 구한다.
// Absolute value. No math stdlib, so derive it by comparison.
function 절댓값(값: float) -> float {
if 값 < 0.0 { -값 } else { 값 }
}
// 표시용 값. 음의 0 같은 미세 값을 0으로 정리한다.
// Display value: clean up tiny values such as negative zero to 0.
function 표시값(값: float) -> float {
if 절댓값(값) < 엡실론 { 0.0 } else { 값 }
}
// HTML 이스케이프. 변수 이름과 오류 메시지는 사용자 입력이라 출력 전에 반드시 이스케이프한다.
// HTML escape. Variable names and error text are user input, so always escape before output.
function 이스케이프(원문: string) -> string {
// &를 먼저 치환한다. 나중 치환이 넣는 &가 다시 이스케이프되지 않도록.
// Replace & first so the & introduced by later escapes is not double-escaped.
원문.replace("&", "&").replace("<", "<").replace(">", ">").replace("\"", """)
}
// 숫자(0~9) 글자인가.
// Is the scalar an ASCII digit (0-9)?
function 숫자글(글: string) -> bool {
let 코드 = 글.codePointAt(0) ?? 0
코드 >= 48 && 코드 <= 57
}
// 변수 이름에 쓸 수 있는 글자인가: 영문/숫자/밑줄/점, 또는 한글(음절·자모).
// Is the scalar allowed in a variable name: ASCII letter/digit/_/. or Hangul (syllable/jamo)?
function 변수글(글: string) -> bool {
let 코드 = 글.codePointAt(0) ?? 0
(코드 >= 48 && 코드 <= 57) || (코드 >= 65 && 코드 <= 90) || (코드 >= 97 && 코드 <= 122)
|| 코드 == 95 || 코드 == 46
|| (코드 >= 44032 && 코드 <= 55203) || (코드 >= 4352 && 코드 <= 4607)
|| (코드 >= 12592 && 코드 <= 12687)
}
// 유효한 변수 이름인가. 정수가 아니고, 숫자로 시작하지 않으며, 허용 글자만으로 이뤄져야 한다.
// Is this a valid variable name: not an integer, not digit-led, only allowed characters.
function 유효변수(토: string) -> bool {
if 토 == "" { return false }
match toInt(토) {
case Some(_) => { return false }
case None => {}
}
let 글자들 = 토.scalars()
if 숫자글(글자들[0]) { return false }
for 글 in 글자들 {
if !변수글(글) { return false }
}
true
}
// 한 변(좌변 또는 우변)을 파싱한다. 모든 항에 기본부호를 곱해 이름별 계수와 상수를 모은다.
// Parse one side; multiply every term by the base sign, collecting name-keyed coeffs and a constant.
// 토큰은 공백으로 구분한다. 항은 정수, 변수, 또는 `정수 * 변수`이고 +/-로 잇는다. 잘못된 입력은 Err.
// Tokens are space-separated. A term is an integer, a variable, or `int * var`, joined by +/-. Bad input -> Err.
function 한변파싱(식: string, 기본부호: float) -> Result<한변결과, string> {
let 토큰들 = 식.trim().split(" ").filter(토 => 토 != "")
if 토큰들.length == 0 { return Err("빈 식입니다") }
let mut 이름항들: Array<항> = []
let mut 상수 = 0.0
let mut 부호 = 기본부호
let mut 위치 = 0
// 부호 뒤에 항이 와야 한다. +/-를 만나면 켜고, 항을 만나면 끈다. 끝에 켜져 있으면 매달린 부호다.
// A sign must be followed by a term. Set on +/-, clear on a term; if still set at the end it dangles.
let mut 부호대기 = false
while 위치 < 토큰들.length {
let 토 = 토큰들[위치]
if 토 == "+" {
if 부호대기 { return Err("부호가 연달아 올 수 없습니다") }
부호 = 기본부호
부호대기 = true
위치 = 위치 + 1
} else if 토 == "-" {
if 부호대기 { return Err("부호가 연달아 올 수 없습니다") }
부호 = -기본부호
부호대기 = true
위치 = 위치 + 1
} else if 토 == "*" {
return Err("'*'의 위치가 잘못되었습니다")
} else {
match toInt(토) {
case Some(수) => {
// 정수다. 다음 토큰이 *이면 계수*변수, 아니면 상수.
// An integer. If the next token is *, it is coeff*var, otherwise a constant.
if 위치 + 1 < 토큰들.length && 토큰들[위치 + 1] == "*" {
if 위치 + 2 < 토큰들.length && 유효변수(토큰들[위치 + 2]) {
이름항들.push(항 { 이름: 토큰들[위치 + 2], 계수: 부호 * toFloat(수) })
위치 = 위치 + 3
} else {
return Err("'*' 뒤에 변수가 필요합니다")
}
} else {
상수 += 부호 * toFloat(수)
위치 = 위치 + 1
}
}
case None => {
// 변수다(계수 1). 유효하지 않은 토큰이면 오류.
// A variable (coefficient 1). An invalid token is an error.
if 유효변수(토) {
이름항들.push(항 { 이름: 토, 계수: 부호 })
위치 = 위치 + 1
} else {
return Err("알 수 없는 토큰: '" + 토 + "'")
}
}
}
부호 = 기본부호
부호대기 = false
}
}
if 부호대기 {
return Err("부호 뒤에 항이 필요합니다")
}
Ok(한변결과 { 이름항들: 이름항들, 상수: 상수 })
}
// 가우스-조던 소거. 부분 피벗팅으로 안정화하고 상태를 분류한다.
// Gauss-Jordan elimination with partial pivoting; classifies the system.
function 풀기(행렬입력: Array<Array<float>>, 변수수: int) -> 풀이 {
let mut 행렬 = 행렬입력
let 행수 = 행렬.length
let mut 값들: Array<float> = []
let mut 열피벗: Array<bool> = []
let mut 피벗의행: Array<int> = []
for 초기 in 0..<변수수 { 값들.push(0.0); 열피벗.push(false); 피벗의행.push(0) }
let mut 피벗행 = 0
let mut 열 = 0
while 열 < 변수수 && 피벗행 < 행수 {
// 이 열에서 절댓값이 가장 큰 행을 찾는다(부분 피벗팅).
// Find the row with the largest absolute value in this column (partial pivoting).
let mut 최대행 = 피벗행
let mut 최댓값 = 절댓값(행렬[피벗행][열])
for 탐색 in (피벗행 + 1)..<행수 {
if 절댓값(행렬[탐색][열]) > 최댓값 {
최댓값 = 절댓값(행렬[탐색][열])
최대행 = 탐색
}
}
if 최댓값 < 엡실론 {
// 피벗 없음. 자유 열이다.
// No pivot here; this is a free column.
열 = 열 + 1
} else {
// 피벗행과 최대행의 내용을 자리별로 맞바꾼다(별칭을 피하려 원소 단위로).
// Swap pivot row and max row element by element (to avoid aliasing).
for 자리 in 0..<(변수수 + 1) {
let 임시 = 행렬[피벗행][자리]
행렬[피벗행][자리] = 행렬[최대행][자리]
행렬[최대행][자리] = 임시
}
// 피벗행을 정규화해 피벗을 1로 만든다.
// Normalize the pivot row so the pivot becomes 1.
let 피벗값 = 행렬[피벗행][열]
for 정규 in 0..<(변수수 + 1) { 행렬[피벗행][정규] /= 피벗값 }
// 다른 모든 행에서 이 열을 소거한다.
// Eliminate this column from every other row.
for 대상 in 0..<행수 {
if 대상 != 피벗행 {
let 배수 = 행렬[대상][열]
for 소거 in 0..<(변수수 + 1) {
행렬[대상][소거] -= 배수 * 행렬[피벗행][소거]
}
}
}
열피벗[열] = true
피벗의행[열] = 피벗행
피벗행 = 피벗행 + 1
열 = 열 + 1
}
}
// 피벗 변수 값은 완전 소거(RREF)가 끝난 뒤에 해당 행의 우변에서 읽는다(중간에 읽으면 이후 소거로
// 값이 바뀐다). 자유 변수는 0으로 둔다.
// Read each pivot variable's value from its row's RHS only AFTER full RREF (reading mid-way is
// stale because later elimination updates earlier rows). Free variables stay 0.
for 추출 in 0..<변수수 {
if 열피벗[추출] { 값들[추출] = 행렬[피벗의행[추출]][변수수] }
}
// 모순 검사: 변수 계수가 모두 0인데 우변이 0이 아닌 행. 계수·상수를 ±10000으로 제한했으므로(처리에서
// 거름) 고정 임계로 충분하다. 진짜 모순의 잔차(>= 약 1e-4)는 잡고 float 잡음(약 1e-12)은 무시한다.
// Conflict check: a row whose variable coeffs are all ~0 but whose RHS is not. Coefficients and
// constants are capped at +/-10000 (rejected in 처리), so a fixed threshold suffices: a real
// contradiction's residual (>= ~1e-4) is caught while float noise (~1e-12) is ignored.
let mut 모순 = false
for 검사행 in 0..<행수 {
let mut 계수합 = 0.0
for 계수열 in 0..<변수수 { 계수합 += 절댓값(행렬[검사행][계수열]) }
if 계수합 < 엡실론 && 절댓값(행렬[검사행][변수수]) > 모순엡실론 { 모순 = true }
}
let 상태: 풀이상태 = if 모순 { 풀이상태.모순 } else if 피벗행 < 변수수 { 풀이상태.부족 } else { 풀이상태.유일 }
풀이 { 상태: 상태, 값들: 값들, 열피벗: 열피벗 }
}
// 변수 이름이 `<바탕>.x`이고 `<바탕>.폭`도 있으면 가로 상자다. 바탕 이름을 Some으로 돌려준다(아니면 None).
// A variable named `<base>.x` with a matching `<base>.폭` is a horizontal box; return Some(base) (None otherwise).
function 상자바탕(이름: string, 변수들: Array<string>) -> Option<string> {
let 조각 = 이름.split(".")
if 조각.length < 2 { None }
else if 조각[조각.length - 1] != "x" { None }
else {
let 바탕 = 조각.slice(0, 조각.length - 1).join(".")
if (바탕 + ".폭") in 변수들 { Some(바탕) } else { None }
}
}
// 배치된 상자 하나: 바탕 이름과 그 x·폭. 병렬 배열 대신 이름 있는 레코드로 모은다.
// One laid-out box: its base name and x/width, collected as a named record instead of parallel arrays.
record 상자 { 이름: string, 엑스: float, 폭: float }
// 풀린 상자들을 가로 막대 SVG로 그린다. 좌표는 float이고 라벨은 이스케이프한다.
// Draw the solved boxes as horizontal-bar SVG. Coordinates are floats; labels are escaped.
function 상자그림(변수들: Array<string>, 값들: Array<float>) -> string {
let mut 값맵: Map<string, float> = Map.new()
for 이 in 0..<변수들.length { 값맵.insert(변수들[이], 값들[이]) }
let mut 상자들: Array<상자> = []
for 이름 in 변수들 {
match 상자바탕(이름, 변수들) {
case Some(바탕) => {
상자들.push(상자 {
이름: 바탕,
엑스: 값맵.getOr(바탕 + ".x", 0.0),
폭: 값맵.getOr(바탕 + ".폭", 0.0),
})
}
case None => {}
}
}
if 상자들.length == 0 { "" }
else {
// viewBox 너비는 가장 오른쪽 상자 끝과 최소 10.0 중 큰 값이다.
// The viewBox width is the larger of the rightmost box edge and a 10.0 floor.
let 최대 = 상자들.map(상 => 상.엑스 + 상.폭).reduce(10.0, (현재최대, 오른끝) => if 오른끝 > 현재최대 { 오른끝 } else { 현재최대 })
let 높이 = toFloat(상자들.length * 34 + 10)
let mut 본문 = ""
// y 좌표는 위치 기반이라 색인 루프를 유지한다(범위에는 .map이 없다).
// The y coordinate is positional, so keep the index loop (ranges have no .map).
for 번호 in 0..<상자들.length {
let 상 = 상자들[번호]
let 세로 = toFloat(번호 * 34 + 8)
본문 += "<rect x=\"{상.엑스}\" y=\"{세로}\" width=\"{상.폭}\" height=\"24\" fill=\"none\" stroke=\"#111\" />"
본문 += "<text x=\"{상.엑스 + 4.0}\" y=\"{세로 + 16.0}\" font-size=\"12\" font-family=\"monospace\" fill=\"#111\">{이스케이프(상.이름)}</text>"
}
"<svg viewBox=\"0 0 {최대 + 10.0} {높이}\" width=\"100%\" style=\"border:1px solid #e3e3e3;margin-top:12px\">" + 본문 + "</svg>"
}
}
function 렌더(변수들: Array<string>, 결과: 풀이) -> string {
match 결과.상태 {
case 모순 => "<div class=\"err\">모순된 제약입니다. 해가 없습니다.</div>"
case 부족 => {
let 목록 = 변수목록(변수들, 결과)
let 그림 = 상자그림(변수들, 결과.값들)
"<div class=\"bad\">제약이 부족합니다. 자유 변수는 0으로 둔 한 가지 해입니다.</div>" + 목록 + 그림
}
case 유일 => {
let 목록 = 변수목록(변수들, 결과)
let 그림 = 상자그림(변수들, 결과.값들)
목록 + 그림
}
}
}
// 변수별 값(자유 변수는 0으로 둔 한 가지 해).
// Per-variable values (free variables fixed at 0 for one particular solution).
function 변수목록(변수들: Array<string>, 결과: 풀이) -> string {
let mut 목록 = "<div class=\"out\">"
for 번호 in 0..<변수들.length {
let 표시 = if 결과.열피벗[번호] { "" } else { " (자유)" }
목록 += "{이스케이프(변수들[번호])} = {표시값(결과.값들[번호])}{표시}<br>"
}
목록 + "</div>"
}
// 연산자(+ - * =) 둘레에 공백을 넣어 빽빽한 입력(x+y=3)도 띄어쓴 입력처럼 토큰화되게 한다.
// 변수 이름의 점(.)은 연산자가 아니라 건드리지 않는다.
// Pad operators (+ - * =) with spaces so compact input (x+y=3) tokenizes like spaced input.
// The dot (.) inside variable names is not an operator and is left untouched.
function 띄우기(줄: string) -> string {
줄.replace("+", " + ").replace("-", " - ").replace("*", " * ").replace("=", " = ")
}
function 처리(입력: string) -> string {
let 줄들 = 입력.split("\n")
let mut 변수들: Array<string> = []
let mut 방정식들: Array<방정식> = []
for 줄번호 in 0..<줄들.length {
let 다듬 = 줄들[줄번호].trim()
let 표시줄 = 줄번호 + 1
if 다듬 != "" && !다듬.startsWith("#") {
let 부분 = 띄우기(다듬).split("=")
if 부분.length != 2 {
return "<div class=\"err\">{표시줄}번째 줄: 등호(=)가 정확히 하나여야 합니다.</div>"
}
match 한변파싱(부분[0], 1.0) {
case Err(메시지) => { return "<div class=\"err\">{표시줄}번째 줄: {이스케이프(메시지)}</div>" }
case Ok(좌) => {
match 한변파싱(부분[1], -1.0) {
case Err(메시지) => { return "<div class=\"err\">{표시줄}번째 줄: {이스케이프(메시지)}</div>" }
case Ok(우) => {
// 좌변 - 우변 = 0 으로 합친다. 상수는 우변으로 옮긴다.
// Combine as left - right = 0; the constant moves to the RHS.
let mut 항모음: Array<항> = []
for 항 in 좌.이름항들 { 항모음.push(항) }
for 항 in 우.이름항들 { 항모음.push(항) }
// 계수·상수를 ±10000으로 제한한다. 이 범위 밖은 float 정밀도가 보장되지 않아
// 잘못 계산하느니 거절한다(문서화된 MVP 경계).
// Cap coefficients and constants at +/-10000. Beyond it float precision is not
// guaranteed, so reject rather than miscompute (a documented MVP boundary).
let 그우변 = -(좌.상수 + 우.상수)
// 같은 변수의 계수는 합산되므로(예: 10000*x + x = 10001*x) 합산한 뒤의 계수를 캡한다.
// Coefficients for the same variable are summed, so cap the AGGREGATED coefficient.
let mut 합: Map<string, float> = Map.new()
for 항 in 항모음 { 합.insert(항.이름, 합.getOr(항.이름, 0.0) + 항.계수) }
let 너무큼 = 합.keys.reduce(절댓값(그우변) > 10000.0, (누적, 이름) => 누적 || 절댓값(합.getOr(이름, 0.0)) > 10000.0)
if 너무큼 {
return "<div class=\"err\">{표시줄}번째 줄: 계수와 상수는 ±10000 이내여야 합니다.</div>"
}
for 항 in 항모음 {
if !(항.이름 in 변수들) { 변수들.push(항.이름) }
}
방정식들.push(방정식 { 이름항들: 항모음, 우변: 그우변 })
}
}
}
}
}
}
if 방정식들.length == 0 {
"<div class=\"meta\">제약(예: 상자1.x = 0)을 한 줄에 하나씩 입력하세요.</div>"
} else if 변수들.length == 0 {
// 변수 없는 상수 방정식들: 우변이 0이 아니면 모순(예: 0 = 1).
// Constant-only equations: a non-zero RHS is a contradiction (e.g. 0 = 1).
let 상수모순 = 방정식들.reduce(false, (누적, 방) => 누적 || 절댓값(방.우변) > 엡실론)
if 상수모순 {
"<div class=\"err\">모순된 제약입니다. 해가 없습니다.</div>"
} else {
"<div class=\"out\">제약을 모두 만족합니다. 변수가 없습니다.</div>"
}
} else {
// 밀집 행렬을 만든다: 행 = 방정식, 너비 = 변수수 + 1(우변).
// Build the dense matrix: rows = equations, width = variables + 1 (RHS).
let 변수수 = 변수들.length
let mut 이름색인: Map<string, int> = Map.new()
for 이 in 0..<변수들.length { 이름색인.insert(변수들[이], 이) }
let mut 행렬: Array<Array<float>> = []
for 방 in 방정식들 {
let mut 행: Array<float> = []
for 칸 in 0..<(변수수 + 1) { 행.push(0.0) }
for 항 in 방.이름항들 {
match 이름색인.get(항.이름) {
case Some(색인) => { 행[색인] += 항.계수 }
case None => {}
}
}
행[변수수] = 방.우변
행렬.push(행)
}
렌더(변수들, 풀기(행렬, 변수수))
}
}
input() |> 처리 |> print