Homework 5

Due: See homework page
Directory name in your github repository for this homework (case sensitive): hw5

Updates

2026/04/03 - Coding portion is released.

Written Portion

Problem 0 - No Written Portion for this Homework (0%)

Coding Portion

Github Classroom URL

Signup link to create your HW5 repo: signup link

Reminder: A Few Notes on Repositories

Never clone one repo into another. Clone your new homework repo under (in) the cs104-repos.
Clone your repo using the ssh approach, NOT https.
- Clone your repo:

  git clone git@github.com:usc-csci104-spring2026/<your_hw5_repo>

In the VS Code editor, choose File..Open Folder and then find and open that folder (i.e. cs104-repos/<your_hw5_repo>)

Problem 1 - Recursion, Counting, and Combinations (50%)

Consider the popular game (at least at the time of this writing) of Wordle. A 5-letter English word is chosen at random (though we will extend this to support n-letter words) and the user has some number of chances to guess the word. As the user guesses words, letters in their guess that match the selected word in the correct location are highlighted in green, while letters (which may include duplicates) that are part of the word but not in the correct location are highlighted in yellow. So, if the selected word was total and the user guessed treat, the first t and a in treat would be highlighted in green to indicate they are in the correct location and the last t would be marked in yellow to indicate that there is another t in the select word but not at the correct location, and all other letters (such as r) would appear in gray to indicate they are not found in the word.

In this program, you will write a tool to aide players of a Wordle-like game (it does not have the exact semantics of Wordle, but is similar). Suppose the user would like to know what English-language words exist that meet certain criteria (so they can think of potential guesses). The user will provide you an input of how many letters the word is, what letters have already been guessed in their correct location (akin to the green letters), and a list of letters that they know MUST appear in the word (akin to the yellow letters, but without indicating where those letters CANNOT be). They will NOT provide the list of gray letters, meaning you will need to try all possible letters when trying to fill in a blank location in the word.

So your task will be to write a function (and any desired helper functions), to compute all possible English-language words that exist given a string containing the already-guessed letters that are in the correct location (we will refer to these as fixed letters since they may not change position and must stay in that location) and a string of the already-guessed letters that are MUST appear in the word somewhere (we will refer to these as floating letters since their position may be in any of the remaining locations). Again, we are not actually writing code to play the game but code that can help players consider potential future guesses given some of the knowledge they’ve learned from previous guesses. Your approach should be to generate all possible strings of lower-case, alpha characters that contain the fixed haracters (in their given location), floating characters (in any locations), and fill in any remaining letters with all possible options and then check if any of those strings are true English-language words. We will provide a std::set<std::string> of all possible English-language words (i.e. essentially a dictionary) that you may use for this task (which we read from a provided file: dict-eng.txt).

The signature of the function you are to write must be (and cannot be changed):

std::set<std::string> wordle(
    const std::string& in,
    const std::string& floating,
    const std::set<std::string>& dict);

Note: We realize that this may be an inefficient approach to finding all the words that match the given constraints. If we were not forcing you to use this approach, it may be easier to find the words that start with a given letter and iterate through them in the sorted order that the set provides checking to see if the word matches the given constraints. However, one can see that if the first letter or two are unknown, then this may require iterating through the whole dictionary, and so, in some cases, may be faster to generate all the possible strings, as we do here.

Input format

To indicate how many letters the selected word has AND the correct, fixed location letters already guessed, we will use a string of length n (for an n-letter word), using the - character to indicate a blank location and characters filling in the correct, fixed locations. So the input string -i- means we want to find all 3 letter words that have an i as the middle character.

We will then pass in a second string of the floating (yellow) characters that contains the characters (in any order) that we know must be part of the selected word but whose location is unknown. So if you were given a first input string of -i-- and second input string dn, you should output all words that have i as the 2nd letter and contain d and n. A sample output is below. Since the results are stored in a set, they can be printed in any order. We have provided a “driver”/test program (wordle-driver.cpp) that will take in these two strings from the command line, call your function, and then print out the results from the set of strings returned.

Program execution and command line arguments.

