Coursetree 1.5

New Features:

• Successor relationships
• Textbooks by ISBN from the bookstore
• Department requirements
• 2 clicks at most to look up information on a course
• Intelligent back button behavior
• Links to Wikipedia
• HTML5 semantic markup

Bugfixes:

• All issues listed in the previous release notes
• Phrase “one of” being missed by the scraper
• Parser can handle phrases such as “taken prior to”
• M(y)isunderstanding regarding commas corrected
  • CS 136 or 145, MATH 135
  • now becomes (CS 136 or 145) and MATH 135
  • should see more prerequisites listed as a result
• Courses being overwritten by labs

Bugs:

• A couple of quirks showing up as errors in the parser
  • EARTH 121, 121L or 122, 122L should be interpreted as EARTH 121/EARTH 122
  • CHEM 264 or 28/262 should be interpreted as CHEM 264/CHEM 282/CHEM262
• Courses overlapping in the prerequisite graph

Waterloo Course Planner has been tested and works on IE8, Firefox 3.6, Chrome 9, Safari 5, and Opera 11.

Coursetree 1.0

Features:

• All of the courses in the course calendar, categorized by department
• Displays course title and description
• Color codes for the time of the year a course is offered
• Less clicks to look up information on a course
• Draws prerequisite diagram
• Nodes can be toggled to show an alternative list of prerequisites

Bugs:

• Some courses were rejected by the scraper
• Some courses are missing prerequisites, possibly a parsing issue
• Due to the above two bugs, some prerequisites won’t show
• Some nodes at the bottom of the prerequisite tree appear to be transparent

Recommended browsers for Waterloo Course Planner: Firefox, Chrome, and Opera.

For this part of the project, the goal is to generate a list of courses that meets the requirements for a course from a string stored in the database in a specific format. The entire project was designed so that each component is modular. This way, each component could be written and tested independently, and the complexity of the task is greatly reduced. Likewise, the project consists of so many high level components it appears, at first glance, to be incapable of being one piece. To my surprise, I put together Scrapy + PLY + Django, and it all works beautifully.

Part of the reason these separate components can all come together is that the specifications were set in stone before design, and the design itself (choosing the web framework, scraper, compiler) is tailored with the whole in mind. So for this part, these are the requirements:

From a string of prerequisites separated by commas, with alternatives separated by slashes, generate a list of lists that represents all possible course combinations, without more than one course selected out of each group of alternatives.

Basically, it’s a combination of a list of lists of strings.
 

Once the goal was set, the coding phase was straightforward. Simply understand the meaning of the input, and use a python function to turn it into the specified output.

Can you imagine anything useful coming out of this line of code?

I can, because I’ve seen it. Here’s a small slice:

MATH 137 or 147
 ACTSC 231, STAT 230 or 240
MATH 136 or 146
ACTSC 232
ACTSC 371
AFM 272;ACTSC 291
STAT 330, 333
STAT 330, 333
 ACTSC 331, STAT 330
AFM 372;ACTSC 391;ACTSC 231;ACTSC 231 and BUS 393;STAT 330;STAT 334
AFM 372;ACTSC 391;ACTSC 231;ACTSC 231 and BUS 393;STAT 333 or 334
ACTSC 331
AFM 101 or BUS 227
AFM 101

A master piece at its time, and quite decent to maintain with the documentation:

And a light comes through. There is a better way, better than I ever imagined. In fact, the ugly phase of evolution comes before the flowering. A metaphor for this would be the pollution during industrialization and a bloom of clean industries following it due to the emphasis on knowledge rather than machine labor.
Simply pass on the parenthesis in the lexer and rewrite the grammar so that it can see more of the input before having to make a decision for shift/reduce conflicts. This is similar to using a parser with more lookahead, an oracle that sees infinitely many steps ahead.

Yet, no matter how sweet the code,

it is time to part ways.

What comes next,

no one knows.

This age is past,

and the ground is laid for the next one.

PLY is a Python implementation of Lex and Yacc originally written for Unix. Previously, I used it for tokenizing prerequisite strings. The goal is to have a program that performs the following trick:

