এক সারি switch, একসাথে সরাও আর মেলাও

Alice একটা lamp-এর সারির উপর ছিদ্র করা cardboard রেখেছে। ছিদ্র দিয়ে শুধু নিচের lamp-টা ছোঁয়া যায়। ও কিছু lamp-এর state বদলাতে চায়, কিন্তু ঢাকা lamp ছোঁয়া যাবে না। তুমি হলে কোন জায়গায় চাপ লাগবে, সেটা কীভাবে লিখে রাখতে?

প্রতি position-এ একটা উত্তর

ধরো, কাগজে lamp-এর সমান ঘর এঁকেছ। জ্বলা lamp-এর ঘরে 1, বন্ধ lamp-এর ঘরে 0। এই দুই state-এর একটাকে ধরে রাখার নাম bit। একটা bit-এ একসাথে দুইটা উত্তর থাকে না। তোমার প্রশ্নটা এমন হতে হবে, যার উত্তর হ্যাঁ বা না।

এই রকম অনেকগুলো bit পাশাপাশি রাখে bitset। C++-এ এর নাম std::bitset<N>। Header হলো <bitset>। এখানে N বলে, মোট কয়টা position থাকবে। প্রত্যেক position-এর নিজস্ব index আছে, তাই একটা নির্দিষ্ট lamp-এর অবস্থাও আলাদা করে পড়তে পারবে।

Position-গুলোর মানে কিন্তু library ঠিক করে দেয় না। আজ position 5 মানে lamp 5। অন্য কাজ হলে সেটা seat 5 হতে পারে। আবার position 5 দিয়ে total ওজন 5 বানানো যায় কি না, সেটাও রাখতে পারো। একই storage, তোমার প্রশ্ন বদলালে মানেও বদলাবে।

Mask কথাটা শুনলে ভাববে, কোন position ধরতে চাই তার pattern। Alice-এর ছিদ্রগুলো একটা mask। যেখানে 1, সেখানে হাত দেওয়া যায়। আরেকটা mask বলে দিতে পারে কোথায় state বদলানো দরকার। পুরো সারি নিয়ে হিসাব করার সুবিধাটা এখানেই।

তবে একটা bit-এ count জমাতে যেয়ো না। একই position আবার mark করলে সেটার state এখনও 1। কতবার mark হয়েছে, সে খবর আর নেই। কাজ শুরু করার আগে নিজেকে জিজ্ঞেস করো, আমার সত্যিই শুধু হ্যাঁ বা না লাগছে তো? উত্তরটা না হলে অন্য storage লাগবে।

Width input-এর আগেই ঠিক

bitset<8> লিখলে 8-টা position-এর একটা type তৈরি হয়। bitset<16> আরেকটা type। Compiler যখন code বোঝে, তখনই এই width জানা চাই। Program চালিয়ে user-এর কাছ থেকে n পড়ে নতুন করে ওই type বানানো যাবে না।

Maria এখানে জিজ্ঞেস করে, কিন্তু input-এর n ছোটবড় হলে কী করব? আগে problem-এর সর্বোচ্চ সীমা দেখো। n বড়জোর 128 হলে bitset<128> নিতে পারো। তারপর নিচের n-টা position ব্যবহার করবে। বাকি position zero রাখবে। আসল width কিন্তু তখনও 128।

এখানে capacity আর ব্যবহার করা অংশ আলাদা। খাতায় 128টা ঘর এঁকে তার মধ্যে 17টা কাজে লাগানোর মতো। 17টা কাজে লাগালেই বাকি ঘরগুলো উধাও হয় না। বড় constant নেওয়ার আগে memory হিসাব করা তাই দরকার। সব bit বন্ধ থাকলেও storage পুরোটা থাকে।

