Module ৪ · if, switch আর loop

পুরো program: FizzBuzz থেকে prime sieve

Freeপড়াlesson ৩ / ৯

এই lesson-এ যা শিখবে

Fixed starter-এর উপর সাতটা পুরো program লিখতে পারবে, FizzBuzz-এর একটা রূপ থেকে prime sieve পর্যন্ত, প্রতিটা তার আসল output-সহ।
বুঝিয়ে বলতে পারবে একটা if chain-এ জোড়া test-টা কেন সবার আগে বসে, আর prime check কেন বর্গমূলে গিয়ে থামতে পারে।
Input-এর উপর এক pass-এই একটা চলতি উত্তর রাখতে পারবে, প্রতিটা value এমন জায়গা থেকে শুরু করে যাতে প্রথম item-টা ধোঁকা দিতে না পারে।

অনেক junior developer interview আজও শুরু হয় একই ছোট্ট কাজ দিয়ে। 1 থেকে গুনতে থাকো; 3-এর গুণিতক হলে বলো "Fizz", 5-এর গুণিতক হলে "Buzz", দুটোরই হলে "FizzBuzz"। এর নাম FizzBuzz, আর এটা অঙ্কের পরীক্ষা না। এটা দেখে তুমি একটা loop-এর ভিতরে একটা if বসিয়ে ক্রমটা ঠিক রাখতে পারো কিনা। এই lesson কাজটা সৎভাবে করে, তারপর আরও ছয়টা program বানায়, একদম সেই পর্যন্ত যেগুলো একজন কাজের programmer লেখে।

সাতটা program-এর একই গড়ন

এখানের প্রতিটা program-এ চারটা ধাপ। Starter-এর next() আর nextInt() দিয়ে পড়ে, input-এর উপর loop চালায়, প্রতিটা value নিয়ে কিছু একটা সিদ্ধান্ত নেয়, আর out-এ একটা লাইন push করে। Starter-এর শেষ লাইন সবকিছু একসাথে print করে। Module 1-এ দুইটা loop-এর গড়ন দেখেছিলে, "যেমন আছে তেমন ব্যবহার করো" বলে; lesson 01 আর 02 সেগুলো বুঝিয়ে দিয়েছে। এই program-গুলো দুটোই ব্যবহার করে।

Input পড়ার দুই উপায়

const n = nextInt();
for (let i = 0; i < n; i++) { ...read one value... }

let token = next();
while (token !== undefined) {
  ...use token...
  token = next();
}

for loop খাটে তখন, যখন input বলে দেয় কয়টা value আসবে: "the first line holds n"।
while loop খাটে তখন, যখন input শেষ না হওয়া পর্যন্ত চলে। Token ফুরিয়ে গেলে next() ফেরত দেয় undefined।
break যেকোনো loop থেকে সাথে সাথে বের করে দেয়, আর continue সোজা পরের pass-এ চলে যায়। দুটোই দেখিয়েছে lesson 02।

FizzBuzz, সৎভাবে

Zara খেলাটার একটা party রূপ খেলে। 3-এর গুণিতক হলে "Fizz", 7-এর গুণিতক হলে "Bazz", আর দুটোরই গুণিতক হলে "FizzBazz"। নিচে 12 থেকে 21 পর্যন্ত সংখ্যার জন্য if chain-টা। Test-গুলোর ক্রমটা খেয়াল করে পড়ো।

const out = [];
for (let i = 12; i <= 21; i++) {
  if (i % 3 === 0 && i % 7 === 0) {
    out.push("FizzBazz");
  } else if (i % 3 === 0) {
    out.push("Fizz");
  } else if (i % 7 === 0) {
    out.push("Bazz");
  } else {
    out.push(i);
  }
}
console.log(out.join("\n"));

Fizz
13
Bazz
Fizz
16
17
Fizz
19
20
FizzBazz