./wordle-driver -i-- dn

Printed results:

bind
dine
ding
dins
dint
find
hind
kind
mind
rind
wind

Use wordle-driver to do some sanity tests of your code before moving on to any of the tests from our grading suite. Note: To discourage any attempt to hard-code or game the system, the instructor may run additional tests after submission that were not provided, though they will be similar in format and content.

Requirements and Assumptions

As always you may not change the signature of the primary function provided.
You MAY define helper functions in wordle.cpp.
You MUST use a recursive approach to find all combinations of letters to form the length-n word. Failure to do so will lead to a 0 on this part of the assignment.
- Really you should only have 1 or 2 loops to help set the characters in any given location, and maybe 1 to 2 other loops to help with various constraint checks, etc. But to ensure you do not somehow brute-force the solutions, you may use at most 5 loops in your entire implementation in wordle.cpp.
You may NOT use any functions from the algorithm library (nor should you really need to).
You do NOT need to implement any kind of backtracking approach where you attempt to determine if a string can possibly be an valid English-language word as you are forming it. Instead, just generate all possible strings and check if each word is in the dictionary once it has the full n letters.

Hints and Approach

Recall that when generating all combinations you use recursion to build up a combination 1 “place” at a time, with each recursion responsible for 1 “place/location” of the combination. For that place, each recursion should try all the viable “options”, recursing after each one, and, upon return, undo and try the next option if a solution has not been found (or if multiple solutions are desired). Think carefully about what “options” should be tried at each location. Can any letter be used at any open place? What limitaiton do the floating letters provide?

By generating all combinations of n-length words that meet the restrictions given by the fixed and floating characters, it becomes simple to check whether the combination is a valid English-language word once the combination has its full n letters.

Problem 2 - Recursion and Backtracking and Boolean Satisfiability (50%)

Suppose a company needs to schedule d (which stands for needed) out of k (possible) workers (e.g. nurses at a hospital) per day given their availability over an n day period. The company requires exactly d workers (nurses) per day but does not allow any individual to work more than m (maxShifts) shifts over the n day period. Given d, m, and the k workers’ availability for each of the n days, write a backtracking search function to schedule the nurses, such that exactly d work on each of the n days and no one works more than m shifts.

The prototype for the function you will write is given below, along with some typedefs for the input and output data structures.

// type for the ID of a worker
typedef unsigned int Worker_T;
// n-by-k Matrix of each of the k workers' availability over an n-day period
typedef std::vector<std::vector<bool>> AvailabilityMatrix;
// n-by-d matrix with the d worker IDs who are scheduled 
// to work on each of the n days
typedef std::vector<std::vector<Worker_T> > DailySchedule;

/**
 * @brief Produces a work schedule given worker availability,
 *        the number of needed workers per day, and the maximum 
 *        shifts any single worker is allowed. Returns true if
 *        and the valid schedule if a solution exists, and false
 *        otherwise. 
 * 
 * @param [in]  avail n x k vector of vectors (i.e. matrix) of the availability
 *                    of the k workers for each of the n days
 * @param [in]  dailyNeed Number of workers needed per day (aka d)
 * @param [in]  maxShifts Maximum shifts any worker is allowed over 
 *                        the n day period (aka m)
 * @param [out] sched n x d vector of vectors indicating the d workers
 *                    who are scheduled to work on each of the n days
 * @return true if a solution exists; sched contains the solution
 * @return false if no solution exists; sched is undefined (can be anything)
 */
bool schedule(
    const AvailabilityMatrix& avail,
    const size_t dailyNeed,
    const size_t maxShifts,
    DailySchedule& sched
);

Explanation

The avail matrix is an n row by k column matrix of booleans. Each row represents one day of the schedule and each column is one worker’s availability to work on each day.

           W  W  W  W
           o  o  o  o
           r  r  r  r
           k  k  k  k
           e  e  e  e
           r  r  r  r
           0  1  2  3

           |  |  |  |
           |  |  |  |
           V  V  V  V

Day 0 -->  1  1  1  1
Day 1 -->  1  0  1  0
Day 2 -->  1  1  0  1
Day 3 -->  1  0  0  1

