إلكونت جافاسكريبت مشروع تطبيقي لبناء رجل آلي (روبوت) عبر جافاسكريبت

اقتباس

إن السؤال عن تفكير الآلات يشبه تمامًا سؤالك هل تستطيع الغواصات السباحة أم لا.

__ إدزجر ديكسترا Edsger Dijkstra، المخاطر التي تهدد علوم الحاسوب.

يختلف هذا المقال قليلًا عن باقي الفصول، إذ سأدَع الحديث عن النظريات قليلًا لننشئ نحن وأنت برنامجًا سويًا، فالنظرية وإن كانت مهمة جدًا لتعلم كيفية البرمجة، إلا أنّ قراءة البرامج الحقيقية وفهم شيفراتها لا تقل أهمية، ومشروعنا في هذا المقال هو بناء روبوت ينفِذ مهمة في عالم افتراضي، وستكون تلك المهمة توصيل الطرود واستلامها.

قرية المرج Meadowfield

سيعمل الروبوت الخاص بنا في قرية صغيرة تُدعى قرية المرج، حيث يوجد فيها أحد عشر مكانًا بينها أربعة عشر طريقًا، ويمكن وصف القرية بالمصفوفة التالية:

const roads = [
  "Salma's House-Omar's House",   "Salma's House-Cabin",
  "Salma's House-Post Office",   "Omar's House-Town Hall",
  "Sara's House-Mostafa's House", "Sara's House-Town Hall",
  "Mostafa's House-Sama's House", "Sama's House-Farm",
  "Sama's House-Shop",          "Marketplace-Farm",
  "Marketplace-Post Office",     "Marketplace-Shop",
  "Marketplace-Town Hall",       "Shop-Town Hall"
];

وتكوِّن شبكة الطرق في القرية مخططًا graph، وهو عبارة عن تجميعة من نقاط لتمثل الأماكن في القرية، مع خطوط تصل بينها بحيث تمثل الطرق، وسيكون هذا هو العالم الذي سيتحرك الروبوت فيه.

لكن ليس من السهل التعامل مع مصفوفة السلاسل النصية السابقة، إذ لا نريد إلا الوجهات التي يمكننا الذهاب إليها من أي نقطة معطاة لنا، وعلى ذلك فسنحوِّل قائمة الطرق إلى هيكل بيانات يخبرنا بالمناطق التي نستطيع الذهاب إليها من كل نقطة أو مكان، انظركما يلي:

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 object عند إعطائها مصفوفة من الحدود edges، حيث تخزن فيها لكل عقدةٍ مصفوفةً من العقد المتصلة بها. كما تستخدِم تابع method للذهاب من سلسلة الطريق النصية التي تحمل الصيغة "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 أولًا إن كان ثمة طريق من الموقع الحالي إلى موقع الوِجهة، وإن لم يكن، فسيعيد الحالة القديمة بما أنّ هذه الخطوة غير صالحة، ثم يُنشئ حالةً جديدةً يكون فيها موقع الوِجهة هو الموقع الجديد للروبوت.

لكن سيحمل هذا الروبوت معه طرودًا أخرى غير هذا الطرد، ويأخذها معه إلى موقع تسليم الطرد المسمى، ثم يتابع حملها معه بعد تسليم الطرد، ليذهب بكل منها إلى موقع تسليمه الذي يخصه، ولكي نحصل على بيانات تلك الطرود عند أي نقطة زمنية نريدها، فسنحتاج إلى إنشاء فئة set جديدة نضع فيها تلك الطرود التي يحملها إلى الموقع الجديد، ثم يترك الطرود الواجب تسليمها في موقع التسليم، أي نحذفها من فئة الطرود غير المسلَّمة. ويتكفل بعملية الانتقال استدعاء map، بينما نستدعي filter ليتولى عملية التسليم.

لا تتغير كائنات الطرود عند نقلها، وإنما يعاد إنشاؤها، ويعطينا التابع move حالة جديدة للقرية مع ترك الحالة القديمة كما هي دون تغيير، انظر كما يلي:

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

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

تُسلَّم الطرود عند مواضع تسليمها مع حركة الروبوت بين تلك المواقع، ويُرى أثر ذلك في الحالة التالية، لكن ستظل الحالة الابتدائية تصف الموقف الذي يكون فيه الروبوت عند مكتب البريد ومعه الطرد الغير مسلَّم بعد.

البيانات الثابتة Persistent Data

تُسمى هياكل البيانات التي لا تتغير بالهياكل الثابتة persistent، أو غير القابلة للتغير immutable، وتحاكي السلاسل النصية والأرقام في بقائها كما هي، بدلًا من احتواء أشياء مختلفة في كل مرة.