একটা if chain প্রথম যে branch-এর test true হয়, সেটা চালায়, বাকিগুলো বাদ দেয়। 21 পাস করে i % 3 === 0 test, তাই যে chain আগে 3-এর কথা জিজ্ঞেস করে, সে "Fizz" print করে ফেলে, জোড়া test-এর কাছে আর পৌঁছায়ই না। তাই সবচেয়ে নির্দিষ্ট test-টা বসে সবার আগে। উল্টো ক্রমটা আর তার আসল output দেখাবে common mistake 1।

Chain-এর একটা দুর্বলতা আছে। দুইটা শব্দে লাগে চারটা branch; তিনটা শব্দে লাগে আটটা, প্রতিটা মিশ্রণের জন্য একটা। সৎ সমাধানটা শব্দ বেছে নেয় না, শব্দটা গড়ে তোলে।

Example 1: শব্দটা গড়ে তোলো

নতুন যা: তিনটা আলাদা if statement, প্রতিটা একটা করে টুকরো জোড়ে, কোনো else ছাড়া; আর সংখ্যাটায় ফিরে যেতে word || i। Zara 11-এর গুণিতকের জন্য যোগ করে "Boom"।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const n = nextInt();
for (let k = 0; k < n; k++) {
  const i = nextInt();
  let word = "";
  if (i % 3 === 0) {
    word += "Fizz";
  }
  if (i % 7 === 0) {
    word += "Bazz";
  }
  if (i % 11 === 0) {
    word += "Boom";
  }
  out.push(word || i);
}

console.log(out.join("\n"));

10
FizzBazz
Boom
FizzBoom
BazzBoom
FizzBazzBoom
Bazz
Fizz

এই output-টা input 8, তারপর 10 21 22 33 77 231 7 9-এর জন্য। 231 হলো 3 গুণ 7 গুণ 11, তাই তিনটা test-ই নিজের টুকরো জোড়ে। কোনো test পাস না করলে word থেকে যায় "", যেটা falsy, তাই || সংখ্যাটা দেয় (Module 2)। ক্রম নিয়ে আর মাথাব্যথা নেই, আর চতুর্থ একটা শব্দ মানে শুধু আরেকটা লাইন।

Run in Compiler

যে loop দুই কারণে থামে

কিছু loop থামে গোনা শেষ হলে, কিছু থামে কোনো ঘটনা ঘটলে। অনুমানের খেলায় দুটোই আছে: চেষ্টা ফুরিয়ে যেতে পারে, আবার ঠিক উত্তরও লেগে যেতে পারে। একটা কারণ সামলায় loop-এর নিজের test, অন্যটা সামলায় break।

Example 2: সীমা-বাঁধা একটা অনুমানের খেলা

নতুন যা: একটা while loop যার test হলো সীমাটা, আর ঠিক অনুমানের জন্য আর আগেভাগে ফুরিয়ে যাওয়া input-এর জন্য break। Alice একটা গোপন সংখ্যা ঠিক করে, আর নির্দিষ্ট কয়েকবার চেষ্টা করতে দেয়।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const secret = nextInt();
const limit = nextInt();
let tries = 0;
let found = false;

while (tries < limit) {
  const token = next();
  if (token === undefined) {
    break;
  }
  tries++;
  const guess = Number(token);
  if (guess === secret) {
    found = true;
    break;
  }
  out.push(guess + " is too " + (guess < secret ? "low" : "high"));
}

if (found) {
  out.push("got it in " + tries);
} else {
  out.push("no luck after " + tries + ", it was " + secret);
}

console.log(out.join("\n"));

50 is too high
25 is too low
37 is too low
43 is too high
got it in 5

এই output-টা input 42 5, তারপর 50 25 37 43 42 10-এর জন্য। পঞ্চম অনুমানটা ঠিক, সীমার ঠিক ভিতরে, তাই 10 আর পড়াই হয় না। found flag-টা মনে রাখে loop কেন থামল, কারণ loop-এর পরে দুই কারণকে দেখতে একই রকম লাগে। সীমা 4 করে দাও, শেষ লাইন হয়ে যাবে no luck after 4, it was 42।