At first glance, it looks like a simple task. Just replace “,” “and” with “,”, and replace “/” “or” with “/”. Regular expressions could do that. Then there comes the issue with the comma and its interpretation depending on the level in the hierarchy. So using PLY to do the same thing turned out to be much easier, since grammar rules are used instead of regular expressions. I put together a quick prototype in an hour.

That’s pretty good for a start, but doesn’t get much better for interpreting the input correctly.

Output:

('SEMI', ('SEMI', ('COMMA', 'CHEM 120', '123'), ('OR', ('COMMA', 'PHYS 111', '121'))), ('OR', ('COMMA', 'PHYS 112', '122')))
('OR', ('OR', ('OR', ('OR', ('OR', ('COMMA', ('OR', ('COMMA', 'EARTH 121', '121L'), '122'), '122L'), '153'), 'CIVE 153'), 'CIVE 253'), 'GEOE 153'), 'ENVE 153')
('OR', ('OR', 'PHYS 112', '122'), '125')
('COMMA', ('OR', 'CHEM 254', 'EARTH 421'), 'CHEM 350')
('AND', ('AND', ('OR', ('COMMA', ('COMMA', 'PHYS 112', '122'), '125')), ('OR', ('COMMA', ('COMMA', ('COMMA', ('COMMA', 'MATH 118', '119'), '128'), '138'), '148'))), ('OR', ('COMMA', ('COMMA', ('COMMA', ('COMMA', ('COMMA', ('COMMA', ('COMMA', 'AMATH 250', '350'), 'CIVE 222'), 'ENVE 223'), 'MATH 218'), '228'), 'ME 203'), 'SYDE 211')))
('OR', ('COMMA', ('COMMA', ('COMMA', 'PSCI 250', '255'), '260'), '264'))
('OR', ('COMMA', ('COMMA', ('SLASH', 'ANTH 201', 'CLAS 221'), 'ANTH 203'), '233'))
('OR', ('OR', ('COMMA', ('OR', 'MATH 135', '145'), 'STAT 220'), '230'), '240')
(('AND', 'AMATH 250', ('OR', 'MATH 237', '247')), 'Level 3A')
Syntax error at 'LexToken(LPARENS,'(',1,16)'
Syntax error at 'LexToken(RPARENS,')',1,32)'
None
('COMMA', ('OR', 'CS 240', 'SE 240'), ('COMMA', 'CS 246', 'ECE 222'))
Syntax error at 'LexToken(LPARENS,'(',1,8)'
Syntax error at 'LexToken(RPARENS,')',1,25)'
None
('AND', ('OR', ('SLASH', ('SLASH', 'AMATH 341', 'CM 271'), 'CS 371'), 'CS 370'), ('OR', ('OR', 'MATH 128', '138'), '148'))
('OR', ('OR', ('COMMA', ('OR', 'MATH 135', '145'), 'STAT 220'), '230'), '240')
('AND', 'AMATH 250', 'MATH 237')
('AND', ('OR', ('COMMA', 'BIOL 140', 'BIOL 208'), '330'), ('OR', 'BIOL 308', '330'))
('AND', ('OR', ('OR', 'MATH 229', '239'), '249'), ('OR', ('SLASH', ('COMMA', ('COMMA', ('SLASH', ('COMMA', 'CO 227', '250'), '350'), '355'), 'CO 352'), 'CM 340')))
('COMMA', ('OR', 'CS 240', 'SE 240'), ('COMMA', 'CS 246', 'ECE 222'))
('AND', 'CS 241', ('OR', ('OR', 'STAT 206', '230'), '240'))

This was the BNF grammar encoded:

prereq : cp
cp  : cp AND cgparens
	| cp COMMA cgparens
	| cp COMMA AND cgparens
	| cp SEMI cgparens
	| cp SEMI AND cgparens
	| cg
cg : cg OR courses
   | cg SLASH courses
   | cg COMMA courses
   | cg COMMA OR courses
   | LPARENS cg RPARENS
   | ONE OF cg
   | courses