بما أن كل شيء في جافاسكربت قابل للتغير تقريبًا، فسيتطلب العمل مع كائنات أو بيانات ثابتة جهدًا، وعملًا إضافيًا، ونوعًا من التقييد، حيث لدينا دالة Object.freeze من أجل هذا، إذ تؤثر على الكائن وتجمده، وذلك لتجعله يتجاهل الكتابة على خصائصه، فتستطيع استخدام ذلك لضمان ثبات كائناتك إن أردت، لكن تذكر أن هذا التجميد يعني أن الحاسوب سيبذل مزيدًا من الجهد.

نفضل إخبار العامة بترك الكائن الفلاني وشأنه وعدم العبث به، آملين تذكّرهم ذلك، بدلًا من إخبارهم بتجاهل تحديثات بعينها.

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

لكن هنا يبرز سؤال إن كنت منتبهًا، فإن كانت اللغة نفسها تحثنا على جعل كل شيء متغيرًا وتتوقع منا ذلك، فلماذا نخرج عن هذا المسلك لنجعل بعض الكائنات ثابتةً لا تقبل التغيير؟

الإجابة بسيطة وهي أن هذا سيساعدنا في فهم برامجنا أكثر، إذ يتعلق الأمر بإدارة التعقيد لبرامجنا، فإن كانت الكائنات التي في نظامنا ثابتةً ومستقرةً، فيمكننا إجراء عمليات عليها إجراءً معزولًا -حيث سيعطينا التحرك إلى منزل سلمى مثلًا من أي حالة بدء معطاة الحالة الجديدة نفسها في كل مرة-،؛ أما إن كانت الكائنات تتغير مع الوقت، فسيضيف هذا بعدًا جديدًا من التعقيد إلى العمليات والتفكير المنطقي لحل المشكلة.

وربما تقول أن مسألة توصيل الطرود، والروبوت، وهذه القرية الصغيرة، سهل أمرها ويمكن إدارتها، وربما أنت محق، لكن المعيار الذي يحدد نوع النظم الممكن بناؤها هو فهمنا نحن لتلك الأنظمة ومدى ما يمكننا فهمه مطلقًا، فأيّ شيء يسرّع فهم شيفرتك، فسيمهد لك الطريق لبناء نظم أكثر تطورًا.

لكن رغم سهولة فهم النظم المبنية على هياكل بيانات ثابتة، فقد يكون من الصعب تصميم نظام مثل هذا، وخاصةً إن لم تكن لغة البرمجة التي تستخدمها مصمَّمةً لذلك، كما سنبحث عن فرص استخدام هياكل البيانات الثابتة في هذه السلسلة مع استخدامنا للهياكل المتغيرة كذلك.

المحاكاة

ينظر روبوت التوصيل إلى العالم، ويقرر الاتجاه الذي يريد السير فيه، وعليه فيمكننا القول أنّ الروبوت هو دالة تأخذ كائن 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 = [
  "Salma's House", "Cabin", "Salma's House", "Omar's House",
  "Town Hall", "Sara's House", "Mostafa's House",
  "Sama's House", "Shop", "Sama's House", "Farm",
  "Marketplace", "Post Office"
];

نحتاج إلى الاستفادة من ذاكرة الروبوت إذا أردنا استخدام الروبوت المتتبع للطريق route-following، حيث يحذف الروبوت العنصر الأول عند كل منعطف ويحتفظ ببقية الطريق:

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

سيكون هذا الروبوت بهذا الأسلوب الجديد أسرع من الأسلوب الأول، إذ سيكون أقصى عدد من الاتجاهات التي يسلكها أو المنعطفات التي يأخذها هو 26 -وهو ضعف عدد الأماكن في طريق القرية-، وإن كان في العادة أقل من هذا العدد، فليست جميع الأماكن بها طرود بريد في كل مرة.

اكتشاف الطريق Pathfinding

لنبحث في طريقة أكثر تطورًا من المرور على جميع الأماكن في القرية في كل مرة، فلا شك في أن الروبوت سيكون أكثر كفاءة إذا عدّل سلوكه ليناسب العمل الحقيقي المراد تنفيذه؛ لذا يجب امتلاكه القدرة على التحرك نحو طرد معين أو موقع تسليم بعينه، وعليه نحتاج دالة لإيجاد الطريق المناسبة.

تُعَدّ مشكلة إيجاد الطريق باستخدام مخطط هي مشكلة البحث، حيث نستطيع تحديد ما إذا كان الحل المعطى -أي الطريق- مناسبًا أم لا، لكن لا نستطيع حساب الحل بالطريقة نفسها عند حساب حاصل جمع 2+2 مثلًا، وإنما يجب إنشاء حلولًا محتملةً لإيجاد واحد صالح.

