import Mathlib /-! # Gray Code An n-bit gray code sequence is a sequence of 2n integers where: Every integer is in the inclusive range [0, 2n - 1], The first integer is 0, An integer appears no more than once in the sequence, The binary representation of every pair of adjacent integers differs by exactly one bit, and The binary representation of the first and last integers differs by exactly one bit. Given an integer n, return any valid n-bit gray code sequence. ## Constraints - 1 <= n <= 16 ## Provided examples - `n = 2` → `[0, 1, 3, 2]` - `n = 1` → `[0, 1]` - `n = 3` → `[0, 1, 3, 2, 6, 7, 5, 4]` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 16. one below the stated minimum) - invalid input: `n = 17` ([structural] a predicate that admits 1 <= n <= 16. one past the stated maximum) - invalid input: `n = 100` ([structural] a predicate that admits 1 <= n <= 16. order of magnitude past the ceiling) - `n = 2` → `[0, 2]` is wrong ([structural] length is not required to be 2^n. two-entry path satisfies all conditions except length) - `n = 1` → `[1, 0]` is wrong ([structural] drops the first-integer-0 condition. starts at 1 but still is a 1-bit gray code) - `n = 3` → `[0, 1, 3, 2]` is wrong ([structural] the answer for n-1 is accepted as an n-bit sequence. valid 2-bit code, wrong length) -/ namespace PGrayCode abbrev Input := Nat abbrev Output := List Nat /-! ### Specification helpers -/ /-- Two naturals differ in exactly one bit position among the low `n` bits, i.e. their xor is `2^k` for some `k < n`. -/ def IsOneBitApart (n a b : Nat) : Prop := ∃ k : Nat, k < n ∧ a ^^^ b = 2 ^ k /-! ### Validity predicate (V) -/ /-- Valid input: a bit count `n` with `1 ≤ n ≤ 16`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 16 /-! ### Ideal specification (P_spec) -/ /-- `result` is an n-bit Gray code sequence: it has length `2 ^ n`, starts with 0, every adjacent pair from first through last and back to first differs in exactly one bit, and its elements are pairwise distinct and each below `2 ^ n`. -/ def grayCode_spec (input : Input) (result : Output) : Prop := result.length = 2 ^ input ∧ result.head! = 0 ∧ result.Chain' (IsOneBitApart input) ∧ IsOneBitApart input result.getLastI result.head! ∧ result.Nodup ∧ ∀ x ∈ result, x < 2 ^ input /-! ### Decidable specification (P_check) -/ /-- Decidable form of `IsOneBitApart`: some `k < n` has `a ^^^ b = 2 ^ k`. -/ def oneBitApart (n a b : Nat) : Bool := (List.range n).any (fun k => a ^^^ b == 2 ^ k) /-- Every adjacent pair of the list satisfies `oneBitApart n`, mirroring `List.Chain'`. -/ def pairsChain (n : Nat) : List Nat → Bool | a :: b :: xs => oneBitApart n a b && pairsChain n (b :: xs) | _ => true /-- No element occurs twice, mirroring `List.Nodup`. -/ def nodupList : List Nat → Bool | [] => true | x :: xs => !(x ∈ xs) && nodupList xs /-- Every element of the list is below `2 ^ n`, mirroring `∀ x ∈ result, x < 2 ^ n`. -/ def allBelow (n : Nat) : List Nat → Bool | [] => true | x :: xs => (x < 2 ^ n) && allBelow n xs /-- Executable checker for `grayCode_spec` with the bounded existential realized over `List.range n`. -/ def grayCode_check (input : Input) (result : Output) : Bool := result.length == 2 ^ input && result.head! == 0 && pairsChain input result && oneBitApart input result.getLastI result.head! && nodupList result && allBelow input result theorem gray_root (hc : ∀ n xs, pairsChain n xs = true ↔ xs.Chain' (IsOneBitApart n)) (hn : ∀ xs, nodupList xs = true ↔ xs.Nodup) (hb : ∀ n xs, allBelow n xs = true ↔ ∀ x ∈ xs, x < 2 ^ n) (n : Nat) (xs : List Nat) : grayCode_check n xs ↔ grayCode_spec n xs := by simp [grayCode_check, grayCode_spec, hc, hn, hb, oneBitApart, IsOneBitApart, and_assoc] theorem gray_chain (n : Nat) (xs : List Nat) : pairsChain n xs = true ↔ xs.Chain' (IsOneBitApart n) := by induction xs with | nil => simp [pairsChain, List.Chain'] | cons a xs ih => cases xs with | nil => simp [pairsChain, List.Chain'] | cons b xs => simpa [pairsChain, List.Chain', oneBitApart, IsOneBitApart] using and_congr (show oneBitApart n a b = true ↔ IsOneBitApart n a b by simp [oneBitApart, IsOneBitApart]) ih theorem gray_nodup (xs : List Nat) : nodupList xs = true ↔ xs.Nodup := by induction xs with | nil => simp [nodupList] | cons x xs ih => simp [nodupList, ih] theorem gray_below (n : Nat) (xs : List Nat) : allBelow n xs = true ↔ ∀ x ∈ xs, x < 2 ^ n := by induction xs with | nil => simp [allBelow] | cons x xs ih => simp [allBelow, ih] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem grayCode_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : grayCode_check input result ↔ grayCode_spec input result := by exact gray_root gray_chain gray_nodup gray_below input result /-! ### Main algorithm (impl) -/ /-- The n-bit Gray code built by binary reflection: start from `[0]` and at each level append the reverse of the current code with every element raised by `2 ^ k`. -/ def grayCodeImpl (input : Input) : Output := match input with | 0 => [0] | k + 1 => let prev := grayCodeImpl k prev ++ prev.reverse.map (· + 2 ^ k) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem grayCodeImpl_correct (input : Input) (h : isValidInput input) : grayCode_spec input (grayCodeImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 2 #guard isValidInput 1 #guard isValidInput 3 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 17) #guard !(isValidInput 100) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard grayCode_check 2 [0, 1, 3, 2] #guard grayCode_check 1 [0, 1] #guard grayCode_check 3 [0, 1, 3, 2, 6, 7, 5, 4] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(grayCode_check 2 [0, 2]) #guard !(grayCode_check 1 [1, 0]) #guard !(grayCode_check 3 [0, 1, 3, 2]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard grayCodeImpl 2 == [0, 1, 3, 2] #guard grayCodeImpl 1 == [0, 1] #guard grayCodeImpl 3 == [0, 1, 3, 2, 6, 7, 5, 4] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard grayCode_check 2 (grayCodeImpl 2) #guard grayCode_check 1 (grayCodeImpl 1) #guard grayCode_check 3 (grayCodeImpl 3) end PGrayCode