Here we look at the word ladder theme. We will use a list of four-letter words.

Here we look at the word ladder theme. We will use a list of
four-letter words. The main task now is to implement a function that
finds the shortest path between two four-letter words, where adjacent
words differ in one letter, with the additional novelty that we are
allowed a budget of fake words, words that are not on the list of valid words.
Let’s look at an example: If we want to find the shortest way to change four to five,
where we can only change one letter at a time and each word must be on
the valid word list, it takes us 6 moves:
four-tour-torr-tore-tire-fire-five. Every word here is on the word list.
Now
say we want to change four into five and we are allowed one fake word.
Adjacent words still have to differ by one letter, by now we are allowed
to use one fake word along the way. Now we can do it in just 4 moves:
four-forr*-fore-fire-five. Here forr is a fake word. All the other words
are on the valid word list.
We can also allow 2 fake words on
our way from four to five. Then we can do it in just 3 moves:
four-fovr*-fove*-five. As four and five differ on 3 letters, it will
always take us at least 3 moves to go from four to five. We cannot
improve on the length of the shortest path using more fake words.
Your main task for this part is to implement the member function shortestPathWithFakes which lives in the class LadderWithFakes.
We
leave a lot up to you in the scaffold. You can add whatever member
variables, helper functions, and libraries you need to complete the
task. We will test your implementation like this:
LadderWithFakes G {“4words.txt”};
std::vector<:string> path = G.shortestPathWithFakes(“four”, “five”, 1);
// check that path has the right properties
The starting and ending words will always be valid words.
ALL THE FILES ARE IN THE ZIP FILE
There are 15 tests provided in main.cpp. Each of these tests has equal weight.
Your code is additionally tested against 20 test cases (the 15 from
main.cpp plus 5 more) when you press mark. If your code does not time
out on the marker (VERY IMPORTANT)
Hints:
We again want to translate this into a graph problem. Remember that to
use breadth-first search we do not need to explicitly construct the
entire graph. All we need is to be able to iterate over all the vertices
which are adjacent to a given vertex. We can apply breadth-first search
on a very large graph and just explore a small part of it.
Imagine a directed graph where the vertices are represented by a std::pair<:string int>
. The string is going to be a four-letter string (word or non-word) and
the int represents a number of fakes. We have edges as follows. For any
four-letter string a, if b is a valid four letter word and a,b differ
on a single letter, then we have an edge {a, k} -> {b,k} for any
integer k (we only have to consider k at most our budget of fake words).
For any four-letter string a, if b is not a valid word, and a and b
differ on a single letter then we have an edge {a, k} -> {b, k+1}.
This is what we want because if we follow this edge we will use another
fake word so the number of fake words on the path we are taking goes up.
When we are looking for a path from origin to destination with a budget of BB fake words, we are looking for a shortest path from {origin, 0} to {destination, k} in this graph, over all k<=Bk<=B.
We can use breadth-first search to find such a shortest path!
Thebreadth-first solution can pass all the test cases in main.cpp, but it will time out when marked. To pass within time on the marker try implementing the Dijkstra/A* approach