So we see in the avail matrix above that every worker is available to work on day 0 while only worker 0 and 2 are available on day 1, and so on.

You should produce a schedule solution that is an n by d matrix, where each row represents a day in the schedule and stores the d IDs of the workers who have been scheduled to work that day (each entry must thus be a value in the range 0 to k-1). So given the availability matrix above and inputs of m=2 and d=2, a valid schedule results would be:

The above indicates that on day 0 (top row), worker 1 and 2 will be scheduled. Then on day 1 (next row), worker 0 and 2 will be scheduled and so on. You can verify with the avaialbility matrix that all workers are available on their scheduled days and no worker works more than m=2 shifts.

Testing

We have provided a “driver”/test program (schedwork-driver.cpp) where you can alter an availability matrix and values for d (dailyNeed) and m (maxShifts) and then call your algorithm and print the results.

Use schedwork-driver to do some sanity tests of your code before moving on to any of the tests from our grading suite. Note: To discourage any attempt to hard-code or game the system, the instructor may run additional tests after submission that were not provided, though they will be similar in format and content.

Requirements and Assumptions

As always you may not change the signature of the primary function provided.
You MAY define helper functions in schedworker.cpp
You MUST use a recursive approach that follows the general backtracking structure presentedin class. Failure to use such a recursive approach will lead to a 0 on this part of the assignment.
You MAY use functions from the algorithm library such as std::find, if you desire.
The order in which you list the worker IDs in each row of the final schedule doesn’t matter (i.e. if Worker 1, 2, 3 is scheduled to work on a given day, then 3, 2, 1 is also acceptable).

Hints and Approach

Recall that a backtracking search algorithm is a recursive algorithm that is similar to generating all combinations, but skipping the recursion and moving on to another option if the current option violates any of the constraints. It is likely easiest to recurse over each place in the schedule (i.e. the 2D sched matrix). Each recursive call would be responsible for filling in one of the n*d schedule openings, ensuring the constraints of availability and the maximum number of shifts allowed for each worker is met. If you have already done a lab regarding backtracking search, it would likely be beneficial to look it over.

Submission Files

Add, commit and push your source files including all the .cpp and .h files and Makefile.
Do NOT add/commit/push .o files or executables (things that the compiler can easily generate anytime we need). If you want to avoid adding files you should not, you can add the lines to your .gitignore and then save, add, commit, push the .gitignore

Do NOT commit/push any test suite folder/files that we provide from the resources repo. When we grade your code, we will move a fresh copy of the hw5_tests folder into your repo, cd to that test folder, and run

cmake .
make grade

WAIT You aren’t done yet. Complete the last section below to ensure you’ve committed all your code.

Commit then Re-clone your Repository

Be sure to add, commit, and push your code in your hw5 directory to your assignment repository. Now double-check what you’ve committed, by following the directions below (failure to do so may result in point deductions):

In your terminal, cd to the top level folder (e.g. cs104-repos) that has your resources and hw5-<your_reponame> repos, etc.

cd ~
cd cs104-repos  # or wherever you store your repos

Create a subfolder called verify using the mkdir command below and then cd into that folder.

mkdir -p verify
cd verify

Clone a new copy (of the latest contents that you pushed) of your assignment repo hw_username repo:

git clone git@github.com:usc-csci104-spring2026/hw5-<your_reponame>.git`
cd hw5-<your_reponame>

Copy the test suite folder again into this new repo copy: `

cp -rf ../../resources/hw5_tests  .

Recompile and rerun your programs and tests to ensure that what you submitted works. You may need to copy over a test-suite folder from the resources repo, if one was provided.

cd hw5_tests
cmake .
make grade

And ensure all the tests pass (or the ones you expect to pass).

If there is a discrepancy, you likely did not add/commit/push your latest code. Go back to your cs104-repos/hw5-<your_username> repo/folder and figure out what did not get pushed, and rectify the situation.

Then, you can come back to cs104-repos/verify/hw5-<your_username>/hw5_tests and re-run make grade, repeating this process until it gives the expected results.