فصل 7پروژه: ساخت یک ربات

[...] این سوال که آیا ماشین‌ها می‌توانند فکر کنند یا نه [...] مثل این است که بپرسیم آیا زیردریایی‌ها می‌توانند شنا کنند.

در فصل‌های "پروژه"، موقتا مطلب جدیدی معرفی نمی‌کنم و به جای آن باهم روی ساخت یک برنامه کار خواهیم کرد. مطالب تئوری برای برنامه‌نویسی لازم هستند، اما خواندن و فهمیدن برنامه‌های واقعی نیز به همان اندازه اهمیت دارند.

پروژه‌ی ما در این فصل، ساخت یک ماشین خودکار است؛ برنامه‌ی کوچکی که وظیفه‌ای را در یک جهان مجازی انجام می‌دهد. ماشین خودکار ما، یک ربات نامه‌رسان است که بسته‌های پستی را تحویل گرفته و به مقصدشان می‌رساند.

روستای مدوفیلد

روستای مدوفیلد زیاد بزرگ نیست. دارای 11 مکان است که 14 راه بین آن‌ها وجود دارد. می‌توان آن را با این آرایه از راه‌ها توصیف نمود:

const roads = [
  "Alice's House-Bob's House",   "Alice's House-Cabin",
  "Alice's House-Post Office",   "Bob's House-Town Hall",
  "Daria's House-Ernie's House", "Daria's House-Town Hall",
  "Ernie's House-Grete's House", "Grete's House-Farm",
  "Grete's House-Shop",          "Marketplace-Farm",
  "Marketplace-Post Office",     "Marketplace-Shop",
  "Marketplace-Town Hall",       "Shop-Town Hall"
];

شبکه‌ی راه‌ها در این روستا، یک گراف تشکیل می‌دهد. یک گراف مجموعه‌ای از نقطه‌ها است (مکان‌ها در روستا) به همراه خطوطی که بین آن‌ها قرار می‌گیرند (راه‌ها). این گراف همان جهانی خواهد بود که ربات ما در آن حرکت خواهد کرد.

کارکردن با آرایه‌ای از رشته‌ها، زیاد راحت نیست. ما می‌خواهیم بدانیم از هر مکان به چه مقصد‌هایی می‌توان رفت. بیایید لیست راه‌ها را به ساختار داده‌ای تبدیل کنیم که برای هر مکان، جا‌هایی که می‌توان رفت را مشخص کند.

function buildGraph(edges) {
  let graph = Object.create(null);
  function addEdge(from, to) {
    if (graph[from] == null) {
      graph[from] = [to];
    } else {
      graph[from].push(to);
    }
  }
  for (let [from, to] of edges.map(r => r.split("-"))) {
    addEdge(from, to);
    addEdge(to, from);
  }
  return graph;
}

const roadGraph = buildGraph(roads);

تابع buildGraph، با گرفتن آرایه‌ای از راه‌ها، شیئی نگاشت‌گونه را ایجاد خواهد کرد که برای هر‌گره، آرایه‌ای از ‌گره‌های متصل به آن را ذخیره خواهد کرد.

تابع از متد split برای تبدیل رشته‌های راه، که به صورت "انتها-ابتدا" (start-end) می‌باشند، به آرایه‌های دوعنصری استفاده می‌کند که نقاط شروع و پایان در آن‌ها جدا شده است.

ماموریت

ربات ما در روستا گشت خواهد زد و بسته‌هایی که در مکان‌های مختلف پراکنده می‌باشند و هر کدام به مکان دیگری باید برده شوند را گرفته و در مقصد‌هایشان تحویل می‌دهد.

این ماشین خودکار باید در هر نقطه تصمیم بگیرد که مکان بعدی کجاست. زمانی که همه‌ی بسته‌ها تحویل داده شدند، ماموریتش تمام می‌شود.

برای شبیه‌سازی این فرایند، باید یک جهان مجازی تعریف کنیم که آن را توصیف کند. این مدل، مکان ربات و بسته‌ها را مشخص می‌کند. زمانی که ربات تصمیم می‌گیرد که به سمتی حرکت کند، لازم است تا مدل را به روزرسانی کنیم تا شرایط جدید را منعکس کند.

