Programming Languages Homework

Programming Languages Homework
Spring 2008
Rowan University

You may work together on these programming assignments, in teams of up to 3 people. If you work in a team, e-mail only one copy of the program and submit only one printout with all the team members' names on them.

This semester, you will solve the same programming problem four times: once in Scheme, once in Ada, once in Prolog, and once in an imperative language of your choice.

General problem description

The Simplistic Primary Predictor predicts the winner of a state's primary election based on several factors:

The state that the candidate comes from
The region of the country the candidate comes from
The number of times a television commercial for the candidate has aired in that state
The number of days the candidate has spent campaigning in that state
The number of primary elections the candidate has won so far this year

The input to the program will be the name of a state (as a 2-letter abbreviation), followed by a list of information about each of several candidates. The information about each candidate will be:

A single letter representing the name of the candidate
A two-letter state abbreviation, representing the home state of the candidate
An integer, representing the number of television commercials for the candidate that have aired in the current state.
An integer, representing the number of days that the candidate has spent campaigning in he state.
An integer, representing the number of primaries and caucuses the candidate has won so far this year

The program will compute a score for each candidate that attempts to predict the candidate's likelihood of success. The score is computed as follows: Begin with a score of 0. If the candidate's home state is the same as the current state, add 50 points. If the candidate's home state's region is the same as the current state's region, add 20 points. Add 1 for every 10 commercials that have aired. (Round down to the nearest integer: 37 commercials gives 3 points.) Add 1 for every day the candidate has spent campaigning in the state. Add 5 for every primary or caucus the candidate has won so far.

Use these regions in our calculations:

Region number	Region Description	States in Region
1	Northeast	ME, NH, VT, MA, CT, RI, NY, PA, NJ, DE, MD
2	Southeast	VA, NC, SC, GA, FL, AL, MS, TN, KY, WV, AR, LA
3	Lakes	OH, MI, IN, IL, WI, MN
4	Central	IA, MO, ND, SD, NB, KS, OK, TX
5	West	MT, WY, CO, NM, AZ, UT, ID, NV
6	Pacific	WA, OR, CA, AK, HI

The output will be a list of candidates' names and scores.

Disclaimer: While I have based the sample data below on some actual 2008 candidates, I have completely invented the numbers for commercials and campaign days. The number of wins so far is based on election results as of mid-January; this number, of course, will change constantly throughout the primary season.

You are guaranteed that there will be at least one candidate in the input, and that there will be no more than 100 candidates.

Note: As you write your programs, try to implement the classification into regions as elegantly as possible. Try to avoid the 100-line solution, if you can:

        if state = "ME" then
                region = 1
        elseif state = "NH" then
                region = 1
        ...
        end if;

Many languages at least permit the use of boolean operators:

	if state = "ME" or state = "NH" or ... then

and some languages contain structures such as lists and sets that allow even more compact solutions.

Think about how to use the control constructs and data structures of your language to implement this classification process as elegantly as your language will allow.

Example 1:

Input:

        NJ
        C NY 85 3 4
        O IL 95 6 2
        E SC 73 4 0
        R MA 102 0 3
        H AR 84 3 1
        M AZ 123 0 1
        P TX 10 2 0
        G NY 67 2 0

Output:

Example 2:

Input:

        AZ
        R MA 120 8 3
        H AR 163 3 1
        M AZ 209 10 1
        P TX 112 11 0
        G NY 302 4 0
        C NY 134 2 4
        O IL 290 3 2
        E SC 176 5 0
        K OH 83 9 0

Output:

Testing suggestion:

Since the input for this problem is lengthy, I suggest creating a file containing the test data, and then using either cut-and-paste with the mouse or input redirection to run the test examples. This will save a considerable amount of typing.

1. Imperative-language problem

