07 Proyek Robot Pengantar Paket

Bab 7 dari Eloquent JavaScript. Sebelumnya: 06 Kehidupan Rahasia Objek. Berikutnya: 08 Bug dan Error.

Pertanyaan apakah Mesin Bisa Berpikir […] kira-kira sama relevannya dengan pertanyaan apakah Kapal Selam Bisa Berenang.

— Edsger Dijkstra, The Threats to Computing Science

Di bab-bab “proyek”, saya bakal berhenti nonjokin kamu dengan teori baru sebentar, dan sebagai gantinya kita bakal ngerjain sebuah program bareng-bareng. Teori itu perlu buat belajar memprogram, tapi baca dan paham program beneran sama pentingnya.

Proyek kita di bab ini adalah ngebangun automaton, program kecil yang ngelakuin tugas di dunia virtual. Automaton kita bakal jadi robot pengantar surat yang ngambil dan nganterin paket.

Meadowfield

Desa Meadowfield gak terlalu besar. Dia terdiri dari 11 tempat dengan 14 jalan di antaranya. Dia bisa digambarkan dengan array jalan ini:

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"
];

Jaringan jalan di desa ini membentuk graph. Graph adalah kumpulan titik (tempat di desa) dengan garis di antaranya (jalan). Graph ini bakal jadi dunia tempat robot kita bergerak.

Array string ini gak terlalu gampang buat dikerjain. Yang kita minati adalah tujuan-tujuan yang bisa kita capai dari tempat tertentu. Kita konversi daftar jalannya jadi struktur data yang, buat setiap tempat, ngasih tahu kita apa yang bisa dicapai dari sana.

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

Dikasih array edge (sisi), buildGraph bikin objek map yang, buat setiap node (simpul), nyimpen array node yang terhubung. Dia pakai method split buat pergi dari string jalan, yang berbentuk "Start-End", ke array dua elemen yang berisi awal dan akhir sebagai string terpisah.

Tugasnya

Robot kita bakal bergerak di sekitar desa. Ada paket di berbagai tempat, masing-masing dialamatkan ke tempat lain. Robotnya ngambil paket waktu nemuinnya dan nganterinnya waktu nyampe di tujuannya.

Automaton-nya harus mutusin, di setiap titik, mau ke mana berikutnya. Dia udah nyelesaiin tugasnya waktu semua paket udah dianterin.

Biar bisa nyimulasiin proses ini, kita harus mendefinisikan dunia virtual yang bisa menggambarkannya. Model ini ngasih tahu kita di mana robotnya dan di mana paket-paketnya. Waktu robotnya udah mutusin buat pindah ke suatu tempat, kita perlu ngupdate modelnya buat nyerminin situasi baru.

Kalau kamu mikir dalam kerangka pemrograman berorientasi objek, dorongan pertamamu mungkin mulai mendefinisikan objek buat berbagai elemen di dunia ini: class buat robot, satu buat paket, mungkin satu buat tempat. Ini lalu bisa megang properti yang menggambarkan keadaan mereka saat ini, kaya tumpukan paket di sebuah lokasi, yang bisa kita ubah waktu ngupdate dunianya.

Ini salah. Setidaknya, biasanya salah. Fakta bahwa sesuatu kedengarannya kaya objek gak otomatis berarti dia harus jadi objek di programmu. Secara refleks nulis class buat setiap konsep di aplikasimu cenderung ninggalin kamu dengan kumpulan objek yang saling terhubung yang masing-masing punya keadaan internal yang berubah-ubah. Program kaya gitu sering susah dipahami dan karena itu gampang rusak.

Sebagai gantinya, kita padatkan keadaan desanya jadi kumpulan nilai minimal yang mendefinisikannya. Ada lokasi robot saat ini dan kumpulan paket yang belum dianterin, yang masing-masing punya lokasi saat ini dan alamat tujuan. Itu aja.

Sekalian, kita bikin supaya kita gak ngubah keadaan ini waktu robotnya bergerak tapi malah ngitung keadaan baru buat situasi setelah pergerakannya.

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

