Module Code: CMT120
Module Title: Fundamentals of Programming
Assessment Title: Programming Challenges
Learning Outcomes
The learning outcomes for this assessment are as follows:
• LO1: Use high-level programming languages to complete programming tasks.
• LO2: Demonstrate familiarity with programming concepts, simple data-structures and algorithms.
Submission Instructions
The coversheet can be found under ‘Assessment & Feedback’ in the COMSC- ORG-SCHOOL organisation on Learning Central.
All files should be submitted via Learning Central. The submission page can be found under ‘Assessment & Feedback’ in the CMT120 module on Learning Central. Your submission should consist of a single file:
|
Description
|
Type
|
Name
|
|
Cover Sheet Python Code
|
1 .pdf file 1 .py file
|
[Student number] .pdf [Student number] .py
|
Replace [Student number] with your Cardif’s user name, which is typ- ically a letter 'c' (or 'd') + your student number, e.g. c1234567.
Any code submitted will be run on a system equivalent to the laptops provided to the students, and must be submitted as stipulated in the in- structions above. The code should run without any changes being required to the submitted code, including editing of filenames.
Any deviation from the submission instructions above (including the number and types of files submitted) may result in a deduction of up to 10% from the overall mark.
Staf reserve the right to invite students to a meeting to discuss course- work submissions.
If you are unable to submit your work due to technical difficulties, please submit your work via e-mail to comsc-submissions@cardif.ac.uk and notify the module leader.
Assessment Description
To complete this coursework, you must complete a set of five programming challenges in Python. The challenges are described in detail below, and you are also provided with a set of test cases that will check whether your code produces the required output or not. In particular, you will be given two test cases per exercise. You should make sure that your submitted code passes the supplied tests to ensure it functions correctly. However, please note that your code will be tested against a further two diferent test cases, which you have not been supplied with. In total then each exercise will be tested against four test cases, including the two provided. You should therefore ensure that you try to cover all possible inputs and that your code still functions correctly. Your code will need to pass all four tests (two seen, two unseen) in order to score full marks for the functionality. Note that there is a time limit of three seconds to each test. If your code does not provide a correct answer within the time limit the test is failed.
Instructions for completing the challenges
• You will find template code for the assignment on Learning Central. Inside the template you will find a template .py file, in which you should complete your solutions. You will also finda test_template .py file containing the test cases that will check your code’s functionality, along with a folder of test data required for some of the tests. You are also supplied with a Readme .md file containing detailed instructions on how to run the test cases to check your code.
• In the templates, the functions’ interfaces are given but the functions’ bodies are empty. Solve the exercises by correctly filling in the func- tions’ bodies.
• It is forbidden to change the functions’ interfaces. However, new functions can be defined to support the solution of the exercises. These functions must have names that are diferent from those already present in the templates.
• You are NOT allowed to import any additional modules. Use of mod- ule functions will result in zero marks for the corresponding exercises.
• In all the exercises, you can assume that the inputs are provided in the appropriate format and type. Therefore, error-checking is not needed.
• The final submission should NOT contain any input, print, or console.log statements.
You will be given marks for solving each problem within the time limit. Further marks will be awarded for solution style. and quality. The mark scheme is described in further detail later.
Exercise 1: Spacemon Competition
Spacemons are spirits that come from other planets of our star system. When two spacemons meet, they feel the urge to fight until one or them is defeated. Warlocks conjure, tame, and train teams of spacemons, to make them compete in a spectacular tournament.
Note: the paragraph above is a work of fiction.
In this exercise, you are required to complete the function
exercise1(roster1,roster2), which simulates the result of a competition between two teams of spacemons, roster1 and roster2; the function re- turns True if roster1 wins, or False otherwise.
Disclaimer: no spacemon was harmed in the making of this exercise.
A spacemon is represented as a three-element tuple (planet, energy, power), where planet represents the type of the spacemon, energy is its stamina, and power is its ability to reduce another spacemon’s energy. A roster is simply a list of spacemons.
The planet of a spacemon is particularly important as certain types are stronger/weaker against others, as represented in Table 1.
Table 1: Attack multipliers depending on type.
In the table, the rows correspond to the attacking spacemon, the columns correspond to the defending spacemon. The cells show the multiplier that must be applied to the attacker’s power to determine how much energy the defender loses.
A competition is divided into one-on-one matches. Spacemons take part in the competition according to their position in the roster. There- fore, the first match is between the first spacemon of each roster. The spacemons take turns to attack, with the first roster always attacking first. When a spacemon attacks, the total damage inflicted on the opponent is: damage = type_mult * power, where type_mult is the multiplier specified in Table 1. The damage is then subtracted from the opponent’s energy. If a spacemon’s energy drops to 0 (or less), the spacemon is defeated and the match ends. Then, a new match starts between the winner of the previ- ous match and the next spacemon in the opponent’s roster. The winning spacemon does not recover any lost energy between matches; also, the first spacemon to attack is, again, the one from the first roster.
Example: Let us consider the following rosters.
• roster1 is comprised of (‘Earth’,100,10) and (‘Earth’,100,10).
• roster2 is comprised of (‘Mercury’,80,10) and (‘Venus’,80,10).
In the first match, the Earth spacemon defeats the Mercury spacemon; how- ever, it loses 70 points of energy. In the second match, the former winner is defeated by the Venus spacemon, which receives 10 points of damage. Fi- nally, the Venus spacemon wins the third match, losing 35 points of energy. The second roster wins the competition and, therefore, the function returns False.
Exercise 2: Five Letter Unscramble
For this exercise you need to use the provided wordle .txt file that contains a list of 5-letter words used in the game Wordle.
Disclaimer: This list is taken directly from the Wordle game and there- fore may contain some words which some people may find o ensive. Reader discretion is advised.
Complete function exercise2(s) that, given a string containing letters, returns the number of unique words in wordle .txt that can be obtained by rearranging the characters in the string. Each character in s can be used at most once.
Examples:
• exercise2(‘sehuoh’) returns 1, as the string can be rearranged into ‘house’ .
• exercise2(‘caarto’) returns 5, as the string can be rearranged into ‘carat’ , ‘carta’ , ‘actor’ , ‘aorta’ , ‘taroc’ .
Exercise 3: Wordle Set
For this exercise you need to use the provided wordle .txt file that contains a list of 5-letter words used in the game Wordle. Disclaimer: This list is taken directly from the Wordle game and therefore may contain some words which some people may find offensive. Reader discretion is advised.
Wordle is a web-based word game created and developed by Welsh soft- ware engineer Josh Wardle. Players have six attempts to guess a five-letter word, with feedback given for each guess in the form. of colored tiles indicat- ing when letters match or occupy the correct position. After every guess, each letter is marked as either green, yellow or gray: green indicates that letter is correct and in the correct position, yellow means it is in the answer but not in the right position, while gray indicates it is not in the answer at all. Multiple instances of the same letter in a guess, such as the “o”s in “robot”, will be colored green or yellow only if the letter also appears mul- tiple times in the answer; otherwise, excess repeating letters will be colored gray (Wikipedia contributors, 2022).
Let us define a “Wordle set” as the set of five-letter words in wordle .txt that match a given configuration of green, yellow, and gray letters. Com- plete function exercise3(green,yellow,gray) that returns the cardinality (i.e. the size) of the corresponding Wordle set. In particular, green is a dic- tionary that specifies the letters whose positions are known. The keys are positions (i.e., 0,1,2,3,4) and their associated values are their corresponding letters. Only positions with known letters are included in the dictionary. yellow is a dictionary specifying the letters that are in the answer but their position is not known. The keys are letters and their values are sets of known wrong positions (i.e., 0,1,2,3,4). Finally, gray is a set of letters that are known to not be in the answer. Note that a letter cannot be in gray and, at the same time, in green or in yellow. However, a letter could be both in green and in yellow and the clues could refer to the same letter.
Example: Given green = {1:’i’,3:’c’}, yellow = {’e’:{3}}, and gray = {’r’,’a’,’s’,’d’,’f’}, exercise3(green,yellow,gray) returns 5, as the Wordle set is comprised of ‘wince’, ‘mince’, ‘niece’, ‘piece’, and ‘yince’.
Exercise 4: 2D Most Rewarding Shortest Path
Complete the function exercise4(env), which finds the shortest path from a starting cell A to an arrival cell B on a grid, having the highest reward.
Attribute env describes the environment. An environment is a matrix that can contain the following characters: A, B, O, X, and R. A and B are the starting and arrival cell, respectively. An O represents an empty space, an X represents an obstacle, and an R represents a reward. An example is presented in Table 2.
Table 2: Sample 2D environment.
A cell is adjacent only to other cells in the same row or column. For example, the cell containing an A in the top-left corner is adjacent only to the X on the right and the O at the bottom - diagonals are not considered adjacent.
When searching for the shortest path, only empty and reward cells (Os and Rs, respectively) can be traversed. If a path passes through a reward cell, the reward is collected. Figure 1 shows two shortest paths (note: there are actually more than two shortest paths in this example), one approaching the B from the top (in red) and the other from the bottom (in blue); both have a length of seven. However, the former has a total reward of three, while the latter has a total reward of one. Therefore, the red path is the one that the function is looking for.
Parameter env is given to the function as a list of sublists, where each sublist contains characters corresponding to a row. The representation cor-
Figure 1: Two shortest paths.
responding to the environment above would be:
[[‘A’,‘X’,‘R’,‘R’,‘R’],[‘O’,‘O’,‘O’,‘X’,‘B’],[‘O’,‘O’,‘O’,‘O’,‘R’]].
The function should return a 2-value tuple containing the length of the shortest path and the total reward collected.
Example: Given the environment above, the function should return (7,3).
Hint: You might want to enumerate all the paths from A to B (excluding those that pass through the same cell twice) . Then, you can can choose the shortest path having the highest reward.
Exercise 5: Social Network Analysis
Social network analysis (SNA) is the process of investigating social structures through the use of networks and graph theory. It characterizes networked structures in terms of nodes (individual actors, people, or things within the network) and the ties, edges, or links (relationships or interactions) that connect them (Wikipedia contributors, 2021b). Figure 2 shows a sample social network with seven actors.
Figure 2: Sample social network with 7 actors.
Network (and graphs) can be represented as adjacency matrices. An adjacency matrix is a square matrix having as many rows and columns as there are actors in the network. A cell is 1 if the actors corresponding to the row and the column are connected by an edge, and is 0 otherwise. The matrix corresponding to the social network in Figure 2 can be found below in Table 3. In turn, matrices can be represented as a list of sublists, as explained in Exercise 9.
Table 3: Adjacency matrix corresponding to the social network in Figure 2.
In graph theory, a clique is a subset of nodes of a graph such that every two distinct nodes in the clique are adjacent; that is, every pair of nodes in the clique must be connected. A maximal clique is a clique that cannot be extended by including one more adjacent vertex (Wikipedia contributors, 2021a). In SNA, a clique represents a tightly-knit group or community. Figure 3 illustrates all the maximal cliques that can be found in the sample network: (A,B,C), (B,D), (D,F,G), and (D,E,F). Following the definition above, node E cannot be added to the yellow click (D,F,G), as node E is not connected to node G and, therefore, (D,E,F,G) would not be a clique.
Figure 3: Maximal cliques in the sample social network. Each clique is highlighted in a diferent colour.
As it can be seen from the example, a node can belong to multiple maxi- mal cliques. It is interesting to identify actors that belong to multiple cliques, as they can act as bridges between communities and be extremely influential.
In this exercise you need to complete the function exercise5(network) which, given the adjacency matrix of a social network as a list of sublists, returns the number of maximal cliques that each actor belongs to as a list.
Example: The result of applying exercise5(network) on the adja- cency matrix in Table 3 would be [1,2,1,3,1,2,1].