اگر با تفکر برنامه‌نویسی شیءگرا به مسئله نگاه می‌کنید، حرکت اول شما شاید تعریف اشیاء مجزا برای عناصر مختلف این جهان باشد: یک کلاس برای ربات، یک کلاس برای یک بسته، و شاید یکی هم برای مکان‌ها. این کلاس‌ها می‌توانند خاصیت‌هایی را هم داشته باشند که وضعیت فعلی آن‌ها را نگه داری کند. مانند تعداد بسته‌ها در یک مکان، که می‌توانند با به‌روز‌رسانی جهان، تغییر کنند.

این کار اشتباه است.

حداقل، معمولا اشتباه است. اینکه چیزی به نظر می‌رسد که یک شیء است، به این معنا نیست که در برنامه‌ی شما هم باید به عنوان یک شیء در نظر گرفته شود. این کار، در نظر گرفتن کلاس‌های مجزا برای تک تک مفاهیم در برنامه، شما را به سمتی می‌برد که با مجموعه‌ای از اشیاء به هم متصل روبرو شوید که هر کدام وضعیت درونی قابل تغییر خود را دارند. معمولا به سختی می‌توان این‌گونه برنامه‌ها را درک کرد و در نتیجه، به سادگی با مشکل روبرو می‌شوند.

به جای آن، بیایید وضعیت روستا را با کوچکترین مجموعه‌ مقادیری که می‌تواند آن را توصیف کند خلاصه کنیم؛ موقعیت فعلی ربات و مجموعه‌ی بسته‌هایی که هنوز تحویل داده نشده‌اند. این بسته‌ها هر کدام دارای یک موقعیت فعلی و یک آدرس مقصد می‌باشند.

اجازه دهید آن را طوری بسازیم که با حرکت ربات، خود وضعیت را تغییر ندهیم بلکه یک وضعیت جدید محاسبه کنیم که حالت بعد از حرکت را نشان می‌دهد.

class VillageState {
  constructor(place, parcels) {
    this.place = place;
    this.parcels = parcels;
  }

  move(destination) {
    if (!roadGraph[this.place].includes(destination)) {
      return this;
    } else {
      let parcels = this.parcels.map(p => {
        if (p.place != this.place) return p;
        return {place: destination, address: p.address};
      }).filter(p => p.place != p.address);
      return new VillageState(destination, parcels);
    }
  }
}

متد move جایی است که کار صورت می‌گیرد. این متد ابتدا وجود مسیری بین مکان فعلی و مقصد را بررسی می‌کند، و در صورت نبود مسیر، وضعیت قبلی را برمی‌گرداند، دلیل آن هم این است که حرکت خواسته شده معتبر نیست.

سپس، یک وضعیت جدید ایجاد می‌کند که در آن، مقصد به عنوان مکان جدید ربات در نظر گرفته می‌شود. همچنین لازم است تا یک مجموعه‌ی جدید از بسته‌ها ایجاد شود – بسته‌هایی که ربات در حال حمل آن‌ها است (در مکان فعلی ربات قرار دارند) و باید به مکان جدید برده شوند. و بسته‌هایی که مقصدشان مکان جدید است و باید تحویل داده شوند – که باید از مجموعه‌ی بسته‌های تحویل داده نشده، حذف شوند. فراخوانی map عمل حرکت ربات و فراخوانی filter کار تحویل بسته‌ها را انجام می‌دهد.

اشیاء مربوط به بسته‌ها، زمانی که جابه‌جا می‌شوند تغییری نمی‌کنند بلکه از نو ایجاد می‌شوند. متد move به ما وضعیت جدیدی از روستا را می‌دهد و حالت قبلی را دست‌نخورده باقی می‌گذارد.

let first = new VillageState(
  "Post Office",
  [{place: "Post Office", address: "Alice's House"}]
);
let next = first.move("Alice's House");

console.log(next.place);
// → Alice's House
console.log(next.parcels);
// → []
console.log(first.place);
// → Post Office

متد move باعث می‌شود که بسته، تحویل داده شود و این عمل در وضعیت بعدی قابل مشاهده است. اما وضعیت ابتدایی هنوز شرایطی را نشان می‌دهد که ربات در دفتر پست است و بسته تحویل داده نشده است.

داده‌های مانا (Persistent Data)