Method move adalah tempat aksinya terjadi. Dia pertama ngecek apakah ada jalan dari tempat saat ini ke tujuan, dan kalau gak, dia ngembaliin keadaan lama, karena ini bukan pergerakan yang valid.

Berikutnya, method-nya bikin keadaan baru dengan tujuan sebagai tempat baru robot. Dia juga perlu bikin kumpulan paket baru, paket yang lagi dibawa robot (yang ada di tempat robot saat ini) perlu dipindahin ikut ke tempat baru. Dan paket yang dialamatkan ke tempat baru perlu dianterin, yaitu, mereka perlu dihapus dari kumpulan paket yang belum dianterin. Pemanggilan map ngurusin pemindahannya, dan pemanggilan filter ngurusin pengantarannya.

Objek paket gak diubah waktu dipindahin tapi dibikin ulang. Method move ngasih kita keadaan desa baru tapi ngebiarin yang lama sepenuhnya utuh.

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

Pergerakannya bikin paketnya dianterin, yang tercermin di keadaan berikutnya. Tapi keadaan awalnya masih menggambarkan situasi di mana robotnya ada di kantor pos dan paketnya belum dianterin.

Data Persistent

Struktur data yang gak berubah disebut immutable atau persistent. Mereka berperilaku sangat mirip string dan angka dalam hal mereka adalah apa adanya dan tetap begitu, bukannya berisi hal berbeda di waktu berbeda.

Di JavaScript, hampir semua hal bisa diubah, jadi kerja dengan nilai yang seharusnya persistent butuh sedikit pengendalian diri. Ada fungsi bernama Object.freeze yang ngubah objek supaya penulisan ke propertinya diabaikan. Kamu bisa pakai itu buat mastiin objekmu gak diubah, kalau kamu mau hati-hati. Ngebekuin emang ngeharusin komputer ngelakuin kerja ekstra, dan bikin update diabaikan kira-kira sama mungkinnya bikin orang bingung dengan bikin mereka ngelakuin hal yang salah. Saya biasanya lebih suka cuma ngasih tahu orang bahwa objek tertentu gak boleh diutak-atik dan berharap mereka ingat.

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

Kenapa saya repot-repot gak ngubah objek padahal bahasanya jelas ngarepin saya ngelakuinnya? Karena itu ngebantu saya paham program saya. Ini soal manajemen kerumitan lagi. Waktu objek-objek di sistem saya adalah hal yang tetap dan stabil, saya bisa mempertimbangkan operasi pada mereka secara terisolasi, pindah ke rumah Alice dari keadaan awal tertentu selalu ngehasilin keadaan baru yang sama. Waktu objek berubah seiring waktu, itu nambahin dimensi kerumitan yang sama sekali baru ke jenis penalaran ini.

Buat sistem kecil kaya yang kita bangun di bab ini, kita bisa nanganin sedikit kerumitan ekstra itu. Tapi batasan paling penting soal jenis sistem apa yang bisa kita bangun adalah seberapa banyak yang bisa kita pahami. Apa pun yang bikin kodemu lebih gampang dipahami bikin mungkin buat ngebangun sistem yang lebih ambisius.

Sayangnya, walaupun memahami sistem yang dibangun di atas struktur data persistent lebih gampang, ngedesain-nya, terutama waktu bahasa pemrogramanmu gak ngebantu, bisa sedikit lebih susah. Kita bakal nyari kesempatan buat pakai struktur data persistent di buku ini, tapi kita juga bakal pakai yang bisa berubah.

Simulasi

Robot pengantar ngelihat dunia dan mutusin ke arah mana dia mau bergerak. Jadi kita bisa bilang robot adalah fungsi yang ngambil objek VillageState dan ngembaliin nama tempat terdekat.

Karena kita mau robot bisa ngingat sesuatu biar mereka bisa bikin dan ngejalanin rencana, kita juga ngasih mereka memori mereka dan ngebolehin mereka ngembaliin memori baru. Jadi, yang dikembaliin robot adalah objek yang berisi arah yang dia mau tuju dan nilai memori yang bakal dikasih balik ke dia waktu dia dipanggil berikutnya.

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

