Doublet (Word Ladder) Solver — C++11

This program solves doublet/word ladder puzzles: given two 5‑letter words, it finds the shortest path from one to the other by changing one letter at a time, using only valid words from knuth.txt.

It builds a graph where every node is a dictionary word and edges connect words that differ by exactly one letter, then runs Breadth‑First Search (BFS) to find the shortest path.

---

Project Summary

• Dictionary: knuth.txt (5‑letter words).
• Graph: vertices = words, edges = Hamming distance 1.
• Algorithm: BFS for shortest path.
• Outputs: Prints the word ladder (e.g., black -> ... -> white).
• Included: graph2.h adjacency‑list graph (borrowed utility).

The provided main2.cpp already solves seven example doublets; you can swap in any two 5‑letter words from knuth.txt.

---

Repository Layout (suggested)

.
├── main2.cpp        # Builds the word graph from knuth.txt and runs BFS ladders
├── graph2.h         # Lightweight adjacency-list graph utilities
└── knuth.txt        # Dictionary of 5-letter words (one per line)

---

Build & Run

Requires a C++ compiler with C++11 support (e.g., g++, Clang, MSVC).

# Build
g++ -std=c++11 -O2 -o doublet main2.cpp

# Run (uses the seven hardcoded examples in main2.cpp)
./doublet

You should see output like:

reading dictionary into graph...

Solving black to white...
black -> ...
...
Solving amigo to signs...
amigo -> ...

---

How It Works

1. similar(w1, w2)
   Returns true iff the words differ by exactly one letter (Hamming distance = 1).

2. words_to_graph(wordfile, v1)

   • Reads all words from knuth.txt into v1.
   • Adds a vertex per word to the graph.
   • Adds an undirected edge between any pair of words differing by one letter.

3. solve_doublet(w1, w2, g, words)

   • Breadth‑first search (BFS) from w1 to w2.
   • Tracks parents to reconstruct the shortest path.
   • Prints the ladder if one exists; otherwise prints “There is no solution!”.

---

Complexity Notes

• Graph construction is O(N² · L) in the naive pairwise comparison (N = #words, L = word length).
  For the 5‑letter word list in knuth.txt, this is acceptable. For larger dictionaries you can optimize by bucketing words using wildcard patterns (e.g., _ETAL, M_TAL, …) to reduce comparisons to near‑linear.

• BFS is O(N + M) where M is the number of edges.

---

Customize / Extend

• Try your own pairs: Edit the seven solve_doublet(...) calls in main2.cpp with your words (must exist in knuth.txt).
• Accept command‑line input (optional): Replace the hardcoded pairs with argv parsing to run ./doublet start end.
• Different dictionary: Swap knuth.txt for another 5‑letter list (one word per line).

---

File Formats

• knuth.txt
  Plain text, one 5‑letter word per line. Case is treated as written (compare consistently).

---

Example: Adding Your Own Pair

In main2.cpp, modify:

solve_doublet("black","white",g1,words);
solve_doublet("tears","smile",g1,words);
// ...

For a custom pair:

solve_doublet("spice","space",g1,words);

---

Troubleshooting

• “There is no solution!”: Ensure both words are in knuth.txt and have the same length (5).
• Slow build step: Graph creation is quadratic; try an optimized neighbor‑generation scheme if you enlarge the dictionary.
• Character case: Keep all words lowercase or make comparisons case‑insensitive consistently.