import Mathlib /-! # Find Duplicate File In System Given a list paths of directory info, including the directory path, and all the files with contents in this directory, return all the duplicate files in the file system in terms of their paths. You may return the answer in any order. A group of duplicate files consists of at least two files that have the same content. A single directory info string in the input list has the following format: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" It means there are n files (f1.txt, f2.txt ... fn.txt) with content (f1_content, f2_content ... fn_content) respectively in the directory "root/d1/d2/.../dm". Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory. The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format: "directory_path/file_name.txt" ## Constraints - 1 <= paths.length <= 2 * 10^4 - 1 <= paths[i].length <= 3000 - 1 <= sum(paths[i].length) <= 5 * 10^5 - paths[i] consist of English letters, digits, '/', '.', '(', ')', and ' '. - You may assume no files or directories share the same name in the same directory. - You may assume each given directory info represents a unique directory. A single blank space separates the directory path and file info. ## Provided examples - `paths = ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]` → `[["root/a/2.txt", "root/c/d/4.txt", "root/4.txt"], ["root/a/1.txt", "root/c/3.txt"]]` - `paths = ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)"]` → `[["root/a/2.txt", "root/c/d/4.txt"], ["root/a/1.txt", "root/c/3.txt"]]` - `paths = ["root 1.txt(a) 2.txt(ab) 3.txt(abc) 4.txt(abcd)"]` → `[]` ## Synthesized negative examples - invalid input: `paths = ["root/a 1.txt(a_b)"]` ([structural] a predicate that admits paths[i] consist of English letters, digits, '/', '.', '(', ')', and ' '.. defeats a predicate that ignores characters inside file content) - invalid input: `paths = ["root/a 1.txt(x) 1.txt(y)"]` ([structural] a predicate that admits You may assume no files or directories share the same name in the same directory.. defeats a predicate that groups by content but never checks name uniqueness) - invalid input: `paths = ["root/[a 1.txt(x)"]` ([structural] a predicate that admits paths[i] consist of English letters, digits, '/', '.', '(', ')', and ' '.. defeats a predicate that checks file info but not the directory path) - `paths = ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]` → `[["root/a/2.txt", "root/c/d/4.txt", "root/4.txt"], ["root/a/1.txt", "root/c/3.txt"], ["root/a/1.txt", "root/a/2.txt"]]` is wrong ([structural] groups are not required to have equal contents. Extra group pairs files with different contents.) - `paths = ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)"]` → `[]` is wrong ([structural] no completeness requirement forces any groups to be reported. empty output returns no duplicates) - `paths = ["root 1.txt(a) 2.txt(ab) 3.txt(abc) 4.txt(abcd)"]` → `[["root/1.txt", "root/2.txt"]]` is wrong ([structural] files in a group are not required to have the same content. The two paths exist but contents a and ab differ.) -/ namespace PFindDuplicateFileInSystem abbrev Input := List String abbrev Output := List (List String) /-! ### Specification helpers -/ /-- Split a character list at each `sep`, keeping empty fields so stray separators are visible. -/ def splitKeepEmpty (sep : Char) : List Char → List (List Char) | [] => [[]] | c :: cs => if c == sep then [] :: splitKeepEmpty sep cs else match splitKeepEmpty sep cs with | x :: xs => (c :: x) :: xs | [] => [[c]] /-- Split a character list at the first `'('`, giving the parts before and after it. -/ def splitAtFirstParen : List Char → Option (List Char × List Char) | [] => none | '(' :: cs => some ([], cs) | c :: cs => (splitAtFirstParen cs).map fun (a, b) => (c :: a, b) /-- A character allowed in a directory info string: a letter, a digit, or `/ . ( ) space`. -/ def isAllowedChar (c : Char) : Bool := ('a' ≤ c && c ≤ 'z') || ('A' ≤ c && c ≤ 'Z') || ('0' ≤ c && c ≤ '9') || c == '/' || c == '.' || c == '(' || c == ')' || c == ' ' /-- A directory path is `root` followed by nonempty `/`-separated components. -/ def isValidDirPath (d : String) : Bool := match splitKeepEmpty '/' d.toList with | [] => false | r :: comps => r == "root".toList && comps.all fun comp => !comp.isEmpty /-- Parse a file info entry of the form `file_name.txt(content)` into name and content. -/ def parseFileEntry (e : String) : Option (String × String) := match splitAtFirstParen e.toList with | none => none | some (name, rest) => if rest.getLast? == some ')' && ".txt".toList.isSuffixOf name && name != ".txt".toList then some (String.mk name, String.mk rest.dropLast) else none /-- Parse a directory info string into its directory path and its `(name, content)` entries. -/ def parseDirInfo (s : String) : Option (String × List (String × String)) := match splitKeepEmpty ' ' s.toList with | [] => none | d :: es => if isValidDirPath (String.mk d) && !es.isEmpty then match (es.mapM fun e => parseFileEntry (String.mk e)) with | none => none | some entries => some (String.mk d, entries) else none /-- No value occurs twice in the list. -/ def nodupBool : List String → Bool | [] => true | x :: xs => !xs.elem x && nodupBool xs /-- Every directory path and every full file path mentioned in `paths`. -/ def allFullPaths (paths : List String) : List String := (paths.filterMap parseDirInfo).flatMap fun (dir, entries) => dir :: entries.map fun (name, _) => dir ++ "/" ++ name /-- File path `p` is listed in `paths` with content `c`. -/ def FileHasContent (paths : List String) (p c : String) : Prop := ∃ s ∈ paths, ∃ d, ∃ entries, parseDirInfo s = some (d, entries) ∧ ∃ name, (name, c) ∈ entries ∧ p = d ++ "/" ++ name /-- `g` lists in some order exactly the files of `paths` with content `c`, at least two of them. -/ def IsDuplicateGroup (paths : List String) (g : List String) (c : String) : Prop := (∀ p, p ∈ g ↔ FileHasContent paths p c) ∧ g.Nodup ∧ 2 ≤ g.length /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 20000 well-formed directory info strings over the allowed alphabet, each of length 1 to 3000 with total length 1 to 500000, and all directory and file paths distinct. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 20000 && input.all (fun s => 1 ≤ s.length && s.length ≤ 3000 && s.toList.all isAllowedChar) && 1 ≤ (input.map String.length).sum && (input.map String.length).sum ≤ 500000 && input.all (fun s => (parseDirInfo s).isSome) && nodupBool (allFullPaths input) && (input.filterMap parseDirInfo).all (fun (dir, entries) => entries.all (fun (name, _) => (input.filterMap parseDirInfo).all (fun (other, _) => !(other.startsWith (dir ++ "/" ++ name ++ "/"))))) /-! ### Ideal specification (P_spec) -/ /-- `result` is exactly the duplicate groups of `input`: every member is a duplicate group for some content, and for every content occurring in `input` exactly one member is a duplicate group for it when at least two files share it and none otherwise. -/ def duplicateFileGroups_spec (input : Input) (result : Output) : Prop := (∀ g ∈ result, ∃ c, IsDuplicateGroup input g c) ∧ ∀ c, (∃ p, FileHasContent input p c) → ((∃ p₁ p₂, p₁ ≠ p₂ ∧ FileHasContent input p₁ c ∧ FileHasContent input p₂ c) → ∃! i : Fin result.length, IsDuplicateGroup input (result.get i) c) ∧ ((¬ ∃ p₁ p₂, p₁ ≠ p₂ ∧ FileHasContent input p₁ c ∧ FileHasContent input p₂ c) → ∀ i : Fin result.length, ¬ IsDuplicateGroup input (result.get i) c) /-! ### Decidable specification (P_check) -/ /-- Every `(full path, content)` pair listed in `paths`, through the specification's own parser. -/ def fileContentTable (paths : List String) : List (String × String) := (paths.filterMap parseDirInfo).flatMap fun (dir, entries) => entries.map fun (name, c) => (dir ++ "/" ++ name, c) /-- Every content occurring as a file content in `paths`, with repetition. -/ def contentsOf (paths : List String) : List String := (fileContentTable paths).map Prod.snd /-- The file paths listed in `paths` whose listed content is `c`. -/ def pathsWithContent (paths : List String) (c : String) : List String := (fileContentTable paths).filterMap fun (p, c') => if c' == c then some p else none /-- Boolean reading of `FileHasContent`: `paths` lists file `p` with content `c`. -/ def hasContentBool (paths : List String) (p c : String) : Bool := (fileContentTable paths).any fun (p', c') => p' == p && c' == c /-- Boolean reading of `IsDuplicateGroup`: `g` is nodup, has at least two members, every member has content `c`, and every listed file with content `c` is a member. -/ def isDuplicateGroupBool (paths : List String) (g : List String) (c : String) : Bool := nodupBool g && 2 ≤ g.length && (g.all fun p => hasContentBool paths p c) && (pathsWithContent paths c).all fun p => g.elem p /-- Executable checker for `duplicateFileGroups_spec`, with contents truncated to those occurring in `input`. -/ def duplicateFileGroups_check (input : Input) (result : Output) : Bool := (result.all fun g => (contentsOf input).any fun c => isDuplicateGroupBool input g c) && (contentsOf input).all fun c => if 2 ≤ (pathsWithContent input c).length then ((List.finRange result.length).filter fun i => isDuplicateGroupBool input (result.get i) c).length == 1 else (List.finRange result.length).all fun i => !(isDuplicateGroupBool input (result.get i) c) theorem nodupBool_iff (l : List String) : nodupBool l = true ↔ l.Nodup := by induction l with | nil => simp [nodupBool] | cons x xs ih => simp only [nodupBool, Bool.and_eq_true, Bool.not_eq_true', List.nodup_cons, ih, List.elem_eq_mem, decide_eq_false_iff_not] theorem mem_fileContentTable (paths : List String) (p c : String) : (p, c) ∈ fileContentTable paths ↔ FileHasContent paths p c := by constructor · intro hm rw [fileContentTable, List.mem_flatMap] at hm obtain ⟨⟨d, entries⟩, hde, hin⟩ := hm rw [List.mem_filterMap] at hde obtain ⟨s, hs, hparse⟩ := hde obtain ⟨⟨name, c'⟩, hne, heq⟩ := List.mem_map.mp hin simp only [Prod.mk.injEq] at heq obtain ⟨h1, h2⟩ := heq subst h2 exact ⟨s, hs, d, entries, hparse, name, hne, h1.symm⟩ · rintro ⟨s, hs, d, entries, hparse, name, hne, hp⟩ rw [fileContentTable, List.mem_flatMap] refine ⟨(d, entries), List.mem_filterMap.mpr ⟨s, hs, hparse⟩, ?_⟩ exact List.mem_map.mpr ⟨(name, c), hne, by simp [hp]⟩ theorem hasContentBool_iff (paths : List String) (p c : String) : hasContentBool paths p c = true ↔ FileHasContent paths p c := by rw [← mem_fileContentTable] unfold hasContentBool rw [List.any_eq_true] constructor · rintro ⟨⟨p', c'⟩, hm, he⟩ simp only [Bool.and_eq_true, beq_iff_eq] at he obtain ⟨h1, h2⟩ := he subst h1; subst h2 exact hm · intro hm exact ⟨(p, c), hm, by simp⟩ theorem mem_pathsWithContent (paths : List String) (p c : String) : p ∈ pathsWithContent paths c ↔ FileHasContent paths p c := by rw [← mem_fileContentTable] unfold pathsWithContent rw [List.mem_filterMap] constructor · rintro ⟨⟨p', c'⟩, hm, he⟩ have he' : (if (c' == c) = true then some p' else none) = some p := he by_cases hc : (c' == c) = true · rw [if_pos hc] at he' have hpp : p' = p := Option.some.inj he' have hcc : c' = c := by simpa using hc subst hpp; subst hcc exact hm · rw [if_neg hc] at he' exact absurd he' (by simp) · intro hm exact ⟨(p, c), hm, by simp⟩ theorem mem_contentsOf (paths : List String) (c : String) : c ∈ contentsOf paths ↔ ∃ p, FileHasContent paths p c := by unfold contentsOf rw [List.mem_map] constructor · rintro ⟨⟨p, c'⟩, hm, he⟩ exact ⟨p, he ▸ (mem_fileContentTable paths p c').mp hm⟩ · rintro ⟨p, hp⟩ exact ⟨(p, c), (mem_fileContentTable paths p c).mpr hp, rfl⟩ theorem isDuplicateGroupBool_iff (paths : List String) (g : List String) (c : String) : isDuplicateGroupBool paths g c = true ↔ IsDuplicateGroup paths g c := by unfold isDuplicateGroupBool IsDuplicateGroup simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, nodupBool_iff, hasContentBool_iff] constructor · rintro ⟨⟨⟨hnd, hlen⟩, hfwd⟩, hbwd⟩ refine ⟨fun p => ⟨fun hp => hfwd p hp, fun hp => ?_⟩, hnd, hlen⟩ exact List.mem_of_elem_eq_true (hbwd p ((mem_pathsWithContent paths p c).mpr hp)) · rintro ⟨hiff, hnd, hlen⟩ exact ⟨⟨⟨hnd, hlen⟩, fun p hp => (hiff p).mp hp⟩, fun p hp => List.elem_eq_true_of_mem ((hiff p).mpr ((mem_pathsWithContent paths p c).mp hp))⟩ theorem map_fst_fileContentTable_sublist (paths : List String) : ((fileContentTable paths).map Prod.fst).Sublist (allFullPaths paths) := by unfold fileContentTable allFullPaths generalize (paths.filterMap parseDirInfo) = L induction L with | nil => simp | cons a L ih => obtain ⟨d, entries⟩ := a simp only [List.flatMap_cons, List.map_append, List.map_map] exact List.Sublist.append (List.sublist_cons_self _ _) ih theorem pathsWithContent_sublist (paths : List String) (c : String) : (pathsWithContent paths c).Sublist ((fileContentTable paths).map Prod.fst) := by unfold pathsWithContent generalize (fileContentTable paths) = L induction L with | nil => simp | cons a L ih => obtain ⟨p, c'⟩ := a by_cases hc : (c' == c) = true · simp only [List.filterMap_cons, List.map_cons, if_pos hc] exact List.Sublist.cons_cons _ ih · simp only [List.filterMap_cons, List.map_cons, if_neg hc] exact List.Sublist.cons _ ih theorem pathsWithContent_nodup (input : Input) (hv : isValidInput input = true) (c : String) : (pathsWithContent input c).Nodup := by have hnd : (allFullPaths input).Nodup := by rw [← nodupBool_iff] unfold isValidInput at hv simp only [Bool.and_eq_true] at hv exact hv.1.2 exact List.Nodup.sublist ((pathsWithContent_sublist input c).trans (map_fst_fileContentTable_sublist input)) hnd theorem two_distinct_of_nodup {α : Type} (l : List α) (hnd : l.Nodup) (hlen : 2 ≤ l.length) : ∃ a b, a ≠ b ∧ a ∈ l ∧ b ∈ l := by rcases l with _ | ⟨a, _ | ⟨b, t⟩⟩ · simp at hlen · simp at hlen · refine ⟨a, b, ?_, by simp, by simp⟩ intro he rw [List.nodup_cons] at hnd exact hnd.1 (by simp [he]) theorem two_le_pathsWithContent_iff (input : Input) (hv : isValidInput input = true) (c : String) : 2 ≤ (pathsWithContent input c).length ↔ ∃ p₁ p₂, p₁ ≠ p₂ ∧ FileHasContent input p₁ c ∧ FileHasContent input p₂ c := by constructor · intro hlen obtain ⟨a, b, hab, ha, hb⟩ := two_distinct_of_nodup _ (pathsWithContent_nodup input hv c) hlen exact ⟨a, b, hab, (mem_pathsWithContent input a c).mp ha, (mem_pathsWithContent input b c).mp hb⟩ · rintro ⟨p₁, p₂, hne, h1, h2⟩ have hs : ([p₁, p₂] : List String) ⊆ pathsWithContent input c := by intro x hx simp only [List.mem_cons, List.not_mem_nil, or_false] at hx rcases hx with rfl | rfl · exact (mem_pathsWithContent input x c).mpr h1 · exact (mem_pathsWithContent input x c).mpr h2 have hnd2 : ([p₁, p₂] : List String).Nodup := by simp [hne] have hle := (List.subperm_of_subset hnd2 hs).length_le simpa using hle theorem length_filter_finRange_eq_one_iff (n : Nat) (f : Fin n → Bool) : ((List.finRange n).filter f).length = 1 ↔ ∃! i : Fin n, f i = true := by have hmem : ∀ i : Fin n, i ∈ ((List.finRange n).filter f) ↔ f i = true := by intro i rw [List.mem_filter] exact ⟨fun hh => hh.2, fun hf => ⟨List.mem_finRange i, hf⟩⟩ constructor · intro hlen obtain ⟨a, ha⟩ := List.length_eq_one_iff.mp hlen refine ⟨a, (hmem a).mp (by rw [ha]; simp), ?_⟩ intro j hj have hj2 := (hmem j).mpr hj rw [ha, List.mem_singleton] at hj2 exact hj2 · rintro ⟨a, ha, huniq⟩ have hnd : ((List.finRange n).filter f).Nodup := List.Nodup.sublist List.filter_sublist (List.nodup_finRange n) have hsub : ((List.finRange n).filter f) ⊆ [a] := by intro x hx rw [List.mem_singleton] exact huniq x ((hmem x).mp hx) have h1 := (List.subperm_of_subset hnd hsub).length_le have h2 : a ∈ ((List.finRange n).filter f) := (hmem a).mpr ha have h3 : 0 < ((List.finRange n).filter f).length := List.length_pos_of_mem h2 simp only [List.length_cons, List.length_nil] at h1 omega theorem content_mem_of_isDuplicateGroup (input : Input) (g : List String) (c : String) (hg : IsDuplicateGroup input g c) : c ∈ contentsOf input := by obtain ⟨hiff, hnd, hlen⟩ := hg rcases g with _ | ⟨a, t⟩ · simp at hlen · exact (mem_contentsOf input c).mpr ⟨a, (hiff a).mp (by simp)⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem duplicateFileGroups_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : duplicateFileGroups_check input result ↔ duplicateFileGroups_spec input result := by unfold duplicateFileGroups_check duplicateFileGroups_spec simp only [Bool.and_eq_true, List.all_eq_true] constructor · rintro ⟨hA, hB⟩ refine ⟨?_, ?_⟩ · intro g hg obtain ⟨c, hc, hdg⟩ := List.any_eq_true.mp (hA g hg) exact ⟨c, (isDuplicateGroupBool_iff input g c).mp hdg⟩ · intro c hcex have hb := hB c ((mem_contentsOf input c).mpr hcex) refine ⟨?_, ?_⟩ · intro hdup rw [if_pos ((two_le_pathsWithContent_iff input h c).mpr hdup), beq_iff_eq] at hb obtain ⟨i, hi, huniq⟩ := (length_filter_finRange_eq_one_iff _ _).mp hb exact ⟨i, (isDuplicateGroupBool_iff _ _ _).mp hi, fun j hj => huniq j ((isDuplicateGroupBool_iff _ _ _).mpr hj)⟩ · intro hnodup i hdg rw [if_neg (fun hl => hnodup ((two_le_pathsWithContent_iff input h c).mp hl))] at hb have hall := List.all_eq_true.mp hb i (List.mem_finRange i) rw [Bool.not_eq_true', (isDuplicateGroupBool_iff _ _ _).mpr hdg] at hall exact Bool.noConfusion hall · rintro ⟨hA, hB⟩ refine ⟨?_, ?_⟩ · intro g hg obtain ⟨c, hdg⟩ := hA g hg exact List.any_eq_true.mpr ⟨c, content_mem_of_isDuplicateGroup input g c hdg, (isDuplicateGroupBool_iff _ _ _).mpr hdg⟩ · intro c hcm obtain ⟨h1, h2⟩ := hB c ((mem_contentsOf input c).mp hcm) by_cases hlen : 2 ≤ (pathsWithContent input c).length · rw [if_pos hlen, beq_iff_eq] obtain ⟨i, hi, huniq⟩ := h1 ((two_le_pathsWithContent_iff input h c).mp hlen) exact (length_filter_finRange_eq_one_iff _ _).mpr ⟨i, (isDuplicateGroupBool_iff _ _ _).mpr hi, fun j hj => huniq j ((isDuplicateGroupBool_iff _ _ _).mp hj)⟩ · rw [if_neg hlen] refine List.all_eq_true.mpr fun i _ => ?_ rw [Bool.not_eq_true', Bool.eq_false_iff, ne_eq] intro hcon exact h2 (fun hd => hlen ((two_le_pathsWithContent_iff input h c).mpr hd)) i ((isDuplicateGroupBool_iff _ _ _).mp hcon) /-! ### Implementation helpers -/ /-- Group file records by content in one pass, keeping each group's paths in input order and dropping contents with fewer than two files. -/ def groupByContent (records : List (String × String)) : List (List String) := let m := records.foldl (fun acc (p, c) => acc.insert c (p :: acc.getD c [])) ({} : Std.HashMap String (List String)) m.toList.filterMap fun (_, ps) => if 2 ≤ ps.length then some ps.reverse else none /-! ### Main algorithm (impl) -/ /-- Group file records by content with deterministic ordering: paths within a group appear in input order, and groups appear in reverse order of their content's first occurrence. -/ def groupByContentOrdered (records : List (String × String)) : List (List String) := let (order, m) := records.foldl (fun (order, m) (p, c) => if m.contains c then (order, m.insert c (p :: m.getD c [])) else (c :: order, m.insert c [p])) (([], {}) : List String × Std.HashMap String (List String)) order.filterMap fun c => let ps := m.getD c [] if 2 ≤ ps.length then some ps.reverse else none /-- Duplicate file groups by parsing once into (path, content) records and grouping by content with an ordered association list. -/ def findDuplicateFiles (input : Input) : Output := groupByContentOrdered (fileContentTable input) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findDuplicateFiles_correct (input : Input) (h : isValidInput input) : duplicateFileGroups_spec input (findDuplicateFiles input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"] #guard isValidInput ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)"] #guard isValidInput ["root 1.txt(a) 2.txt(ab) 3.txt(abc) 4.txt(abcd)"] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ["root/a 1.txt(a_b)"]) #guard !(isValidInput ["root/a 1.txt(x) 1.txt(y)"]) #guard !(isValidInput ["root/[a 1.txt(x)"]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard duplicateFileGroups_check ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"] [["root/a/2.txt", "root/c/d/4.txt", "root/4.txt"], ["root/a/1.txt", "root/c/3.txt"]] #guard duplicateFileGroups_check ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)"] [["root/a/2.txt", "root/c/d/4.txt"], ["root/a/1.txt", "root/c/3.txt"]] #guard duplicateFileGroups_check ["root 1.txt(a) 2.txt(ab) 3.txt(abc) 4.txt(abcd)"] [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(duplicateFileGroups_check ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"] [["root/a/2.txt", "root/c/d/4.txt", "root/4.txt"], ["root/a/1.txt", "root/c/3.txt"], ["root/a/1.txt", "root/a/2.txt"]]) #guard !(duplicateFileGroups_check ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)"] []) #guard !(duplicateFileGroups_check ["root 1.txt(a) 2.txt(ab) 3.txt(abc) 4.txt(abcd)"] [["root/1.txt", "root/2.txt"]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findDuplicateFiles ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"] == [["root/a/2.txt", "root/c/d/4.txt", "root/4.txt"], ["root/a/1.txt", "root/c/3.txt"]] #guard findDuplicateFiles ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)"] == [["root/a/2.txt", "root/c/d/4.txt"], ["root/a/1.txt", "root/c/3.txt"]] #guard findDuplicateFiles ["root 1.txt(a) 2.txt(ab) 3.txt(abc) 4.txt(abcd)"] == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard duplicateFileGroups_check ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"] (findDuplicateFiles ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]) #guard duplicateFileGroups_check ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)"] (findDuplicateFiles ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)"]) #guard duplicateFileGroups_check ["root 1.txt(a) 2.txt(ab) 3.txt(abc) 4.txt(abcd)"] (findDuplicateFiles ["root 1.txt(a) 2.txt(ab) 3.txt(abc) 4.txt(abcd)"]) end PFindDuplicateFileInSystem