Bayangin apa yang harus dilakuin robot buat “nyelesaiin” keadaan tertentu. Dia harus ngambil semua paket dengan ngunjungin setiap lokasi yang punya paket dan nganterinnya dengan ngunjungin setiap lokasi tujuan paket, tapi cuma setelah ngambil paketnya.

Strategi paling bodoh apa yang mungkin bisa jalan? Robotnya bisa cuma jalan ke arah acak setiap giliran. Itu berarti, dengan kemungkinan besar, dia akhirnya bakal nemuin semua paket lalu juga di suatu titik nyampe tempat mereka harus dianterin.

Ini bentuknya:

function randomPick(array) {
  let choice = Math.floor(Math.random() * array.length);
  return array[choice];
}
 
function randomRobot(state) {
  return {direction: randomPick(roadGraph[state.place])};
}

Ingat bahwa Math.random() ngembaliin angka antara 0 dan 1, tapi selalu di bawah 1. Ngaliin angka kaya gitu dengan panjang array lalu nerapin Math.floor ke hasilnya ngasih kita indeks acak buat array-nya.

Karena robot ini gak perlu ngingat apa pun, dia ngabaikan argumen keduanya (ingat bahwa fungsi JavaScript bisa dipanggil dengan argumen ekstra tanpa efek buruk) dan ngilangin properti memory di objek yang dia kembaliin.

Buat bikin robot canggih ini kerja, kita pertama butuh cara buat bikin keadaan baru dengan beberapa paket. Method static (ditulis di sini dengan langsung nambahin properti ke constructor) adalah tempat yang bagus buat naruh fungsionalitas itu.

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

Kita gak mau ada paket yang dikirim dari tempat yang sama dengan tujuannya. Karena alasan ini, loop do terus milih tempat baru waktu dia dapet yang sama dengan alamatnya.

Kita nyalain dunia virtual.

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

Robotnya butuh banyak giliran buat nganterin paket karena dia gak ngerencanain ke depan dengan baik. Kita bakal ngatasin itu segera.

Buat perspektif yang lebih menyenangkan soal simulasinya, kamu bisa pakai fungsi runRobotAnimation yang tersedia di environment pemrograman bab ini. Ini ngejalanin simulasinya, tapi bukannya ngeluarin teks, dia nunjukin robotnya bergerak di peta desa.

runRobotAnimation(VillageState.random(), randomRobot);

Cara runRobotAnimation diimplementasiin bakal tetap jadi misteri buat sekarang, tapi setelah kamu baca bab-bab selanjutnya dari buku ini, yang ngebahas integrasi JavaScript di browser web, kamu bakal bisa nebak cara kerjanya.

Rute Truk Pos

Kita harusnya bisa jauh lebih baik dari robot acak. Perbaikan gampang adalah ngambil petunjuk dari cara pengantaran surat di dunia nyata bekerja. Kalau kita nemuin rute yang ngelewatin semua tempat di desa, robotnya bisa ngejalanin rute itu dua kali, di titik mana dia dijamin selesai. Ini salah satu rute kaya gitu (mulai dari kantor pos):

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"
];

Buat ngimplementasiin robot pengikut rute, kita perlu memanfaatkan memori robot. Robotnya nyimpen sisa rutenya di memorinya dan ngebuang elemen pertama setiap giliran.

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

Robot ini udah jauh lebih cepat. Dia bakal butuh maksimal 26 giliran (dua kali rute 13 langkah) tapi biasanya kurang.

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

Pathfinding

Tetap aja, saya gak bakal beneran nyebut ngikutin rute tetap secara buta sebagai perilaku cerdas. Robotnya bisa kerja lebih efisien kalau dia nyesuaiin perilakunya ke kerjaan sebenarnya yang perlu dilakuin.

Buat itu, dia harus bisa dengan sengaja bergerak ke arah paket tertentu atau ke arah lokasi tempat paket harus dianterin. Ngelakuin itu, bahkan waktu tujuannya lebih dari satu langkah jauhnya, bakal butuh semacam fungsi pencari rute.