Run in Compiler

দুইটা loop দিয়ে একটা grid

একটা loop-এর ভিতরে আরেকটা loop থাকলে তাকে বলে nested loop। বাইরের loop-এর প্রতিটা pass-এ ভিতরের loop তার সব pass পুরো ঘুরে আসে। তাই 6 সারি আর 6 কলামের grid-এ ভিতরের body চলে 36 বার।

Example 3: গুণের একটা grid

নতুন যা: nested for loop, আর কলামগুলো সোজা লাইনে রাখতে padStart। String(x).padStart(w) text-এর বাঁ দিকে space বসায়, যতক্ষণ না সেটা w character লম্বা হয়; বিস্তারিত Module 3-এ।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const n = nextInt();
const width = String(n * n).length + 1;

for (let row = 1; row <= n; row++) {
  let line = "";
  for (let col = 1; col <= n; col++) {
    line += String(row * col).padStart(width);
  }
  out.push(line);
}

console.log(out.join("\n"));

  1  2  3  4  5  6
  2  4  6  8 10 12
  3  6  9 12 15 18
  4  8 12 16 20 24
  5 10 15 20 25 30
  6 12 18 24 30 36

এই output-টা input 6-এর জন্য। সবচেয়ে চওড়া সংখ্যা n * n, মানে 36, যার character 2টা, তাই প্রতিটা ঘর 3 চওড়া, এক space বাড়তি। line বাইরের loop-এর ভিতরে নতুন করে তৈরি হয়, তাই প্রতিটা সারি খালি থেকে শুরু হয়। দুই counter-এর নাম আলাদা, row আর col; দুটোর একই নাম দিলে কী হয়, দেখাবে common mistake 3।

Run in Compiler

এটা কি prime? বর্গমূলে গিয়ে থামো

Prime হলো 1-এর চেয়ে বড় এমন পূর্ণসংখ্যা, যাকে শুধু 1 আর সে নিজে ভাগ করতে পারে। n যাচাই করতে 2 থেকে শুরু করে প্রতিটা ভাজক d চেষ্টা করো। ভাজক আসে জোড়ায়: d যদি n-কে ভাগ করে, তাহলে n / d-ও করে, আর দুটোর একটা n-এর বর্গমূলের চেয়ে বড় না। তাই d * d n-কে ছাড়িয়ে গেলেই loop থামতে পারে, আর কোনো ভাজক পেয়ে গেলে তো সাথে সাথেই।

Example 4: আগেভাগে বের হয়ে যাওয়া prime check

নতুন যা: trial division, যেখানে loop-এর test d * d <= n, আর প্রথম ভাজক পেলেই break। Program-টা যে জোড়াটা পেল, সেটাও print করে।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const count = nextInt();
for (let k = 0; k < count; k++) {
  const n = nextInt();
  let divisor = 0;
  for (let d = 2; d * d <= n; d++) {
    if (n % d === 0) {
      divisor = d;
      break;
    }
  }
  if (n < 2) {
    out.push(n + ": neither prime nor composite");
  } else if (divisor === 0) {
    out.push(n + ": prime");
  } else {
    out.push(n + ": not prime, " + divisor + " x " + n / divisor);
  }
}

console.log(out.join("\n"));

1: neither prime nor composite
2: prime
91: not prime, 7 x 13
97: prime
7919: prime
1000001: not prime, 101 x 9901

এই output-টা input 6, তারপর 1 2 91 97 7919 1000001-এর জন্য। 2-এর বেলায় ভিতরের loop একবারও চলে না, কারণ 2 গুণ 2 আগেই 2-কে ছাড়িয়ে গেছে। 7919-এর বেলায় সে d চেষ্টা করে 2 থেকে 88 পর্যন্ত, কারণ 89 গুণ 89 হলো 7921। বর্গমূলে না থামলে চেষ্টা করতে হতো প্রায় 7,900টা ভাজক।

Run in Compiler

Sieve: ভাগ না করে কেটে দাও Intermediate

