CS136 Assignment 10

Due Monday, Dec. 3 at 11:59 am sharp. There are no late submissions for this assignment.

You may not use recursion in any of your solutions. If applicable, you may use the C implementation of an AVL tree provided for Assignment 7.

Assignment 10 Problem 1 [20 marks]. File scoreboard.c

• score string number
  Record number as the score for the player whose name is string. No output is produced. Assume number is an integer between -999999999 and 999999999.
• best string
  Output a line containing best string number where number is the best score recorded so far for the player whose name is string.
  Output ? instead of number if no score has been recorded for the player.
• highscore
  Output a line containing highscore number where number is the highest score recorded for any player so far. Output highscore ? if no score has been recorded.
• Any command other than score, best, highscore. Ignore the command and proceed to the next one.

Your program must stop after processing 1000 valid commands, or at end of file, whichever occurs first. If a name (or any other symbol) in the input exceeds 20 characters, you must read the entire name, but consider only the first 20 characters (see Sample Input). You may not use any heap storage.

The following files will be available in the marmoset environment, should you choose to use them: readstring.h, readstring.c. You may wish to try out the provided function using test_readstring.c to get a feel for how it works.

Sample Input

score FredFlintstonefromBedrock 10
score Wilma 20
score FredFlintstonefromBe 20
highscore
score Betty 30
highscore
best FredFlintstonefromBedrock
score FredFlintstonefromBedrock 25
best FredFlintstonefromBeyond
best Barney

Output for Sample Input

highscore 20
highscore 30
best FredFlintstonefromBe 20
best FredFlintstonefromBe 25
best Barney ?

Assignment 10 Problem 2 [20 marks]. File: scoreboard.c

• disqualify symbol
  Remove all scores for the player whose name is symbol. Subsequent highscore commands will exclude the scores achieved by this player. The player may re-enter the game after being disqualified: score symbol newscore sets the player's new high score to newscore.

Sample Input

score Fred 10
score Wilma 20
score Fred 20
highscore
score Betty 30
highscore
best Fred
score Fred 25
best Fred
disqualify Betty
highscore
best Betty

Output for Sample Input

highscore 20
highscore 30
best Fred 20
best Fred 25
highscore 25
best Betty ?

Assignment 10 Problem 3 [20 marks]. File: scoreboard.c

• leaders
  Output a line containing leaders followed by the names of all players tied for the highest score. Output a single space before each player's name. The names should be in lexicographic order according to their ASCII representation. If there are no leaders, output leaders ?.

Sample Input

score Fred 10
score Wilma 20
score Fred 20
leaders

Output for Sample Input

leaders Fred Wilma

Assignment 10 Problem 4 [20 marks]. File: scoreboard.c

Sample Input

score FredFlintstonefromBedrock 10
score Wilma 20
score FredFlintstonefromBe 20
highscore
score Betty 30
highscore
best FredFlintstonefromBedrock
score FredFlintstonefromBedrock 25
best FredFlintstonefromBeyond
best Barney

Output for Sample Input

highscore 20
highscore 30
best FredFlintstonefromBedrock 10
best FredFlintstonefromBeyond ?
best Barney ?

Bonus: Assignment 10 Problem 5 [20 marks]. File: scoreboard.c

• The running time of the commands score, best, highscore and disqualify must be O(n), where n is the number of commands processed before the current command.
• The running of leaders must be O(m*n) where m is the number of current leaders and n is the number of commands processed before the current command.
• The program must be able to handle an arbitrary number of commands in the input, limited only by available memory.

Bonus: Assignment 10 Problem 6 [10 marks]. File: scoreboard.c