সীমাই যদি শুধু input থেকে জানা যায়, তাহলে vector<bool>-এর কথা ভাবতে পারো। ওর length চলার সময় ঠিক করা যায়। তবে bitset-এর মতো পুরো row shift করার operator সেখানে পাবে না। কোনটা নেবে, সেটা operation দেখেও ঠিক করতে হবে। Lesson 04-এ এই বাছাইটা করব।

Index গুনবে ডান থেকে

একটা binary string দেখে বাঁ দিকের প্রথম character-কে bit 0 ভাবা খুব সহজ। এখানেই একটু থামো। Bit 0 থাকে ডানের একদম শেষে। তার বাঁয়ে bit 1। সবচেয়ে বাঁয়ে bit N-1। সাধারণ binary সংখ্যা লেখার নিয়মটাই এখানে চলে।

তোমার গল্পে যদি বাঁ থেকে cell গোনা হয়, সেটাও চলবে। শুধু cell আর bit-এর মিলটা স্পষ্ট করে লিখতে হবে। বাঁয়ের cell-কে বড় index দিতে পারো। চাইলে input ঘুরিয়েও নিতে পারো। কিন্তু মাঝপথে নিয়ম বদলালে shift ঠিক লিখেও ভুল দিকে সরিয়ে ফেলবে।

to_string() পুরো width-টাই লেখে। সামনের zero বাদ দেয় না। তাই n-টা lamp-এর জন্য বড় capacity নিলে output-এর সময় শুধু দরকারি n character রাখবে। এখানে display কতটুকু দেখাবে আর storage কতটুকু আছে, দুইটা আলাদা সিদ্ধান্ত।

String দিয়ে bitset বানালে character-গুলো binary digit হিসেবে পড়ে। Decimal সংখ্যার লেখা হিসেবে না। ছোট string দিলে তার bit-গুলো নিচের index-এ বসে। বড় index-এর বাড়তি জায়গা zero থাকে। তাই input-এর ডানের শেষ character আর bit 0-এর সম্পর্কটা একই থাকে।

একটা row মেলানোর তিন নিয়ম

প্রথম নিয়ম AND, operator &। দুই mask-এর একই position-এ 1 থাকলেই ফলের ওই position-এ 1 থাকবে। Alice-এর দরকারি press আর allowed hole মেলাতে এটা কাজে লাগে। একটা position-এর হিসাব পাশের position-এ গিয়ে কিছু যোগ করে না।

দ্বিতীয়টা OR, operator |। যেকোনো এক পাশে 1 থাকলেই position-টা রাখবে। ধরো, দুই route-এর যেকোনোটা দিয়ে যাওয়া যায়। দুই route-এর possible stop একসাথে ধরতে OR চলে। তবে দুটোতেই একই stop থাকলে সেটা দুইবার গোনা হয় না। Mask count জমায় না।

তৃতীয়টা XOR, operator ^। দুই পাশে state আলাদা হলে 1 রাখে। তাই আগের ছবি আর পরের ছবি মিলিয়ে কী বদলেছে, সেটা ধরতে সুবিধা। একই toggle mask দুইবার দিলে আগের state ফিরে আসে। কারণ এক position দুইবার উল্টালে আগের জায়গাতেই যায়।

আর ~ হলো complement। Width-এর ভেতরের প্রতিটা bit উল্টে দেয়। এটা অসীম একটা row বানায় না। বড় capacity ব্যবহার করলে বাড়তি position-ও উল্টাবে, সেটা মনে রাখবে। দরকার হলে কাজের frame mask দিয়ে ওই বাড়তি অংশ বাদ দিতে হবে।

এখানে & আর && গুলিয়ে ফেলো না। প্রথমটা position ধরে কাজ করে। দ্বিতীয়টা পুরো truth value মেলায়। Mask বানানোর পরে এক কথায় কিছু আছে কি না জানতে any() call করবে। কিছুই নেই কি না চাইলে none()।

Shift-এ position সরে, width না