n পর্যন্ত সব prime খুঁজতে প্রতিটা সংখ্যা আলাদা করে যাচাই করলে একই কাজ বারবার হয়। Sieve of Eratosthenes, যার নাম আন্দাজ 240 খ্রিস্টপূর্বাব্দের এক গ্রিক পণ্ডিতের নামে, কাজটা উল্টে দেয়। সব সংখ্যা লিখে ফেলো, তারপর যে prime-ই পাও, তার গুণিতকগুলো কেটে দাও। যেগুলো কখনো কাটা পড়েনি, সেগুলোই prime।

Program-টা প্রতিটা সংখ্যার জন্য একটা করে true বা false flag রাখে, একটা array-তে। new Array(n + 1).fill(true) বানায় n + 1টা ঘর, 0 থেকে n নম্বর, সবগুলোতে true। isPrime[m] m নম্বর ঘরটা পড়ে, আর isPrime[m] = false ওটাকে কেটে দেয়। Array ঠিকমতো শেখাবে Module 7; এখানে array মানে শুধু এক সারি flag।

Example 5: 30 পর্যন্ত sieve

নতুন যা: flag-এর একটা array, একটা ভিতরের loop যেটা m += p দিয়ে p করে লাফায়, আর আগেই কাটা সংখ্যা বাদ দিতে continue।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const n = nextInt();
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;

for (let p = 2; p * p <= n; p++) {
  if (!isPrime[p]) {
    continue;
  }
  let crossed = "";
  for (let m = p * p; m <= n; m += p) {
    if (isPrime[m]) {
      isPrime[m] = false;
      crossed += " " + m;
    }
  }
  out.push("crossed by " + p + ":" + crossed);
}

let primes = "";
for (let i = 2; i <= n; i++) {
  if (isPrime[i]) {
    primes += " " + i;
  }
}
out.push("primes:" + primes);

console.log(out.join("\n"));

crossed by 2: 4 6 8 10 12 14 16 18 20 22 24 26 28 30
crossed by 3: 9 15 21 27
crossed by 5: 25
primes: 2 3 5 7 11 13 17 19 23 29

এই output-টা input 30-এর জন্য, আর ছবির সাথে লাইনে লাইনে মেলে। প্রতিটা prime p কাটা শুরু করে p * p থেকে, কারণ এর ছোট প্রতিটা গুণিতকের একটা ছোট ভাজক আছে, যে আগেই ওটাকে কেটে রেখেছে। 4-কে continue বাদ দেয়, কারণ 2 ওটাকে কেটেছে। Sieve কোনো ভাগই করে না, তাই n পর্যন্ত সব prime দরকার হলে এটাই জেতে।

Run in Compiler

switch দিয়ে একটা menu

একটা switch একটা value-কে case value-গুলোর একটা তালিকার সাথে মেলায়, === দিয়ে, আর প্রথম মিলে যাওয়া জায়গায় লাফ দেয়। এর একমাত্র ফাঁদটা lesson 02 দেখিয়েছে: break না থাকলে run গড়িয়ে পরের case-এ ঢুকে পড়ে। ওই গড়িয়ে পড়ার (fall-through) একমাত্র সৎ ব্যবহারটাও দেখিয়েছে: কয়েকটা case যখন একই কাজ ভাগ করে নেয়।

Example 6: Kenji-র coffee kiosk

নতুন যা: একটা while loop-এর ভিতরে একটা switch, যেখানে দুইটা case একই কাজে জোট বেঁধেছে। প্রতিটা শব্দ একটা item, আর pay bill print করে নতুন bill শুরু করে।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

let total = 0;
let token = next();

while (token !== undefined) {
  switch (token) {
    case "tea":
      total += 20;
      break;
    case "coffee":
      total += 50;
      break;
    case "cake":
    case "muffin":
      total += 40;
      break;
    case "pay":
      out.push("paid " + total);
      total = 0;
      break;
    default:
      out.push("no item " + token);
  }
  token = next();
}

