CSCI1540 Fundamental Computing with C++, Fall 2020/21
Department of Computer Science and Engineering,
Assignment 5: Ghost Leg
Due: 20:00, Tue 24 Nov 2020 File name: ghostleg.cpp Full marks: 100
Introduction
The objective of this assignment is to practice the use of 2-D arrays with loops. You will write a
program to play Ghost Leg (), a method of lottery to create pairings between some players
and some items. It consists of some vertical lines, with some other lines called legs connecting two
adjacent vertical lines scattered arbitrarily along their length. Two legs must not connect at the same
point nor cross each other. A player will choose a vertical line at the top, and follow this line
downwards. When a leg is encountered, follow the leg to get to another vertical line and continue
downwards. Repeat this procedure until the end of a vertical line is reached. Then the player is
paired with the item at the bottom of the vertical line. Figure 1 shows an example Ghost Leg
configuration. A player who picks K at the top will eventually arrive at item b at the bottom. The
pairings between the top and bottom must be a one-one correspondence. No two items at the top
would reach the same item at the bottom. Your program shall generate a Ghost Leg configuration
with some user inputs, and then traverse paths from top to bottom to reveal all the pairings.
Figure 1: A Ghost Leg Configuration
Program Specification
Array Representation of a Ghost Leg Configuration
➢ Figure 2 shows the printing format of a Ghost Leg configuration. It corresponds to the
configuration in Figure 1. We name the top and bottom ends of the vertical lines as A–O and a–o
respectively, and we use 0–10 to denote the positions along the vertical lines. There can be three
kinds of legs: (1) legs that go horizontal (-), (2) legs that go up left-to-right (/), and (3) legs that go
down left-to-right (\). They are marked in different ways in the printing.
CSCI1540 Fundamental Computing with C++,
Figure 2: Printing Format of a Ghost Leg Configuration
➢ You are required to use a two-dimensional array of char with 21 rows and 14 columns to
represent a Ghost Leg configuration.
char map[21][14];
➢ This array will be used to store the contents to the right of the vertical lines in a Ghost Leg
configuration. The array stores the symbols ‘-’, ‘<’, ‘!’, ‘>’, and ‘ ’ (space). Figure 3 shows the
array contents that correspond to the Ghost Leg configuration in Figure 2. The space ‘ ’ is shown
as ˽ for clarity.
➢ We do not store the vertical lines in this array. They are just printed out but not stored.
➢ The numbers to the leftmost of the Ghost Leg configuration (0–10) are for user input purpose
only. (See phase 2 of Program Flow later.) They are not exactly the row indices of the array. E.g.,
the row with leftmost number 5 actually corresponds to row index 10 of the array.
➢ There are 15 vertical lines (A–N) but there are only 14 columns in the array. This is because there
can be no legs to the right of vertical line N, so we do not have to store anything for line N.
/ leg
\ leg
- leg
CSCI1540 Fundamental Computing with C++,
Figure 3: Example Array Contents of a Ghost Leg Configuration
Program Flow
The program should execute in the following three phases:
1. Initialize the Ghost Leg configuration (Easy!)
➢ You should initialize the Ghost Leg configuration to be empty. (The array should contain all spaces
and no legs.)
2. Add and draw the legs to the map (Difficult!)
➢ In this phase, you should repeatedly prompt the program user to enter leg locations and add
them to the map, until a special input (see below) is entered.
➢ Each input leg consists of the positions of its two endpoints. Each position is a character followed
by an integer. E.g., B0 C3 means a leg connecting positions B0 and C3. (Hint: you can use
cin >> … >> … >> … >> …; to read in the four components in the input.) The leg will then
be added to the map. Figure 4 shows an example of adding a leg B0 C3 to an empty Ghose Leg
map.
Figure 4: Adding a leg B0 C3
CSCI1540 Fundamental Computing with C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 4 of 8
➢ A special input Z0 Z0 is used to denote the end of entering legs. You do not really draw this leg
in the map.
➢ You can assume that the column inputs are always uppercase letters. But you still need to check if
a user input is valid or not. An input is valid if it is the special input Z0 Z0 or all the followings are
satisfied.
▪ The column labels are A–O and the row labels are 0–10.
▪ The first and second positions of the input must be in consecutive and ascending columns. E.g.,
B0 C3 is valid but B0 D3 and C3 B0 are invalid.
▪ The input leg cannot cross an existing leg. E.g., with an existing leg B0 C3, you can no longer
add B1 C1.
▪ The input leg cannot connect with an existing leg at its two endpoints. E.g., with an existing leg
B0 C3, you can no longer add any legs that connect positions B0 or C3.
➢ When the user enters an invalid input, you need to display a warning message and ask the user to
enter again until a valid input is made.
3. Find all the pairings from top to bottom (Difficult!)
➢ In this phase, you should start from every point A to O at the top to traverse to the bottom of the
map to discover the pairings at the bottom labeled a to o, according to the rule of Ghost Leg.
➢ All the pairings should then be displayed.
Special Requirements
➢ Global variables (variables declared outside any functions) are not allowed. Nonetheless, const
ones do not count.
➢ Your program should be decomposed into at least five functions (including main()). At least
two functions should have array parameter(s).
Sample Run
In the following sample run, the blue text is user input and the other text is the program printout.
More sample runs are provided in Blackboard. Besides, you can try the provided sample program for
other input. Your program output should be exactly the same as the sample program (same text,
symbols, letter case, spacings, etc.). Note that there is a space after the ‘:’ in the program printout.
CSCI1540 Fundamental Computing with C++, Fall 2020/21
Department of Computer Science and Engineering,
a b c d e f g h i j k l m n o
Enter a leg (Z0 Z0 to finish): O1 P3↵
Invalid. Try again!
Enter a leg (Z0 Z0 to finish): A0 B11↵
Invalid. Try again!
Enter a leg (Z0 Z0 to finish): B1 C2↵
Invalid. Try again!
Enter a leg (Z0 Z0 to finish): B2 A3↵
Invalid. Try again!
Enter a leg (Z0 Z0 to finish): B1 C1↵
Invalid. Try again!
Enter a leg (Z0 Z0 to finish): B3 C0↵
Invalid. Try again!
Enter a leg (Z0 Z0 to finish): A1 B0↵
CSCI1540 Fundamental Computing with C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 6 of 8
Invalid. Try again!
Enter a leg (Z0 Z0 to finish): C3 D3↵
Invalid. Try again!
Enter a leg (Z0 Z0 to finish): A3 B2↵
A B C D E F G H I J K L M N O
a b c d e f g h i j k l m n o
⋮ (Many inputs skipped. See Blackboard for full version.)
CSCI1540 Fundamental Computing with C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 7 of 8
A B C D E F G H I J K L M N O
a b c d e f g h i j k l m n o
CSCI1540 Fundamental Computing with C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 8 of 8
Matching results...
Submission and Marking
➢ Your program file name should be ghostleg.cpp. Submit the file in Blackboard
(https://blackboard.cuhk.edu.hk/).
➢ Insert your name, student ID, and e-mail as comments at the beginning of your source file.
➢ Besides the above information, your program should further include suitable comments as
documentation.
➢ You can submit your assignment multiple times. Only the latest submission counts.
➢ Your program should be free of compilation errors and warnings.
➢ Do NOT plagiarize. Sending your work to others is subjected to the same penalty as the copying
student.