import random
import unittest

from dynamic_programming_lab import common_topics, study_plan


def is_subsequence(candidate, text):
    source = iter(text)
    return all(any(char == current for current in source) for char in candidate)


def brute_lcs(first, second):
    return max(len(candidate) for mask in range(1 << len(first))
               if is_subsequence(candidate := "".join(char for i, char in enumerate(first) if mask >> i & 1), second))


class PlannerTests(unittest.TestCase):
    def test_worked_example(self):
        lessons = [("A", 3, "AC"), ("B", 4, "ABD"), ("C", 2, "BC")]
        result = study_plan(lessons, "ABCD", 6)
        self.assertEqual(result, {"chosen": ["B", "C"], "minutes": 6, "score": 5,
            "alignment": [{"id": "A", "matched": "AC", "score": 2},
                          {"id": "B", "matched": "ABD", "score": 3},
                          {"id": "C", "matched": "BC", "score": 2}]})

    def test_no_lessons_and_zero_budget(self):
        self.assertEqual(study_plan([], "ABC", 3)["chosen"], [])
        self.assertEqual(study_plan([("A", 1, "A")], "A", 0)["score"], 0)

    def test_empty_or_unrelated_target(self):
        for target in ["", "XYZ"]:
            result = study_plan([("A", 2, "ABC")], target, 10)
            self.assertEqual((result["chosen"], result["minutes"], result["score"]), ([], 0, 0))

    def test_cannot_reuse_one_lesson(self):
        result = study_plan([("A", 2, "AB")], "AB", 20)
        self.assertEqual((result["chosen"], result["score"]), (["A"], 2))

    def test_equal_score_skips_later_lesson(self):
        result = study_plan([("first", 3, "AB"), ("later", 2, "AB")], "AB", 3)
        self.assertEqual((result["chosen"], result["minutes"]), (["first"], 3))

    def test_lcs_respects_order_and_repetition(self):
        for first, second, expected in [("AB", "BA", 1), ("AAA", "AA", 2), ("ABC", "AC", 2)]:
            match = common_topics(first, second)
            self.assertEqual(len(match), expected)
            self.assertTrue(is_subsequence(match, first))
            self.assertTrue(is_subsequence(match, second))

    def test_invalid_input(self):
        for lessons, budget in [([], -1), ([("A", 0, "A")], 2),
                ([("A", -1, "A")], 2), ([("A", 1, "A"), ("A", 2, "B")], 3)]:
            with self.subTest(lessons=lessons), self.assertRaises(ValueError):
                study_plan(lessons, "AB", budget)

    def test_random_lcs_and_knapsack_against_enumeration(self):
        rng = random.Random(126)
        for _ in range(70):
            target = "".join(rng.choices("ABC", k=rng.randrange(6)))
            lessons = [(str(i), rng.randint(1, 5), "".join(rng.choices("ABC", k=rng.randrange(6))))
                       for i in range(rng.randrange(7))]
            budget = rng.randrange(13)
            scores = [brute_lcs(topics, target) for _, _, topics in lessons]
            expected = max(sum(scores[i] for i in range(len(lessons)) if mask >> i & 1)
                           for mask in range(1 << len(lessons))
                           if sum(lessons[i][1] for i in range(len(lessons)) if mask >> i & 1) <= budget)
            result = study_plan(lessons, target, budget)
            self.assertEqual(result["score"], expected)
            self.assertEqual([row["score"] for row in result["alignment"]], scores)
            chosen = set(result["chosen"])
            self.assertEqual(len(chosen), len(result["chosen"]))
            self.assertEqual(result["minutes"], sum(minutes for identity, minutes, _ in lessons if identity in chosen))
            self.assertLessEqual(result["minutes"], budget)
            self.assertEqual(result["score"], sum(score for (identity, _, _), score in zip(lessons, scores) if identity in chosen))


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