import random
import unittest
from collections import Counter

from interview_lab import incident_brief, minimum_cover


def brute_brief(events, window, k, required):
    accepted, seen = [], set()
    for ticket in events:
        if ticket[0] not in seen:
            seen.add(ticket[0])
            accepted.append(ticket)
    now = events[-1][1] if events else 0
    active = [ticket for ticket in accepted if ticket[1] > now - window]
    counts = Counter(ticket[2] for ticket in active)
    best = [] if not required else None
    for left in range(len(accepted)):
        for right in range(left, len(accepted)):
            if set(required) <= {ticket[2] for ticket in accepted[left:right + 1]}:
                candidate = [ticket[0] for ticket in accepted[left:right + 1]]
                if best is None or len(candidate) < len(best):
                    best = candidate
    return {"accepted": [ticket[0] for ticket in accepted], "duplicates": len(events) - len(accepted),
            "active_count": len(active), "top": sorted(counts.items(), key=lambda pair: (-pair[1], pair[0]))[:k],
            "minimum_cover": best}


class IncidentTests(unittest.TestCase):
    def test_worked_example(self):
        events = [("a", 0, "login"), ("b", 1, "payment"), ("a", 2, "login"),
                  ("c", 3, "login"), ("d", 6, "search"), ("e", 7, "payment")]
        self.assertEqual(incident_brief(events, 5, 2, ["login", "payment"]),
            {"accepted": ["a", "b", "c", "d", "e"], "duplicates": 1,
             "active_count": 3, "top": [("login", 1), ("payment", 1)], "minimum_cover": ["a", "b"]})

    def test_empty(self):
        self.assertEqual(incident_brief([], 3, 2, ["x"]), {"accepted": [], "duplicates": 0,
            "active_count": 0, "top": [], "minimum_cover": None})
        self.assertEqual(minimum_cover([], []), [])

    def test_window_boundary_is_exclusive(self):
        result = incident_brief([("a", 0, "x"), ("b", 5, "y")], 5, 9, ["x", "y"])
        self.assertEqual((result["active_count"], result["top"]), (1, [("y", 1)]))
        self.assertEqual(result["minimum_cover"], ["a", "b"])

    def test_duplicate_still_advances_clock(self):
        result = incident_brief([("a", 0, "x"), ("a", 10, "changed")], 5, 2, ["x"])
        self.assertEqual((result["active_count"], result["top"], result["duplicates"]), (0, [], 1))
        self.assertEqual(result["minimum_cover"], ["a"])

    def test_shorter_cover_can_appear_later(self):
        events = [("a", 0, "x"), ("b", 1, "other"), ("c", 2, "y"), ("d", 3, "x")]
        self.assertEqual(incident_brief(events, 10, 2, ["x", "y"])["minimum_cover"], ["c", "d"])

    def test_missing_target_and_zero_k(self):
        result = incident_brief([("a", 0, "x")], 1, 0, ["missing"])
        self.assertEqual(result["top"], [])
        self.assertIsNone(result["minimum_cover"])

    def test_invalid_input(self):
        for events, window, k in [([], 0, 1), ([], 1, -1), ([("a", -1, "x")], 1, 1),
                ([("a", 2, "x"), ("b", 1, "y")], 1, 1)]:
            with self.subTest(events=events), self.assertRaises(ValueError):
                incident_brief(events, window, k, [])

    def test_random_streams_against_brute_force(self):
        rng = random.Random(137)
        for _ in range(150):
            now, events = 0, []
            for _ in range(rng.randrange(15)):
                now += rng.randrange(4)
                events.append((str(rng.randrange(10)), now, rng.choice("ABC")))
            window, k = rng.randint(1, 8), rng.randrange(5)
            required = rng.sample(list("ABCD"), rng.randrange(5))
            self.assertEqual(incident_brief(events, window, k, required),
                             brute_brief(events, window, k, required))


if __name__ == "__main__":
    unittest.main()