import Mathlib /-! # Orderly Queue You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string. Return the lexicographically smallest string you could have after applying the mentioned step any number of moves. ## Constraints - 1 <= k <= s.length <= 1000 - s consist of lowercase English letters. ## Provided examples - `s = "cba", k = 1` → `"acb"` - `s = "baaca", k = 3` → `"aaabc"` - `s = "aaa", k = 3` → `"aaa"` ## Synthesized negative examples - invalid input: `s = "a", k = 0` ([structural] a predicate that admits 1 <= k <= s.length <= 1000. one step below the k lower bound) - invalid input: `s = "a", k = 2` ([structural] a predicate that admits 1 <= k <= s.length <= 1000. k one past s.length; a predicate checking k's own range alone accepts it) - invalid input: `s = "", k = 1` ([structural] a predicate that admits 1 <= k <= s.length <= 1000. empty string where at least one character is required) - `s = "cba", k = 1` → `"bac"` is wrong ([structural] minimality stated as achievability alone. one move from cba, reachable but not minimal) - `s = "baaca", k = 3` → `"abaac"` is wrong ([structural] minimality stated as achievability alone. reachable but lexicographically larger than true) - `s = "aaa", k = 3` → `"aaaaa"` is wrong ([structural] achievability stated without minimality. two appends reachable but not lexicographically smallest) -/ namespace POrderlyQueue abbrev Input := (String) × (Nat) abbrev Output := String /-! ### Specification helpers -/ /-- `t` is obtained from `s` by choosing one of the first `k` characters of `s` and appending it to the end, preserving the order of the others. -/ def IsLegalMove (k : Nat) (s t : String) : Prop := ∃ i : Nat, ∃ c : Char, i < k ∧ s.toList[i]? = some c ∧ t.toList = s.toList.take i ++ s.toList.drop (i + 1) ++ [c] /-- `tr` is a nonempty sequence of strings whose first element is `s` and whose consecutive pairs satisfy `IsLegalMove k`. -/ def IsLegalTrace (k : Nat) (s : String) (tr : List String) : Prop := tr.head? = some s ∧ tr.Chain' (IsLegalMove k) /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ k ≤ s.length ≤ 1000` and every character of `s` is a lowercase English letter. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.2 && input.2 ≤ input.1.length && input.1.length ≤ 1000 && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'z') /-! ### Ideal specification (P_spec) -/ /-- `result` is the lexicographically least final string reached by any legal trace for `k` from `s`: some legal trace ends at `result`, and no legal trace ends at a lexicographically smaller string. -/ def orderlyQueue_spec (input : Input) (result : Output) : Prop := IsLeast {t | ∃ tr : List String, IsLegalTrace input.2 input.1 tr ∧ tr.getLast? = some t} result /-! ### Decidable specification (P_check) -/ /-- The cyclic rotations of `s`, one for each starting position. -/ def rotationsOf (s : String) : List String := (List.range s.length).map fun n => String.mk (s.toList.rotate n) /-- Every rearrangement of the characters of `s`, as strings. -/ def rearrangementsOf (s : String) : List String := s.toList.permutations.map String.mk /-- Executable checker for `orderlyQueue_spec`: `result` must be a reachable string (a rotation of `s` when `k = 1`, a rearrangement of `s` when `k ≥ 2`) and no reachable string may be lexicographically smaller. -/ def orderlyQueue_check (input : Input) (result : Output) : Bool := let candidates := if input.2 = 1 then rotationsOf input.1 else rearrangementsOf input.1 decide (result ∈ candidates ∧ ∀ t ∈ candidates, result ≤ t) theorem oq_check_eq (input : Input) (result : String) : orderlyQueue_check input result = decide (result ∈ (if input.2 = 1 then rotationsOf input.1 else rearrangementsOf input.1) ∧ ∀ t ∈ (if input.2 = 1 then rotationsOf input.1 else rearrangementsOf input.1), result ≤ t) := rfl theorem oq_spec_iff (input : Input) (result : String) : orderlyQueue_spec input result ↔ ((∃ tr : List String, IsLegalTrace input.2 input.1 tr ∧ tr.getLast? = some result) ∧ ∀ y : String, (∃ tr : List String, IsLegalTrace input.2 input.1 tr ∧ tr.getLast? = some y) → result ≤ y) := Iff.rfl /-- A legal move, read on character lists. -/ def oqMv (k : Nat) (a b : List Char) : Prop := ∃ i : Nat, ∃ c : Char, i < k ∧ a[i]? = some c ∧ b = a.take i ++ a.drop (i + 1) ++ [c] theorem oq_reach_str (k : Nat) (s t : String) : (∃ tr : List String, IsLegalTrace k s tr ∧ tr.getLast? = some t) ↔ Relation.ReflTransGen (oqMv k) s.toList t.toList := by have hstr : Relation.ReflTransGen (IsLegalMove k) s t ↔ Relation.ReflTransGen (oqMv k) s.toList t.toList := by constructor · intro hr exact hr.lift String.toList (fun a b hab => hab) · intro hr have hl : Relation.ReflTransGen (IsLegalMove k) (String.ofList s.toList) (String.ofList t.toList) := hr.lift String.ofList (fun a b hab => by show oqMv k (String.ofList a).toList (String.ofList b).toList rw [String.toList_ofList, String.toList_ofList] exact hab) rwa [String.ofList_toList, String.ofList_toList] at hl rw [← hstr] constructor · rintro ⟨tr, ⟨hhead, hchain⟩, hlast⟩ cases tr with | nil => simp at hhead | cons a l => simp only [List.head?_cons, Option.some.injEq] at hhead subst hhead have hl := List.relationReflTransGen_of_exists_isChain (a :: l) hchain (List.cons_ne_nil _ _) rw [List.getLast?_eq_getLast (List.cons_ne_nil _ _), Option.some.injEq] at hlast rw [hlast] at hl exact hl · intro hr obtain ⟨l, hc, hl⟩ := List.exists_isChain_cons_of_relationReflTransGen hr exact ⟨s :: l, ⟨rfl, hc⟩, by rw [List.getLast?_eq_getLast (List.cons_ne_nil _ _), hl]⟩ theorem oq_mv_rot (k : Nat) (hk : 1 ≤ k) (a : List Char) (hne : a ≠ []) : oqMv k a (a.rotate 1) := by cases a with | nil => exact absurd rfl hne | cons x xs => exact ⟨0, x, by omega, rfl, by simp [List.rotate_cons_succ, List.rotate_zero]⟩ theorem oq_mv1 (a b : List Char) : oqMv 1 a b → b = a.rotate 1 := by rintro ⟨i, c, hi, hc, rfl⟩ obtain rfl : i = 0 := by omega cases a with | nil => simp at hc | cons x xs => simp at hc subst hc simp [List.rotate_cons_succ, List.rotate_zero] theorem oq_rot_reach (k : Nat) (hk : 1 ≤ k) (l : List Char) (hne : l ≠ []) : ∀ n : Nat, Relation.ReflTransGen (oqMv k) l (l.rotate n) := by intro n induction n with | zero => rw [List.rotate_zero] | succ n ih => have hne' : l.rotate n ≠ [] := by intro he apply hne apply List.length_eq_zero_iff.mp rw [← List.length_rotate l n, he, List.length_nil] have hs := oq_mv_rot k hk _ hne' rw [List.rotate_rotate] at hs exact ih.tail hs theorem oq_k1 (l : List Char) (hne : l ≠ []) (t : List Char) : Relation.ReflTransGen (oqMv 1) l t ↔ ∃ n < l.length, t = l.rotate n := by have hpos : 0 < l.length := List.length_pos_iff.mpr hne constructor · intro hr induction hr with | refl => exact ⟨0, hpos, (List.rotate_zero l).symm⟩ | tail _ hbc ih => obtain ⟨n, _, rfl⟩ := ih refine ⟨(n + 1) % l.length, Nat.mod_lt _ hpos, ?_⟩ rw [oq_mv1 _ _ hbc, List.rotate_rotate, List.rotate_mod] · rintro ⟨n, _, rfl⟩ exact oq_rot_reach 1 (le_refl 1) l hne n theorem oq_mv_perm (k : Nat) (a b : List Char) : oqMv k a b → b.Perm a := by rintro ⟨i, c, _, hc, rfl⟩ obtain ⟨hlt, hce⟩ := List.getElem?_eq_some_iff.mp hc have hsplit : a = a.take i ++ c :: a.drop (i + 1) := by rw [← hce, ← List.drop_eq_getElem_cons hlt, List.take_append_drop] conv_rhs => rw [hsplit] exact (List.perm_append_singleton _ _).trans List.perm_middle.symm theorem oq_swap01 (k : Nat) (hk : 2 ≤ k) (a b : Char) (rest : List Char) : Relation.ReflTransGen (oqMv k) (a :: b :: rest) (b :: a :: rest) := by have h1 : oqMv k (a :: b :: rest) ((a :: rest) ++ [b]) := ⟨1, b, by omega, rfl, by simp⟩ have h2 := oq_rot_reach k (by omega) ((a :: rest) ++ [b]) (by simp) (a :: rest).length rw [List.rotate_append_length_eq] at h2 exact Relation.ReflTransGen.head h1 h2 theorem oq_swapAt (k : Nat) (hk : 2 ≤ k) (A : List Char) (a b : Char) (B : List Char) : Relation.ReflTransGen (oqMv k) (A ++ a :: b :: B) (A ++ b :: a :: B) := by have r1 := oq_rot_reach k (by omega) (A ++ a :: b :: B) (by simp) A.length rw [List.rotate_append_length_eq] at r1 have r2 : Relation.ReflTransGen (oqMv k) ((a :: b :: B) ++ A) ((b :: a :: B) ++ A) := oq_swap01 k hk a b (B ++ A) have r3 := oq_rot_reach k (by omega) ((b :: a :: B) ++ A) (by simp) (b :: a :: B).length rw [List.rotate_append_length_eq] at r3 exact (r1.trans r2).trans r3 /-- One adjacent transposition anywhere in the list. -/ def oqSw (a b : List Char) : Prop := ∃ A : List Char, ∃ x y : Char, ∃ B : List Char, a = A ++ x :: y :: B ∧ b = A ++ y :: x :: B theorem oq_perm_sw (l l' : List Char) (h : l.Perm l') : Relation.ReflTransGen oqSw l l' := by induction h with | nil => exact .refl | cons x _ ih => exact ih.lift (x :: ·) (fun a b hab => by obtain ⟨A, u, v, B, h1, h2⟩ := hab exact ⟨x :: A, u, v, B, by rw [h1]; rfl, by rw [h2]; rfl⟩) | swap x y l => exact .single ⟨[], y, x, l, rfl, rfl⟩ | trans _ _ ih1 ih2 => exact ih1.trans ih2 theorem oq_sw_reach (k : Nat) (hk : 2 ≤ k) (l l' : List Char) (h : Relation.ReflTransGen oqSw l l') : Relation.ReflTransGen (oqMv k) l l' := by induction h with | refl => exact .refl | tail _ hs ih => obtain ⟨A, x, y, B, rfl, rfl⟩ := hs exact ih.trans (oq_swapAt k hk A x y B) theorem oq_k2 (k : Nat) (hk : 2 ≤ k) (l t : List Char) : Relation.ReflTransGen (oqMv k) l t ↔ t.Perm l := by constructor · intro hr induction hr with | refl => exact List.Perm.refl _ | tail _ hbc ih => exact (oq_mv_perm k _ _ hbc).trans ih · intro hp exact oq_sw_reach k hk l t (oq_perm_sw l t hp.symm) theorem oq_mem_rot (s t : String) : t ∈ rotationsOf s ↔ ∃ n < s.toList.length, t.toList = s.toList.rotate n := by unfold rotationsOf simp only [List.mem_map, List.mem_range] constructor · rintro ⟨n, hn, rfl⟩ exact ⟨n, hn, String.toList_ofList⟩ · rintro ⟨n, hn, heq⟩ refine ⟨n, hn, ?_⟩ rw [← heq] exact String.ofList_toList theorem oq_mem_perm (s t : String) : t ∈ rearrangementsOf s ↔ t.toList.Perm s.toList := by unfold rearrangementsOf simp only [List.mem_map, List.mem_permutations] constructor · rintro ⟨p, hp, rfl⟩ exact (by rw [String.toList_ofList]; exact hp : (String.ofList p).toList.Perm s.toList) · intro hp exact ⟨t.toList, hp, String.ofList_toList⟩ theorem oq_reach (input : Input) (h : isValidInput input) (t : String) : (∃ tr : List String, IsLegalTrace input.2 input.1 tr ∧ tr.getLast? = some t) ↔ t ∈ (if input.2 = 1 then rotationsOf input.1 else rearrangementsOf input.1) := by have hv := h simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at hv obtain ⟨⟨⟨hk1, hkn⟩, -⟩, -⟩ := hv have hne : input.1.toList ≠ [] := by intro he have := congrArg List.length he rw [String.length_toList, List.length_nil] at this omega rw [oq_reach_str] by_cases hk : input.2 = 1 · rw [if_pos hk, oq_mem_rot, hk] exact oq_k1 _ hne _ · rw [if_neg hk, oq_mem_perm] exact oq_k2 _ (by omega) _ _ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem orderlyQueue_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : orderlyQueue_check input result ↔ orderlyQueue_spec input result := by rw [oq_check_eq, decide_eq_true_iff, oq_spec_iff] constructor · rintro ⟨hm, hlb⟩ exact ⟨(oq_reach input h result).mpr hm, fun y hy => hlb y ((oq_reach input h y).mp hy)⟩ · rintro ⟨hm, hlb⟩ exact ⟨(oq_reach input h result).mp hm, fun y hy => hlb y ((oq_reach input h y).mpr hy)⟩ /-! ### Implementation helpers -/ /-- The lexicographically smallest cyclic rotation of `s`, folded over `rotationsOf s` with `s` (rotation 0) as the initial best. -/ def minimumRotation (s : String) : String := (rotationsOf s).foldl (fun best t => if best ≤ t then best else t) s /-- The characters of `s` in ascending order, used when `k ≥ 2` because every rearrangement is then reachable. -/ def sortStringForKGe2 (s : String) : String := String.mk (List.insertionSort (fun a b => decide (a ≤ b)) s.toList) /-! ### Main algorithm (impl) -/ /-- Branch on `k`: the least rotation of `s` when `k = 1`, the sorted characters of `s` when `k ≥ 2`. -/ def lexicographicallySmallestAfterMoves (input : Input) : Output := if input.2 = 1 then minimumRotation input.1 else sortStringForKGe2 input.1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem lexicographicallySmallestAfterMoves_correct (input : Input) (h : isValidInput input) : orderlyQueue_spec input (lexicographicallySmallestAfterMoves input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("cba", 1) #guard isValidInput ("baaca", 3) #guard isValidInput ("aaa", 3) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("a", 0)) #guard !(isValidInput ("a", 2)) #guard !(isValidInput ("", 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard orderlyQueue_check ("cba", 1) "acb" #guard orderlyQueue_check ("baaca", 3) "aaabc" #guard orderlyQueue_check ("aaa", 3) "aaa" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(orderlyQueue_check ("cba", 1) "bac") #guard !(orderlyQueue_check ("baaca", 3) "abaac") #guard !(orderlyQueue_check ("aaa", 3) "aaaaa") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard lexicographicallySmallestAfterMoves ("cba", 1) == "acb" #guard lexicographicallySmallestAfterMoves ("baaca", 3) == "aaabc" #guard lexicographicallySmallestAfterMoves ("aaa", 3) == "aaa" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard orderlyQueue_check ("cba", 1) (lexicographicallySmallestAfterMoves ("cba", 1)) #guard orderlyQueue_check ("baaca", 3) (lexicographicallySmallestAfterMoves ("baaca", 3)) #guard orderlyQueue_check ("aaa", 3) (lexicographicallySmallestAfterMoves ("aaa", 3)) end POrderlyQueue