ساختار‌های داده‌ای که تغییر نمی‌کنند را تغییرناپذیر (immutable) یا مانا (persistent) می‌نامند. این ساختار‌ها، بسیار شبیه به رشته‌ها و اعداد عمل می‌کنند، یعنی همیشه آن چیزی خواهند بود که هستند و به همین حالت می‌مانند، نه اینکه در زمان‌های مختلف محتوای مختلفی داشته باشند.

در جاوااسکریپت، تقریبا همه چیز را می‌توان تغییر داد. بنابراین کار کردن با مقدار‌هایی که قرار است مانا باشند موانعی خواهند داشت. تابعی به نام Object.freeze وجود دارد که در صورت اعمال به یک شیء، باعث می‌شود نتوان خاصیت‌های آن شیء را تغییر داد. اگر قصد دارید تا جوانب احتیاط را رعایت کنید، می‌توانید از این متد برای جلوگیری از تغییر شیءتان استفاده کنید. ثابت نگه‌داشتن شیء باعث می‌شود که کامپیوتر کار بیشتری انجام دهد، و در نظر نگرفتن به‌روز‌رسانی اشیاء، به احتمال زیاد افراد را به اشتباه می‌اندازد. بنابراین من معمولا ترجیح می‌دهم که به دیگران اعلام کنم که یک فلان شیء را نباید دستکاری کرد و امیدوار باشم که دیگران هم رعایت کنند.

let object = Object.freeze({value: 5});
object.value = 10;
console.log(object.value);
// → 5

چرا اصرار دارم که اشیاء را تغییر ندهم، با اینکه زبان به روشنی این کار را مجاز می‌داند؟

زیرا این کار به من در درک برنامه‌ها کمک می‌کند. این موضوع دوباره به مدیریت پیچیدگی برنامه باز می‌گردد. زمانی که اشیاء در سیستم من چیز‌هایی ثابت و پایدار هستند، می‌توانم فرض کنم که عملیات روی آن‌ها در فضایی جداگانه انجام می‌پذیرد – رفتن به خانه‌ی Alice، از یک وضعیت ابتدایی داده شده، همیشه وضعیت جدید یکسانی را تولید می‌کند. زمانی که اشیاء در طول زمان تغییر می‌کنند، این کار باعث اضافه شدن بعد دیگری از پیچیدگی به این‌گونه نتیجه‌گیری می‌گردد.

برای یک سیستم کوچک مانند چیزی که در این فصل در حال ساخت آن هستیم، می‌توانیم از پس این پیچیدگی اضافی بر بیاییم. اما مهم‌ترین محدودیتی که در نوع سیستم‌هایی که می‌توانیم بسازیم وجود دارد آن است که تا چه حد می‌توانیم آن سیستم‌ها را درک کنیم. هر چیزی که درک کد شما را آسان‌تر کند، باعث می‌شود که بتوانید سیستم بلندپروازانه‌تری بسازید.

متاسفانه، با وجود اینکه درک سیستمی که با ساختار‌های داده‌ی مانا ساخته شده آسان‌تر است، طراحی آن، مخصوصا وقتی که خود زبان برنامه‌نویسی کمکی نمی‌کند، ممکن است کمی مشکل‌تر باشد. با این حال، ما به دنبال فرصت‌هایی برای استفاده از ساختار‌های داده مانا در این کتاب خواهیم بود، همچنین از موارد قابل تغییر نیز استفاده خواهیم کرد.

شبیه‌سازی

یک ربات تحویل دهنده به جهان پیرامون خود نگاه می‌کند و تصمیم می‌گیرد که از کدام جهت باید حرکت کند. بر این اساس، می‌توانیم بگوییم که یک ربات یک تابع است که یک شیء از نوع VillageState را گرفته و نام یک مکان نزدیک را برمی گرداند.

به دلیل اینکه ربات‌ها قادر به برنامه‌ریزی و اجرای آن باشند، باید بتوانند چیز‌هایی به خاطر بسپارند. پس به آن‌ها حافظه‌شان را ارسال می‌کنیم و امکان برگرداندن حافظه‌ی جدید را نیز فراهم می‌سازیم. پس، چیزی که یک ربات برمی‌گرداند شیئی است که دارای دو چیز است: جهتی که قرار است به سمت آن حرکت کند و یک مقدار حافظه که در فراخوانی بعد استفاده می‌شود.

