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).
type 항 = { 이름: string, 계수: float }
type 한변결과 = { 이름항들: Array<항>, 상수: float }
type 방정식 = { 이름항들: Array<항>, 우변: float }
// 닫힌 풀이 상태. 변수 이름과 오류 메시지는 입력 경계라 string으로 둔다.
// Closed solution status. Variable names and error messages stay string at the input boundary.
type 풀이상태 = "유일" | "모순" | "부족"
type 풀이 = { 상태: 풀이상태, 값들: Array<float>, 열피벗: Array<bool> }
// 레코드 리터럴은 문자열 리터럴을 넓히므로 풀이 생성은 헬퍼에서 좁힌다.
// Record literals widen string literals, so solution records narrow through this helper.
function 풀이만들기(상태: 풀이상태, 값들: Array<float>, 열피벗: Array<bool>) -> 풀이 {
{ 상태: 상태, 값들: 값들, 열피벗: 열피벗 }
}
let 엡실론 = 0.000001
// 모순 판정은 더 엄격한 임계값을 쓴다. 큰 계수에서 생기는 미세한 비일관성도 잡되, 일반적인 부동소수
// 잡음(보통 1e-12 이하)에는 반응하지 않는다.
// 계수·상수를 ±10000으로 제한하므로(처리) 고정 모순 임계로 충분하다. 진짜 모순의 잔차는 약 1e-4 이상,
// float 잡음은 약 1e-12라 1e-6이 둘을 안전하게 가른다.
// Coefficients/constants are capped at +/-10000 (처리), so a fixed conflict 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 {
let mut 결과 = ""
for 글 in 원문.scalars() {
if 글 == "&" { 결과 = 결과 + "&" }
else if 글 == "<" { 결과 = 결과 + "<" }
else if 글 == ">" { 결과 = 결과 + ">" }
else if 글 == "\"" { 결과 = 결과 + """ }
else { 결과 = 결과 + 글 }
}
결과
}
// 숫자(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 토큰들 = filter(식.trim().split(" "), 토 => 토 != "")
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> = []
let mut 초기 = 0
while 초기 < 변수수 { 값들.push(0.0); 열피벗.push(false); 피벗의행.push(0); 초기 = 초기 + 1 }
let mut 피벗행 = 0
let mut 열 = 0
while 열 < 변수수 && 피벗행 < 행수 {
// 이 열에서 절댓값이 가장 큰 행을 찾는다(부분 피벗팅).
// Find the row with the largest absolute value in this column (partial pivoting).
let mut 최대행 = 피벗행
let mut 최댓값 = 절댓값(행렬[피벗행][열])
let mut 탐색 = 피벗행 + 1
while 탐색 < 행수 {
if 절댓값(행렬[탐색][열]) > 최댓값 {
최댓값 = 절댓값(행렬[탐색][열])
최대행 = 탐색
}
탐색 = 탐색 + 1
}
if 최댓값 < 엡실론 {
// 피벗 없음. 자유 열이다.
// No pivot here; this is a free column.
열 = 열 + 1
} else {
// 피벗행과 최대행의 내용을 자리별로 맞바꾼다(별칭을 피하려 원소 단위로).
// Swap pivot row and max row element by element (to avoid aliasing).
let mut 자리 = 0
while 자리 <= 변수수 {
let 임시 = 행렬[피벗행][자리]
행렬[피벗행][자리] = 행렬[최대행][자리]
행렬[최대행][자리] = 임시
자리 = 자리 + 1
}
// 피벗행을 정규화해 피벗을 1로 만든다.
// Normalize the pivot row so the pivot becomes 1.
let 피벗값 = 행렬[피벗행][열]
let mut 정규 = 0
while 정규 <= 변수수 { 행렬[피벗행][정규] = 행렬[피벗행][정규] / 피벗값; 정규 = 정규 + 1 }
// 다른 모든 행에서 이 열을 소거한다.
// Eliminate this column from every other row.
let mut 대상 = 0
while 대상 < 행수 {
if 대상 != 피벗행 {
let 배수 = 행렬[대상][열]
let mut 소거 = 0
while 소거 <= 변수수 {
행렬[대상][소거] = 행렬[대상][소거] - 배수 * 행렬[피벗행][소거]
소거 = 소거 + 1
}
}
대상 = 대상 + 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.
let mut 추출 = 0
while 추출 < 변수수 {
if 열피벗[추출] { 값들[추출] = 행렬[피벗의행[추출]][변수수] }
추출 = 추출 + 1
}
// 모순 검사: 변수 계수가 모두 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 모순임계 = 모순엡실론
let mut 모순 = false
let mut 검사행 = 0
while 검사행 < 행수 {
let mut 계수합 = 0.0
let mut 계수열 = 0
while 계수열 < 변수수 { 계수합 = 계수합 + 절댓값(행렬[검사행][계수열]); 계수열 = 계수열 + 1 }
if 계수합 < 엡실론 && 절댓값(행렬[검사행][변수수]) > 모순임계 { 모순 = true }
검사행 = 검사행 + 1
}
let mut 상태: 풀이상태 = "유일"
if 모순 { 상태 = "모순" } else if 피벗행 < 변수수 { 상태 = "부족" }
풀이만들기(상태, 값들, 열피벗)
}
// 변수 이름이 `<바탕>.x`이고 `<바탕>.폭`도 있으면 가로 상자다. 바탕 이름을 돌려준다(아니면 "").
// A variable named `<base>.x` with a matching `<base>.폭` is a horizontal box; return the base ("" otherwise).
function 상자바탕(이름: string, 변수들: Array<string>) -> string {
let 조각 = 이름.split(".")
if 조각.length < 2 { "" }
else if 조각[조각.length - 1] != "x" { "" }
else {
let 바탕 = 조각.slice(0, 조각.length - 1).join(".")
match 변수들.indexOf(바탕 + ".폭") {
case Some(_) => 바탕
case None => ""
}
}
}
function 값구하기(이름: string, 변수들: Array<string>, 값들: Array<float>) -> float {
match 변수들.indexOf(이름) {
case Some(색인) => 값들[색인]
case None => 0.0
}
}
// 풀린 상자들을 가로 막대 SVG로 그린다. 좌표는 float이고 라벨은 이스케이프한다.
// Draw the solved boxes as horizontal-bar SVG. Coordinates are floats; labels are escaped.
function 상자그림(변수들: Array<string>, 값들: Array<float>) -> string {
let mut 이름들: Array<string> = []
let mut 엑스들: Array<float> = []
let mut 폭들: Array<float> = []
let mut 최대 = 10.0
for 이름 in 변수들 {
let 바탕 = 상자바탕(이름, 변수들)
if 바탕 != "" {
let 엑스 = 값구하기(바탕 + ".x", 변수들, 값들)
let 폭 = 값구하기(바탕 + ".폭", 변수들, 값들)
이름들.push(바탕)
엑스들.push(엑스)
폭들.push(폭)
if 엑스 + 폭 > 최대 { 최대 = 엑스 + 폭 }
}
}
if 이름들.length == 0 { "" }
else {
let 높이 = toFloat(이름들.length * 34 + 10)
let mut 본문 = ""
let mut 번호 = 0
while 번호 < 이름들.length {
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>"
번호 = 번호 + 1
}
"<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\">"
let mut 번호 = 0
while 번호 < 변수들.length {
let 표시 = if 결과.열피벗[번호] { "" } else { " (자유)" }
목록 = 목록 + "{이스케이프(변수들[번호])} = {표시값(결과.값들[번호])}{표시}<br>"
번호 = 번호 + 1
}
목록 + "</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 {
let mut 결과 = ""
for 글 in 줄.scalars() {
if 글 == "+" || 글 == "-" || 글 == "*" || 글 == "=" {
결과 = 결과 + " " + 글 + " "
} else {
결과 = 결과 + 글
}
}
결과
}
function 처리(입력: string) -> string {
let 줄들 = 입력.split("\n")
let mut 변수들: Array<string> = []
let mut 방정식들: Array<방정식> = []
let mut 줄번호 = 0
while 줄번호 < 줄들.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 합이름: Array<string> = []
let mut 합값: Array<float> = []
for 항 in 항모음 {
match 합이름.indexOf(항.이름) {
case Some(찾음) => { 합값[찾음] = 합값[찾음] + 항.계수 }
case None => { 합이름.push(항.이름); 합값.push(항.계수) }
}
}
let mut 너무큼 = 절댓값(그우변) > 10000.0
for 값 in 합값 { if 절댓값(값) > 10000.0 { 너무큼 = true } }
if 너무큼 {
return "<div class=\"err\">{표시줄}번째 줄: 계수와 상수는 ±10000 이내여야 합니다.</div>"
}
for 항 in 항모음 {
match 변수들.indexOf(항.이름) {
case Some(_) => {}
case None => { 변수들.push(항.이름) }
}
}
방정식들.push({ 이름항들: 항모음, 우변: 그우변 })
}
}
}
}
}
줄번호 = 줄번호 + 1
}
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 mut 상수모순 = false
for 방 in 방정식들 { if 절댓값(방.우변) > 엡실론 { 상수모순 = true } }
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 행렬: Array<Array<float>> = []
for 방 in 방정식들 {
let mut 행: Array<float> = []
let mut 칸 = 0
while 칸 <= 변수수 { 행.push(0.0); 칸 = 칸 + 1 }
for 항 in 방.이름항들 {
match 변수들.indexOf(항.이름) {
case Some(색인) => { 행[색인] = 행[색인] + 항.계수 }
case None => {}
}
}
행[변수수] = 방.우변
행렬.push(행)
}
렌더(변수들, 풀기(행렬, 변수수))
}
}
print(처리(input()))