import random
def generate_timetable(streams, subjects, teacher_subjects):

    DAYS = ["Monday","Tuesday","Wednesday","Thursday","Friday"]

    PERIODS = [
        "P1","P2","P3","P4","BREAK",
        "P6","P7","P8","P9","LUNCH",
        "P11","P12"
    ]

    FRIDAY_PERIODS = ["P1","P2","P3","P4","BREAK","P6","P7"]

    MORNING_PERIODS = ["P1","P2","P3","P4"]

    # ------------------------------------
    # Helper: periods per day
    # ------------------------------------
    def get_periods_for_day(day):
        return FRIDAY_PERIODS if day == "Friday" else PERIODS

    # ------------------------------------
    # INITIALIZE EMPTY TIMETABLE
    # ------------------------------------
    timetable = {
        day: {
            stream.id: {p: None for p in PERIODS}
            for stream in streams
        }
        for day in DAYS
    }

    # Lock break & lunch
    for day in DAYS:
        for stream in streams:
            timetable[day][stream.id]["BREAK"] = "BREAK"
            timetable[day][stream.id]["LUNCH"] = "LUNCH"

    # ------------------------------------
    # Teacher busy map
    # ------------------------------------
    teacher_busy = {
        teacher.id: {day: set() for day in DAYS}
        for teacher in {ts.teacher for ts in teacher_subjects}
    }

    # ------------------------------------
    # Find teacher
    # ------------------------------------
    def get_teacher(subject, stream, day, period):
        for ts in teacher_subjects:
            if (
                ts.subject_id == subject.exam_subject_id
                and ts.stream_id == stream.id
                and period not in teacher_busy[ts.teacher_id][day]
            ):
                return ts.teacher
        return None

    # ------------------------------------
    # ALLOCATION FUNCTION
    # ------------------------------------



    def allocate(subject_queryset, periods):
        print("ALLOCATE called with periods:", periods)

        for subject in subject_queryset:
            for stream in streams:
                remaining = subject.weekly_periods
                print(f"Allocating subject {subject.exam_subject.subject_code} "
                      f"for stream {stream.id}, remaining={remaining}")

                for day in DAYS:
                    for period in periods:
                        if remaining <= 0:
                            break

                        if timetable[day][stream.id][period] is None:
                            teacher = get_teacher(subject, stream, day, period)
                            if teacher:
                                timetable[day][stream.id][period] = {
                                    "name": (
                                        subject.exam_subject.subject_shortname
                                        or subject.exam_subject.subject_name_eng
                                    ),
                                    "color": subject.exam_subject.color_code,
                                }
                                teacher_busy[teacher.id][day].add(period)
                                remaining -= 1

                                print(
                                    f"PLACED: {subject.exam_subject.subject_code} "
                                    f"{day} {period} stream={stream.id}"
                                )




    # ------------------------------------
    # 1️⃣ MORNING PRIORITY SUBJECTS
    # ------------------------------------
    allocate(
        subjects.filter(morning_priority=True),
        MORNING_PERIODS
    )

    # ------------------------------------
    # 2️⃣ OTHER SUBJECTS
    # ------------------------------------
    allocate(
        subjects.filter(morning_priority=False),
        [p for p in PERIODS if p not in ["BREAK", "LUNCH"]]
    )

    return timetable