Masalah nemuin rute lewat graph adalah masalah pencarian yang tipikal. Kita bisa tahu apakah solusi tertentu (sebuah rute) valid, tapi kita gak bisa langsung ngitung solusinya kaya yang bisa kita lakuin buat 2 + 2. Sebagai gantinya, kita harus terus bikin solusi potensial sampai kita nemuin yang jalan.

Jumlah rute yang mungkin lewat graph itu tak terbatas. Tapi waktu nyari rute dari A ke B, kita cuma tertarik sama yang mulai di A. Kita juga gak peduli sama rute yang ngunjungin tempat yang sama dua kali, itu pasti bukan rute paling efisien ke mana pun. Jadi itu ngurangin jumlah rute yang harus dipertimbangkan pencari rutenya.

Sebenernya, karena kita paling tertarik sama rute terpendek, kita mau mastiin kita ngelihat rute pendek sebelum ngelihat yang lebih panjang. Pendekatan yang bagus adalah “numbuhin” rute dari titik awal, ngeksplorasi setiap tempat yang bisa dicapai yang belum dikunjungi sampai sebuah rute nyampe tujuan. Dengan cara itu, kita cuma bakal ngeksplorasi rute yang berpotensi menarik, dan kita tahu bahwa rute pertama yang kita temuin adalah rute terpendek (atau salah satu rute terpendek, kalau ada lebih dari satu).

Ini fungsi yang ngelakuin ini:

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

Eksplorasinya harus dilakuin dalam urutan yang benar, tempat-tempat yang dicapai duluan harus dieksplorasi duluan. Kita gak bisa langsung ngeksplorasi tempat begitu kita nyampe di sana karena itu berarti tempat-tempat yang dicapai dari sana juga bakal langsung dieksplorasi, dan seterusnya, walaupun mungkin ada jalur lain yang lebih pendek yang belum dieksplorasi.

Makanya, fungsinya nyimpen work list (daftar kerja). Ini array tempat yang harus dieksplorasi berikutnya, bareng rute yang bikin kita nyampe di sana. Dia mulai cuma dengan posisi awal dan rute kosong.

Pencariannya lalu beroperasi dengan ngambil item berikutnya di daftar dan ngeksplorasinya, yang berarti dia ngelihat semua jalan dari tempat itu. Kalau salah satunya adalah tujuannya, rute yang selesai bisa dikembaliin. Kalau gak, kalau kita belum ngelihat tempat ini sebelumnya, item baru ditambahin ke daftar. Kalau kita udah ngelihatnya sebelumnya, karena kita ngelihat rute pendek duluan, kita udah nemuin rute yang lebih panjang ke tempat itu atau yang persis sama panjangnya dengan yang udah ada, dan kita gak perlu ngeksplorasinya.

Kamu bisa ngebayangin ini sebagai jaring rute yang diketahui merayap keluar dari lokasi awal, tumbuh merata di semua sisi (tapi gak pernah kusut balik ke dirinya sendiri). Begitu benang pertama nyampe lokasi tujuan, benang itu ditelusuri balik ke awal, ngasih kita rute kita.

Kode kita gak nanganin situasi di mana gak ada item kerja lagi di daftar kerja karena kita tahu graph kita terhubung, artinya setiap lokasi bisa dicapai dari semua lokasi lain. Kita bakal selalu bisa nemuin rute antara dua titik, dan pencariannya gak bisa gagal.

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

Robot ini pakai nilai memorinya sebagai daftar arah buat bergerak, sama kaya robot pengikut rute. Setiap kali daftar itu kosong, dia harus nyari tahu harus ngapain berikutnya. Dia ngambil paket pertama yang belum dianterin di kumpulan dan, kalau paket itu belum diambil, ngerencanain rute ke arahnya. Kalau paketnya udah diambil, dia masih perlu dianterin, jadi robotnya bikin rute ke arah alamat pengantaran sebagai gantinya.

Kita lihat gimana hasilnya.

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

