fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <unordered_set>
  5. #include <string>
  6. #include <queue>
  7.  
  8. using namespace std;
  9.  
  10. // ✅ LeetCode-like function to find the shortest ladder length (BFS)
  11. int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
  12.     unordered_set<string> wordSet(wordList.begin(), wordList.end());
  13.     if (!wordSet.count(endWord)) return 0;
  14.  
  15.     queue<pair<string, int>> q;
  16.     q.push({beginWord, 1});
  17.  
  18.     while (!q.empty()) {
  19.         auto [word, steps] = q.front(); q.pop();
  20.         if (word == endWord) return steps;
  21.  
  22.         for (int i = 0; i < word.size(); i++) {
  23.             string temp = word;
  24.             for (char c = 'a'; c <= 'z'; c++) {
  25.                 temp[i] = c;
  26.                 if (wordSet.count(temp)) {
  27.                     wordSet.erase(temp);
  28.                     q.push({temp, steps + 1});
  29.                 }
  30.             }
  31.         }
  32.     }
  33.  
  34.     return 0; // no path found
  35. }
  36.  
  37. // ✅ Checks if two words differ by exactly one letter
  38. bool isOneLetterDiff(const string& a, const string& b) {
  39.     if (a.length() != b.length()) return false;
  40.     int diff = 0;
  41.     for (int i = 0; i < a.length(); ++i)
  42.         if (a[i] != b[i] && ++diff > 1)
  43.             return false;
  44.     return diff == 1;
  45. }
  46.  
  47. // ✅ Validates the entire path submitted by the player
  48. bool isValidLadderPath(const vector<string>& path,
  49.                        const unordered_set<string>& dictionary,
  50.                        const string& startWord,
  51.                        const string& endWord) {
  52.     if (path.empty() || path.front() != startWord || path.back() != endWord)
  53.         return false;
  54.  
  55.     for (const string& word : path) {
  56.         if (!dictionary.count(word)) {
  57.             cout << "❌ Word not in dictionary: " << word << endl;
  58.             return false;
  59.         }
  60.     }
  61.  
  62.     for (int i = 1; i < path.size(); ++i) {
  63.         if (!isOneLetterDiff(path[i - 1], path[i])) {
  64.             cout << "❌ Invalid step: " << path[i - 1] << " -> " << path[i] << endl;
  65.             return false;
  66.         }
  67.     }
  68.  
  69.     return true;
  70. }
  71.  
  72. // ✅ Loads dictionary of given length from file
  73. unordered_set<string> loadDictionary(const string& filename, int wordLength, vector<string>& wordListOut) {
  74.     unordered_set<string> dict;
  75.     ifstream file(filename);
  76.     string word;
  77.     while (file >> word) {
  78.         if (word.length() == wordLength) {
  79.             dict.insert(word);
  80.             wordListOut.push_back(word); // for ladderLength()
  81.         }
  82.     }
  83.     return dict;
  84. }
  85.  
  86. // 🧩 Entry point
  87. int main() {
  88.     string startWord = "cold";
  89.     string endWord = "warm";
  90.  
  91.     // 🔽 Load dictionary and filtered word list
  92.     vector<string> wordList;
  93.     unordered_set<string> dictionary = loadDictionary("words.txt", startWord.length(), wordList);
  94.  
  95.     // 🧠 Calculate the minimum steps required
  96.     int minSteps = ladderLength(startWord, endWord, wordList);
  97.     if (minSteps == 0) {
  98.         cout << "❌ No valid transformation from " << startWord << " to " << endWord << ".\n";
  99.         return 0;
  100.     }
  101.  
  102.     cout << "🎮 Game Start! Transform '" << startWord << "' to '" << endWord << "'.\n";
  103.     cout << "📏 Minimum steps possible: " << minSteps << endl;
  104.  
  105.     // 🧑‍💻 Simulate user path input (replace this with actual input from player)
  106.     vector<string> userPath = {"cold", "cord", "card", "ward", "warm"}; // <-- replace with user input logic
  107.  
  108.     // ✅ Validate player path
  109.     if (isValidLadderPath(userPath, dictionary, startWord, endWord)) {
  110.         cout << "✅ Valid path submitted!\n";
  111.         int playerSteps = userPath.size();
  112.         cout << "📦 Player steps: " << playerSteps << endl;
  113.  
  114.         // 🧮 Score computation
  115.         int score = 0;
  116.         if (playerSteps == minSteps) score = 100;
  117.         else if (playerSteps > minSteps) score = max(0, 100 - 10 * (playerSteps - minSteps));
  118.         else score = 0;
  119.  
  120.         cout << "🏆 Score: " << score << "/100\n";
  121.     } else {
  122.         cout << "❌ Invalid path submitted.\n";
  123.     }
  124.  
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
❌ No valid transformation from cold to warm.
https://ideone.com/YrB0Ws
language:
C++ (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!