function runRobot(state, robot, memory) {
  for (let turn = 0;; turn++) {
    if (state.parcels.length == 0) {
      console.log(`Done in ${turn} turns`);
      break;
    }
    let action = robot(state, memory);
    state = state.move(action.direction);
    memory = action.memory;
    console.log(`Moved to ${action.direction}`);
  }
}

ببینید یک ربات برای اینکه یک وضعیت داده شده را حل کند، چه کار باید انجام دهد. برای برداشتن بسته‌ها، باید به همه‌ی موقعیت‌هایی که بسته دارند برود و برای تحویل آن‌ها، باید به همه‌ی موقعیت‌هایی که بسته‌ای به آنجا آدرس‌دهی شده است سر بزند، البته بعد از اینکه بسته را تحویل گرفت.

احمقانه‌ترین استراتژی برای حل این موضوع چیست؟ ربات می‌تواند به صورت تصادفی هر بار به جهتی برود. معنای آن این است که به احتمال زیاد، در نهایت به همه‌ی بسته‌ها دست خواهد یافت و بالاخره به مکان‌هایی که باید آن‌ها را تحویل دهد نیز می‌رسد.

در این جا می‌توان نمونه‌ی این کد را دید:

function randomPick(array) {
  let choice = Math.floor(Math.random() * array.length);
  return array[choice];
}

function randomRobot(state) {
  return {direction: randomPick(roadGraph[state.place])};
}

به خاطر داشته باشید که متد Math.random() عددی بین صفر و یک تولید می‌کند که همیشه کمتر از یک است. ضرب این عدد در طول یک آرایه و بعد اعمال Math.floor به آن باعث می‌شود که به صورت تصادفی یکی از اندیس‌های آرایه را بدست بیاوریم.

به دلیل اینکه این ربات نیازی ندارد تا چیزی را به خاطر داشته باشد، پس آرگومان دوم در نظر گرفته نمی‌شود (به یاد دارید که در جاوااسکریپت می‌توان بدون ایجاد خطا، یک تابع را با آرگومان بیشتر فراخوانی کرد) و خاصیت memory را هم در شیء خروجی قرار نمی‌دهد.

برای بکار انداختن این ربات، ابتدا لازم است راهی برای ایجاد یک وضعیت جدید به وسیله‌ی چند بسته پیدا کنیم. یک متد ایستا (در اینجا به طور مستقیم با افزودن یک خاصیت به سازنده تعریف می‌شود) جای خوبی برای این قابلیت است.

VillageState.random = function(parcelCount = 5) {
  let parcels = [];
  for (let i = 0; i < parcelCount; i++) {
    let address = randomPick(Object.keys(roadGraph));
    let place;
    do {
      place = randomPick(Object.keys(roadGraph));
    } while (place == address);
    parcels.push({place, address});
  }
  return new VillageState("Post Office", parcels);
};

بسته‌هایی که آدرس مبدا و مقصدشان یکی است را نیازی نیست در نظر بگیریم. به همین علت، حلقه do تا زمانی که مبدا و مقصد برابر باشد، به گرفتن مکان‌ها ادامه می‌دهد.

بیاید تا یک جهان مجازی را شروع کنیم.

runRobot(VillageState.random(), randomRobot);
// → Moved to Marketplace
// → Moved to Town Hall
// → …
// → Done in 63 turns

برای تحویل بسته‌ها، ربات باید حرکت‌های زیادی انجام دهد به این خاطر که از پیش به خوبی برنامه‌ریزی نشده است. به زودی این مشکل را حل خواهیم کرد.

برای دیدن نمایی بهتر از شبیه‌سازی، می‌توانید از تابع runRobotAnimation استفاده کنید که در فضای برنامه‌نویسی این فصل موجود است. این تابع برای شبیه‌سازی، به جای استفاده از متن ساده، از حرکت ربات در نقشه‌ی روستا استفاده می‌کند.

runRobotAnimation(VillageState.random(), randomRobot);

نحوه‌ی پیاده‌سازی تابع runRobotAnimation فعلا سربسته می ماند، اما بعد از اینکه فصل‌‌های بعدی کتاب را خواندید، که به موضوع جاوااسکریپت در مرورگر‌های وب می‌پردازد، می‌توانید حدس بزنید که چگونه کار می‌کند.

