TopCoder Inv 2001 R1 - Prerequisites

資訊

路徑：Tournament \ 1-16 \ 1 - Inv 2001 R1 \ Prerequisites
分數：1000

題目

程式介面

Class Name: Prerequisites
Mathod Name: orderClasses
Parameters: String[]
Returns: String[]
Method signature: string[] orderClasses(string[] classSchedule)

說明

學生在大學修課時，會遇到複雜的先修課問題，也就是某些課會有要求需先修完另外某些課後才能修，所以我們來寫一支幫助排定修課續順的程式。程式會輸入字串陣列，每一筆資料表示課程與此課程的先修課，格式大致如下：

1	{系所代碼}{課號}: {先修課} {先修課}

例如

1	CSE111: CSE110 MATH101

請依據以下規則排出修課的順序：

課程的先修課必須全部修過後才能修。
同時有多個課程可以修時，先修課號數字小的。
承上，如果數字相同時，則先修系所代碼按字母排序先的。
當輸入資料錯誤時，回傳空的字串陣列。例如無法修完先修課或是先修課不存在。

系統保證輸入

系所代碼：3 或 4 個字母 [A-Z]。
課號：100-999。
如果沒有先修課會以冒號結尾。

範例

輸入：{
"CSE121: CSE110",
"CSE110:",
"MATH122:",
}
輸出：{"CSE110","CSE121","MATH122"}

輸入：{
"ENGL111: ENGL110",
"ENGL110: ENGL111"
}
輸出：{}

輸入：{
"ENGL111: ENGL110"
}
輸出：{}

輸入：{
"CSE258: CSE244 CSE243 INTR100"
"CSE221: CSE254 INTR100"
"CSE254: CSE111 MATH210 INTR100"
"CSE244: CSE243 MATH210 INTR100"
"MATH210: INTR100"
"CSE101: INTR100"
"CSE111: INTR100"
"ECE201: CSE111 INTR100"
"ECE111: INTR100"
"CSE243: CSE254"
"INTR100:"
}
輸出：{"INTR100","CSE101","CSE111","ECE111","ECE201","MATH210","CSE254","CSE221","CSE243","CSE244","CSE258"}

解法

聽起來類似遊戲的技能樹，要學會 B 技能前先要學會 A 技能，很容易就想要去記錄使用者學習的狀態，找出下一個可以學習的，不過實際上真的這樣子想去寫的話就太複雜，畢竟不是要開發甚麼系統。這邊我利用簡單的減法反向思考，使用過濾和排序逐一取出下一個課程，並將課程從清單中刪去。

語法

採用較易理解的寫法，效能並非最好

using System;
using System.Collections.Generic;
using System.Text;

namespace Prerequisites
{
    class Prerequisites
    {
        public string[] orderClasses(string[] classSchedule)
        {
            try
            {
                List<string> result = new List<string>();

                // parse
                Dictionary<string, List<string>> courses = new Dictionary<string, List<string>>();
                foreach (string line in classSchedule)
                {
                    string[] tmp = line.Split(':');
                    courses[tmp[0]] = new List<string>(tmp[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries));
                }

                string course = Next(courses);
                while (course != null)
                {
                    result.Add(course);
                    // 將修過的課從先修課中刪除
                    courses.Remove(course);
                    foreach (List<string> prerequisites in courses.Values)
                        prerequisites.Remove(course);
                    course = Next(courses);
                }
                if(courses.Count > 0)
                    return new string[0];
                return result.ToArray();
            }
            catch
            {
                return new string[0];
            }
        }

        private string Next(Dictionary<string, List<string>> courses)
        {
            // filter
            List<string> candidates = new List<string>();
            foreach (KeyValuePair<string, List<string>> pair in courses)
                if (pair.Value.Count == 0)
                    candidates.Add(pair.Key);

            if (candidates.Count == 0)
                return null;

            candidates.Sort(Compare);
            return candidates[0];
        }

        private int Compare(string cousre1, string course2)
        {
            int num1 = int.Parse(cousre1.Substring(cousre1.Length - 3));
            int num2 = int.Parse(course2.Substring(course2.Length - 3));
            if (num1 == num2)
            {
                string code1 = cousre1.Remove(cousre1.Length - 3);
                string code2 = course2.Remove(course2.Length - 3);
                return code1.CompareTo(code2);
            }
            else
                return num1.CompareTo(num2);
        }
    }
}