if (total > 0) {
  out.push("unpaid " + total);
}

console.log(out.join("\n"));

paid 110
no item juice
paid 60
unpaid 50

এই output-টা input tea cake coffee pay muffin juice tea pay coffee-এর জন্য। cake আর muffin-এর দাম একই, তাই খালি case "cake": ইচ্ছে করেই গড়িয়ে পড়ে। যে শব্দের কোনো case নেই, তাকে ধরে default। খেয়াল রেখো, switch-এর ভিতরের break বের করে switch থেকে, চারপাশের loop থেকে না।

Run in Compiler

এক pass-এই হিসাব

চলতি (running) value মানে যেটা প্রতিটা item আসার সাথে সাথে update হয়, যেমন একটা total। চলতি value থাকলে program প্রতিটা item একবারই পড়ে, আর কিছু জমিয়ে রাখে না। প্রতিটা চলতি value-র দরকার একটা নিরাপদ শুরু। Count শুরু হয় 0 থেকে। এখন পর্যন্ত সবচেয়ে বড়টা (largest-so-far) শুরু হয় -Infinity থেকে, যেটাকে যেকোনো আসল সংখ্যা হারিয়ে দেয়, নয়তো প্রথম item থেকেই।

Example 7: এক সপ্তাহের তাপমাত্রা

নতুন যা: এক loop-এ কয়েকটা চলতি value, আর আগের item মনে রাখতে previous। David-এর আবহাওয়ার খাতায় দিনে একটা করে তাপমাত্রা, input শেষ না হওয়া পর্যন্ত।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

let count = 0;
let highest = -Infinity;
let highestDay = 0;
let biggestRise = 0;
let frostDays = 0;
let previous = 0;

let token = next();
while (token !== undefined) {
  const t = Number(token);
  count++;
  if (t > highest) {
    highest = t;
    highestDay = count;
  }
  if (count > 1 && t - previous > biggestRise) {
    biggestRise = t - previous;
  }
  if (t < 0) {
    frostDays++;
  }
  previous = t;
  token = next();
}

out.push("days " + count);
out.push("highest " + highest + " on day " + highestDay);
out.push("biggest rise " + biggestRise);
out.push("frost days " + frostDays);

console.log(out.join("\n"));

days 7
highest 12 on day 7
biggest rise 13
frost days 2

এই output-টা input 3 -2 4 9 7 -1 12-এর জন্য। শেষ দিনে -1 থেকে 12-তে ওঠাটা 13। count > 1 প্রথম দিনটাকে আগলে রাখে, কারণ ওর আগে কোনো দিন নেই। >= না লিখে > লেখায় সর্বোচ্চটা প্রথম যেদিন ছোঁয়া হয়েছে, সেই দিনটাই থাকে। যে সপ্তাহে শুধু ঠান্ডাই বাড়ে, সেখানে biggest rise আসে 0, আর এটা এই program-এর নিজের বেছে নেওয়া নিয়ম।

Run in Compiler

এটা কোথায় কাজে লাগে

চাকরির screening। Imran Ghory 2007 সালের এক blog post-এ চাকরিপ্রার্থী ছাঁকতে FizzBuzz-এর প্রস্তাব দেন। একই বছর Jeff Atwood-এর "Why Can't Programmers.. Program?" এটাকে বিখ্যাত করে দেয়।
OpenSSL। সম্ভাব্যতা-নির্ভর Miller-Rabin test-এর আগে OpenSSL একটা সম্ভাব্য prime-কে ছোট ছোট prime-এর একটা table দিয়ে ভাগ করে দেখে। সস্তা এই early exit বেশিরভাগ প্রার্থীকে শুরুতেই বাদ দিয়ে দেয়।
Unix-এর wc tool। একটা file-এর লাইন, শব্দ আর byte গোনে এক pass-এই, Example 7-এর মতো চলতি count দিয়ে।
Redux। ওদের documentation একটা reducer লেখে action.type-এর উপর একটা switch হিসেবে, প্রতিটা action-এর জন্য একটা case আর একটা default সহ, ঠিক Kenji-র kiosk-এর গড়নে।

