ENGG1330 Computer Programming I Assignment
Page 1 of 12
ENGG 1330 Computer Programming I (24-25 Semester 2)
Programming Assignment
Due date: 9:30am, 30-Apr-2025 (Wed)
Important notes
• The purpose of the programming assignment is to assess your ability to implement
solu5ons for problems using knowledge learnt from this course. Only Python built-in
features are sufficient to solve problems in this assignment. It is unnecessary to import
any modules to do this assignment. Zero mark will be given to programs that import
any modules. If you are unsure, feel free to contact us for clarifica5on.
• While programming style is not graded, you are highly recommended to use func5ons
to factor your program, write clear and 5dy codes, e.g., descrip5ve comments, concise
and clear naming, appropriate spacing.
Submission
• Virtual Programming Lab (VPL) will be set up for submission and tes5ng. Only the last
submission will be used for assessment.
• Your program outputs must conform with the required formats, such as spacing and
alignment in order to pass the test cases. If you are unsure about the requirements, feel
free to contact us for clarifica5on.
• A few public test cases are provided in VPLs for checking whether your programs meet
the basic requirements. You are encouraged to test the robustness of your programs by
crea5ng more test cases on your own. Your programs will be assessed with another
set of private test cases.
• 20% will be deducted from the final mark for every 24-hour aOer the submission due
date. Do not submit any program aOer the due date if your work is final. Any
submission aOer the due date will be regarded as late submission.
Plagiarism
• Confirmed plagiarism cases (detected by the system) will get zero mark and subject to
disciplinary ac5ons. The penalty applies to the source provider(s) as well. In other
words, students who submit same/highly similar programs will all get zero mark.
Students have full responsibility to protect their programs from being accessed by
others.
• Every year in the past, several students had found engaged in plagiarism. They all got
zero mark for the assignment and a warning leWer issued by the Department Head.
Questions
• If you have any ques5ons about the requirements of a programming problem, please
send email to the corresponding author.
ENGG1330 Computer Programming I Assignment
Page 2 of 12
Programming Problem 1: Student Informa5on System [20%]
(author: LI Jiaqi, email: lijq@eee.hku.hk)
Write a program that gets the name of a student file, reads the file and performs the
following user commands. The program should con5nue to prompt for commands un5l the
user quits the program.
Input SpecificaIon
• The user commands and parameters, if any, are separated by a space with no space
at the end.
• The user commands and parameters are case-insensi5ve, i.e., the program should
accept both uppercase and lowercase.
• The order of records in the student file is random.
• Each line in the student file represents a student record.
• Each student record consists of the following four values separated by a comma ','
and all the values are valid and conform with the following format.
o Student ID: unique 8-digit number
o Name: First name (first character capitalized) followed by last name (first
character capitalized) aOer a space, <20 characters
o Major: a single string in uppercase, <5 characters
o GPA: a floa5ng point number in 1 decimal place
Output SpecificaIon
• In case of valid command with non-empty result, output the result.
• In case of empty result, print "Empty result".
• In case of invalid command, print "Invalid command".
User Commands and Output DescripIons
Command and
parameters
Example Descrip5on
AV [major] AV Calculate and print the average GPA in 2 decimal places of
all students in the file.
AV CE Calculate and print the average GPA in 2 decimal places of
all CE students.
CN [major] CN Count and print the numbers of students in the file.
CN CE Count and print the numbers of CE students.
LI [major] [gpa] LI List informa5on of all students in the file in table format*.
LI CE List informa5on all CE students in table format*.
LI CE 3.0 List informa5on all CE students with GPA>=3.0 in table
format*.
* Table format:
• Number of columns: 4
• Number of rows: number of the students in the result
• Column 1: Student ID, width: 10, leO-aligned
• Column 2: Student name, width: 20, right-aligned
• Column 3: Major, width: 5, right-aligned
ENGG1330 Computer Programming I Assignment
Page 3 of 12
• Column 4: GPA, width: 5, right-aligned
• The students are listed in alphabe5cal order of the last name
and then the first name.
QU QU Print "Program terminated" and quit the system.
Samples
ENGG1330 Computer Programming I Assignment
Page 4 of 12
Programming Problem 2: Mark and Recapture [20%]
(author: LIN Xuehong, email: u3011238@connect.hku.hk)
To find out the number of animals in an area (popula5on), it is imprac5cal to count every
individual. A method called "mark and recapture" is commonly used to es5mate an animal
popula5on's size. A por5on of the popula5on is captured, marked, and released. Later,
another por5on will be captured and the number of marked individuals within the sample is
counted. Since the number of marked individuals within the second sample should be
propor5onal to the number of marked individuals in the whole popula5on, an es5mate of
the total popula5on size can be obtained by dividing the number of marked individuals by
the propor5on of marked individuals in the second sample.
Formally, the popula5on size is es5mated as follows. Let
n = Number of animals marked in the first sample
K = Number of animals captured in the second sample
k = Number of recaptured animals that were marked
The es5mated popula5on size is N = n * K / k
Write a program to input the following three lists.
• A list of animals marked in the first sample
• A list of animals captured in the second sample
• A list indica5ng which of the corresponding recaptured animals in the second sample
were marked where a '1' is marked and a '0' is not marked
AOer doing the calcula5on, the program outputs the es5mated popula5on size for each of
the animals, one animal on a line in alphabe5cal order of animal's name. If there are any
animals of which their popula5on size cannot be es5mated in the case of n=0 or k=0 or k>n,
the program outputs a list of these animals in alphabe5cal order. If the number of marks in
the last list does not match the number of animals in the second sample, output "Invalid
data".
Format
• Names of animals in the input lists are case insensi5ve.
• Names of animals in the output are in uppercase.
• Items in a list are separated by a space with no space at the end
Samples
ENGG1330 Computer Programming I Assignment
Page 5 of 12
Choose ANY TWO out of the remaining THREE programming
problems. Note that they carry different marks according to the
level of difficulty and the maximum mark of the whole assignment
is bounded by 100%.
Programming Problem 3: Hit the Bricks [25%]
(author: LIN Xuehong, email: u3011238@connect.hku.hk)
Write a program to hit a brick ceiling. The brick ceiling is represented by a 2D array of
integers ranging from 0 to 4, where a '0' means no brick and a posi5ve integer is the weight
of the brick. A hit at the ceiling is represented by a pair of row number and column number
where row number starts from 1 at the top and column number starts from 1 on the leO.
Ini5ally, all bricks on the input ceiling are safe, i.e., no brick will fall without a hit. Also, all
bricks on edges of the ceiling must be safe, i.e., bricks on edges never fall even when there is
a hit. If a hit is at a brick not on an edge, the brick will fall. The remaining bricks can s5ll
s5ck on the ceiling if one of the following condi5ons holds, otherwise, they will also fall.
• The brick is on the edge.
• The number of adjacent bricks (above, below, leO and right) is greater than or equal
to the weight of the brick.
The program inputs the following numbers.
• Number of rows on the ceiling
• Number of columns on the ceiling
• The ceiling before hit, which is represented by weights of bricks, entered row by row,
and weights in each row are separated by a space with no space at the end
• A list of hits, where each hit is represented by a pair of row number and column
number, separated by a comma ',' and hits are separated by a space with no space at
the end
The program outputs the ceiling aOer each hit, which is represented by weights of bricks,
printed row by row, and weights in each row are separated by a space with no space at the
end.
ENGG1330 Computer Programming I Assignment
Page 6 of 12
Samples
Explana5on of the samples:
• AOer the first hit (4,3), the ceiling remains no change because the brick is on the
edge.
• AOer the second hit (3,3),
o the brick at (3,3) falls
• AOer the third hit (2,3),
o the brick at (2,3) falls
o the brick at (2,2) also falls because the number of adjacent bricks of the brick
at (2,2) drops to 2 and becomes less than the weight of the brick at (2,2),
which is 3.
If a colon ':' appears at the
end of a line, there is no
space aOer the colon.
ENGG1330 Computer Programming I Assignment
Page 7 of 12
Programming Problem 4: Arithme5c Expression Validator [30%]
(author: LIN Mingxian, email: mingxianlin@connect.hku.hk)
Write a program to validate an input arithme5c expression containing only the following
elements.
• Variables
• Natural numbers (posi5ve integers)
• Arithme5c operators: addi5on (+), subtrac5on (-), mul5plica5on (*) and division (/)
• Parentheses: ()
Requirements:
• Valid expressions
o Output "Valid: [operator sequence]", where the operator sequence is a list of
operators in execu5on order, separated by a space, with no space at the end.
o Special case:
§ No operator is present (e.g., single variable, number): output "Valid:
None".
• Invalid expressions
o Output "Invalid: [index]", where the index, star5ng from 0, indicates the
posi5on of the first invalid token in the input expression.
o A token refers to an individual element in the input expression such as a
variable, a number, an operator, an open parenthesis or a closing parenthesis.
o Special cases:
§ Empty parentheses, (): index indicates the posi5on of the closing
parenthesis.
§ Unclosed parentheses: output "Invalid: -1"
§ Trailing operator, an operator appears at the end of the input
expression: output "Invalid: -1"
• Valida5on rules
o Variable naming:
§ Variables must follow Python naming rules
§ Start with a leWer or underscore (_), followed by alphanumeric
characters or underscores.
§ Cannot be a Python reserved keyword as shown the following list.
['False', 'None', 'True', 'and', 'as', 'assert', 'async', 'await', 'break',
'class', 'con5nue', 'def', 'del', 'elif', 'else', 'except', 'finally', 'for',
'from', 'global', 'if', 'import', 'in', 'is', 'lambda', 'nonlocal', 'not', 'or',
'pass', 'raise', 'Output', 'try', 'while', 'with', 'yield']
o Operator placement:
§ Must be placed between two operands.
§ Operators cannot be consecu5ve.
o Parentheses:
§ All parentheses must be properly balanced and non-empty.
ENGG1330 Computer Programming I Assignment
Page 8 of 12
Your choices of difficulty
You may choose to ignore parentheses in the input arithmetic expression. In more
than half of the test cases, the input expressions do not contain parentheses. So, a correct
program that can validate arithmetic expressions without parentheses can still get more
than half of the marks in this problem.
Samples
• Valid Expressions
• Invalid expressions
o Invalid variable names
o Invalid operator placements
o Invalid parentheses
ENGG1330 Computer Programming I Assignment
Page 9 of 12
Programming Problem 5: Maze Solving with Backtracking Op5miza5on [35%]
(author: LIANG Shuang, email: sliang57@connect.hku.hk)
Background
The backtracking mechanism is a systematic algorithmic paradigm used to solve constraint
satisfaction and combinatorial optimization problems. In this problem, you will implement
backtracking mechanism to solve maze problems.
Part 0: Import Main Program
The following main program is given and embedded in VPL. So, you do not need to
include the code of the main program in your uploaded file. You must name your
uploaded file as "a5.py" and the function names must be the same as the ones required by
this problem. You must put this line of code, import a5_main, in the first line of your
uploaded program to allow your program to access the code in the main program.
ENGG1330 Computer Programming I Assignment
Page 10 of 12
The main program performs the following tasks.
• Ask user to enter the maze filename.
• Call the function load_maze() to load the maze structure.
• Print the maze returned by the function load_maze().
• Print the start and end coordinates returned by the function load_maze().
• Call the function backtracking() to solve the maze.
• Print the path returned by the function backtracking().
• In case of no solution, print "No solution exists!".
Note that the coordinates of a point refers to the row number star5ng from 0 at the top and
the column number star5ng from 0 on the leO, i.e., the coordinates of the top-leO corner of
a maze is (0,0).
Part 1: Load the Maze
Write the function load_maze(file_path) to load the maze structure from the input
text file.
The maze file contains the following elements:
• Walls: Represented by “*”
• Paths: Represented by “.”
• Start Point: Represented by “S”
• End Point: Represented by “T”
The function has to do the following tasks.
• Read the input text file.
• Convert the start point, the paths, and the end point to 0, and the walls to 1.
• Store the maze in a 2D list.
• Return the 2D list, the coordinates of the start point and end point.
Structure of the Function load_maze
def load_maze(file_path): """
Loads the maze structure from the input text file and converts it into a 2D
list.
Args:
file_path (str): Path to the maze text file.
Returns:
maze (list): 2D list representing the maze, where each item in the list is a
sub-list representing a row of the maze.
start (tuple): Coordinates of the start point.
end (tuple): Coordinates of the end point.
"""
# Complete your code here.
return maze, start, end
ENGG1330 Computer Programming I Assignment
Page 11 of 12
Part 2: Solving the Maze by Backtracking Mechanism
Write the function backtracking(maze, start, end) to implement backtracking
mechanism to solve mazes. Backtracking is an algorithmic technique for solving problems
by exploring potential paths and undoing (backtracking) steps when a dead-end is
encountered.
ImplementaIon Details
(1) Use a stack to record the player’s movement history. The stack allows backtracking by
popping the most recent posi5on when a dead-end is reached. In your func5on, the stack
records the state of every move consis5ng of three components: (posi5on, path, remaining
direc5ons).
position: coordinates (x, y) of the current posi5on
path: list of coordinates visited so far
remaining_directions: direc5ons yet to explore at this posi5on
(2) Use a list visited to store the posi5ons visited so far.
(3) Define directions as [(0, 1), (1, 0), (0, -1), (-1, 0)] (right, down, leO, up). For each
posi5on, try all direc5ons in reverse order, i.e., try up first, and then try leO next and so on
so forth.
(4) Define condi5onal statements to check whether a move is valid. A move is valid if:
A) The new posi5on is within the maze boundaries.
B) The new posi5on is on the path.
C) The new posi5on is not visited.
(5) If a valid move is found:
A) Move to the new posi5on.
B) Push the new state (posi5on, path, remaining direc5ons) to the stack.
(6) If no valid moves remain (dead-end encountered):
A) Remove the current posi5on from visited to allow revisi5ng to explore other
poten5al paths.
B) Pop the stack to trace back.
(7) Termina5on condi5ons:
A) Success: return the path if the current posi5on matches the end point.
B) No path found: Return None if the stack is empty.
Structure of the Function backtracking
def backtracking(maze, start, end):
# Complete your code here
while stack:
# Complete your code here
if current == end:
return path
# Complete your code here
return None
stack = [(position, path, remaining_directions), ...]
ENGG1330 Computer Programming I Assignment
Page 12 of 12
Important Note
Your program has to comply with the requirements and implementa5on details s5pulated in
this problem in order to find the expected path using backtracking. Even if your program can
find an alterna5ve path, it cannot pass the test cases.
Samples
Explanation of the first 3 steps
• At Step 0, the current posi5on is at the start point (0,4), the path consists of the start
point (0,4) and the direc5ons yet to explore consists of all direc5ons.
• At Step 1, the current posi5on is at (1,4) aOer trying up, leO and down at (0,4).
• At Step 2, the current posi5on is at (2,4) aOer trying up, leO and down at (1,4).
• At Step 3, the current posi5on is at (2,5) aOer trying up, leO, down and right at (2,4).
Step stack (posi'on, path, remaining direc'ons) from top to bo6om visited
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