courses : courses OR course
	   | courses SLASH course
	   | courses COMMA course
	   | course
course : DEPT NUM
	   | NUM

, which gives a surprising error whenever parenthesis appeared:

yacc.py: 389:Action : Reduce rule [course -> DEPT NUM] with ['BIOL','140'] and goto state 23
   yacc.py: 423:Result :  ('BIOL 140')
   yacc.py: 389:Action : Reduce rule [courses -> course] with ['BIOL 140'] and goto state 22
   yacc.py: 423:Result :  ('BIOL 140')
   yacc.py: 389:Action : Reduce rule [course -> NUM] with ['140L'] and goto state 24
   yacc.py: 423:Result :  ('140L')
   yacc.py: 389:Action : Reduce rule [courses -> courses COMMA course] with ['BIOL 140',',','140L'] and goto state 21
   yacc.py: 423:Result :  (('COMMA', 'BIOL 140', '140L'))
   yacc.py: 493:Error  : courses COMMA . LexToken(LPARENS,'(',1,16)
   yacc.py: 493:Error  : courses COMMA . error
   yacc.py: 493:Error  : courses . error
   yacc.py: 493:Error  : . error
   yacc.py: 389:Action : Reduce rule [course -> DEPT NUM] with ['BIOL','208'] and goto state 23
   yacc.py: 423:Result :  ('BIOL 208')
   yacc.py: 389:Action : Reduce rule [courses -> course] with ['BIOL 208'] and goto state 22
   yacc.py: 423:Result :  ('BIOL 208')
   yacc.py: 389:Action : Reduce rule [course -> NUM] with ['330'] and goto state 24
   yacc.py: 423:Result :  ('330')
   yacc.py: 389:Action : Reduce rule [courses -> courses OR course] with ['BIOL 208','or','330'] and goto state 19
   yacc.py: 423:Result :  (('OR', 'BIOL 208', '330'))
   yacc.py: 389:Action : Reduce rule [cg -> courses] with [] and goto state 18
   yacc.py: 423:Result :  (('OR', 'BIOL 208', '330'))
   yacc.py: 493:Error  : cg . LexToken(RPARENS,')',1,32)
   yacc.py: 493:Error  : cg . error
   yacc.py: 493:Error  : . error
   yacc.py: 493:Error  : . $end

It means the parser just refused to use the rule cg : courses and subsequently cg : LPARENS cg RPARENS. At that time, I thought it must be something wrong with the grammar. Forgetting the parenthesis would have been an option, only if the compiler gave the correct interpretation. With that in mind, I worked on getting the final result:

I realize at this point that PLY couldn’t fly:

   yacc.py: 389:Action : Reduce rule [nums -> NUM] with ['121'] and goto state 19
   yacc.py: 423:Result :  ('121')
   yacc.py: 389:Action : Reduce rule [nums -> nums COMMA NUM] with ['121',',','121L'] and goto state 22
   yacc.py: 423:Result :  ('121/121L')
   yacc.py: 389:Action : Reduce rule [nums -> nums OR NUM] with ['121/121L','or','122'] and goto state 20
   yacc.py: 423:Result :  ('121/121L/122')
   yacc.py: 389:Action : Reduce rule [nums -> nums COMMA NUM] with ['121/121L/122',',','122L'] and goto state 22
   yacc.py: 423:Result :  ('121/121L/122/122L')
   yacc.py: 389:Action : Reduce rule [nums -> nums OR NUM] with [,'or','153'] and goto state 20
   yacc.py: 423:Result :  ('121/121L/122/122L/153')
   yacc.py: 493:Error  : DEPT nums OR . LexToken(DEPT,'CIVE',1,39)

It seems to be stuck on the rule nums : nums OR NUM. I did a test by deleting that rule. Then it parsed the rest of the string fine, just missing a few NUMs. For some reason, PLY just refused to use the rule cl : cl OR courses. I checked the PLY documentation. Yup, PLY turned out to be an iron balloon. “shift/reduce conflicts are resolved in favor of shifting (the default).” Of course, once the mystery is solved, the solution is not hard to find.