Write a program to solve the homework problem described above, using one of the following languages: C, C++, or Java. (If you have another favorite language you'd prefer to use, talk to me.)

The input will contain the current state on a line by itself, then each candidate's information on a separate line. A candidate's information will be the five items listed in the general problem description (a letter, a 2-letter state, and three integers), separated by spaces. A dot on a line by itself will indicate the end of input.

The output will be a list of candidates' names and scores, using the format illustrated in the examples below.

Examples:

Input:

        NJ
        C NY 85 3 4
        O IL 95 6 2
        E SC 73 4 0
        R MA 102 0 3
        H AR 84 3 1
        M AZ 123 0 1
        P TX 10 2 0
        G NY 67 2 0
	.

Output:

Input:

        AZ
        R MA 120 8 3
        H AR 163 3 1
        M AZ 209 10 1
        P TX 112 11 0
        G NY 302 4 0
        C NY 134 2 4
        O IL 290 3 2
        E SC 176 5 0
        K OH 83 9 0
	.

Output:

Note: If this input format is difficult to use in the language you have chosen, you may instead read the input items on separate lines, like this:

	NJ
	C
	NY
	85
	3
	4
	O
	IL
	95
	6	
	2
	.

You should still use a dot (.) on a line by itself to indicate the end of the input.

2. Scheme problem

Write a Scheme program to solve the problem described above. Define a function (predict State L) which takes a State and a candidate information list L as parameters and returns a list of candidate-score pairs. The candidate information list and the candidate-score list should have the format illustrated in the examples below.

You may assume that list L will be in the correct format when the function is called; you do not have to error-check for a non-list or an incorrectly formed list. In your program, you may write and call any additional functions that are helpful in the computation.

Examples:

(predict 'NJ
	'( (C NY 85 3 4)
	   (O IL 95 6 2)
	   (E SC 73 4 0)
	   (R MA 102 0 3)
	   (H AR 84 3 1)
	   (M AZ 123 0 1)
	   (P TX 10 2 0)
	   (G NY 67 2 0) ))

should return

((C 51) (O 25) (E 11) (R 45) (H 16) (M 17) (P 3) (G 28))

and

(predict 'AZ
	'( (R MA 120 8 3)
	   (H AR 163 3 1)
	   (M AZ 209 10 1)
	   (P TX 112 11 0)
	   (G NY 302 4 0)
	   (C NY 134 2 4)
	   (O IL 290 3 2)
	   (E SC 176 5 0)
	   (K OH 83 9 0) ))

should return

((R 35) (H 24) (M 105) (P 22) (G 34) (C 35) (O 42) (E 22) (K 17))

3. Ada problem

Write a Ada program to solve the problem described above.

The output will be a list of candidates' names and scores, using the format illustrated in the examples below.

Examples:

Input:

        NJ
        C NY 85 3 4
        O IL 95 6 2
        E SC 73 4 0
        R MA 102 0 3
        H AR 84 3 1
        M AZ 123 0 1
        P TX 10 2 0
        G NY 67 2 0
	.

Output:

Input:

        AZ
        R MA 120 8 3
        H AR 163 3 1
        M AZ 209 10 1
        P TX 112 11 0
        G NY 302 4 0
        C NY 134 2 4
        O IL 290 3 2
        E SC 176 5 0
        K OH 83 9 0
	.

Output:

4. Prolog problem

Write a Prolog program to solve the problem described above. Define a predicate predict(+State, +L, -Prediction) which takes State, a list of candidate information L and a variable Prediction as parameters; predict should succeed with Prediction set to the appropriate candidate-score list. The format for both lists (similar to the formats used for the Scheme problem) is illustrated in the examples below. The candidate names and state names, both in parameter State and in list L, will be entirely in lower case.

You may assume that list L will be in the correct format when the predicate is called; you do not have to error-check for a non-list or an incorrectly formed list. You may also assume that Prediction will be a variable when the predicate is called.

In your program, you may write and call any additional predicates that are helpful in the computation.

Examples:

predict(nj, [
                [c, ny, 85, 3, 4],
                [o, il, 95, 6, 2],
                [e, sc, 73, 4, 0],
                [r, ma, 102, 0, 3],
                [h, ar, 84, 3, 1],
                [m, az, 123, 0, 1],
                [p, tx, 10, 2, 0],
                [g, ny, 67, 2, 0] ], Prediction).

should succeed with Prediction set to

[[c, 51], [o, 25], [e, 11], [r, 45], [h, 16], [m, 17], [p, 3], [g, 28]]

and

predict(az, [
                [r, ma, 120, 8, 3],
                [h, ar, 163, 3, 1],
                [m, az, 209, 10, 1],
                [p, tx, 112, 11, 0],
                [g, ny, 302, 4, 0],
                [c, ny, 134, 2, 4],
                [o, il, 290, 3, 2],
                [e, sc, 176, 5, 0],
                [k, oh, 83, 9, 0] ], ScoreList).

should succeed with Prediction set to

[[r, 35], [h, 24], [m, 105], [p, 22], [g, 34], [c, 35], [o, 42], [e, 22], [k, 17]]

In each case, turn in:

A paper printout of the text of the program
A paper printout of a sample run of the program (use script to capture the input and output)
An e-mailed version of the program

Nancy Tinkham
Computer Science Department, Rowan University