যে ভুলগুলো সবাই করে

১. জোড়া test সবার শেষে।

const out = [];
for (let i = 19; i <= 21; i++) {
  if (i % 3 === 0) {
    out.push("Fizz");
  } else if (i % 7 === 0) {
    out.push("Bazz");
  } else if (i % 3 === 0 && i % 7 === 0) {
    out.push("FizzBazz");
  } else {
    out.push(i);
  }
}
console.log(out.join("\n"));

19
20
Fizz

কোনো error নেই, আর 21 বলছে "Fizz"। প্রথম test-ই 21-এর সাথে মিলে গেছে, তাই জোড়া branch-টা কখনো চলতেই পারে না। সবচেয়ে নির্দিষ্ট test সবার আগে বসাও, নয়তো Example 1-এর মতো শব্দটা গড়ে তোলো। ভুলটা তুমি করবে, কারণ খেলার নিয়ম যে ক্রমে বলা হয়, তুমি সেই ক্রমেই লেখো।

২. যে prime check 1-কে prime বলে।

const n = 1;
let prime = true;
for (let d = 2; d * d <= n; d++) {
  if (n % d === 0) {
    prime = false;
    break;
  }
}
console.log(n + (prime ? " is prime" : " is not prime"));

1 is prime

1-এর জন্য loop একবারও চলে না, তাই flag-কে false করার কেউ নেই। শুরু করো let prime = n >= 2; দিয়ে, তাহলে 0, 1 আর negative সংখ্যা loop-এর আগেই বাদ পড়ে। ভুলটা চোখ এড়াবে, কারণ তুমি test করো 7 আর 9 দিয়ে, 1 দিয়ে কখনো না।

৩. দুই loop-এর counter-এর একই নাম।

const out = [];
for (let i = 1; i <= 3; i++) {
  let line = "";
  for (let i = 1; i <= 3; i++) {
    line += String(i * i).padStart(3);
  }
  out.push(line);
}
console.log(out.join("\n"));

  1  4  9
  1  4  9
  1  4  9

কোনো error নেই। ভিতরের let i একটা নতুন variable, যেটা বাইরেরটাকে আড়াল করে ফেলে, তাই i * i দুইবারই কলামটা নেয়। প্রতিটা সারি একই রকম আসে। Counter-এর নাম দাও সে যা গোনে সেই অনুযায়ী, row আর col। ভুলটা করবে, কারণ যেকোনো loop-এ তোমার আঙুল আপনা থেকেই i টাইপ করে।

৪. যে চলতি minimum 0 থেকে শুরু হয়।

const temps = [5, 8, 3, 9];
let lowest = 0;
for (const t of temps) {
  if (t < lowest) {
    lowest = t;
  }
}
console.log("lowest " + lowest);

lowest 0

কোনো error নেই, অথচ 0 তালিকাতেই নেই। কোনো তাপমাত্রাই শুরুর 0-এর নিচে না, তাই ওটা নড়েই না। শুরু করো Infinity থেকে, নয়তো প্রথম item থেকে। তুমি 0 থেকে শুরু করবে, কারণ total শুরু হয় সেখান থেকে, আর minimum-কেও একই জাতের জিনিস মনে হয়।

মাথা খাটাও

const n = 97;
let tests = 0;
for (let d = 2; d * d <= n; d++) {
  tests++;
  if (n % d === 0) {
    break;
  }
}
console.log(tests);

n = 97-এর জন্য এই trial division কয়টা সংখ্যা যাচাই করে? আর প্রথম লাইনটা বদলে const n = 100; করলে কয়টা? Run করার আগে দুটোই কাগজে বের করো।

97-এর জন্য সবচেয়ে বড় কোন d-তে d * d <= 97 খাটে, খুঁজে বের করো, আর মনে রেখো একটা prime কখনো break ঘটায় না। 100-এর জন্য ভাবো, কোন d ওকে সবার আগে ভাগ করে।