Robot ini biasanya nyelesaiin tugas nganterin 5 paket dalam sekitar 16 giliran. Itu sedikit lebih baik dari routeRobot tapi masih jelas gak optimal. Kita bakal terus menyempurnakannya di latihan.

Ringkasan

1. Jaringan jalan desa dimodelkan sebagai graph: objek map yang, buat tiap tempat, nyimpen array tempat yang terhubung.
2. Jangan refleks bikin class buat tiap “benda”. Keadaan dunia dipadatkan jadi minimal: posisi robot + daftar paket yang belum dianterin.
3. VillageState.move gak ngubah state lama, tapi ngitung dan ngembaliin state baru (data persistent). Ini bikin program lebih gampang dinalar.
4. Robot = fungsi (state, memory) => {direction, memory}. runRobot ngejalanin simulasinya sampai paket habis.
5. Tiga robot: randomRobot (asal jalan, ~63 giliran), routeRobot (ngikutin rute tetap, maks 26 giliran), goalOrientedRobot (pakai findRoute, ~16 giliran).
6. findRoute itu pencarian breadth-first pakai work list: eksplorasi tempat yang paling dekat dulu, jadi rute pertama yang ketemu pasti terpendek.

Latihan

Ngukur Robot

Susah buat ngebandingin robot secara objektif cuma dengan ngebiarin mereka nyelesaiin beberapa skenario. Mungkin satu robot kebetulan dapet tugas yang lebih gampang atau jenis tugas yang dia jago, sedangkan yang lain gak.

Tulis fungsi compareRobots yang ngambil dua robot (dan memori awal mereka). Dia harus ngehasilin 100 tugas dan ngebiarin kedua robot nyelesaiin setiap tugas ini. Waktu selesai, dia harus ngeluarin rata-rata jumlah langkah yang diambil setiap robot per tugas.

Demi keadilan, pastiin kamu ngasih setiap tugas ke kedua robot, bukannya ngehasilin tugas berbeda per robot.

function compareRobots(robot1, memory1, robot2, memory2) {
  // Kodemu di sini
}
 
compareRobots(routeRobot, [], goalOrientedRobot, []);

Petunjuk:

Kamu harus nulis varian dari fungsi runRobot yang, bukannya nge-log kejadiannya ke konsol, ngembaliin jumlah langkah yang diambil robot buat nyelesaiin tugasnya.

Fungsi pengukuranmu lalu bisa, di dalam loop, ngehasilin keadaan baru dan ngitung langkah yang diambil masing-masing robot. Waktu udah ngehasilin cukup pengukuran, dia bisa pakai console.log buat ngeluarin rata-rata buat setiap robot, yaitu total jumlah langkah yang diambil dibagi jumlah pengukuran.

Solusi:

function countSteps(state, robot, memory) {
  for (let steps = 0;; steps++) {
    if (state.parcels.length == 0) return steps;
    let action = robot(state, memory);
    state = state.move(action.direction);
    memory = action.memory;
  }
}
 
function compareRobots(robot1, memory1, robot2, memory2) {
  let total1 = 0, total2 = 0;
  for (let i = 0; i < 100; i++) {
    let state = VillageState.random();
    total1 += countSteps(state, robot1, memory1);
    total2 += countSteps(state, robot2, memory2);
  }
  console.log(`Robot 1 needed ${total1 / 100} steps per task`)
  console.log(`Robot 2 needed ${total2 / 100}`)
}
 
compareRobots(routeRobot, [], goalOrientedRobot, []);

Efisiensi Robot

Bisa kamu nulis robot yang nyelesaiin tugas pengantaran lebih cepat dari goalOrientedRobot? Kalau kamu ngamatin perilaku robot itu, hal bodoh apa yang jelas dia lakuin? Gimana itu bisa diperbaiki?

Kalau kamu nyelesaiin latihan sebelumnya, kamu mungkin mau pakai fungsi compareRobots-mu buat memverifikasi apakah kamu memperbaiki robotnya.

// Kodemu di sini
 
runRobotAnimation(VillageState.random(), yourRobot, memory);

Petunjuk:

