import Mathlib /-! # Text Justification Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left-justified, and no extra space is inserted between words. Note: A word is defined as a character sequence consisting of non-space characters only. Each word's length is guaranteed to be greater than 0 and not exceed maxWidth. The input array words contains at least one word. ## Constraints - 1 <= words.length <= 300 - 1 <= words[i].length <= 20 - words[i] consists of only English letters and symbols. - 1 <= maxWidth <= 100 - words[i].length <= maxWidth ## Provided examples - `words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16` → `["This is an", "example of text", "justification. "]` - `words = ["What", "must", "be", "acknowledgment", "shall", "be"], maxWidth = 16` → `["What must be", "acknowledgment ", "shall be "]` - `words = ["LongWord1234567890", "Short", "AnotherLongWord1234567", "Tiny", "Word"], maxWidth = 25` → `["LongWord1234567890 Short", "AnotherLongWord1234567 ", "Tiny Word "]` ## Synthesized negative examples - invalid input: `words = [], maxWidth = 16` ([structural] a predicate that admits 1 <= words.length <= 300. empty array below the word-list floor) - invalid input: `words = [""], maxWidth = 100` ([structural] a predicate that admits 1 <= words[i].length <= 20. zero-length word; a length- and width-checking predicate accepts it) - invalid input: `words = ["hello"], maxWidth = 4` ([structural] a predicate that admits words[i].length <= maxWidth. word length exceeds the given maxWidth; parameter-wise checking accepts it) - `words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16` → `["This is an", "example of text", "justification."]` is wrong ([structural] line lengths are not required to reach maxWidth. text is left just without padding to width) - `words = ["What", "must", "be", "acknowledgment", "shall", "be"], maxWidth = 16` → `["What must be", "acknowledgment ", "shall be "]` is wrong ([structural] line width one less than maxWidth is accepted. last line has 15 chars instead of 16) - `words = ["LongWord1234567890", "Short", "AnotherLongWord1234567", "Tiny", "Word"], maxWidth = 25` → `["LongWord1234567890 Short", "AnotherLongWord1234567 ", "Tiny Word "]` is wrong ([structural] line width is accepted as maxWidth+1 instead of maxWidth. Every line is one character too wide; only maxWidth is broken.) -/ namespace PTextJustification abbrev Input := (List String) × (Nat) abbrev Output := List String /-! ### Specification helpers -/ /-- The line is the block's words in order, with `gaps` spaces between adjacent words and `t` trailing spaces. -/ def isBuiltFromGaps (block : List String) (gaps : List Nat) (t : Nat) (line : String) : Prop := gaps.length + 1 = block.length ∧ (∀ g ∈ gaps, 1 ≤ g) ∧ line = String.join (List.zipWith (fun w g => w ++ String.mk (List.replicate g ' ')) block (gaps ++ [0])) ++ String.mk (List.replicate t ' ') /-- The least width a line holding the block can have: word lengths plus one space between adjacent words. -/ def minLineWidth (block : List String) : Nat := (block.map String.length).sum + (block.length - 1) /-- The line has length exactly `width` and is the nonempty block's words in order, separated by positive gaps of spaces, with possible trailing spaces. -/ def IsLineOfWords (block : List String) (width : Nat) (line : String) : Prop := block ≠ [] ∧ line.length = width ∧ ∃ gaps : List Nat, ∃ t : Nat, isBuiltFromGaps block gaps t line /-- The gaps obey the distribution rule: non-last lines differ by at most one with longer gaps first and no trailing spaces (a one-word line is left-justified); last lines use single gaps and pad on the right. -/ def IsEvenlyJustified (block : List String) (width : Nat) (isLast : Bool) (line : String) : Prop := ∃ gaps : List Nat, ∃ t : Nat, isBuiltFromGaps block gaps t line ∧ if isLast then ∀ g ∈ gaps, g = 1 else (gaps = [] ∨ t = 0) ∧ (∃ g : Nat, ∀ x ∈ gaps, x = g ∨ x = g + 1) ∧ gaps.Pairwise (· ≥ ·) /-- `blocks` is a contiguous partition of `words` into nonempty blocks that each fit on a line, and no block can absorb the next block's first word. -/ def IsGreedySegmentation (words : List String) (width : Nat) (blocks : List (List String)) : Prop := blocks.flatten = words ∧ (∀ b ∈ blocks, b ≠ []) ∧ (∀ b ∈ blocks, minLineWidth b ≤ width) ∧ List.Chain' (fun b b' => ∀ h : b' ≠ [], width < minLineWidth (b ++ [b'.head h])) blocks /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 300 nonempty words of printable non-space ASCII, each at most `maxWidth` long, with `1 ≤ maxWidth ≤ 100`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 300 && input.1.all (fun w => 1 ≤ w.length && w.length ≤ input.2 && w.toList.all (fun c => '!' ≤ c && c ≤ '~')) && 1 ≤ input.2 && input.2 ≤ 100 /-! ### Ideal specification (P_spec) -/ /-- `result` justifies `input`: some contiguous partition of the words into nonempty blocks has `result` as exactly its lines at width `input.2`, is greedy, and has every line evenly justified but the last, which is left-justified. -/ def justifyText_spec (input : Input) (result : Output) : Prop := ∃ blocks : List (List String), blocks.flatten = input.1 ∧ (∀ b ∈ blocks, b ≠ []) ∧ List.Forall₂ (fun b l => IsLineOfWords b input.2 l) blocks result ∧ IsGreedySegmentation input.1 input.2 blocks ∧ ∀ k : Nat, ∀ hk : k < result.length, ∀ hk' : k < blocks.length, IsEvenlyJustified blocks[k] input.2 (decide (k + 1 = blocks.length)) result[k] /-! ### Decidable specification (P_check) -/ /-- One Boolean for each gap between adjacent words, selecting where a line break occurs. -/ abbrev PartitionCode (words : List String) : Type := Fin (words.length - 1) → Bool /-- The adjacent pairs of elements in a list. -/ def consecutivePairs {α : Type} : List α → List (α × α) | a :: b :: xs => (a, b) :: consecutivePairs (b :: xs) | _ => [] /-- The block boundaries selected by the cut code, including both ends of the word list. -/ def cutPositions (words : List String) (cuts : PartitionCode words) : List Nat := (0 :: ((List.finRange (words.length - 1)).filterMap fun i => if cuts i then some (i.val + 1) else none)) ++ [words.length] /-- The contiguous partition of the words selected by the cut code. -/ def blocksOfCode (words : List String) (cuts : PartitionCode words) : List (List String) := if words.length = 0 then [] else (consecutivePairs (cutPositions words cuts)).map fun bounds => (words.drop bounds.1).take (bounds.2 - bounds.1) /-- A string consisting of the given number of spaces. -/ def spaces (n : Nat) : String := String.mk (List.replicate n ' ') /-- The line built from a block with the given internal gaps and trailing spaces. -/ def buildLine (block : List String) (gaps : List Nat) (trailing : Nat) : String := (String.join (List.zipWith (fun word gap => word ++ spaces gap) block (gaps ++ [0]))) ++ spaces trailing /-- The forced internal gaps of an evenly justified multi-word non-last line. -/ def evenlySpacedGaps (block : List String) (width : Nat) : List Nat := let gapCount := block.length - 1 let room := width - (block.map String.length).sum if gapCount = 0 then [] else List.replicate (room % gapCount) (room / gapCount + 1) ++ List.replicate (gapCount - room % gapCount) (room / gapCount) /-- The unique line determined by a block, the width, and whether the block is last. -/ def specifiedLine (block : List String) (width : Nat) (isLast : Bool) : String := let gaps := if isLast then List.replicate (block.length - 1) 1 else evenlySpacedGaps block width let trailing := if isLast then width - minLineWidth block else if block.length = 1 then width - (block.map String.length).sum else 0 buildLine block gaps trailing /-- The lines determined by all blocks, with only the final block left-justified. -/ def specifiedLines (width : Nat) : List (List String) → List String | [] => [] | [block] => [specifiedLine block width true] | block :: next :: rest => specifiedLine block width false :: specifiedLines width (next :: rest) /-- Executable form of the contiguous, fitting, greedy block conditions. -/ def greedySegmentationCheck (words : List String) (width : Nat) (blocks : List (List String)) : Bool := decide (blocks.flatten = words) && blocks.all (fun block => decide (block ≠ [])) && blocks.all (fun block => decide (minLineWidth block ≤ width)) && (consecutivePairs blocks).all (fun pair => match pair.2 with | [] => true | word :: _ => decide (width < minLineWidth (pair.1 ++ [word]))) /-- Whether a decoded partition witnesses the specification for the candidate output. -/ def partitionAccepted (input : Input) (result : Output) (blocks : List (List String)) : Bool := decide (blocks.flatten = input.1) && blocks.all (fun block => decide (block ≠ [])) && decide (result = specifiedLines input.2 blocks) && greedySegmentationCheck input.1 input.2 blocks /-- Executable checker for `justifyText_spec` over the finite cut codes. -/ def justifyText_check (input : Input) (result : Output) : Bool := decide (∃ code : PartitionCode input.1, partitionAccepted input result (blocksOfCode input.1 code) = true) theorem valid_len (words : List String) (width : Nat) (h : isValidInput (words, width) = true) : 1 ≤ words.length := by cases words with | nil => simp [isValidInput] at h | cons a t => simp theorem check_eq (words : List String) (width : Nat) (result : List String) : justifyText_check (words, width) result = decide (∃ code : PartitionCode words, partitionAccepted (words, width) result (blocksOfCode words code) = true) := rfl theorem spec_eq (words : List String) (width : Nat) (result : List String) : justifyText_spec (words, width) result ↔ ∃ blocks : List (List String), blocks.flatten = words ∧ (∀ b ∈ blocks, b ≠ []) ∧ List.Forall₂ (fun b l => IsLineOfWords b width l) blocks result ∧ IsGreedySegmentation words width blocks ∧ ∀ k : Nat, ∀ hk : k < result.length, ∀ hk' : k < blocks.length, IsEvenlyJustified blocks[k] width (decide (k + 1 = blocks.length)) result[k] := Iff.rfl /-- Blocks cut out of `xs` at ascending boundary positions, starting at `a`. -/ def blocksOf (xs : List String) : Nat → List Nat → List (List String) | _, [] => [] | a, p :: ps => (xs.drop a).take (p - a) :: blocksOf xs p ps /-- The interior boundary positions of a block decomposition starting at `a`. -/ def interiorOf : Nat → List (List String) → List Nat | _, [] => [] | a, b :: t => if t.isEmpty then [] else (a + b.length) :: interiorOf (a + b.length) t theorem blocksOf_nil (xs : List String) (a : Nat) : blocksOf xs a [] = [] := rfl theorem interiorOf_nil (a : Nat) : interiorOf a [] = [] := rfl theorem blocksOf_cons (xs : List String) (a p : Nat) (ps : List Nat) : blocksOf xs a (p :: ps) = (xs.drop a).take (p - a) :: blocksOf xs p ps := rfl theorem interiorOf_single (a : Nat) (b : List String) : interiorOf a [b] = [] := rfl theorem interiorOf_cons (a : Nat) (b c : List String) (t : List (List String)) : interiorOf a (b :: c :: t) = (a + b.length) :: interiorOf (a + b.length) (c :: t) := rfl theorem decode_blocksOf (xs : List String) (a : Nat) (ps : List Nat) : (consecutivePairs (a :: ps)).map (fun bounds => (xs.drop bounds.1).take (bounds.2 - bounds.1)) = blocksOf xs a ps := by induction ps generalizing a with | nil => rfl | cons p ps ih => simp [consecutivePairs, blocksOf_cons, ih] theorem blocksOf_interiorOf (xs : List String) : ∀ (bs : List (List String)) (a : Nat), bs ≠ [] → xs.drop a = bs.flatten → blocksOf xs a (interiorOf a bs ++ [a + bs.flatten.length]) = bs := by intro bs induction bs with | nil => intro a hne _; exact absurd rfl hne | cons b t ih => intro a _ hd have hslice : (xs.drop a).take (a + b.length - a) = b := by rw [hd, List.flatten_cons] exact List.take_left' (by omega) cases t with | nil => rw [interiorOf_single, List.nil_append, blocksOf_cons, blocksOf_nil] rw [show (([b] : List (List String)).flatten).length = b.length by simp] rw [hslice] | cons c t' => have hlen : a + ((b :: c :: t').flatten).length = (a + b.length) + ((c :: t').flatten).length := by simp [List.flatten_cons] omega rw [interiorOf_cons, List.cons_append, blocksOf_cons, hslice, hlen] have hd2 : xs.drop (a + b.length) = (c :: t').flatten := by rw [← List.drop_drop, hd, List.flatten_cons] exact List.drop_left' rfl rw [ih (a + b.length) (by simp) hd2] theorem interiorOf_props : ∀ (bs : List (List String)) (a : Nat), (∀ b ∈ bs, b ≠ []) → (∀ p ∈ interiorOf a bs, a < p ∧ p < a + bs.flatten.length) ∧ List.Pairwise (· < ·) (interiorOf a bs) := by intro bs induction bs with | nil => intro a _; rw [interiorOf_nil]; exact ⟨by simp, List.Pairwise.nil⟩ | cons b t ih => intro a hne cases t with | nil => rw [interiorOf_single]; exact ⟨by simp, List.Pairwise.nil⟩ | cons c t' => have hb : 0 < b.length := List.length_pos_iff.mpr (hne b (by simp)) have hc : 0 < c.length := List.length_pos_iff.mpr (hne c (by simp)) obtain ⟨ihb, ihp⟩ := ih (a + b.length) (fun x hx => hne x (by simp [hx])) have hfl : ((b :: c :: t').flatten).length = b.length + ((c :: t').flatten).length := by simp [List.flatten_cons] have hcl : c.length ≤ ((c :: t').flatten).length := by simp [List.flatten_cons] rw [interiorOf_cons] constructor · intro p hpm rcases List.mem_cons.mp hpm with h1 | h1 · subst h1; rw [hfl]; omega · have := ihb p h1 rw [hfl]; omega · rw [List.pairwise_cons] exact ⟨fun p hpm => (ihb p hpm).1, ihp⟩ theorem finRange_map_val (m : Nat) : (List.finRange m).map Fin.val = List.range m := by apply List.ext_getElem <;> simp theorem finRange_filterMap (m : Nat) (p : Nat → Bool) : (List.finRange m).filterMap (fun i : Fin m => if p i.val then some (i.val + 1) else none) = (List.range m).filterMap (fun j => if p j then some (j + 1) else none) := by rw [← finRange_map_val m, List.filterMap_map] rfl theorem range'_filterMap_eq (q : Nat → Bool) : ∀ (len s : Nat) (I : List Nat), List.Pairwise (· < ·) I → (∀ x ∈ I, s ≤ x ∧ x < s + len) → (∀ j, s ≤ j → j < s + len → (q j = true ↔ j ∈ I)) → (List.range' s len).filterMap (fun j => if q j then some j else none) = I := by intro len induction len with | zero => intro s I _ hb _ rw [List.range'_zero, List.filterMap_nil] symm rw [List.eq_nil_iff_forall_not_mem] intro x hx have := hb x hx omega | succ len ih => intro s I hpw hb hiff rw [List.range'_succ] by_cases hs : q s = true · have hfs : (fun j => if q j then some j else none) s = some s := by simp [hs] rw [List.filterMap_cons_some (f := fun j => if q j then some j else none) hfs] have hmem : s ∈ I := (hiff s (Nat.le_refl s) (by omega)).mp hs cases I with | nil => exact absurd hmem (by simp) | cons hd ys => obtain ⟨hhd, htl⟩ := List.pairwise_cons.mp hpw have hhs : hd = s := by by_contra hh have hys : s ∈ ys := by rcases List.mem_cons.mp hmem with h1 | h1 · exact absurd h1.symm hh · exact h1 have h2 := hhd s hys have h3 := (hb hd (by simp)).1 omega subst hhs congr 1 refine ih (hd + 1) ys htl ?_ ?_ · intro x hx have h1 := hhd x hx have h2 := (hb x (by simp [hx])).2 omega · intro j hj1 hj2 rw [hiff j (by omega) (by omega), List.mem_cons] constructor · rintro (rfl | hh) · omega · exact hh · intro hh; exact Or.inr hh · have hfs : (fun j => if q j then some j else none) s = none := by simp [hs] rw [List.filterMap_cons_none (f := fun j => if q j then some j else none) hfs] refine ih (s + 1) I hpw ?_ ?_ · intro x hx have h1 := hb x hx have h2 : x ≠ s := by intro he subst he exact hs ((hiff x h1.1 h1.2).mpr hx) omega · intro j hj1 hj2 exact hiff j (by omega) (by omega) theorem range_shift (m : Nat) (I : List Nat) : (List.range m).filterMap (fun j => if decide (j + 1 ∈ I) then some (j + 1) else none) = (List.range' 1 m).filterMap (fun j => if decide (j ∈ I) then some j else none) := by rw [List.range'_eq_map_range, List.filterMap_map] congr 1 funext j simp [Nat.add_comm] theorem range_filterMap_eq (m : Nat) (I : List Nat) (hpw : List.Pairwise (· < ·) I) (hb : ∀ x ∈ I, 1 ≤ x ∧ x ≤ m) : (List.range m).filterMap (fun j => if decide (j + 1 ∈ I) then some (j + 1) else none) = I := by rw [range_shift] refine range'_filterMap_eq (fun j => decide (j ∈ I)) m 1 I hpw ?_ ?_ · intro x hx have := hb x hx omega · intro j _ _ simp theorem blocksOfCode_eq (xs : List String) (hn : 1 ≤ xs.length) (cuts : PartitionCode xs) : blocksOfCode xs cuts = blocksOf xs 0 (((List.finRange (xs.length - 1)).filterMap (fun i => if cuts i then some (i.val + 1) else none)) ++ [xs.length]) := by unfold blocksOfCode cutPositions rw [if_neg (by omega), List.cons_append, decode_blocksOf] theorem encode_exists (xs : List String) (hn : 1 ≤ xs.length) (bs : List (List String)) (hfl : bs.flatten = xs) (hne : ∀ b ∈ bs, b ≠ []) : ∃ cuts : PartitionCode xs, blocksOfCode xs cuts = bs := by have hbsne : bs ≠ [] := by intro he rw [he, List.flatten_nil] at hfl rw [← hfl] at hn simp at hn obtain ⟨hIb, hIpw⟩ := interiorOf_props bs 0 hne refine ⟨fun i => decide (i.val + 1 ∈ interiorOf 0 bs), ?_⟩ rw [blocksOfCode_eq xs hn] have hfm : (List.finRange (xs.length - 1)).filterMap (fun i : Fin (xs.length - 1) => if decide (i.val + 1 ∈ interiorOf 0 bs) then some (i.val + 1) else none) = interiorOf 0 bs := by rw [finRange_filterMap (xs.length - 1) (fun j => decide (j + 1 ∈ interiorOf 0 bs))] refine range_filterMap_eq _ _ hIpw ?_ intro q hq have hq2 := hIb q hq rw [hfl] at hq2 omega rw [hfm] have hbi := blocksOf_interiorOf xs bs 0 hbsne (by rw [List.drop_zero, hfl]) rw [hfl, Nat.zero_add] at hbi exact hbi theorem buildLine_length : ∀ (block : List String) (gaps : List Nat) (t : Nat), gaps.length + 1 = block.length → (buildLine block gaps t).length = (block.map String.length).sum + gaps.sum + t := by have hsp : ∀ n : Nat, (spaces n).length = n := by intro n show (String.ofList (List.replicate n ' ')).length = n rw [String.length_ofList, List.length_replicate] have key : ∀ (block : List String) (gaps : List Nat), gaps.length + 1 = block.length → ((List.zipWith (fun word gap => word ++ spaces gap) block (gaps ++ [0])).map String.length).sum = (block.map String.length).sum + gaps.sum := by intro block induction block with | nil => intro gaps hg; simp at hg | cons w ws ih => intro gaps hg cases gaps with | nil => cases ws with | nil => simp [hsp] | cons _ _ => simp at hg | cons g gs => have h2 : gs.length + 1 = ws.length := by simpa using hg simp only [List.cons_append, List.zipWith_cons_cons, List.map_cons, List.sum_cons, String.length_append, hsp, ih gs h2] omega intro block gaps t hg unfold buildLine rw [String.length_append, String.length_join, key block gaps hg, hsp] theorem evenlySpacedGaps_eq (block : List String) (width : Nat) : evenlySpacedGaps block width = (if block.length - 1 = 0 then ([] : List Nat) else List.replicate ((width - (block.map String.length).sum) % (block.length - 1)) ((width - (block.map String.length).sum) / (block.length - 1) + 1) ++ List.replicate ((block.length - 1) - (width - (block.map String.length).sum) % (block.length - 1)) ((width - (block.map String.length).sum) / (block.length - 1))) := rfl theorem evenSplit_props (gc q r : Nat) (hgc : 0 < gc) (hq : 1 ≤ q) (hr : r < gc) : ((List.replicate r (q + 1) ++ List.replicate (gc - r) q).length = gc) ∧ (∀ x ∈ List.replicate r (q + 1) ++ List.replicate (gc - r) q, 1 ≤ x) ∧ (∀ x ∈ List.replicate r (q + 1) ++ List.replicate (gc - r) q, x = q ∨ x = q + 1) ∧ List.Pairwise (· ≥ ·) (List.replicate r (q + 1) ++ List.replicate (gc - r) q) ∧ (List.replicate r (q + 1) ++ List.replicate (gc - r) q).sum = gc * q + r := by refine ⟨?_, ?_, ?_, ?_, ?_⟩ · simp only [List.length_append, List.length_replicate]; omega · intro x hx rcases List.mem_append.mp hx with h1 | h1 · have := List.mem_replicate.mp h1; omega · have := List.mem_replicate.mp h1; omega · intro x hx rcases List.mem_append.mp hx with h1 | h1 · exact Or.inr (List.mem_replicate.mp h1).2 · exact Or.inl (List.mem_replicate.mp h1).2 · rw [List.pairwise_append] refine ⟨by simp, by simp, ?_⟩ intro a ha b hb have h1 := (List.mem_replicate.mp ha).2 have h2 := (List.mem_replicate.mp hb).2 omega · rw [List.sum_append, List.sum_replicate_nat, List.sum_replicate_nat] have hle : r * q ≤ gc * q := Nat.mul_le_mul (Nat.le_of_lt hr) (Nat.le_refl q) rw [Nat.mul_add, Nat.mul_one, Nat.sub_mul] omega theorem gaps_shape : ∀ (gaps : List Nat) (g : Nat), (∀ x ∈ gaps, x = g ∨ x = g + 1) → List.Pairwise (· ≥ ·) gaps → ∃ m, m ≤ gaps.length ∧ gaps = List.replicate m (g + 1) ++ List.replicate (gaps.length - m) g := by intro gaps induction gaps with | nil => intro g _ _; exact ⟨0, by simp⟩ | cons a t ih => intro g hall hpw obtain ⟨hhd, htl⟩ := List.pairwise_cons.mp hpw obtain ⟨m, hm, hrep⟩ := ih g (fun x hx => hall x (List.mem_cons_of_mem a hx)) htl rcases hall a (List.mem_cons_self ..) with ha | ha · have hz : m = 0 := by by_contra hne0 have hmem : g + 1 ∈ t := by rw [hrep] exact List.mem_append_left _ (List.mem_replicate.mpr ⟨hne0, rfl⟩) have := hhd _ hmem omega subst hz refine ⟨0, by simp, ?_⟩ have ht : t = List.replicate t.length g := by simpa using hrep rw [List.replicate_zero, List.nil_append, List.length_cons, Nat.sub_zero, List.replicate_succ, ha, ← ht] · refine ⟨m + 1, by simp only [List.length_cons]; omega, ?_⟩ rw [ha, List.replicate_succ, List.cons_append, List.length_cons, show t.length + 1 - (m + 1) = t.length - m from by omega] exact congrArg (fun l => (g + 1) :: l) hrep theorem evenlySpaced_unique (gc room : Nat) (gaps : List Nat) (hgc : 0 < gc) (hlen : gaps.length = gc) (hsum : gaps.sum = room) (hg : ∃ g : Nat, ∀ x ∈ gaps, x = g ∨ x = g + 1) (hpw : List.Pairwise (· ≥ ·) gaps) : gaps = List.replicate (room % gc) (room / gc + 1) ++ List.replicate (gc - room % gc) (room / gc) := by obtain ⟨g, hgall⟩ := hg obtain ⟨m, hm, hrep⟩ := gaps_shape gaps g hgall hpw rw [hlen] at hm hrep have hsum2 : m * (g + 1) + (gc - m) * g = room := by rw [← hsum, hrep, List.sum_append, List.sum_replicate_nat, List.sum_replicate_nat] have hmul : m * g ≤ gc * g := Nat.mul_le_mul hm (Nat.le_refl g) have hkey : gc * g + m = room := by rw [Nat.mul_add, Nat.mul_one, Nat.sub_mul] at hsum2 omega rcases Nat.lt_or_ge m gc with hlt | hge · have hd : room / gc = g := by rw [← hkey, Nat.mul_add_div hgc, Nat.div_eq_of_lt hlt, Nat.add_zero] have hmo : room % gc = m := by rw [← hkey, Nat.mul_add_mod, Nat.mod_eq_of_lt hlt] rw [hd, hmo] exact hrep · have hmeq : m = gc := Nat.le_antisymm hm hge have hroom : room = gc * (g + 1) := by rw [← hkey, hmeq]; ring have hd : room / gc = g + 1 := by rw [hroom, Nat.mul_div_cancel_left _ hgc] have hmo : room % gc = 0 := by rw [hroom, Nat.mul_mod_right] rw [hd, hmo, List.replicate_zero, List.nil_append, Nat.sub_zero, hrep, hmeq] simp theorem evenlySpacedGaps_props (block : List String) (width : Nat) (hfit : minLineWidth block ≤ width) : (evenlySpacedGaps block width).length = block.length - 1 ∧ (∀ x ∈ evenlySpacedGaps block width, 1 ≤ x) ∧ (∃ g : Nat, ∀ x ∈ evenlySpacedGaps block width, x = g ∨ x = g + 1) ∧ List.Pairwise (· ≥ ·) (evenlySpacedGaps block width) := by rw [evenlySpacedGaps_eq] by_cases hgc : block.length - 1 = 0 · rw [if_pos hgc] exact ⟨by simp [hgc], by simp, ⟨0, by simp⟩, List.Pairwise.nil⟩ · rw [if_neg hgc] have hgcpos : 0 < block.length - 1 := Nat.pos_of_ne_zero hgc have hfit' : (block.map String.length).sum + (block.length - 1) ≤ width := hfit have hroom : block.length - 1 ≤ width - (block.map String.length).sum := by omega have hq : 1 ≤ (width - (block.map String.length).sum) / (block.length - 1) := (Nat.one_le_div_iff hgcpos).mpr hroom have hr : (width - (block.map String.length).sum) % (block.length - 1) < block.length - 1 := Nat.mod_lt _ hgcpos obtain ⟨h1, h2, h3, h4, _⟩ := evenSplit_props (block.length - 1) ((width - (block.map String.length).sum) / (block.length - 1)) ((width - (block.map String.length).sum) % (block.length - 1)) hgcpos hq hr exact ⟨h1, h2, ⟨_, h3⟩, h4⟩ theorem evenlySpacedGaps_sum (block : List String) (width : Nat) (hgc : 0 < block.length - 1) (hfit : minLineWidth block ≤ width) : (evenlySpacedGaps block width).sum = width - (block.map String.length).sum := by rw [evenlySpacedGaps_eq, if_neg (by omega)] have hfit' : (block.map String.length).sum + (block.length - 1) ≤ width := hfit have hroom : block.length - 1 ≤ width - (block.map String.length).sum := by omega have hq : 1 ≤ (width - (block.map String.length).sum) / (block.length - 1) := (Nat.one_le_div_iff hgc).mpr hroom have hr : (width - (block.map String.length).sum) % (block.length - 1) < block.length - 1 := Nat.mod_lt _ hgc obtain ⟨_, _, _, _, h5⟩ := evenSplit_props (block.length - 1) ((width - (block.map String.length).sum) / (block.length - 1)) ((width - (block.map String.length).sum) % (block.length - 1)) hgc hq hr rw [h5] exact Nat.div_add_mod _ _ theorem built_iff (block : List String) (gaps : List Nat) (t : Nat) (line : String) : isBuiltFromGaps block gaps t line ↔ (gaps.length + 1 = block.length ∧ (∀ g ∈ gaps, 1 ≤ g) ∧ line = buildLine block gaps t) := Iff.rfl theorem specifiedLine_eq (block : List String) (width : Nat) (isLast : Bool) : specifiedLine block width isLast = buildLine block (if isLast then List.replicate (block.length - 1) 1 else evenlySpacedGaps block width) (if isLast then width - minLineWidth block else if block.length = 1 then width - (block.map String.length).sum else 0) := rfl theorem line_iff (b : List String) (width : Nat) (isLast : Bool) (l : String) (hne : b ≠ []) (hfit : minLineWidth b ≤ width) : (l = specifiedLine b width isLast) ↔ (IsLineOfWords b width l ∧ IsEvenlyJustified b width isLast l) := by have hblen : 1 ≤ b.length := List.length_pos_iff.mpr hne have hfit' : (b.map String.length).sum + (b.length - 1) ≤ width := hfit have hmw : minLineWidth b = (b.map String.length).sum + (b.length - 1) := rfl rw [specifiedLine_eq] unfold IsLineOfWords IsEvenlyJustified by_cases hL : isLast = true · simp only [if_pos hL] have hGlen : (List.replicate (b.length - 1) (1 : Nat)).length + 1 = b.length := by rw [List.length_replicate]; omega have hGpos : ∀ g ∈ List.replicate (b.length - 1) (1 : Nat), 1 ≤ g := by intro g hg; rw [(List.mem_replicate.mp hg).2] have hGsum : (List.replicate (b.length - 1) (1 : Nat)).sum = b.length - 1 := by rw [List.sum_replicate_nat]; omega constructor · rintro rfl have hlen : (buildLine b (List.replicate (b.length - 1) 1) (width - minLineWidth b)).length = width := by rw [buildLine_length _ _ _ hGlen, hGsum, hmw]; omega refine ⟨⟨hne, hlen, List.replicate (b.length - 1) 1, width - minLineWidth b, hGlen, hGpos, rfl⟩, List.replicate (b.length - 1) 1, width - minLineWidth b, ⟨hGlen, hGpos, rfl⟩, ?_⟩ intro g hg exact (List.mem_replicate.mp hg).2 · rintro ⟨⟨-, hlen, -⟩, gaps, t, hbuilt, hall1⟩ obtain ⟨hglen, hgpos, hleq⟩ := (built_iff b gaps t l).mp hbuilt have hgaps : gaps = List.replicate (b.length - 1) 1 := List.eq_replicate_iff.mpr ⟨by omega, hall1⟩ subst hleq rw [hgaps] at hlen ⊢ rw [buildLine_length _ _ _ hGlen, hGsum] at hlen rw [show t = width - minLineWidth b from by rw [hmw]; omega] · simp only [if_neg hL] by_cases hb1 : b.length = 1 · rw [if_pos hb1] have hgc0 : b.length - 1 = 0 := by omega have hE : evenlySpacedGaps b width = [] := by rw [evenlySpacedGaps_eq, if_pos hgc0] rw [hE] have hGlen : ([] : List Nat).length + 1 = b.length := by rw [List.length_nil]; omega constructor · rintro rfl have hlen : (buildLine b [] (width - (b.map String.length).sum)).length = width := by rw [buildLine_length _ _ _ hGlen, List.sum_nil]; omega exact ⟨⟨hne, hlen, [], width - (b.map String.length).sum, hGlen, by simp, rfl⟩, [], width - (b.map String.length).sum, ⟨hGlen, by simp, rfl⟩, Or.inl rfl, ⟨0, by simp⟩, List.Pairwise.nil⟩ · rintro ⟨⟨-, hlen, -⟩, gaps, t, hbuilt, -, -, -⟩ obtain ⟨hglen, hgpos, hleq⟩ := (built_iff b gaps t l).mp hbuilt have hgnil : gaps = [] := by cases gaps with | nil => rfl | cons x xs => rw [List.length_cons] at hglen; omega subst hleq rw [hgnil] at hlen ⊢ rw [buildLine_length _ _ _ hGlen, List.sum_nil] at hlen rw [show t = width - (b.map String.length).sum from by omega] · rw [if_neg hb1] have hgcpos : 0 < b.length - 1 := by omega obtain ⟨hElen, hEpos, hEnear, hEpw⟩ := evenlySpacedGaps_props b width hfit have hEsum := evenlySpacedGaps_sum b width hgcpos hfit have hGlen : (evenlySpacedGaps b width).length + 1 = b.length := by rw [hElen]; omega have hEeq : evenlySpacedGaps b width = List.replicate ((width - (b.map String.length).sum) % (b.length - 1)) ((width - (b.map String.length).sum) / (b.length - 1) + 1) ++ List.replicate ((b.length - 1) - (width - (b.map String.length).sum) % (b.length - 1)) ((width - (b.map String.length).sum) / (b.length - 1)) := by rw [evenlySpacedGaps_eq, if_neg (by omega)] constructor · rintro rfl have hlen : (buildLine b (evenlySpacedGaps b width) 0).length = width := by rw [buildLine_length _ _ _ hGlen, hEsum]; omega exact ⟨⟨hne, hlen, evenlySpacedGaps b width, 0, hGlen, hEpos, rfl⟩, evenlySpacedGaps b width, 0, ⟨hGlen, hEpos, rfl⟩, Or.inr rfl, hEnear, hEpw⟩ · rintro ⟨⟨-, hlen, -⟩, gaps, t, hbuilt, hz, hnear, hpw⟩ obtain ⟨hglen, hgpos, hleq⟩ := (built_iff b gaps t l).mp hbuilt have hgne : gaps ≠ [] := by intro he rw [he, List.length_nil] at hglen omega have ht0 : t = 0 := by rcases hz with hh | hh · exact absurd hh hgne · exact hh subst hleq subst ht0 rw [buildLine_length _ _ _ hglen] at hlen have hgsum : gaps.sum = width - (b.map String.length).sum := by omega have huniq := evenlySpaced_unique (b.length - 1) (width - (b.map String.length).sum) gaps hgcpos (by omega) hgsum hnear hpw rw [huniq, ← hEeq] theorem lines_iff (width : Nat) : ∀ (blocks : List (List String)) (result : List String), (∀ b ∈ blocks, b ≠ []) → (∀ b ∈ blocks, minLineWidth b ≤ width) → ((result = specifiedLines width blocks) ↔ (List.Forall₂ (fun b l => IsLineOfWords b width l) blocks result ∧ ∀ k : Nat, ∀ hk : k < result.length, ∀ hk' : k < blocks.length, IsEvenlyJustified blocks[k] width (decide (k + 1 = blocks.length)) result[k])) := by intro blocks induction blocks with | nil => intro result _ _ constructor · rintro rfl refine ⟨List.Forall₂.nil, ?_⟩ intro k hk hk' simp at hk' · rintro ⟨hF, -⟩ cases hF rfl | cons blk t ih => intro result hne hfit have hbne := hne blk (List.mem_cons_self ..) have hbfit := hfit blk (List.mem_cons_self ..) cases t with | nil => have hstep1 : specifiedLines width [blk] = [specifiedLine blk width true] := rfl have hd : (decide (0 + 1 = ([blk] : List (List String)).length)) = true := by rw [decide_eq_true_eq, List.length_cons, List.length_nil] constructor · rintro rfl have hL := (line_iff blk width true (specifiedLine blk width true) hbne hbfit).mp rfl refine ⟨List.Forall₂.cons hL.1 List.Forall₂.nil, ?_⟩ intro k hk hk' have hk0 : k = 0 := by have hlen0 : (blk :: ([] : List (List String))).length = 1 := rfl omega subst hk0 rw [hd] exact hL.2 · rintro ⟨hF, hEJ⟩ cases result with | nil => cases hF | cons line rs => cases hF with | cons hh htt => cases htt have h0 := hEJ 0 (by simp) (by simp) rw [hd] at h0 have hline := (line_iff blk width true line hbne hbfit).mpr ⟨hh, h0⟩ rw [hstep1, hline] | cons c t' => have hne' : ∀ b ∈ (c :: t'), b ≠ [] := fun x hx => hne x (List.mem_cons_of_mem blk hx) have hfit' : ∀ b ∈ (c :: t'), minLineWidth b ≤ width := fun x hx => hfit x (List.mem_cons_of_mem blk hx) have hstep : specifiedLines width (blk :: c :: t') = specifiedLine blk width false :: specifiedLines width (c :: t') := rfl have hlen1 : (specifiedLines width (blk :: c :: t')).length = (specifiedLines width (c :: t')).length + 1 := by rw [hstep, List.length_cons] have hlen2 : (blk :: c :: t').length = (c :: t').length + 1 := by rw [List.length_cons] have hdec0 : (decide (0 + 1 = (blk :: c :: t').length)) = false := by rw [decide_eq_false_iff_not, hlen2, List.length_cons] omega have hdecs : ∀ k : Nat, (decide (k + 1 + 1 = (blk :: c :: t').length)) = decide (k + 1 = (c :: t').length) := by intro k rw [decide_eq_decide, hlen2] omega constructor · rintro rfl have hL := (line_iff blk width false (specifiedLine blk width false) hbne hbfit).mp rfl obtain ⟨hFt, hEJt⟩ := (ih (specifiedLines width (c :: t')) hne' hfit').mp rfl refine ⟨List.Forall₂.cons hL.1 hFt, ?_⟩ intro k hk hk' rcases Nat.eq_zero_or_pos k with hk0 | hkp · subst hk0 rw [hdec0] exact hL.2 · obtain ⟨k', rfl⟩ : ∃ k', k = k' + 1 := ⟨k - 1, by omega⟩ rw [hdecs k'] exact hEJt k' (by omega) (by omega) · rintro ⟨hF, hEJ⟩ cases result with | nil => cases hF | cons line rs => cases hF with | cons hh htt => have h0 := hEJ 0 (by simp) (by simp) rw [hdec0] at h0 have hline := (line_iff blk width false line hbne hbfit).mpr ⟨hh, h0⟩ have hrs : rs = specifiedLines width (c :: t') := by refine (ih rs hne' hfit').mpr ⟨htt, ?_⟩ intro k hk hk' have hthis := hEJ (k + 1) (by rw [List.length_cons]; omega) (by rw [hlen2]; omega) rw [hdecs k] at hthis exact hthis rw [hstep, hline, hrs] theorem greedyChain_iff (width : Nat) (blocks : List (List String)) : ((consecutivePairs blocks).all (fun pair => match pair.2 with | [] => true | word :: _ => decide (width < minLineWidth (pair.1 ++ [word])))) = true ↔ List.Chain' (fun b b' => ∀ h : b' ≠ [], width < minLineWidth (b ++ [b'.head h])) blocks := by induction blocks with | nil => exact ⟨fun _ => List.isChain_nil, fun _ => rfl⟩ | cons b t ih => cases t with | nil => exact ⟨fun _ => List.isChain_singleton b, fun _ => rfl⟩ | cons c t' => have hcp : consecutivePairs (b :: c :: t') = (b, c) :: consecutivePairs (c :: t') := rfl rw [hcp, List.all_cons, Bool.and_eq_true, ih] have hstep : ((match (b, c).2 with | [] => true | word :: _ => decide (width < minLineWidth ((b, c).1 ++ [word]))) = true) ↔ (∀ h : c ≠ [], width < minLineWidth (b ++ [c.head h])) := by cases c with | nil => exact ⟨fun _ h => absurd rfl h, fun _ => rfl⟩ | cons w ws => constructor · intro hd _; exact of_decide_eq_true hd · intro hd; exact decide_eq_true (hd (by simp)) rw [hstep] show ((∀ h : c ≠ [], width < minLineWidth (b ++ [c.head h])) ∧ List.IsChain (fun x y => ∀ h : y ≠ [], width < minLineWidth (x ++ [y.head h])) (c :: t')) ↔ List.IsChain (fun x y => ∀ h : y ≠ [], width < minLineWidth (x ++ [y.head h])) (b :: c :: t') constructor · rintro ⟨h1, h2⟩ exact List.IsChain.cons_cons h1 h2 · intro hch cases hch with | cons_cons hr hcc => exact ⟨hr, hcc⟩ theorem greedySegCheck_iff (words : List String) (width : Nat) (blocks : List (List String)) : greedySegmentationCheck words width blocks = true ↔ IsGreedySegmentation words width blocks := by unfold greedySegmentationCheck IsGreedySegmentation rw [Bool.and_eq_true, Bool.and_eq_true, Bool.and_eq_true, greedyChain_iff] simp only [decide_eq_true_eq, List.all_eq_true] tauto theorem partitionAccepted_iff (words : List String) (width : Nat) (result : List String) (blocks : List (List String)) : partitionAccepted (words, width) result blocks = true ↔ (blocks.flatten = words ∧ (∀ b ∈ blocks, b ≠ []) ∧ result = specifiedLines width blocks ∧ IsGreedySegmentation words width blocks) := by unfold partitionAccepted simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, greedySegCheck_iff] tauto /-- On valid input the checker accepts exactly the specified outputs. -/ theorem justifyText_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : justifyText_check input result ↔ justifyText_spec input result := by obtain ⟨words, width⟩ := input have hn : 1 ≤ words.length := valid_len words width h rw [check_eq, decide_eq_true_eq, spec_eq] constructor · rintro ⟨code, hacc⟩ obtain ⟨hfl, hne, hres, hgs⟩ := (partitionAccepted_iff words width result _).mp hacc obtain ⟨hF, hEJ⟩ := (lines_iff width _ result hne hgs.2.2.1).mp hres exact ⟨blocksOfCode words code, hfl, hne, hF, hgs, hEJ⟩ · rintro ⟨blocks, hfl, hne, hF, hgs, hEJ⟩ obtain ⟨code, hdec⟩ := encode_exists words hn blocks hfl hne refine ⟨code, ?_⟩ rw [partitionAccepted_iff, hdec] exact ⟨hfl, hne, (lines_iff width blocks result hne hgs.2.2.1).mpr ⟨hF, hEJ⟩, hgs⟩ /-! ### Implementation helpers -/ /-- Greedily packs the remaining words into fitting blocks, keeping completed blocks reversed. -/ def greedyBlocks (width : Nat) (current : List String) (accRev : List (List String)) : List String → List (List String) | [] => if current = [] then accRev.reverse else (current :: accRev).reverse | word :: rest => if current = [] then greedyBlocks width [word] accRev rest else if minLineWidth (current ++ [word]) ≤ width then greedyBlocks width (current ++ [word]) accRev rest else greedyBlocks width [word] (current :: accRev) rest /-! ### Main algorithm (impl) -/ /-- One-pass greedy packing into blocks, formatted by the checker's specified line rules. -/ def fullJustify (input : Input) : Output := specifiedLines input.2 (greedyBlocks input.2 [] [] input.1) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem fullJustify_correct (input : Input) (h : isValidInput input) : justifyText_spec input (fullJustify input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (["This", "is", "an", "example", "of", "text", "justification."], 16) #guard isValidInput (["What", "must", "be", "acknowledgment", "shall", "be"], 16) #guard isValidInput (["LongWord1234567890", "Short", "AnotherLongWord1234567", "Tiny", "Word"], 25) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 16)) #guard !(isValidInput ([""], 100)) #guard !(isValidInput (["hello"], 4)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard justifyText_check (["This", "is", "an", "example", "of", "text", "justification."], 16) ["This is an", "example of text", "justification. "] #guard justifyText_check (["What", "must", "be", "acknowledgment", "shall", "be"], 16) ["What must be", "acknowledgment ", "shall be "] #guard justifyText_check (["LongWord1234567890", "Short", "AnotherLongWord1234567", "Tiny", "Word"], 25) ["LongWord1234567890 Short", "AnotherLongWord1234567 ", "Tiny Word "] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(justifyText_check (["This", "is", "an", "example", "of", "text", "justification."], 16) ["This is an", "example of text", "justification."]) #guard !(justifyText_check (["What", "must", "be", "acknowledgment", "shall", "be"], 16) ["What must be", "acknowledgment ", "shall be "]) #guard !(justifyText_check (["LongWord1234567890", "Short", "AnotherLongWord1234567", "Tiny", "Word"], 25) ["LongWord1234567890 Short", "AnotherLongWord1234567 ", "Tiny Word "]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard fullJustify (["This", "is", "an", "example", "of", "text", "justification."], 16) == ["This is an", "example of text", "justification. "] #guard fullJustify (["What", "must", "be", "acknowledgment", "shall", "be"], 16) == ["What must be", "acknowledgment ", "shall be "] #guard fullJustify (["LongWord1234567890", "Short", "AnotherLongWord1234567", "Tiny", "Word"], 25) == ["LongWord1234567890 Short", "AnotherLongWord1234567 ", "Tiny Word "] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard justifyText_check (["This", "is", "an", "example", "of", "text", "justification."], 16) (fullJustify (["This", "is", "an", "example", "of", "text", "justification."], 16)) #guard justifyText_check (["What", "must", "be", "acknowledgment", "shall", "be"], 16) (fullJustify (["What", "must", "be", "acknowledgment", "shall", "be"], 16)) #guard justifyText_check (["LongWord1234567890", "Short", "AnotherLongWord1234567", "Tiny", "Word"], 25) (fullJustify (["LongWord1234567890", "Short", "AnotherLongWord1234567", "Tiny", "Word"], 25)) end PTextJustification