আজকের এই পর্বে একটা string related প্রবলেম নিয়ে আলোচনা করা হবে।

Problem Statement:

 তোমাকে 1000 টা unique string দেয়া হবে। প্রতিটা string এর সাইজ 6। এই 1000 টা string এর মধ্যে একটি string আছে যেটাকে বলা হবে secret string। এই secret string কোনটা,সে ব্যাপারে তুমি কিছুই জানো না। শুধুমাত্র জাজ এর কাছে এ ব্যাপারে তথ্য থাকবে। তুমি জাজের কাছে কিছু query করতে পারবে। তোমাকে বের করতে হবে সেই secret string টা কোনটা!

জাজের কাছে আমরা যে ধরণের query করতে পারবো তার format এরকমঃ

int query(string)

রিপ্লাই হিসেবে জাজ তোমাকে জানাবে, secret string টির সাথে তোমার পাঠানো string টির কয়টি character exact position এ মিলে গেছে। যদি একটিও character (position সহ) না মিলে থাকে, তাহলে উত্তর আসবে 0। আর যদি এমন হয় যে তুমি সঠিকভাবে secret string টা guess করে জাজের কাছে পাঠিয়েছো, তাহলে উত্তর আসবে 6।

At most 10 টা query করে তোমাকে বলতে হবে, কোন string টি secret string! 😀

Brute Force:

একটা brute force solution এমন হতে পারে যে, আমরা সবগুলো string কেই একবার করে জাজের কাছে পাঠাবো। জাজ যদি একবার 6 রিটার্ন করে, সেই string টিই secret string.

কিন্তু এভাবে worst case এ 1000 টি query লাগতে পারে। তাই এটি ফাইনাল টেস্ট কেইস পাস করবে না।

Improvement:

কেমন হতো, যদি আমরা 1000 টা string এর মধ্যে যেসব string এর কোনো দরকার নেই, তাদের বাদ দিয়ে দিতাম? ধরো 500 টা string ই ফেলে দিলাম! এতে আমাদের লাভ হতো কি?

অবশ্যই হতো, যদি এমনভাবে আমরা সেটটাকে ছোট করতে পারি যেন কখনোই secret string টা বাদ না পরে, তাহলে একটা সময় এসে সেটটায় একটাই মাত্র string থাকবে এবং সেই string টিই হবে secret string!

তো কোনোভাবে ব্যাপারটা গোছানো গেল। কিন্তু string গুলোর এই সেটের সাইজ আমরা ছোট করবো কীভাবে?!

জাজ আমাদের প্রতি কুয়েরিতেই একটি করে ভ্যালু রিটার্ন করছে। আমরা কি কোনোভাবে একে কাজে লাগাতে পারি? ধরে নাও, তোমার কাছে 1000 টা string আছে। এই 1000 টা string এর মধ্যে secret string টি কে ধরলাম S. আমরা এবার 1000 টা string এর মধ্যে randomly একটা string বাছাই করে নিয়ে আসি। ধরি, বাছাইকৃত এই string টি হচ্ছে R. এই string টিকে এবার query হিসেবে জাজের কাছে পাঠাবো। ধরা যাক, জাজ আমাকে যেই ভ্যালুটা রিটার্ন করলো, সেটি হচ্ছে X. এই X বুঝাচ্ছে, R এবং S এর মধ্যে exactly কয়টা পজিশনের character হুবুহু মিলে গেছে।

এবার আমরা আমাদের সেটে শুধুমাত্র সেই string গুলোকেই রাখবো, যাদের সাথে randomly picked সেই string টির স্কোর আসবে exactly X.

যেমন ধরো আমাদের কাছে কিছু string এর একটি সেট দেয়া হয়েছে এমনঃ

S = [ abcdez , abcdee, zbcdex, pppppp, dfkjdc, dfmcze ]

Secret string: abcdez

Randomly একটা string ধরে নিয়ে আসি। ধরা যাক, এটি হচ্ছে dfkjdc. এবার dfkjdc কে জাজের কাছে পাঠালে জাজ আমাদের রিটার্ন করবে 0 (শূণ্য) , অর্থাৎ সিক্রেট স্ট্রিং এর সাথে আমাদের query স্ট্রিং এর কোনো ক্যারেক্টার পজিশন বাই পজিশন মেলেনি। এবার, সেট S এর যেসব string এর সাথে dfkjdc এর স্কোর আসবে 0 , আমরা শুধু তাদেরকেই সেটে রেখে বাকিদের ফেলে দেব।

এবার S হবে এমনঃ

S = [ abcdez , abcdee, zbcdex, pppppp ] এই 4টি string এর প্রত্যেকের স্কোর এসেছে 0। স্কোর বলতে বুঝাচ্ছি আমাদের latest query string টির সাথে exact position এ যতগুলো ক্যারেক্টার মিলে যাচ্ছে সেটার মান। আমাদের latest query string ছিলো dfkjdc.