Left shift-এ bit বড় index-এর দিকে যায়। Right shift-এ ছোট index-এর দিকে। নতুন খালি জায়গায় zero ঢোকে। Width-এর বাইরে যাওয়া bit আর থাকে না। তাই শুধু তিরের দিক মুখস্থ না করে index বাড়ছে না কমছে, সেটা ভাবো।

Circle-এর মতো ঘুরে আবার অন্য মাথায় আসে না। সেটা হলে operation-এর নাম rotation। Shift হারানো bit মনে রাখে না। পরে উল্টো দিকে সরালেই তাই সবসময় আগের pattern ফিরবে না। সীমার বাইরে কিছু গিয়েছিল কি না, সেটাই আসল প্রশ্ন।

b << k লিখলে shifted copy পাবে। b আগের মতোই থাকে। b <<= k লিখলে b-ই বদলায়। Zara একই original strip-এর উপর আলাদা query চালালে প্রথম রূপটা নেবে। নইলে আগের query-র নড়াচড়া পরেরটার মধ্যে ঢুকে যাবে।

Bitset-এ width-এর সমান বা বেশি shift করাও চলে। তখন সব bit হারিয়ে যায়। কিন্তু integer mask-এর shift count-এর নিয়ম আলাদা। একটা type-এ যা চলে, অন্যটায়ও চলবে ধরে নিও না। পরের lesson-এ এই সীমাগুলো operation ধরে দেখবে।

std::bitset<8> lamps("00101100");
bool lit = lamps.test(2);
lamps.set(0);
auto overlap = lamps & std::bitset<8>("00001111");

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<8> lamps("00101100");
    cout << "capacity " << lamps.size() << '\n';
    cout << "lit " << lamps.count() << '\n';
    cout << "position 2 " << lamps.test(2) << '\n';
}

capacity 8
lit 3
position 2 1

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<8> current("00110100"), target("00100101");
    bitset<8> holes("00011111");
    auto change = current ^ target;
    cout << "changes " << change << '\n';
    cout << "forbidden " << (change & ~holes).any() << '\n';
}

changes 00010001
forbidden 0

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<8> marks("00010110");
    for (int d = 0; d <= 3; ++d) {
        cout << "slide " << d << ' ' << (marks << d) << '\n';
    }
    cout << "original " << marks << '\n';
}

slide 0 00010110
slide 1 00101100
slide 2 01011000
slide 3 10110000
original 00010110

এক ধাপ করে যাও। আগে index-এর দিকে movement দেখো। তারপর mask কোন position রাখছে আর কোনটা উল্টাচ্ছে, সেটা দেখো। শেষে তিনটা item নেওয়া বা না নেওয়ার choice গোনা হয়। একটাও না নেওয়াও একটা choice।

এগুলো logical bit-এর সংখ্যা। Object memory-তে ঠিক কত byte নেবে, তার মাপ না। Library word আর alignment-এর জন্য বাড়তি জায়গা লাগতে পারে। তাই chart-টা capacity বোঝায়, sizeof-এর ফল না।

#include <bitset>
#include <iostream>
int main() {
    int n; std::cin >> n;
    std::bitset<n> lamps;
    std::cout << lamps.size();
}

#include <bitset>
#include <iostream>
int main() {
    std::bitset<8> lamps;
    std::cout << "lit lamps, wrong measure " << lamps.size() << '\n';
    std::cout << "lit lamps, correct measure " << lamps.count() << '\n';
}

lit lamps, wrong measure 8
lit lamps, correct measure 0

6
010100
011001
001101

001101

#include <bitset>
#include <iostream>
#include <string>
using namespace std;
int main() {
    int n; string a, t, m;
    cin >> n >> a >> t >> m;
    // Find the required presses, then check the stencil permissions.
}

8 2

// Read n and j. Print the matching bit index.

5 1
00100
01100
00100

// Shift a copy of the hole mask, then check required presses.

পরের lesson-এ প্রতিটা operation আলাদা করে দেখবে, খরচসহ।