مسیر ماشین پست

باید بتوانیم کاری بهتر از ساخت یک ربات تصادفی انجام دهیم. یک بهبود ساده می‌تواند الهام‌گیری از سیستم تحویل پست در دنیای واقعی باشد. اگر مسیری پیدا کنیم که از همه‌ی خانه‌های روستا بگذرد، ربات می‌تواند از آن مسیر دو مرتبه عبور کند. با این کار می‌توان ضمانت کرد که ماموریتش را انجام می‌دهد. در این جا مسیری با این مشخصات آورده شده است (شروع از دفتر پست):

const mailRoute = [
  "Alice's House", "Cabin", "Alice's House", "Bob's House",
  "Town Hall", "Daria's House", "Ernie's House",
  "Grete's House", "Shop", "Grete's House", "Farm",
  "Marketplace", "Post Office"
];

برای پیاده‌سازی ربات مسیرپیما، باید از حافظه‌ی ربات استفاده کنیم. ربات مسیر باقی‌مانده را در حافظه‌اش نگهداری می‌کند و با هر بار جابه‌جایی، اولین عنصر را از آن خارج می‌کند.

function routeRobot(state, memory) {
  if (memory.length == 0) {
    memory = mailRoute;
  }
  return {direction: memory[0], memory: memory.slice(1)};
}

این ربات از ربات قبلی بسیار سریع‌تر عمل می‌کند. در حالت بیشینه 26 حرکت خواهد داشت، (دو برابر مسیر 13 گامی)، اما معمولا کمتر طول خواهد کشید.

runRobotAnimation(VillageState.random(), routeRobot, []);

مسیریابی

هنوز، نمی‌توانم دنباله‌روی کورکورانه از یک مسیر ثابت را واقعا یک رفتار هوشمندانه بنامم. اگر رفتار ربات را به سمت کاری که واقعا باید انجام دهد اصلاح کنیم، می‌تواند با کارایی بیشتری عمل کند.

برای این کار، باید بتواند به صورت دلخواه به سمت یک بسته‌ی مشخص، یا جایی که قرار است بسته تحویل داده شود حرکت کند. انجام این کار، حتی زمانی که تا هدف تنها دو گام یا بیشتر فاصله دارد، به نوعی مسیریابی نیاز دارد.

مساله پیدا کردن یک مسیر در یک گراف، یک مساله‌ی جستجوی معمولی است. ما می‌توانیم بگوییم که یک راه‌حل داده‌شده (یک مسیر) راه حلی معتبر است؛ اما نمی‌توانیم به همان صورت که 2+2 را محاسبه می‌کنیم، به طور مستقیم راه حل را بدست بیاوریم. در عوض، باید به ایجاد راه‌حل‌های بالقوه ادامه دهیم تا زمانی که به مورد صحیح برسیم.

تعداد مسیر‌های ممکن در یک گراف نامتناهی است. اما زمانی که به دنبال مسیری از نقطه‌ی A به B هستیم، تنها به مسیر‌هایی توجه می‌کنیم که از نقطه‌ی A شروع می‌شوند. همچنین به مسیر‌هایی که دوبار از یک مکان عبور می‌کنند، اهمیت نمی‌دهیم – آن‌ها قطعا نمی‌توانند بهترین مسیر باشند. بنابراین، تعداد مسیر‌هایی که مسیریاب باید در نظر بگیرد کاهش می‌یابند.

در واقع، ما بیشتر علاقمندیم تا کوتاهترین مسیر را پیدا کنیم. بنابراین باید اطمینان حاصل کنیم که پیش از مسیر‌های بلند‌تر، مسیر‌های کوتاه بررسی می‌شوند. یک راه حل خوب می‌تواند این باشد که از نقطه‌ی شروع، مسیر‌ها را "رشد" دهیم، و هر مکان قابل دسترسی که قبلا بازدید نکرده‌ایم را بررسی کنیم تا اینکه یک مسیر به هدفش برسد. به این ترتیب، ما فقط مسیر‌هایی را کشف خواهیم کرد که به صورت بالقوه مرتبط به نظر می‌رسند و درنتیجه کوتاهترین مسیر را تا هدف پیدا خواهیم کرد (یا یکی از کوتاهترین مسیر‌ها در صورتی که بیش از یک مسیر وجود داشته باشد).

