ক্রিপ্টারিথমেটিক পাজল সমাধান

ক্রিপ্ট-এরিথমেটিক সমস্যায়, কিছু লেটার ব্যবহার করা হয় ডিজিট অ্যাসাইন করার জন্য। যেন দশটি ভিন্ন লেটার ০ থেকে ৯ পর্যন্ত ডিজিট ভ্যালু ধারণ করে সঠিক এরিথমেটিক অপারেশন করতে পারে। দুটি শব্দ দেওয়া থাকে এবং একটি শব্দ দেওয়া থাকে তাদের যোগফলের উত্তর হিসেবে।

উদাহরণস্বরূপ, দুটি শব্দ 'BASE' এবং 'BALL', এবং রেজাল্ট 'GAMES'। এখন যদি আমরা BASE এবং BALL কে তাদের সিম্বলিক ডিজিট দিয়ে যোগ করি, তবে উত্তর GAMES পাব।

নোট - সর্বোচ্চ দশটি লেটার থাকতে হবে, অন্যথায় সমাধান করা যাবে না।

ইনপুট এবং আউটপুট

ইনপুট: এই অ্যালগরিদম তিনটি শব্দ নেবে। B A S E B A L L ---------- G A M E S আউটপুট: এটি দেখাবে কোন লেটার ০-৯ থেকে কোন নম্বর ধারণ করছে। এই কেসে এটা এমন।  B A S E 2 4 6 1 B A L L 2 4 5 5 --------- --------- G A M E S 0 4 9 1 6

অ্যালগরিদম

এই সমস্যায়, আমরা একটি নোড ডিফাইন করব, যেটি একটি লেটার এবং এর করেসপন্ডিং ভ্যালু ধারণ করবে।

isValid(nodeList, count, word1, word2, word3)

ইনপুট - নোডের লিস্ট, নোড লিস্টে এলিমেন্টের সংখ্যা এবং তিনটি শব্দ।

আউটপুট - True যদি word1 এবং word2-এর ভ্যালুর যোগফল word3-এর ভ্যালুর সমান হয়।

শুরু
  m := 1
  word1-এর ডান থেকে বামে প্রতিটি লেটার i-এর জন্য করুন
    ch := word1[i]
    nodeList-এর সব এলিমেন্ট j-এর জন্য করুন
      যদি nodeList[j].letter = ch, তবে
        ব্রেক করুন
      শেষ
    val1 := val1 + (m * nodeList[j].value)
    m := m * 10
  শেষ
  m := 1
  word2-এর ডান থেকে বামে প্রতিটি লেটার i-এর জন্য করুন
    ch := word2[i]
    nodeList-এর সব এলিমেন্ট j-এর জন্য করুন
      যদি nodeList[j].letter = ch, তবে
        ব্রেক করুন
      শেষ
    val2 := val2 + (m * nodeList[j].value)
    m := m * 10
  শেষ
  m := 1
  word3-এর ডান থেকে বামে প্রতিটি লেটার i-এর জন্য করুন
    ch := word3[i]
    nodeList-এর সব এলিমেন্ট j-এর জন্য করুন
      যদি nodeList[j].letter = ch, তবে
        ব্রেক করুন
      শেষ
    val3 := val3 + (m * nodeList[j].value)
    m := m * 10
  শেষ
  যদি val3 = (val1 + val2), তবে
    return true
  return false
শেষ

permutation(nodeList, count, n, word1, word2, word3)

ইনপুট - নোডের লিস্ট, লিস্টে আইটেম সংখ্যা, অ্যাসাইন করা লেটারের সংখ্যা এবং তিনটি শব্দ।

আউটপুট - True যখন সব লেটার সঠিক ভ্যালু দিয়ে অ্যাসাইন হয়ে যোগফল সমাধান করে।

শুরু
  যদি n লেটার অ্যাসাইন হয়ে যায়, তবে
    ০ থেকে ৯ পর্যন্ত সব ডিজিট i-এর জন্য করুন
      যদি ডিজিট i ইউজড নয়, তবে
        nodeList[n].value := i
        যদি isValid(nodeList, count, word1, word2, word3) = true
          nodeList-এর সব আইটেম j-এর জন্য করুন
            লেটার এবং করেসপন্ডিং ভ্যালু শো করুন।
          শেষ
          return true
      শেষ
    রিটার্ন false
  ০ থেকে ৯ পর্যন্ত সব ডিজিট i-এর জন্য করুন
    যদি ডিজিট i ইউজড নয়, তবে
      nodeList[n].value := i
      i কে ইউজড হিসেবে মার্ক করুন
      যদি permutation(nodeList, count, n+1, word1, word2, word3),
        return true
      অন্যথায় i কে আনইউজড হিসেবে মার্ক করুন
    শেষ
  রিটার্ন false