এবার এই সেট থেকে আবার randomly একটা string বেছে নিয়ে জাজের কাছে পাঠিয়ে দিই। এবার পাঠাই zbcdex কে। জাজ আমাদের এবার রিটার্ন করবে 4.

একই কাজ আবার করে সেটটাকে ছোট করে নিয়ে আসি!

S = [ abcdez , abcdee ]

এবার randomly আরেকটা string কে বাছাই করে জাজের কাছে পাঠিয়ে দিই। ধরা যাক, এবার পাঠাচ্ছি abcdee কে। জাজ আমাদের রিটার্ন করবে 5.

আবার সেট ছোটকরণ চালানোর পরেঃ

S = [ abcdez ]

একটা মাত্র উপাদান থাকার অর্থ হচ্ছে, আমাকে আর কিছু করতে হবে না এখন। এটাই সেই secret string! আমরা এখানে 3টি কুয়েরি চালিয়ে বের করে ফেলেছি আমাদের secret string টি কোনটা! এভাবে খুবই দ্রুত সেটের সাইজ ছোট হতে হতে 1 এ চলে আসবে। কথা হচ্ছে, কত দ্রুত হবে?

সেটের সাইজ যদি 1000 হয়, randomly এভাবে একটা করে string বাছাই করতে থাকলে expected number of queries হতে পারে মাত্র 7 টা! 😀

দারুণ না? একটা গুরুত্বপূর্ণ observation হচ্ছে যে আমাদের হাতে যদি randomly create করা N সংখ্যক string থাকে তাহলে secret string এর সাথে কোনো পজিশনেই মিল পাওয়া যাবে না এমন string এর সংখ্যা হবে প্রায় 80%। কীভাবে? 6 length এর প্রথম পজিশনে ক্যারেক্টার না মেলার probability হবে 25/26. প্রথম এবং দ্বিতীয় পজিশনে না মেলার probability হবে (25/26)^2. এভাবে ৬টা পজিশনেই না মেলার probability হবে (25/26)^6 = 0.79031452573 বা প্রায় 80%!

প্রমাণঃ
স্ট্রিং সেটের সাইজ যদি N হয়,তাহলে expected কতগুলো query লাগতে পারে সেটি বের করার চেষ্টা করা যাক। উত্তরটা বের করা এতোটা সহজ হবে না! কারণ, পুরো প্রক্রিয়াটি randomly হচ্ছে।

একটা ফাংশন define করা যাক E(N) , যেখানে E(N) বুঝায় N size এর একটা সেটকে 1 size এ নামিয়ে নিয়ে আসতে expected number of queries কত হতে পারে। কিছু base case define করা যাকঃ

E(0) = E(1) = 0

নিচে একটি টেবিল দেয়া হলো। Randomly select করা একটি string কে জাজের কাছে পাঠিয়ে শূণ্য থেকে ছয় পর্যন্ত আমরা মোট সাত ধরণের স্কোর পেতে পারি। স্কোর যদি শূণ্য হয়, তাহলে 100 টি string এর মধ্যে আনুমানিক 80 টির মতো string থেকে যাবে, 20 টি বাদ পড়বে( কেন? সেটা উপরেই বলা আছে )। তবে স্কোর যদি 0 না হয়ে 1,2,3,4,5 কিংবা 6 হয়, তখন সেটের নতুন সাইজ কেমন হতে পারে সে ব্যাপারে নিচের টেবিল থেকে ধারণা নেয়া যাকঃ

Score New size of set
0 (25/26)^6 = approx. 80%
1 (6C1) * (25^5 / 26^6) = approx. 19%
2 (6C2) * (25^4 / 26^6) = approx. 2%
3 (6C3) * (25^3 / 26^6) = approx. 0.1%
4 (6C4) * (25^2 / 26^6) = approx 0.003%
5 (6C5) * (25^1 / 26^6) = approx 0.00004%
6 (6C6) * (25^0 / 26^6) = 0%

Elementary level এর probability এর হিসেব নিকেশ করা হয়েছে এখানে। একটু মনোযোগ দিলে সহজেই বুঝে যাওয়ার কথা।

এখন খেয়াল করো। একটা random string বাছাই করে আমরা একটি query খরচ করছি। একটি query খরচ করে আমরা উপরের 7 টি স্টেটের যেকোনো স্টেটে ভিন্ন ভিন্ন probability তে যেতে পারি! যদি probability tree আঁকি, তাহলে আরো পরিষ্কার হওয়ার কথাঃ

তার মানে, N size এর একটি সেট থেকে একটি string randomly বাছাই করলে সেটটির সাইজ কমে দাঁড়াতে পারে 7টি

সাইজের যেকোনো একটিত। যখন সেটের সাইজ 1 হয়ে আসবে, তখন আমরা থামবো। তাহলে expected number of steps হবেঃ

এখানের C++ কোডটির সাহায্যে N এর বিভিন্ন রকম মানের জন্যে expected number of queries calculate করা হয়েছে। দেখে আসতে পারো।

Problem Link: LeetCode – Guess the Word

Submission: C++ Code

সবাইকে ধন্যবাদ। 🙂