package prereqchecker;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
/**
* Steps to implement this class main method:
*
* Step 1:
* AdjListInputFile name is passed through the command line as args[0]
* Read from AdjListInputFile with the format:
* 1. a (int): number of courses in the graph
* 2. a lines, each with 1 course ID
* 3. b (int): number of edges in the graph
* 4. b lines, each with a source ID
*
* Step 2:
* AdjListOutputFile name is passed through the command line as args[1]
* Output to AdjListOutputFile with the format:
* 1. c lines, each starting with a different course ID, then
* listing all of that course's prerequisites (space separated)
*/
public class AdjList {
public static void main(String[] args) {
if (args.length < 2) {
StdOut.println("Execute: java -cp bin prereqchecker.AdjList <adjacency list INput file> <adjacency list OUTput file>");
return;
}
HashMap<String, ArrayList<String>> adjList = new HashMap<>();
StdIn.setFile(args[0]);
while (StdIn.hasNextLine()){
int courses = StdIn.readInt();
for (int i = 0; i < courses; i++) {
adjList.put(StdIn.readString(),new ArrayList<String>());
}
int connections = StdIn.readInt();
for (int i = 0; i < connections; i++){
adjList.get(StdIn.readString()).add(StdIn.readString());
}
}
StdOut.setFile(args[1]);
for (String key: adjList.keySet()){
ArrayList<String> val = adjList.get(key);
StdOut.print(key + " ");
for (String str: val)
StdOut.print(str + " ");
StdOut.println();
}
}
}
package prereqchecker;
import java.util.*;
/**
*
* Steps to implement this class main method:
*
* Step 1:
* AdjListInputFile name is passed through the command line as args[0]
* Read from AdjListInputFile with the format:
* 1. a (int): number of courses in the graph
* 2. a lines, each with 1 course ID
* 3. b (int): number of edges in the graph
* 4. b lines, each with a source ID
*
* Step 2:
* EligibleInputFile name is passed through the command line as args[1]
* Read from EligibleInputFile with the format:
* 1. c (int): Number of courses
* 2. c lines, each with 1 course ID
*
* Step 3:
* EligibleOutputFile name is passed through the command line as args[2]
* Output to EligibleOutputFile with the format:
* 1. Some number of lines, each with one course ID
*/
public class Eligible {
static HashMap<String, ArrayList<String>> adjList = new HashMap<>();
public static void main(String[] args) {
if (args.length < 3) {
StdOut.println("Execute: java -cp bin prereqchecker.Eligible <adjacency list Input file> <eligible Input file> <eligible OUTput file>");
return;
}
StdIn.setFile(args[0]);
while (StdIn.hasNextLine()){
int courses = StdIn.readInt();
for (int i = 0; i < courses; i++){
adjList.put(StdIn.readString(),new ArrayList<String>());
}
int connections = StdIn.readInt();
for (int i = 0; i < connections; i++){
adjList.get(StdIn.readString()).add(StdIn.readString());
}
}
StdIn.setFile(args[1]);
int num_Course = StdIn.readInt();
ArrayList<String> courseTaken = new ArrayList<>(num_Course);
for (int i = 0; i < num_Course; i++){
courseTaken.add(StdIn.readString());
}
StdOut.setFile(args[2]);
HashSet<String> prerequisiteCourses = getPrerequisites(courseTaken);
for (String course : adjList.keySet()){
if(eligible(course, prerequisiteCourses))
StdOut.println(course);
}
}
private static boolean eligible(String course, HashSet<String> prerequisiteCourses) {
if (!prerequisiteCourses.contains(course)){
for (String preCourse: adjList.get(course)){
if (!prerequisiteCourses.contains(preCourse))
return false;
}
return true;
}
return false;
}
private static HashSet<String> getPrerequisites(ArrayList<String> courses) {
HashSet<String> hashSet = new HashSet<>();
for (String courseTaken: courses){
for (String course: adjList.get(courseTaken)){
hashSet.add(course);
}
HashMap<String,Boolean> isVisited = new HashMap<>();
for (String key: adjList.keySet())
isVisited.put(key,false);
hashSet = DFS(courseTaken,hashSet,isVisited);
}
return hashSet;
}
private static HashSet<String> DFS(String prerequisite, HashSet<String> hashSet, HashMap<String, Boolean> isVisited){
isVisited.put(prerequisite,true);
hashSet.add(prerequisite);
Iterator<String> courses = adjList.get(prerequisite).listIterator();
while (courses.hasNext())
{
String course = courses.next();
if (!isVisited.get(course)){
DFS(course,hashSet,isVisited);
}
}
return hashSet;
}
}
package prereqchecker;
import java.util.*;
/**
* Steps to implement this class main method:
*
* Step 1:
* AdjListInputFile name is passed through the command line as args[0]
* Read from AdjListInputFile with the format:
* 1. a (int): number of courses in the graph
* 2. a lines, each with 1 course ID
* 3. b (int): number of edges in the graph
* 4. b lines, each with a source ID
*
* Step 2:
* NeedToTakeInputFile name is passed through the command line as args[1]
* Read from NeedToTakeInputFile with the format:
* 1. One line, containing a course ID
* 2. c (int): Number of courses
* 3. c lines, each with one course ID
*
* Step 3:
* NeedToTakeOutputFile name is passed through the command line as args[2]
* Output to NeedToTakeOutputFile with the format:
* 1. Some number of lines, each with one course ID
*/
public class NeedToTake {
static HashMap<String, ArrayList<String>> adjList = new HashMap<>();
public static void main(String[] args) {
if (args.length < 3) {
StdOut.println("Execute: java NeedToTake <adjacency list INput file> <need to take INput file> <need to take OUTput file>");
return;
}
StdIn.setFile(args[0]);
while (StdIn.hasNextLine()){
int courses = StdIn.readInt();
for (int i = 0; i < courses; i++){
adjList.put(StdIn.readString(),new ArrayList<String>());
}
int connections = StdIn.readInt();
for (int i = 0; i < connections; i++) {
adjList.get(StdIn.readString()).add(StdIn.readString());
}
}
StdIn.setFile(args[1]);
String targetCourse = StdIn.readString();
int num_Course = StdIn.readInt();
ArrayList<String> courseTaken = new ArrayList<>();
for (int i = 0; i < num_Course; i++){
courseTaken.add(StdIn.readString());
}
StdOut.setFile(args[2]);
HashSet<String> coursesNeedToTake = getNeedToTakeCourses(targetCourse,courseTaken);
for (String course: coursesNeedToTake){
StdOut.println(course);
}
}
private static HashSet<String> getNeedToTakeCourses(String targetCourse, ArrayList<String> courseTaken) {
HashSet<String> hashSet1 = getPrerequisites(courseTaken);
HashSet<String> hashSet2 = getPrerequisites(targetCourse);
System.out.println("hashset1: "+hashSet1);
System.out.println("hashset2: "+hashSet2);
hashSet2.removeAll(hashSet1);
hashSet2.remove(targetCourse);
System.out.println("NeedToTake: "+hashSet2);
return hashSet2;
}
private static HashSet<String> getPrerequisites(ArrayList<String> courses) {
HashSet<String> hashSet = new HashSet<>();
for (String courseTaken: courses){
for (String course: adjList.get(courseTaken)){
hashSet.add(course);
}
HashMap<String,Boolean> isVisited = new HashMap<>();
for (String key: adjList.keySet())
isVisited.put(key,false);
hashSet = DFS(courseTaken,hashSet,isVisited);
}
return hashSet;
}
private static HashSet<String> DFS(String prerequisite, HashSet<String> hashSet, HashMap<String, Boolean> isVisited){
isVisited.put(prerequisite,true);
hashSet.add(prerequisite);
Iterator<String> courses = adjList.get(prerequisite).listIterator();
while (courses.hasNext()){
String course = courses.next();
if (!isVisited.get(course)){
DFS(course,hashSet,isVisited);
}
}
return hashSet;
}
private static HashSet<String> getPrerequisites(String course2) {
HashSet<String> hashSet = new HashSet<>();
for (String course: adjList.get(course2)){
hashSet.add(course);
}
HashMap<String,Boolean> isVisited = new HashMap<>();
for(String key: adjList.keySet())
isVisited.put(key,false);
hashSet = DFS(course2,hashSet,isVisited);
return hashSet;
}
}
package prereqchecker;
import java.util.*;
/**
* Steps to implement this class main method:
*
* Step 1:
* AdjListInputFile name is passed through the command line as args[0]
* Read from AdjListInputFile with the format:
* 1. a (int): number of courses in the graph
* 2. a lines, each with 1 course ID
* 3. b (int): number of edges in the graph
* 4. b lines, each with a source ID
*
* Step 2:
* SchedulePlanInputFile name is passed through the command line as args[1]
* Read from SchedulePlanInputFile with the format:
* 1. One line containing a course ID
* 2. c (int): number of courses
* 3. c lines, each with one course ID
*
* Step 3:
* SchedulePlanOutputFile name is passed through the command line as args[2]
* Output to SchedulePlanOutputFile with the format:
* 1. One line containing an int c, the number of semesters required to take the course
* 2. c lines, each with space separated course ID's
*/
public class SchedulePlan {
public static void main(String[] args) {
if ( args.length < 3 ) {
StdOut.println("Execute: java -cp bin prereqchecker.SchedulePlan <adjacency list INput file> <schedule plan INput file> <schedule plan OUTput file>");
return;
}
}
}
package prereqchecker;
import java.util.*;
/**
* Steps to implement this class main method:
*
* Step 1:
* AdjListInputFile name is passed through the command line as args[0]
* Read from AdjListInputFile with the format:
* 1. a (int): number of courses in the graph
* 2. a lines, each with 1 course ID
* 3. b (int): number of edges in the graph
* 4. b lines, each with a source ID
*
* Step 2:
* ValidPreReqInputFile name is passed through the command line as args[1]
* Read from ValidPreReqInputFile with the format:
* 1. 1 line containing the proposed advanced course
* 2. 1 line containing the proposed prereq to the advanced course
*
* Step 3:
* ValidPreReqOutputFile name is passed through the command line as args[2]
* Output to ValidPreReqOutputFile with the format:
* 1. 1 line, containing either the word "YES" or "NO"
*/
public class ValidPrereq {
static HashMap<String, ArrayList<String>> adjList;
public static void main(String[] args) {
if (args.length < 3){
StdOut.println("Execute: java -cp bin prereqchecker.ValidPrereq <adjacency list INput file> <valid prereq INput file> <valid prereq OUTput file>");
return;
}
adjList = new HashMap<>();
StdIn.setFile(args[0]);
while (StdIn.hasNextLine()){
int courses = StdIn.readInt();
for (int i = 0; i < courses; i++){
adjList.put(StdIn.readString(),new ArrayList<String>());
}
int connections = StdIn.readInt();
for (int i = 0; i < connections; i++){
adjList.get(StdIn.readString()).add(StdIn.readString());
}
}
StdIn.setFile(args[1]);
String course1 = StdIn.readString();
String course2 = StdIn.readString();
StdOut.setFile(args[2]);
HashSet<String> courseSet = getPrerequisites(course2);
if (courseSet.contains(course1))
StdOut.print("NO");
else
StdOut.print("YES");
}
private static HashSet<String> getPrerequisites(String course2) {
HashSet<String> hashSet = new HashSet<>();
for (String course: adjList.get(course2)){
hashSet.add(course);
}
HashMap<String,Boolean> isVisited = new HashMap<>();
for (String key: adjList.keySet())
isVisited.put(key,false);
hashSet = DFS(course2,hashSet,isVisited);
return hashSet;
}
private static HashSet<String> DFS(String prerequisite, HashSet<String> hashSet, HashMap<String, Boolean> isVisited){
isVisited.put(prerequisite,true);
hashSet.add(prerequisite);
Iterator<String> courses = adjList.get(prerequisite).listIterator();
while (courses.hasNext()){
String course = courses.next();
if (!isVisited.get(course)){
DFS(course,hashSet,isVisited);
}
}
return hashSet;
}
}
Karen Li 