Create_a_1st_solution.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a708c4fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import random\n",
    "from collections import defaultdict\n",
    "from typing import Iterable, List, Set, Iterator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d87faf62",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'pandas.core.frame.DataFrame'>\n",
      "Int64Index: 244 entries, 0 to 243\n",
      "Data columns (total 10 columns):\n",
      " #   Column            Non-Null Count  Dtype \n",
      "---  ------            --------------  ----- \n",
      " 0   Student ID        244 non-null    object\n",
      " 1   Credits Required  244 non-null    int64 \n",
      " 2   0                 244 non-null    object\n",
      " 3   1                 244 non-null    object\n",
      " 4   2                 244 non-null    object\n",
      " 5   3                 244 non-null    object\n",
      " 6   4                 244 non-null    object\n",
      " 7   5                 244 non-null    object\n",
      " 8   6                 244 non-null    object\n",
      " 9   7                 244 non-null    object\n",
      "dtypes: int64(1), object(9)\n",
      "memory usage: 21.0+ KB\n",
      "<class 'pandas.core.frame.DataFrame'>\n",
      "Int64Index: 46 entries, 0 to 45\n",
      "Data columns (total 5 columns):\n",
      " #   Column        Non-Null Count  Dtype \n",
      "---  ------        --------------  ----- \n",
      " 0   Course ID     46 non-null     object\n",
      " 1   Min Students  46 non-null     int64 \n",
      " 2   Max Students  46 non-null     int64 \n",
      " 3   Time Slot     46 non-null     int64 \n",
      " 4   Credits       46 non-null     int64 \n",
      "dtypes: int64(4), object(1)\n",
      "memory usage: 2.2+ KB\n",
      "<class 'pandas.core.frame.DataFrame'>\n",
      "Int64Index: 244 entries, 0 to 243\n",
      "Data columns (total 10 columns):\n",
      " #   Column            Non-Null Count  Dtype \n",
      "---  ------            --------------  ----- \n",
      " 0   Student ID        244 non-null    object\n",
      " 1   Credits Required  244 non-null    int64 \n",
      " 2   0                 244 non-null    object\n",
      " 3   1                 244 non-null    object\n",
      " 4   2                 244 non-null    object\n",
      " 5   3                 244 non-null    object\n",
      " 6   4                 244 non-null    object\n",
      " 7   5                 244 non-null    object\n",
      " 8   6                 244 non-null    object\n",
      " 9   7                 244 non-null    object\n",
      "dtypes: int64(1), object(9)\n",
      "memory usage: 21.0+ KB\n",
      "<class 'pandas.core.frame.DataFrame'>\n",
      "Int64Index: 46 entries, 0 to 45\n",
      "Data columns (total 5 columns):\n",
      " #   Column        Non-Null Count  Dtype \n",
      "---  ------        --------------  ----- \n",
      " 0   Course ID     46 non-null     object\n",
      " 1   Min Students  46 non-null     int64 \n",
      " 2   Max Students  46 non-null     int64 \n",
      " 3   Time Slot     46 non-null     int64 \n",
      " 4   Credits       46 non-null     int64 \n",
      "dtypes: int64(4), object(1)\n",
      "memory usage: 2.2+ KB\n"
     ]
    }
   ],
   "source": [
    "%run Programming_project_cleaning_and_formatting.ipynb\n",
    "%run getValue_functions_and_Initial_solution.ipynb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b876e00c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_timeslots(courses: Iterable[str]) -> Set[int]:\n",
    "    \"\"\"Return the timeslots for the given courses.\n",
    "    \"\"\"\n",
    "    if not courses: return set()\n",
    "    timeslots = set()\n",
    "    for course in courses:\n",
    "        timeslots.add(getTimeSlotForCourse(course))\n",
    "    return timeslots\n",
    "\n",
    "def sum_credits(courses: Iterable[str]) -> int:\n",
    "    \"\"\"Return the total amount of credits for the given courses.\n",
    "    \"\"\"\n",
    "    if courses:\n",
    "        return sum(getCreditsForCourse(course) for course in courses)\n",
    "    else: \n",
    "        return 0\n",
    "\n",
    "def next_preferred_course(s_id: str, preferences: Iterator[str]) -> str:\n",
    "    \"\"\"Return the next course in the preffered list that is available, otherwise None.\n",
    "    \"\"\"\n",
    "    next_course = next(preferences, None)\n",
    "    if next_course:\n",
    "        if is_available(next_course, s_id):\n",
    "            return next_course\n",
    "        else:\n",
    "            return next_preferred_course(s_id, preferences)\n",
    "    else:\n",
    "        return None\n",
    "\n",
    "def add_student_course(s_id: str, c_id: str) -> None:\n",
    "    \"\"\"Add a student to a course and the course to the students list.\n",
    "    \"\"\"\n",
    "    sol_students[s_id].append(c_id)\n",
    "    sol_courses[c_id].append(s_id)\n",
    "\n",
    "def remove_student_course(s_id: str, c_id: str) -> None:\n",
    "    \"\"\"Remove a student-course pair.\n",
    "    \"\"\"\n",
    "    sol_students[s_id].remove(c_id)\n",
    "    sol_courses[c_id].remove(s_id)\n",
    "    \n",
    "def credits_assigned(s_id) -> int:\n",
    "    \"\"\"Return the amount of assigned credits for the student.\n",
    "    \"\"\"\n",
    "    return sum_credits(sol_students[s_id])\n",
    "    \n",
    "def credits_needed(s_id: str) -> int:\n",
    "    \"\"\"Return how many credits a student still needs.\n",
    "    \"\"\"\n",
    "    return getCreditsRequiredForStudent(s_id) - credits_assigned(s_id)\n",
    "\n",
    "def delete_course(c_id: str) -> None:\n",
    "    \"\"\"Delete a course from the solutions.\n",
    "    \"\"\"\n",
    "    for s_id in sol_courses[c_id]: # remove the course from the students' lists\n",
    "        sol_students[s_id].remove(c_id)\n",
    "    \n",
    "    del sol_courses[c_id] # remove the course from the course list\n",
    "\n",
    "def is_available(c_id: str, s_id: str) -> bool:\n",
    "    \"\"\"Return whether the course is available for the student.\n",
    "    \"\"\"\n",
    "    return getTimeSlotForCourse(c_id) not in get_timeslots(sol_students[s_id]) and len(sol_courses[c_id]) < getMaxStudentsForCourse(c_id)\n",
    "\n",
    "def fix_overloaded_students() -> None:\n",
    "    \"\"\"Remove the last course in a students list that is not needed for their credits.\n",
    "    \"\"\"\n",
    "    for s_id in sol_students.keys():\n",
    "        index = len(sol_students[s_id])-1\n",
    "        needed = credits_needed(s_id)\n",
    "        while needed < 0 and index >= 0:\n",
    "            if getCreditsForCourse(sol_students[s_id][index]) <= -needed:\n",
    "                remove_student_course(s_id, sol_students[s_id][index])\n",
    "                needed = credits_needed(s_id)\n",
    "            index -= 1\n",
    "\n",
    "def get_not_enough_credits():\n",
    "    \"\"\"Return a list of students who do not have enough credits.\n",
    "    \"\"\"\n",
    "    return [s_id for s_id in getAllStudents() if credits_needed(s_id) > 0]\n",
    "\n",
    "def get_not_enough_students():\n",
    "    \"\"\"Return a list of courses which do not have enough students.\n",
    "    \"\"\"\n",
    "    return list(filter(lambda c_id: len(sol_courses[c_id]) < getMinStudentsForCourse(c_id), sol_courses.keys()))\n",
    "\n",
    "def student_sort_function(s_id):\n",
    "    \"\"\"Return the score to sort a student by;\n",
    "    the lowest score will be sorted first.\n",
    "    \"\"\"\n",
    "    return -getCreditsRequiredForStudent(s_id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "47924d5a",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "def assign_students_by_preference():\n",
    "    \"\"\"Generate a first try of a solution based on preference lists.\n",
    "    \"\"\"\n",
    "    # Keep track of students that need to be distributed\n",
    "    to_be_distributed = getAllStudents()\n",
    "    random.shuffle(to_be_distributed)\n",
    "    to_be_distributed.sort(key=student_sort_function)\n",
    "\n",
    "    # Get dict of iterators of preferred courses\n",
    "    preferences = dict((s_id, iter(getListOfPreferedCourses(s_id))) for s_id in to_be_distributed) \n",
    "\n",
    "    # Every student gets their most preferred courses if available\n",
    "    while to_be_distributed:\n",
    "        s_id = to_be_distributed[0]\n",
    "\n",
    "        available_course = next_preferred_course(s_id, preferences[s_id])\n",
    "\n",
    "        if available_course: # If there is an available course, use it\n",
    "            add_student_course(s_id, available_course)\n",
    "\n",
    "            if credits_needed(s_id) <= 0: to_be_distributed.remove(s_id) # Get rid of student with enough credits\n",
    "\n",
    "        else: # If there is no available course, move the student\n",
    "            to_be_distributed.remove(s_id)\n",
    "            not_enough_credits.append(s_id)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "5a1ab3e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Fix all students\n",
    "def assign_students(students_left: List[str], underfilled_courses: List[str]):\n",
    "    \n",
    "    while students_left:\n",
    "        s_id = students_left.pop(0)\n",
    "\n",
    "        if underfilled_courses: # some courses are underfilled\n",
    "            \n",
    "            for c_id in underfilled_courses:\n",
    "                if c_id not in sol_students[s_id]: # find first underfilled course\n",
    "                    \n",
    "                    add_student_course(s_id, c_id) # add student to the course\n",
    "                    \n",
    "                    if credits_needed(s_id) > 0: # student still needs credits\n",
    "                        students_left.append(s_id)\n",
    "                        \n",
    "                    if getMinStudentsForCourse(c_id) <= len(sol_courses[c_id]): # Course has enough students\n",
    "                        underfilled_courses.remove(c_id)\n",
    "                    break\n",
    "        else: # all courses are filled\n",
    "            \n",
    "            for c_id in sol_courses.keys():\n",
    "                # find first course that is not full\n",
    "                if is_available(c_id, s_id):\n",
    "                    add_student_course(s_id, c_id)\n",
    "                    break\n",
    "            \n",
    "            if credits_needed(s_id) > 0: # Student still needs credits\n",
    "                students_left.append(s_id)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "28ac4f60",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Fix courses with too few students\n",
    "\n",
    "# While there still are underfilled courses, fix this\n",
    "def fix_underfilled_courses():\n",
    "    \"\"\"Make sure all courses have enough students.\n",
    "    \"\"\"\n",
    "    while not_enough_students:\n",
    "        removed_course = not_enough_students.pop(0) # Pick the course to remove\n",
    "        new_students = sol_courses[removed_course] # Find the students in this course\n",
    "        for s_id in new_students: remove_student_course(s_id, removed_course) # Delete connections between students/course\n",
    "        delete_course(removed_course) # Remove the course from the solution\n",
    "\n",
    "        not_enough_credits = list(st for st in new_students if getCreditsRequiredForStudent(st) < sum_credits(sol_students[st]))\n",
    "        assign_students(not_enough_credits, not_enough_students)\n",
    "        fix_overloaded_students()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d1389828",
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_solution():\n",
    "    \"\"\"Create a full solution.\n",
    "    \"\"\"\n",
    "    \n",
    "    assign_students_by_preference()\n",
    "\n",
    "    fix_overloaded_students()\n",
    "    \n",
    "    not_enough_credits = get_not_enough_credits()\n",
    "    not_enough_students = get_not_enough_students()\n",
    "    \n",
    "    assign_students(not_enough_credits, not_enough_students)\n",
    "    \n",
    "    fix_overloaded_students()\n",
    "    fix_underfilled_courses()\n",
    "    \n",
    "    return dict(sol_students), dict(sol_courses)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b77a1e26",
   "metadata": {},
   "outputs": [],
   "source": [
    "sol_students = defaultdict(list)\n",
    "sol_courses = defaultdict(list)\n",
    "not_enough_credits = get_not_enough_credits()\n",
    "not_enough_students = get_not_enough_students()\n",
    "sol_students, sol_courses = create_solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "bfe358c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Investigate students\n",
    "for s_id, courses in sol_students.items():\n",
    "    if credits_needed(s_id) > 0:\n",
    "        print(f'Student: {s_id}; Required: {getCreditsRequiredForStudent(s_id)}; has: {sum_credits(courses)}; course credits: {[(course, getCreditsForCourse(course)) for course in courses]}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "6b237d1b",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "df_courses = pd.DataFrame(dict([(c_id, pd.Series(students)) for c_id, students in sol_courses.items()]))\n",
    "df_students = pd.DataFrame(dict([(s_id, pd.Series(courses)) for s_id, courses in sol_students.items()]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "e6f5d510",
   "metadata": {},
   "outputs": [],
   "source": [
    "with pd.ExcelWriter('output.xlsx') as writer:\n",
    "    df_courses.to_excel(writer, sheet_name='Courses', index=False)\n",
    "    df_students.transpose().to_excel(writer, sheet_name='Students')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "320c428c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# we could look at students who already have enough credits but also have\n",
    "# an underfilled course in their preferences to switch between"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}