অনুশীলন ১সহজ

কাল Bob-এর interview, আর ও আসল খেলাটা নির্ভুল চায়, প্রতিটা লাইন।

Input. একটা পূর্ণসংখ্যা n।

Output. n-টা লাইন, 1 থেকে n পর্যন্ত প্রতিটা i-এর জন্য একটা। i যদি 3 আর 5 দুটোরই গুণিতক হয়, print করো FizzBuzz; শুধু 3-এর হলে Fizz, শুধু 5-এর হলে Buzz, নইলে i নিজেই।

Constraints. 1 <= n <= 100000।

Sample. Input 15 দিলে 15 লাইনে 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14 আর FizzBuzz।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

fizzbuzz নামে grade হয়। Hidden test-গুলো চেষ্টা করে n = 1, 15-এর কোনো গুণিতকের দুই পাশের n, আর সবচেয়ে বড় n।

Run in Compiler

অনুশীলন ২মাঝারি

Maria-র কাছে পূর্ণসংখ্যার একটা তালিকা আছে, আর ও এক pass-এই সারাংশটা চায়, wc যেভাবে একটা file গোনে।

Input. n, তারপর n-টা পূর্ণসংখ্যা।

Output. চারটা লাইন: count আর n; min আর সবচেয়ে ছোটটা; max আর সবচেয়ে বড়টা; average আর যোগফলকে n দিয়ে ভাগ, JavaScript সংখ্যাটা যেভাবে print করে (String() যা দেয়)।

Constraints. 1 <= n <= 100000; -1000000000 <= প্রতিটা সংখ্যা <= 1000000000, তাই যোগফল একটা নিখুঁত পূর্ণসংখ্যা।

Sample. Input 5, তারপর 4 -3 12 7 1 দিলে চার লাইনে count 5, min -3, max 12 আর average 4.2।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

min-max-average নামে grade হয়। Hidden test-এ আছে একটা মাত্র সংখ্যার তালিকা, এমন তালিকা যার প্রতিটা সংখ্যাই negative, আর অনুমতির মধ্যে সবচেয়ে বড় value-গুলো।

Run in Compiler

অনুশীলন ৩মাঝারি

Alice-এর খেলা Example 2-এর সীমাটা তুলে দেয়। গোপন সংখ্যা পাওয়া না যাওয়া পর্যন্ত, বা অনুমান ফুরিয়ে না যাওয়া পর্যন্ত, খেলোয়াড় অনুমান করেই যায়।

Input. গোপন সংখ্যা s, তারপর অনুমানগুলো, input শেষ না হওয়া পর্যন্ত। একটাও অনুমান না থাকতে পারে।

Output. ক্রম অনুযায়ী প্রতিটা অনুমানের জন্য এক লাইন। অনুমানটাই গোপন সংখ্যা হলে print করো correct in k, যেখানে k হলো এই পর্যন্ত পড়া অনুমানের সংখ্যা, এটাসহ। তারপর থামো, পরের অনুমানগুলো উপেক্ষা করো। গোপন সংখ্যা বড় হলে print করো higher; ছোট হলে lower। ঠিক অনুমান ছাড়াই input শেষ হলে print করো not found after k, যেখানে k হলো পড়া অনুমানের সংখ্যা, 0-ও হতে পারে।

Constraints. 1 <= s <= 1000000000; বড়জোর 100000টা অনুমান, প্রতিটা 1 থেকে 1000000000।

Sample. Input 50, তারপর 25 75 50 10 দিলে তিন লাইনে higher, lower আর correct in 3।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

guessing-game নামে grade হয়। Hidden test-এ আছে কোনো অনুমান ছাড়া input, প্রথম অনুমানেই ঠিক, আর ঠিক অনুমানের পরেও আরও অনুমান।

Run in Compiler

অনুশীলন ৪কঠিন