تتضح هنا المشكلة أكثر، إذ لا نهايةً لعدد الاحتمالات الممكنة للطرق من خلال مخطط، لكن يمكن تضييق عدد الاحتمالات إذا أردنا الطرق المؤدية من نقطة أ إلى نقطة ب مثلًا، فعندئذ لن يهمنا سوى الطرق التي تبدأ من النقطة أ، كما لا نريد الطرق التي تمر المكان نفسه مرتين، إذ لا تُعَدّ هي الطرق الأكثر كفاءة في أي مكان، ويقلل هذا عدد الطرق التي يجب اعتمادها من قِبَل دالة البحث أكثر وأكثر.

نريد في الواقع أقصر طريق فقط، وعليه يجب النظر في الطرق الأقصر أولًا قبل النظر في الطرق الأطول، وأحد الأساليب لفعل ذلك هو بدء طرق من نقطة تحرك الروبوت لتُستكشف جميع الأماكن التي يمكن الوصول إليها ولم يُذهب إليها بعد، حتى تصل إحدى تلك الطرق إلى المكان المراد تسليم الطرد إليه، وهكذا نستكشف الطرق التي يحتمل أن تكون مفيدة لنا، ونتخذ أقصرها أو واحدًا من أقصر تلك الطرق. كما في الدالة التالية:

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)});
      }
    }
  }
}

يجب أن يتم الاستكشاف بترتيب صحيح، فالأماكن التي يصل إليها أولًا يجب استكشافها أولًا، لكن انتبه إلى أن مكان س مثلًا لا يُستكشف فور الوصول إليه، إذ سيعني هذا أنه علينا استكشاف أماكن يمكن الوصول إليها من س وهكذا، رغم احتمال وجود مسارات أقصر لم تُستكشف بعد.

وعلى هذا فإن الدالة تحتفظ بقائمة عمل work list، وهي مصفوفة من الأماكن التي يجب استكشافها فيما بعد مع الطرق التي توصلنا إليها، حيث تبدأ بموقع ابتدائي للبدء منه وطريق فارغة، ثم يبدأ البحث بعدها بأخذ العنصر التالي في القائمة واستكشافه، مما يعني النظر في جميع الطرق الخارجة من هذا المكان، فإن كان أحدها هو الهدف المراد، فيُعاد طريق تامة finished road، وإلا فسيضاف عنصر جديد إلى القائمة إن لم يُنظر في هذا المكان من قبل.

كذلك، إن كنا قد نظرنا فيه من قبل، فقد وجدنا إما طريق أطول إلى هذا المكان أو واحدة بنفس طول الطريق الموجودة -وبما أننا نبحث عن الطرق الأقصر أولًا- ولا نحتاج إلى استكشافها عندئذ.

تستطيع تخيل هذا بصريًا على أساس شبكة من الطرق المعروفة، حيث تخرج من موقع ابتدائي، وتنمو بانتظام في جميع الجوانب، لكن لا تتشابك مع بعضها أو تنعكس على نفسها؛ وبمجرد وصول خيط من تلك الشبكة إلى الموقع الهدف، فيُتتبَّع ذلك الخيط إلى نقطة البداية ليعطينا الطريق التي نريدها.

لا تعالج شيفرتنا الموقف الذي لا تكون فيه عناصر عمل على قائمة العمل، وذلك لعِلمنا باتصال المخطط الخاص بنا، أي يمكن الوصول إلى كل موقع من جميع المواقع الأخرى، وسنكون قادرين دائمًا على إيجاد طريق ممتدة بين نقطتين، فلا يفشل البحث الذي نجريه.

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

ينهي هذا الروبوت مهمة تسليم خمسة طرود في نحو ستة عشر منعطفًا، وهذا أفضل بقليل من routeRobot، لكن لا زال هناك فرصة للتحسين أكثر من ذلك.

تدريبات

معايرة الروبوت

من الصعب موازنة الروبوتات بجعلها تحل بعض السيناريوهات البسيطة، فلعل أحدها حصل على مهام سهلة دون الآخر.

اكتب دالة compareRobots التي تأخذ روبوتين مع ذاكرتهما الابتدائية، وتولد مائة مهمة، ثم اجعل كل واحد من الروبوتين يحل هذه المهام كلها واحدة واحدة، ويجب أن يكون الخرج عند انتهائهما هو العدد المتوسط للخطوات التي قطعها كل واحد لكل مهمة.

تأكد من إعطاء المهمة نفسها لكلا الروبوتين في تلك المهام المئة لضمان العدل والدقة في النتيجة، بدلًا من توليد مهام مختلفة لكل روبوت.

تستطيع تعديل شيفرة التدريب لكتابة الحل وتشغيلها في طرفية المتصفح إن كنت تقرأ من متصفح، أو بنسخها إلى codepen.