Keterbatasan utama goalOrientedRobot adalah dia cuma mempertimbangkan satu paket dalam satu waktu. Dia sering bakal jalan bolak-balik melintasi desa karena paket yang kebetulan lagi dia lihat kebetulan ada di sisi lain peta, walaupun ada yang lain yang jauh lebih dekat.

Salah satu solusi yang mungkin adalah ngitung rute buat semua paket lalu ngambil yang terpendek. Hasil yang lebih baik lagi bisa didapet, kalau ada beberapa rute terpendek, dengan lebih milih yang pergi buat ngambil paket bukannya nganterin paket.

Solusi:

function lazyRobot({place, parcels}, route) {
  if (route.length == 0) {
    // Gambarkan rute buat setiap paket
    let routes = parcels.map(parcel => {
      if (parcel.place != place) {
        return {route: findRoute(roadGraph, place, parcel.place),
                pickUp: true};
      } else {
        return {route: findRoute(roadGraph, place, parcel.address),
                pickUp: false};
      }
    });
 
    // Ini nentuin prioritas yang didapet sebuah rute waktu milih.
    // Panjang rute dihitung negatif, rute yang ngambil paket
    // dapet bonus kecil.
    function score({route, pickUp}) {
      return (pickUp ? 0.5 : 0) - route.length;
    }
    route = routes.reduce((a, b) => score(a) > score(b) ? a : b).route;
  }
 
  return {direction: route[0], memory: route.slice(1)};
}
 
runRobotAnimation(VillageState.random(), lazyRobot, []);

Group Persistent

Kebanyakan struktur data yang disediain di environment JavaScript standar gak terlalu cocok buat penggunaan persistent. Array punya method slice dan concat, yang ngebolehin kita dengan gampang bikin array baru tanpa ngerusak yang lama. Tapi Set, misalnya, gak punya method buat bikin set baru dengan item ditambahin atau dihapus.

Tulis class baru PGroup, mirip class Group dari Bab 6, yang nyimpen sekumpulan nilai. Kaya Group, dia punya method add, delete, dan has. Tapi method add-nya harus ngembaliin instance PGroup baru dengan anggota yang dikasih ditambahin dan ngebiarin yang lama gak berubah. Sama juga, delete harus bikin instance baru tanpa anggota yang dikasih.

Class-nya harus jalan buat nilai tipe apa pun, gak cuma string. Dia gak harus efisien waktu dipakai dengan jumlah nilai yang besar.

Constructor-nya gak boleh jadi bagian dari interface class (walaupun kamu pasti mau pakainya secara internal). Sebagai gantinya, ada instance kosong, PGroup.empty, yang bisa dipakai sebagai nilai awal.

Kenapa kamu cuma butuh satu nilai PGroup.empty bukannya punya fungsi yang bikin map kosong baru setiap kali?

class PGroup {
  // Kodemu di sini
}
 
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

Petunjuk:

Cara paling praktis buat mewakili kumpulan nilai anggota masih sebagai array, karena array gampang disalin.

Waktu nilai ditambahin ke group, kamu bisa bikin group baru dengan salinan array asli yang udah ditambahin nilainya (misalnya, pakai concat). Waktu nilai dihapus, kamu filter dia dari array-nya.

Constructor class-nya bisa ngambil array kaya gitu sebagai argumennya dan nyimpennya sebagai (satu-satunya) properti instance. Array ini gak pernah diupdate.

Buat nambahin properti empty ke constructor, kamu bisa mendeklarasikannya sebagai properti static.

Kamu cuma butuh satu instance empty karena semua group kosong itu sama dan instance class-nya gak berubah. Kamu bisa bikin banyak group berbeda dari satu group kosong itu tanpa ngaruh ke dia.

Solusi:

class PGroup {
  #members;
  constructor(members) {
    this.#members = members;
  }
 
  add(value) {
    if (this.has(value)) return this;
    return new PGroup(this.#members.concat([value]));
  }
 
  delete(value) {
    if (!this.has(value)) return this;
    return new PGroup(this.#members.filter(m => m !== value));
  }
 
  has(value) {
    return this.#members.includes(value);
  }
 
  static empty = new 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