I’m taking a bite by bite approach to interpreting the course prerequisites from the scraper to make its storage in the database possible. Meanwhile, I already finished the part of it that retrieves the data recursively. The approach I decide to take is the same as building a compiler.

I previously favored a quick approach such as the interpreter pattern.

However, commas in sentences have different meanings depending on the context.

(BIOL 140, BIOL 208 or 330) and (BIOL 308 or 330)

(CS 240 or SE 240), CS 246, ECE 222

The interpreter pattern assumes a symbol only has one meaning. Thanks again to a course I took, I was already familiar with the problem and the solution. Recognizing and defining the problem was the hard part. A quick overview of the steps involved from start to finish:

First step in the compiling process is to tokenize input.  That takes care of blobs such as “Level at least 3A; Not open to General Mathematics students.”. Totally useless in terms of prerequisites. So it should not show up in the token string.

Building the lexer was as simple as specifying the token list, writing regular expressions for them, and setting ignored characters.

Running it gives the output:

LexToken(LPARENS,'(',1,1)
LexToken(DEPT,'CS',1,2)
LexToken(NUM,'240',1,5)
LexToken(OR,'or',1,9)
LexToken(DEPT,'SE',1,12)
LexToken(NUM,'240',1,15)
LexToken(RPARENS,')',1,18)
LexToken(COMMA,',',1,19)
LexToken(DEPT,'CS',1,21)
LexToken(NUM,'246',1,24)
LexToken(COMMA,',',1,27)
LexToken(DEPT,'ECE',1,29)
LexToken(NUM,'222',1,33)

While working on the tree part of the coursetree project, I ran into the question of how to display the course dependencies. I have written a recursive function that returns a recursive list of course prerequisites:

I wanted to turn it into a diagram of course prerequisites and decided 2 flat lists could retain the data:

• a list for the levels
• a list for connections between courses

For example,

would translate to

and

Separating the Levels

We start off with a recursive list representing the tree structure:

To tackle the problem, I first solved a similar one: flattening a list.
This can easily be done in Scheme, as syntax and type declarations do not get in the way.

Here’s the same code translated into Python:

Unfortunately, flatten in Python produces a hypernested structure for flat lists, as (1 2 3) in Scheme is equibalent to (cons 1 (cons 2 (cons 3 empty))) or (1 . (2 . 3)).

The more serious problem is that it exposes a quirk in Python:

Yes, that means the list disappears after being extended with an empty list . . . one of those unpleasant surprises.
So let’s redefine a flat list in Python:

There is a similarity between this approach and the recursive one: different actions are taken for a list node and other nodes. I used a combined functional and imperative approach to solve the problem:

Connecting the Nodes

We start off with a recursive list representing the tree structure, slightly different from the list for separating the levels:

Again, a mix of recursion and iteration easily solves the problem:

Hopefully, you’ve had fun reading this article and meanwhile came up with a better way to represent the tree as a flat structure.

I’ve had the idea of making a self-updating, navigable tree of Waterloo courses. This is the first step. (Actually, not the first step for me. It started with Django, which had to do with my last work report’s comparison to Zen Cart. Some credit goes to Thomas Dimson for inspiration. He made the Course Qualifier.) The main idea for this step is to gather all the information to be stored in a database. With that (the idea and plan) begins the coding phase:

I wanted to gather the course (“SE 101”), name (“Introduction to Methods of Software Engineering”), desc (“An introduction …”), prereq (“Software Engineering students only”), and offered (“F”) each as separate fields

In order to do that, I wrote a spider to crawl the page:

There are several things to note:

• The prereq field here cannot identify “For Software Engineering students only”. The regular expression only matches the course code.
• Offered, unlike other fields, can contain more than one item
• Prereq may be empty

Finally, the spider pipes its results to an output format. CSV format meets the requirements, as it can be inserted into a database.

Two gotchas:

• Because prereq might be empty, there needs to be an exception handler
• Offered may be variable length. The list needs to be joined to output all of the terms the course is offered.

This part of the project was done in 2 hours with Scrapy. The project can be found in the downloads section.