function compareRobots(robot1, memory1, robot2, memory2) {
  // شيفرتك هنا
}

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

إرشادات للحل

سيكون عليك كتابة صورة من دالة runRobot، بحيث تعيد عدد الخطوات التي قطعها الروبوت لإتمام المهمة، بدلًا من تسجيل الأحداث في الطرفية. عندئذ تستطيع دالة القياس توليد حالات جديدة في حلقة تكرارية، وعدّ خطوات كل روبوت؛ وحين تولد قياسات كافية، فيمكنها استخدام console.log لإخراج المتوسط لكل روبوت، والذي سيكون ناتج قسمة العدد الكلي للخطوات المقطوعة على عدد القياسات.

كفاءة الروبوت

هل تستطيع كتابة روبوت ينهي مهمة التوصيل أسرع من goalOrientedRobot؟ ما الأشياء التي تبدو غبيةً بوضوح؟ وكيف يمكن تطويرها؟

إن حللت التدريبات السابقة، فربما تود استخدام دالة compareRobots التي أنشأتَها قبل قليل للتحقق إن كنت قد حسّنت الروبوت أم لا.

تستطيع تعديل شيفرة التدريب لكتابة الحل وتشغيلها في طرفية المتصفح إن كنت تقرأ من متصفح، أو بنسخها إلى codepen.

// شيفرتك هنا

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

إرشادات للحل

إن القيد الرئيسي لـ goalOrientedRobot هو تعاملها مع طرد واحد في كل مرة، وستمضي ذهابًا وإيابًا في القرية، وذلك لأن الطرد الذي تريده موجود على الناحية الأخرى من الخارطة، حتى لو كان في طريقها طرود أخرى أقرب.

أحد الحلول الممكنة هنا هو حساب طرق جميع الطرود ثم أخذ أقصرها، ويمكن الحصول على نتائج أفضل إذا كان لدينا عدة طرق قصيرة، فسنختار حينها الطرق التي فيها التقاط طرد بدلًا من التي فيها تسليم طرد.

المجموعة الثابتة

ستجد أغلب هياكل البيانات الموجودة في بيئة جافاسكربت القياسية لا تناسب الاستخدام الثابت، حيث تملك المصفوفات التابعَين slice وconcat اللذَين يسمحان لنا بإنشاء مصفوفات جديدة دون تدمير القديمة، لكن Set مثلًا ليس فيه توابع لإنشاء فئة جديدة فيها عنصر مضاف إلى الفئة الأولى أو محذوف منها.

اكتب صنف جديد باسم PGroup يشبه الصنف Group من المقال السادس، حيث يخزن مجموعة من القيم، وتكون له التوابع add، وdelete، وhas، كما في الصنف Group تمامًا.

يعيد التابع add فيه نسخةً جديدةً من PGroup مع إضافة العضو المعطى given member وترك القديم دون المساس به، وبالمثل، فيجب على التابع delete إنشاء نسخةً جديدةً ليس فيها العضو المعطى.

يجب أن يعمل هذا الصنف مع أي نوع من القيم وليس السلاسل النصية فقط، ولا تُشترط كفاءته عند استخدامه مع كميات كبيرة من القيم؛ كذلك ليس شرطًا أن يكون الباني constructor جزءًا من واجهة الصنف رغم أنك تريد استخدام ذلك داخليًا، وإنما هناك نسخة فارغة PGroup.empty يمكن استخدامها على أساس قيمة ابتدائية.

لماذا تظن أننا نحتاج إلى قيمة PGroup.empty واحدة فقط بدلًا من دالة تنشئ خارطةً جديدةً وفارغةً في كل مرة؟

تستطيع تعديل شيفرة التدريب لكتابة الحل وتشغيلها في طرفية المتصفح إن كنت تقرأ من متصفح، أو بنسخها إلى codepen.

class PGroup {
  // شيفرتك هنا
}

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 مثلًا-، وتستطيع ترشيحها من المصفوفة حين تُحذف تلك القيمة.

يستطيع باني الصنف أخذ مثل هذه المصفوفة على أساس وسيط، ويخزنها على أنها الخاصية الوحيدة للنسخة، ولا تُحدَّث هذه المصفوفة بعدها.

يحب إضافة الخاصية empty إلى باني غير تابع بعد تعريف الصنف، مثل وسيط عادي.

تحتاج إلى نسخة empty واحدة فقط بسبب تطابق المجموعات الفارغة وعدم تغير نُسَخ الصنف، كما تستطيع إنشاء مجموعات مختلفة عديدة من هذه المجموعة الفارغة دون التأثير عليها.

ترجمة -بتصرف- للفصل السابع من كتاب Elequent Javascript لصاحبه Marijn Haverbeke.