تابع زیر این کار را انجام می‌دهد:

function findRoute(graph, from, to) {
  let work = [{at: from, route: []}];
  for (let i = 0; i < work.length; i++) {
    let {at, route} = work[i];
    for (let place of graph[at]) {
      if (place == to) return route.concat(place);
      if (!work.some(w => w.at == place)) {
        work.push({at: place, route: route.concat(place)});
      }
    }
  }
}

بررسی مکان‌ها باید با ترتیب درست انجام شود – مکان‌هایی که ربات زودتر به آن‌ها رسیده است را باید زودتر بررسی کرد. نمی‌توانیم یک مکان را به محض اینکه به آن رسیدیم مورد بررسی قرار دهیم زیرا در این صورت مکان‌هایی که از آن نقطه بدست می‌آیند را نیز باید بلافاصله بررسی کنیم و به همین ترتیب ادامه دهیم؛ در حالیکه ممکن است مسیر‌های کوتاهتری باشند که اصلا بررسی نشده‌اند.

بنابراین، تابع فهرستی از کار‌ها را نگه داری می‌کند. این فهرست یک آرایه از مکان‌هایی است که باید در گام بعدی، به همراه مسیری که ما را به آنجا می‌رساند بررسی شود. این فهرست کار، در ابتدا فقط یک موقعیت شروع و یک مسیر خالی دارد.

سپس جستجو مورد بعدی در فهرست را می‌گیرد و آن را بررسی می‌کند، به این معنا که همه‌ی راه‌هایی که از آن مکان عبور می‌کنند دیده می‌شوند. اگر یکی از آن‌ها هدف باشد، یک مسیر کامل می‌تواند برگردانده شود. در غیر این صورت، اگر قبلا به این مکان نگاه نکرده باشیم، یک مورد جدید به فهرست اضافه می‌شود. اگر قبلا آن را دیده باشیم، از آنجا که ما اول مسیر‌های کوتاهتر را بررسی می‌کنیم، یا یک مسیر طولانی‌تر به آن محل را پیدا کرده‌ایم یا مسیری دقیقا برابر با مسیری که در فهرست وجود دارد؛ پس نیازی نیست که آن را مورد بررسی قرار دهیم.

می‌توان آن را به عنوان شبکه‌ای مانند تار عنکبوت در نظر گرفت که از موقعیت شروع به صورت برابر و به سمت همه‌ی اضلاع به بیرون پیموده می‌شود (اما تار‌ها با هم قاطی و پیچیده نمی‌شوند). به محض اینکه اولین تار به مکان هدف رسید، این تار تا نقطه‌ی شروع رصد می‌شود و مسیر را مشخص می‌کند.

کد ما به حالتی که در آن، عنصری در آرایه‌ی فهرست کار‌ها وجود ندارد، نمی‌پردازد زیرا می‌دانیم که گراف ما یک گراف متصل است (connected) به این معنی که هر مکان را می‌توان از همه‌ی مکان‌های دیگر بدست آورد. همیشه قادر خواهیم بود مسیری بین دو نقطه پیدا کنیم و عمل جستجو هرگز با شکست روبرو نمی‌شود.

function goalOrientedRobot({place, parcels}, route) {
  if (route.length == 0) {
    let parcel = parcels[0];
    if (parcel.place != place) {
      route = findRoute(roadGraph, place, parcel.place);
    } else {
      route = findRoute(roadGraph, place, parcel.address);
    }
  }
  return {direction: route[0], memory: route.slice(1)};
}

این ربات از مقدار حافظه‌ی خود به عنوان یک لیست از جهت‌ها برای حرکت استفاده می‌کند، درست مانند ربات مسیرپیما. هر زمان که این لیست خالی می‌شود، ربات باید گام بعدی را کشف کند. برای این‌کار، به سراغ اولین بسته‌ی تحویل داده نشده در این مجموعه می‌رود، و اگر آن بسته هنوز برداشته نشده بود، مسیری به سمت آن طرح‌ریزی می‌کند. اگر بسته قبلا تحویل گرفته شده باشد، پس هنوز باید تحویل داده شود، بنابراین ربات، مسیری به سمت آدرس تحویل ایجاد می‌کند.

بیایید ببینیم چگونه کار می‌کند.