শেষ

উদাহরণ

#include <iostream> #include<vector> using namespace std; vector<int> use(10); //১ সেট করুন, যখন এক ক্যারেক্টার আগে অ্যাসাইন করা হয়েছে struct node { char letter; int value; }; int isValid(node* nodeList, const int count, string s1, string s2, string s3) { int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i; for (i = s1.length() - 1; i >= 0; i--) { //প্রথম স্ট্রিংয়ের নাম্বার বের করুন char ch = s1[i]; for (j = 0; j < count; j++) if (nodeList[j].letter == ch) //যখন ch পাওয়া গেল, লুপ ব্রেক করুন break; val1 += m * nodeList[j].value; m *= 10; } m = 1; for (i = s2.length() - 1; i >= 0; i--) { //দ্বিতীয় স্ট্রিংয়ের নাম্বার বের করুন char ch = s2[i]; for (j = 0; j < count; j++) if (nodeList[j].letter == ch) break; val2 += m * nodeList[j].value; m *= 10; } m = 1; for (i = s3.length() - 1; i >= 0; i--) { //তৃতীয় স্ট্রিংয়ের নাম্বার বের করুন char ch = s3[i]; for (j = 0; j < count; j++) if (nodeList[j].letter == ch) break; val3 += m * nodeList[j].value; m *= 10; } if (val3 == (val1 + val2)) //চেক করুন যোগফল ৩য় স্ট্রিংয়ের সমান কিনা return 1; return 0; } bool permutation(int count, node* nodeList, int n, string s1, string s2, string s3) { if (n == count - 1) { //যখন সব ক্যারেক্টারের জন্য ভ্যালু অ্যাসাইন হয়েছে for (int i = 0; i < 10; i++) { if (use[i] == 0) { //যেসব নাম্বার ইউজড নয় nodeList[n].value = i; //ভ্যালু i অ্যাসাইন করুন if (isValid(nodeList, count, s1, s2, s3) == 1) { //ভ্যালিডেশন চেক করুন cout << "Solution found: "; for (int j = 0; j < count; j++) //অ্যাসাইন করা কোড প্রিন্ট করুন cout << " " << nodeList[j].letter << " = " << nodeList[j].value; return true; } } } return false; } for (int i = 0; i < 10; i++) { if (use[i] == 0) { //যেসব নাম্বার ইউজড নয় nodeList[n].value = i; //ভ্যালু i অ্যাসাইন করুন এবং ফিউচার ইউজের জন্য আনঅভেইলেবল মার্ক করুন use[i] = 1; if (permutation(count, nodeList, n + 1, s1, s2, s3)) //নেক্সট ক্যারেক্টারের জন্য যান return true; use[i] = 0; //যখন ব্যাকট্র্যাক করে, আবার এভেইলেবল করুন } } return false; } bool solvePuzzle(string s1, string s2,string s3) { int uniqueChar = 0; //ইউনিক ক্যারেক্টার সংখ্যা int len1 = s1.length(); int len2 = s2.length(); int len3 = s3.length(); vector<int> freq(26); //২৬টি ভিন্ন ক্যারেক্টার আছে for (int i = 0; i < len1; i++) ++freq[s1[i] - 'A']; for (int i = 0; i < len2; i++) ++freq[s2[i] - 'A']; for (int i = 0; i < len3; i++) ++freq[s3[i] - 'A']; for (int i = 0; i < 26; i++) if (freq[i] > 0) //যেসব ফ্রিকোয়েন্সি > ০, সেসব উপস্থিত uniqueChar++; if (uniqueChar > 10) { //কারণ ডেসিমেল সিস্টেমে ১০ ডিজিট আছে cout << "Invalid strings"; return 0; } node nodeList[uniqueChar]; for (int i = 0, j = 0; i < 26; i++) { //তিনটি স্ট্রিংয়ে পাওয়া যাবত ক্যারেক্টার অ্যাসাইন করুন if (freq[i] > 0) { nodeList[j].letter = char(i + 'A'); j++; } } return permutation(uniqueChar, nodeList, 0, s1, s2, s3); } int main() { string s1 = "BASE"; string s2 = "BALL"; string s3 = "GAMES"; if (solvePuzzle(s1, s2, s3) == false) cout << "No solution"; }

আউটপুট

Solution found: A = 4 B = 2 E = 1 G = 0 L = 5 M = 9 S = 6