programming / topcoder
So, topcoder.
If you've never seen the site, you should go. It's here. Its main offering is a timed programming contest. You are assigned a room and a set of problems. You get 75 minutes to code, a 5 minute intermission, and 15 minutes to challenge another player's solution. You get points based on correctness, time, and successful challenge of another competitor's solution (i.e. proving it fails for some input). Also, you can get money for winning contests. I'm not a very fast programmer, and my Java skills are rusty (to be generous), but I've discovered that doing practice programs keeps me awake past 9PM. Problem Solving is Fun. In your face, fatigue!
Most of the problems are pretty standard -- basically, the same kinda stuff you'd get in a CS course for an assignment, most of the challenge lies in how fast you can come up with the solution. I got stuck on the third practice one briefly, a '1000 pt' problem (that means the hardest one), thinking in terms of wild sorting algorithms for linear structures before I drew a picture and was like 'oh duh that's a graph.' I'm stupid. It's been 2 years since I've done any CS. I suck.
All of the problems are (c) topcoder, so technically I'm not supposed to reprint here, but frankly I don't see what's so original about this one, nor do I really believe in copywriting what boils down to a math problem. But intellectual property discussion is outside of this conversation. :)
Instead, I'll paraphrase:
You are in school. You have classes (of the academic kind). These classes have prerequisites. You want to take classes in an order that makes sense (i.e., make sure you take the prerequisites first). You write a program to do so.
The object is to create a class "Prerequisites" with a method
String[] orderClasses(String[] classSchedule) { ... }
'classSchedule' is a String array with the following format:
"classname: prereq1 prereq2 ..."
Each class is composed of a 3-4 letter department name and 3 digit number. You have to sort the classes so that you take the classes in necessary order. I.e., a) you have to take the prerequisites to a class before you take a class, b) lowest class numbers you take first, c) if two classes have the same number, you take the class with the department that comes first in alphabetical order.
You return the array of strings that represents the order in which you'd take classes.
So:
If classSchedule={
"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:"
}
The method should return:
{"INTR100","CSE101","CSE111","ECE111","ECE201","MATH210","CSE254","CSE221","CSE2
43","CSE244","CSE258"}
If a class is listed, and a prerequisite isn't, then you return an empty String array. If it's impossible to calculate the correct order:
e.g. if you had an input of
"ENGL111: ENGL110",
"ENGL110: ENGL111"
then return an empty String array.
I'm thinking of all these silly ways to do it -- why not first sort by ascending class number/dept name, then iterate through each class, promoting each class forward if class[i] is not a prerequisite of class[i + 1]? Uh wait that's so wrong.
Then I drew a picture from a set of sample inputs.
Once I realized I was being an idiot and saw this right away as a directed graph, the problem became easy to solve. If there was a bad input that meant there was a cycle in the graph (in the case of last example I discussed), or a node that didn't exist (for the previous). The Internet provided me with my refresher on a topological sort algorithm for a graph, which I had to implement a class for, since AFAIK Java doesn't have it one its base utils.
I won't paste my code here, because who's going to read it but I guess if you want it, you can leave a comment.
The lesson of the day is: draw a picture! It helps.
If you've never seen the site, you should go. It's here. Its main offering is a timed programming contest. You are assigned a room and a set of problems. You get 75 minutes to code, a 5 minute intermission, and 15 minutes to challenge another player's solution. You get points based on correctness, time, and successful challenge of another competitor's solution (i.e. proving it fails for some input). Also, you can get money for winning contests. I'm not a very fast programmer, and my Java skills are rusty (to be generous), but I've discovered that doing practice programs keeps me awake past 9PM. Problem Solving is Fun. In your face, fatigue!
Most of the problems are pretty standard -- basically, the same kinda stuff you'd get in a CS course for an assignment, most of the challenge lies in how fast you can come up with the solution. I got stuck on the third practice one briefly, a '1000 pt' problem (that means the hardest one), thinking in terms of wild sorting algorithms for linear structures before I drew a picture and was like 'oh duh that's a graph.' I'm stupid. It's been 2 years since I've done any CS. I suck.
All of the problems are (c) topcoder, so technically I'm not supposed to reprint here, but frankly I don't see what's so original about this one, nor do I really believe in copywriting what boils down to a math problem. But intellectual property discussion is outside of this conversation. :)
Instead, I'll paraphrase:
You are in school. You have classes (of the academic kind). These classes have prerequisites. You want to take classes in an order that makes sense (i.e., make sure you take the prerequisites first). You write a program to do so.
The object is to create a class "Prerequisites" with a method
String[] orderClasses(String[] classSchedule) { ... }
'classSchedule' is a String array with the following format:
"classname: prereq1 prereq2 ..."
Each class is composed of a 3-4 letter department name and 3 digit number. You have to sort the classes so that you take the classes in necessary order. I.e., a) you have to take the prerequisites to a class before you take a class, b) lowest class numbers you take first, c) if two classes have the same number, you take the class with the department that comes first in alphabetical order.
You return the array of strings that represents the order in which you'd take classes.
So:
If classSchedule={
"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:"
}
The method should return:
{"INTR100","CSE101","CSE111","ECE111","ECE201","MATH210","CSE254","CSE221","CSE2
43","CSE244","CSE258"}
If a class is listed, and a prerequisite isn't, then you return an empty String array. If it's impossible to calculate the correct order:
e.g. if you had an input of
"ENGL111: ENGL110",
"ENGL110: ENGL111"
then return an empty String array.
I'm thinking of all these silly ways to do it -- why not first sort by ascending class number/dept name, then iterate through each class, promoting each class forward if class[i] is not a prerequisite of class[i + 1]? Uh wait that's so wrong.
Then I drew a picture from a set of sample inputs.
Once I realized I was being an idiot and saw this right away as a directed graph, the problem became easy to solve. If there was a bad input that meant there was a cycle in the graph (in the case of last example I discussed), or a node that didn't exist (for the previous). The Internet provided me with my refresher on a topological sort algorithm for a graph, which I had to implement a class for, since AFAIK Java doesn't have it one its base utils.
I won't paste my code here, because who's going to read it but I guess if you want it, you can leave a comment.
The lesson of the day is: draw a picture! It helps.