ক্রিপ্ট-এরিথমেটিক সমস্যায়, কিছু লেটার ব্যবহার করে ডিজিট অ্যাসাইন করা হয়। যেমন দশটি ভিন্ন লেটার ০ থেকে ৯ পর্যন্ত ডিজিট ভ্যালু ধারণ করে যাতে অ্যারিথমেটিক অপারেশন সঠিক হয়। দুটি শব্দ দেওয়া থাকে এবং একটি শব্দ দেওয়া থাকে যেটি সেই দুটি শব্দের যোগফল হিসেবে উত্তর। উদাহরণস্বরূপ, 'BASE' এবং 'BALL' দুটি শব্দ, এবং ফলাফল 'GAMES'। এখন যদি আমরা BASE এবং BALL তাদের সিম্বলিক ডিজিট দিয়ে যোগ করতে চাই, তবে আমরা GAMES পাব।
নোট - সর্বোচ্চ দশটি লেটার থাকতে হবে, অন্যথায় সমাধান সম্ভব নয়।
ইনপুট
এই অ্যালগরিদম তিনটি শব্দ নেবে।
আউটপুট
এটি দেখাবে কোন লেটার ০-৯ থেকে কোন নম্বর ধারণ করে।
এই কেসে এটি নিচের মতো।
| Letter | A | B | E | G | L | M | S |
| Values | 4 | 2 | 1 | 0 | 5 | 9 | 6 |
অ্যালগরিদম
এই সমস্যার জন্য, আমরা একটি নোড ডিফাইন করব, যেটি একটি লেটার এবং এর সংশ্লিষ্ট ভ্যালু ধারণ করবে।
isValid(nodeList, count, word1, word2, word3)
ইনপুট - নোডের লিস্ট, নোড লিস্টে এলিমেন্টের সংখ্যা এবং তিনটি শব্দ।
আউটপুট - True যদি word1 এবং word2-এর ভ্যালুর যোগফল word3-এর ভ্যালুর সমান হয়।
Begin
m := 1
for each letter i from right to left of word1, do
ch := word1[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done
val1 := val1 + (m * nodeList[j].value)
m := m * 10
done
m := 1
for each letter i from right to left of word2, do
ch := word2[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done
val2 := val2 + (m * nodeList[j].value)
m := m * 10
done
m := 1
for each letter i from right to left of word3, do
ch := word3[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done
val3 := val3 + (m * nodeList[j].value)
m := m * 10
done
if val3 = (val1 + val2), then
return true
return false
End
permutation(nodeList, count, n, word1, word2, word3)
ইনপুট - নোডের লিস্ট, লিস্টে আইটেমের সংখ্যা, অ্যাসাইন করা লেটারের সংখ্যা এবং তিনটি শব্দ।
আউটপুট - True যখন সব লেটার সঠিক ভ্যালু দিয়ে অ্যাসাইন করা হয়েছে যোগফল সমাধান করার জন্য।
Begin
if n letters are assigned, then
for all digits i from 0 to 9, do
if digit i is not used, then
nodeList[n].value := i
if isValid(nodeList, count, word1, word2, word3) = true
for all items j in the nodeList, do
show the letter and corresponding values.
done
return true
done
return false
for all digits i from 0 to 9, do
if digit i is not used, then
nodeList[n].value := i
mark as i is used
if permutation(nodeList, count, n+1, word1, word2, word3),
return true
otherwise mark i as not used
done
return false
End
উদাহরণ
#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) // যেসব ফ্রিকোয়েন্সি > 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
