import Mathlib /-! # Number Of Music Playlists Your music player contains n different songs. You want to listen to goal songs (not necessarily different) during your trip. To avoid boredom, you will create a playlist so that: Every song is played at least once. A song can only be played again only if k other songs have been played. Given n, goal, and k, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo 10^9 + 7. ## Constraints - 0 <= k < n <= goal <= 100 ## Provided examples - `n = 3, goal = 3, k = 1` → `6` - `n = 2, goal = 3, k = 0` → `6` - `n = 2, goal = 3, k = 1` → `2` ## Synthesized negative examples - invalid input: `n = 1, goal = 1, k = -1` ([structural] a predicate that admits 0 <= k < n <= goal <= 100. negative k; catches predicates that only check k < n) - invalid input: `n = 3, goal = 3, k = 3` ([structural] a predicate that admits 0 <= k < n <= goal <= 100. k equals n; catches <= instead of <) - invalid input: `n = 100, goal = 101, k = 0` ([structural] a predicate that admits 0 <= k < n <= goal <= 100. goal one past 100; catches predicates that cap n but forget goal) - `n = 3, goal = 3, k = 1` → `12` is wrong ([structural] the specification drops the requirement that every song is played at least once. counts all valid replay-constrained sequences, including those omitting a song) - `n = 2, goal = 3, k = 0` → `8` is wrong ([structural] drops the requirement that every song be played at least once. counts all 2^3=8 sequences, including AAA and BBB) - `n = 2, goal = 3, k = 1` → `4` is wrong ([structural] length clause read as at most goal rather than exactly goal. Counts length-2 and length-3 valid playlists, missing exact length goal.) -/ namespace PNumberOfMusicPlaylists abbrev Input := (Nat) × (Nat) × (Int) abbrev Output := Nat /-! ### Specification helpers -/ /-- `p` is a playlist of `goal` entries over `n` songs, playing every song at least once with more than `k` positions between any two plays of the same song. -/ def IsValidPlaylist (n : Nat) (goal : Nat) (k : Int) (p : List (Fin n)) : Prop := p.length = goal ∧ (∀ s : Fin n, s ∈ p) ∧ ∀ i j : Nat, i < j → j < p.length → p[i]? = p[j]? → (j : Int) - (i : Int) > k /-! ### Validity predicate (V) -/ /-- Valid input: `0 ≤ k < n ≤ goal ≤ 100`, with the `k < n` comparison in `Int`. -/ def isValidInput (input : Input) : Bool := (0 ≤ input.2.2) && (input.2.2 < (input.1 : Int)) && (input.1 ≤ input.2.1) && (input.2.1 ≤ 100) /-! ### Ideal specification (P_spec) -/ /-- `result` is the size, modulo 1,000,000,007, of a finite collection of playlists containing exactly the valid ones. -/ def numMusicPlaylists_spec (input : Input) (result : Output) : Prop := ∃ S : Finset (List (Fin input.1)), S.card % 1000000007 = result ∧ ∀ p : List (Fin input.1), p ∈ S ↔ IsValidPlaylist input.1 input.2.1 input.2.2 p /-! ### Decidable specification (P_check) -/ /-- All lists of length `goal` over `Fin n`, each exactly once. -/ def allPlaylists (n goal : Nat) : List (List (Fin n)) := match goal with | 0 => [[]] | goal + 1 => (allPlaylists n goal).flatMap fun p => (List.finRange n).map fun s => s :: p /-- Decidable gap check: any two equal entries of `p` are more than `k` positions apart. -/ def gapOk {n : Nat} (k : Int) (p : List (Fin n)) : Bool := (List.range p.length).all fun i => (List.range p.length).all fun j => if i < j ∧ p[i]? = p[j]? then decide ((j : Int) - (i : Int) > k) else true /-- Decidable mirror of `IsValidPlaylist`, with the gap quantifiers bounded by `p.length`. -/ def validPlaylistB {n : Nat} (goal : Nat) (k : Int) (p : List (Fin n)) : Bool := decide (p.length = goal) && decide (∀ s : Fin n, s ∈ p) && gapOk k p /-- The number of valid playlists of length `goal` over `n` songs with gap bound `k`. -/ def countValid (n goal : Nat) (k : Int) : Nat := ((allPlaylists n goal).filter fun p => validPlaylistB goal k p).length /-- Executable checker for `numMusicPlaylists_spec`: the valid-playlist count modulo 1,000,000,007. -/ def numMusicPlaylists_check (input : Input) (result : Output) : Bool := countValid input.1 input.2.1 input.2.2 % 1000000007 == result theorem root_of_bridges (hm : ∀ n goal (p : List (Fin n)), p ∈ allPlaylists n goal ↔ p.length = goal) (hn : ∀ n goal, (allPlaylists n goal).Nodup) (hb : ∀ n goal k (p : List (Fin n)), validPlaylistB goal k p = true ↔ IsValidPlaylist n goal k p) (input : Input) (result : Output) : numMusicPlaylists_check input result ↔ numMusicPlaylists_spec input result := by classical let L := (allPlaylists input.1 input.2.1).filter (validPlaylistB input.2.1 input.2.2) have hmem : ∀ p, p ∈ L.toFinset ↔ IsValidPlaylist input.1 input.2.1 input.2.2 p := by intro p simp only [List.mem_toFinset, L, List.mem_filter, hm, hb] exact ⟨fun h => h.2, fun h => ⟨h.1, h⟩⟩ have hcard : L.toFinset.card = countValid input.1 input.2.1 input.2.2 := by exact List.toFinset_card_of_nodup ((hn _ _).filter _) simp only [numMusicPlaylists_check, beq_iff_eq, numMusicPlaylists_spec] constructor · intro hc exact ⟨L.toFinset, (congrArg (fun x => x % 1000000007) hcard).trans hc, hmem⟩ · rintro ⟨S, hc, hs⟩ have he : S = L.toFinset := by ext p exact (hs p).trans (hmem p).symm simpa only [he, hcard] using hc theorem allPlaylists_mem (n goal : Nat) (p : List (Fin n)) : p ∈ allPlaylists n goal ↔ p.length = goal := by induction goal generalizing p with | zero => simp [allPlaylists] | succ goal ih => cases p with | nil => simp [allPlaylists, List.mem_flatMap, List.mem_map] | cons s p => simp [allPlaylists, List.mem_flatMap, List.mem_map, ih] theorem root_with_membership (hn : ∀ n goal, (allPlaylists n goal).Nodup) (hb : ∀ n goal k (p : List (Fin n)), validPlaylistB goal k p = true ↔ IsValidPlaylist n goal k p) (input : Input) (result : Output) : numMusicPlaylists_check input result ↔ numMusicPlaylists_spec input result := root_of_bridges allPlaylists_mem hn hb input result theorem allPlaylists_nodup (n goal : Nat) : (allPlaylists n goal).Nodup := by induction goal with | zero => simp [allPlaylists] | succ goal ih => rw [allPlaylists, List.nodup_flatMap] constructor · intro p hp exact (List.nodup_finRange n).map (fun a b h => (List.cons.inj h).1) · apply ih.imp intro p q hpq x hx hy rcases List.mem_map.mp hx with ⟨s, hs, rfl⟩ rcases List.mem_map.mp hy with ⟨t, ht, he⟩ exact hpq (List.cons.inj he).2.symm theorem root_with_enumeration (hb : ∀ n goal k (p : List (Fin n)), validPlaylistB goal k p = true ↔ IsValidPlaylist n goal k p) (input : Input) (result : Output) : numMusicPlaylists_check input result ↔ numMusicPlaylists_spec input result := root_with_membership allPlaylists_nodup hb input result theorem gapOk_iff {n : Nat} (k : Int) (p : List (Fin n)) : gapOk k p = true ↔ ∀ i j : Nat, i < j → j < p.length → p[i]? = p[j]? → (j : Int) - (i : Int) > k := by unfold gapOk simp only [List.all_eq_true, List.mem_range] constructor · intro h i j hij hj he have hh := h i (Nat.lt_trans hij hj) j hj simpa [hij, he] using hh · intro h i hi j hj split · next hc => simpa using h i j hc.1 hj hc.2 · rfl theorem validPlaylistB_iff (n goal : Nat) (k : Int) (p : List (Fin n)) : validPlaylistB goal k p = true ↔ IsValidPlaylist n goal k p := by simp only [validPlaylistB, Bool.and_eq_true, decide_eq_true_eq, gapOk_iff, IsValidPlaylist, and_assoc] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem numMusicPlaylists_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : numMusicPlaylists_check input result ↔ numMusicPlaylists_spec input result := by exact root_with_enumeration validPlaylistB_iff input result /-! ### Implementation helpers -/ /-- Number of already-used songs allowed to repeat: `j` when `k < 0`, else `max (j - k.toNat) 0`. -/ def usableRepeats (j : Nat) (k : Int) : Nat := if k < 0 then j else max (j - k.toNat) 0 /-- One DP row over the count of distinct songs, from the previous row, modulo 1,000,000,007. -/ def makeRow (n : Nat) (k : Int) (prev : Array Nat) : Array Nat := (List.range (n + 1)).foldl (fun acc j => let newSong := (if j = 0 then 0 else prev[j - 1]!) * (n - j + 1) let rep := prev[j]! * usableRepeats j k acc.push ((newSong + rep) % 1000000007)) #[] /-! ### Main algorithm (impl) -/ /-- Counts valid playlists by dynamic programming over prefix length and distinct songs used. -/ def countMusicPlaylists (input : Input) : Output := let n := input.1 let goal := input.2.1 let k := input.2.2 let row0 := (List.range (n + 1)).foldl (fun acc j => acc.push (if j = 0 then 1 else 0)) #[] let dp := (List.range goal).foldl (fun row _ => makeRow n k row) row0 dp[n]! /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countMusicPlaylists_correct (input : Input) (h : isValidInput input) : numMusicPlaylists_spec input (countMusicPlaylists input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (3, 3, 1) #guard isValidInput (2, 3, 0) #guard isValidInput (2, 3, 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (1, 1, (-1))) #guard !(isValidInput (3, 3, 3)) #guard !(isValidInput (100, 101, 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard numMusicPlaylists_check (3, 3, 1) 6 #guard numMusicPlaylists_check (2, 3, 0) 6 #guard numMusicPlaylists_check (2, 3, 1) 2 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(numMusicPlaylists_check (3, 3, 1) 12) #guard !(numMusicPlaylists_check (2, 3, 0) 8) #guard !(numMusicPlaylists_check (2, 3, 1) 4) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countMusicPlaylists (3, 3, 1) == 6 #guard countMusicPlaylists (2, 3, 0) == 6 #guard countMusicPlaylists (2, 3, 1) == 2 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard numMusicPlaylists_check (3, 3, 1) (countMusicPlaylists (3, 3, 1)) #guard numMusicPlaylists_check (2, 3, 0) (countMusicPlaylists (2, 3, 0)) #guard numMusicPlaylists_check (2, 3, 1) (countMusicPlaylists (2, 3, 1)) end PNumberOfMusicPlaylists