Chapter 7پروژه: ساخت یک ربات

[...] the question of whether Machines Can Think [...] is about as relevant as the question of whether Submarines Can Swim.

Edsger Dijkstra, The Threats to Computing Science
Picture of a package-delivery robot

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

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

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

روستای مدوفیلد زیاد بزرگ نیست. دارای 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"
];
The village of Meadowfield

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

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

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 شیءای از نوع نگاشت (map) را ایجاد خواهد کرد که برای هر گره، آرایه‌ای از گره‌های متصل به آن را ذخیره خواهد کرد.

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

ماموریت

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

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

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

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

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

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

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

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

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, []);

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

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

کارایی ربات

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

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

// Your code here

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

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

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

گروه پایا (Persistent Group)

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

کلاس جدیدی به نام PGroup بنویسید، شبیه‌ به کلاس Group که در فصل 6 نوشتید، که مجموعه‌ای از مقادیر را ذخیره می‌کند. مانند 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

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

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

سازنده‌ی کلاس می تواند این آرایه را به عنوان آرگومان دریافت کند و آن را به عنوان تنها خاصیت نمونه‌ (instance) ذخیره نماید. این آرایه هرگز تغییر نمی کند.

برای افزودن یک خاصیت غیر متد (empty) به یک سازنده، باید بعد از تعریف کلاس، آن را مانند یک خاصیت معمولی به سازنده اضافه کنید.

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