Kenji জানতে চায়, একটা বড় n পর্যন্ত কয়টা prime আছে, আর তার আগের শেষ prime-টা কোনটা।

Input. একটা পূর্ণসংখ্যা n।

Output. দুইটা লাইন: n-এর সমান বা ছোট prime কয়টা, আর তাদের মধ্যে সবচেয়ে বড়টা, কোনোটা না থাকলে (n < 2) none।

Constraints. 1 <= n <= 15000000।

Sample. Input 30 দিলে দুই লাইনে 10 আর 29।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

count-primes নামে grade হয়। Hidden test-গুলো n = 1 থেকে শুরু করে অনুমতির সবচেয়ে বড় n পর্যন্ত যায়।

Run in Compiler

সচরাচর যে প্রশ্নগুলো আসে

d <= Math.sqrt(n) না লিখে d * d <= n কেন?

এই lesson-এর সংখ্যাগুলোর জন্য দুটোই একই জায়গায় থামে। d * d পুরোটা পূর্ণসংখ্যায় থাকে, তাই বর্গমূলের কোনো গোল করা তোমাকে চমকে দিতে পারে না। Kenji-র পছন্দ যে এতে একটা function call বাঁচে, কিন্তু আসল কারণ নিখুঁত থাকা।
প্রতিটা লাইন out-এ push করে একবারে print করি কেন?

প্রতি লাইনে একটা করে console.log কয়েক হাজার লাইনের পর ধীর হয়ে যায়, আর judge-এর test-এ এক লাখ লাইনও থাকতে পারে। লাইনগুলো জমিয়ে join দিয়ে একবারে print করলে সেই ঝামেলা নেই। তাছাড়া এতে প্রতিটা program-এর গড়ন একই থাকে।
Sieve কি সবসময় trial division-এর চেয়ে ভালো?

না। একটা মাত্র সংখ্যা যাচাই করতে trial division-ই যথেষ্ট, আর তাতে বাড়তি memory লাগে না। n পর্যন্ত সব prime লাগলে sieve জেতে, কিন্তু সে প্রতিটা সংখ্যার জন্য একটা flag রাখে, তাই n = 15,000,000 মানে দেড় কোটি flag।
একটা switch কি string মেলাতে পারে?

পারে। সে মেলায় === দিয়ে, তাই "tea" মেলে শুধু হুবহু "tea" text-এর সাথে। বড় হাতের অক্ষরওয়ালা "Tea" token চলে যায় default-এ।

মূল কথা

একটা if chain-এ প্রথম true test-টাই জেতে, তাই সবচেয়ে নির্দিষ্ট test বসে সবার আগে; শব্দটা গড়ে তুললে ক্রমের ঝামেলাই থাকে না।
একটা loop দুই কারণে থামতে পারে: তার নিজের test, আর একটা break। কোনটা ঘটল, সেটা মনে রাখে একটা flag।
Nested loop গুণ হয়: n সারি আর n কলাম মানে ভিতরের body চলে n গুণ n বার। প্রতিটা counter-কে তার নিজের নাম দাও।
Prime check থামে d * d <= n-এ আর প্রথম ভাজকে; n পর্যন্ত সব prime খুঁজতে sieve গুণিতকগুলো কেটে দেয়।
চলতি value input একবারই পড়ে; minimum বা maximum এমন জায়গা থেকে শুরু করো, যাতে প্রথম item ধোঁকা দিতে না পারে।
আরও গভীরে: Under the Hood, jump দিয়ে loop, iterator protocol আর একটা loop lab (Pro)।

এরপর Kenji-র review বলে "use forEach everywhere", এমন একটা loop-এ যেটাকে আগেভাগে থামতে হবে, আর lesson 04 তিনটা প্রশ্ন দিয়ে ঠিক loop-টা বেছে নেয়।

lesson ৩ শেষ

শেষ হলে চিহ্ন দিন, অগ্রগতি আপনার সাথে থাকবে।

পরেরটা: কোন loop, আর কখন if-এর চেয়ে switch ভালো

পরের lesson