runRobotAnimation(VillageState.random(),
                  goalOrientedRobot, []);

این ربات معمولا تحویل 5 بسته را در 16 حرکت انجام می‌دهد. کمی بهتر از routeRobot کار می‌کند اما قطعا هنوز بهینه نیست.

تمرین‌ها

اندازه‌گیری یک ربات

خیلی سخت بتوان ربات‌ها را بر اساس حل چند مساله‌ی محدود به طور صحیح مقایسه کرد. شاید یک ربات به صورت تصادفی با مساله‌های آسان روبرو شود یا مسائلی که در حل آن‌ها بهتر عمل می‌کند. اما دیگر ربات‌ها این شرایط را نداشته باشند.

تابعی به نام compareRobots بنویسید که دو ربات را دریافت می‌کند (به همراه حافظه‌ی شروع‌شان). تابع باید صد وظیفه ایجاد کرده و هر یک از ربات‌ها باید همه‌ی وظایف را انجام دهند. پس از پایان، متوسط تعداد گام‌هایی که هر ربات برای یک وظیفه برداشته است را برگرداند.

برای رعایت عدالت، مطمئن شوید که هر وظیفه توسط هر دوی ربات‌ها انجام می‌شود و از ایجاد وظایف جدید برای هر ربات پرهیز کنید.

function compareRobots(robot1, memory1, robot2, memory2) {
  // Your code here
}

compareRobots(routeRobot, [], goalOrientedRobot, []);

کارایی ربات

آیا می‌توانید رباتی بنویسید که وظیفه تحویل بسته‌ها را سریع‌تر از ربات goalOrientedRobot انجام دهد؟ با مشاهده‌ی دقیق رفتار آن، چه اشتباهات روشنی انجام می‌دهد؟ چگونه می‌توان آن‌ها را بهبود بخشید؟

اگر تمرین قبلی را حل کرده‌اید، ممکن است بخواهید از تابع compareRobots که نوشته‌اید برای برای بررسی بهبود ربات جدید استفاده کنید.

// Your code here

runRobotAnimation(VillageState.random(), yourRobot, memory);

گروه مانا (Persistent Group)

اکثر ساختار‌های داده‌ای که به صورت استاندارد در جاوااسکریپت وجود دارند، برای استفاده به عنوان ساختار داده‌ی مانا، خیلی مناسب نیستند. آرایه‌ها دارای متد‌های slice و concat می‌باشند که این امکان را فراهم می‌سازند تا آرایه‌های جدید را بدون تغییر آرایه‌ی اصلی ایجاد کنیم. اما مثلا Set، متدی برای ایجاد یک مجموعه‌ی جدید که آیتمی اضافه یا کم داشته باشد ندارد.

کلاس جدیدی به نام PGroup بنویسید، شبیه به کلاس Group که در فصل ?](object#groups) نوشتید، که مجموعه‌ای از مقادیر را ذخیره می‌کند. مانند Group دارای متد‌های add، delete و has خواهد بود.

متد add آن، باید نمونه‌ی جدیدی از ‌PGroup را که شامل عضو جدید می‌باشد، تولید کند و نمونه‌ی قبلی را دست نخورده باقی بگذارد. به طور مشابه، متد delete نمونه‌ی جدیدی بدون عضو داده شده، تولید می‌کند.

کلاس مورد نظر باید بتواند علاوه بر رشته‌، هر نوع داده‌ای را به عنوان کلید قبول کند. نیازی نیست تا کارایی بالایی در کار با تعداد بالای کلید‌ها داشته باشد.

سازنده نباید بخشی از رابط کلاس باشد (اگرچه حتما لازم است که به صورت درونی از آن استفاده کنید). در عوض، یک نمونه‌ی تهی به نام PGroup.empty باید باشد که بتوان از آن برای مقدار ابتدایی استفاده کرد.

چرا به جای داشتن تابعی که بتواند هر بار یک نگاشت تهی جدید ایجاد کند، لازم است تا فقط یک PGroup.empty وجود داشته باشد؟

class PGroup {
  // Your code here
}

let a = PGroup.empty.add("a");
let ab = a.add("b");
let b = ab.delete("a");

console.log(b.has("b"));
// → true
console.log(a.has("b"));
// → false
console.log(b.has("a"));
// → false