Tugas 2 Praktikum Struktur Data: Stack dan Queue

Assignment 2: Stack and Queue

Online dari Rumah

Kembali ke Struktur Data

Tugas ini diberikan pada hari dan tanggal: Selasa, 10 Desember 2024

Petunjuk Umum:

1. Kerjakan secara individu.

2. Kerjakan tugas ini menggunakan bahasa pemrograman Python dengan file format berupa interactive Python notebook (yaitu file berbentuk .ipynb BUKAN .py), yang bisa dibuat misalnya menggunakan Jupyter Notebook atau Google Colaboratory.

3. Harap sertakan penjelasan untuk setiap variabel yang digunakan dan setiap proses secara singkat di sebelah (atas/bawah/kanan) barisnya (dengan comment, #). Selain itu, sertakan juga penjelasan kode (yang bisa mencakupi idenya apa, bagaimana cara eksekusinya, atau tentang algoritma yang digunakan) pada cell di sebelah (atas/bawah) kode.

4. Format nama file untuk Tugas 2 ini adalah:

   Kelas SIAK_Tugas2PrakStrukdat_Nama Lengkap_NPM.ipynb

   Contoh penamaan yang benar:

   Kelas C_Tugas2PrakStrukdat_Haikal Fikri Rabani_2206823713.ipynb

5. Pengumpulan Tugas 2 dilakukan ke Google Forms berikut ini:

   https://bit.ly/KumpulTugas1PrakStrukdat2024Ganjil

6. Apabila ada yang ingin direvisi setelah pengumpulan, lakukan pengumpulan ulang di Google Forms yang sama, tambahkan keterangan bahwa ada revisi, dan tambahkan kata “revisi” pada bagian akhir nama file, contohnya menjadi

   Kelas C_Tugas2PrakStrukdat_Haikal Fikri Rabani_2206823713_revisi.ipynb

   Kelas C_Tugas2PrakStrukdat_Haikal Fikri Rabani_2206823713_revisi2.ipynb

   Kelas C_Tugas2PrakStrukdat_Haikal Fikri Rabani_2206823713_revisi3.ipynb

   (Revisi boleh dilakukan berkali-kali.)

7. Dengan durasi pengerjaan sekitar 2 (dua) minggu, tenggat waktu (deadline) pengumpulan Tugas 2 ini (termasuk revisi) adalah Selasa, 24 Desember 2024, 23.59 WIB.

8. Sesuai standar Universitas Indonesia, plagiarisme dilarang keras dan bisa menyebabkan nilai tugas praktikum menjadi nol untuk semua pihak yang terlibat, tanpa peringatan apapun. Namun, Anda boleh langsung menggunakan kode yang ada di modul praktikum.

9. Module atau package Python yang boleh digunakan (di-import) untuk Tugas 1 ini hanyalah numpy dan graphviz. Apabila Anda berniat ingin menggunakan module lain, harap konfirmasikan ke narahubung terlebih dahulu (bisa saja diperbolehkan).

10. Narahubung untuk Tugas 2 Praktikum Struktur Data adalah:

    Muhammad Fasya Syaifullah (ID LINE: ifasyai)

    Silakan hubungi narahubung di atas apabila ada yang ingin ditanyakan atau dikonfirmasikan.

[50] Soal 1

Di galaksi jauh yang dikenal sebagai Nebula Arkana, umat manusia telah hidup damai selama ribuan tahun, hingga muncul ancaman tak terduga. Ancaman tersebut berasal dari planet baru yang jaraknya 100 tahun cahaya dari Nebula Arkana yang bernama Evangel. Evangel memiliki kekuatan untuk menggerakkan asteroid di sekitar galaksi dan mengirimkannya ke Nebula Arkana dari jarak jauh.

Malam itu, di atas pangkalan luar angkasa Orion Zenith, seorang ilmuwan muda bernama Kaoru memantau pergerakan asteroid ini melalui radar holografis canggih. Ia menyadari bahwa asteroid-asteroid tersebut akan bertabrakan dalam waktu dekat pada kecepatan yang sama. Kaoru menyebutnya sebagai fenomena “Ginga no tatakai” atau “Pertarungan Galaksi”, di mana untungnya, hanya asteroid terkuat yang akan bertahan. Artinya tidak semua asteroid yang dikirim akan langsung mengenai Nebula Arkana. Berikut adalah rincian yang Kaoru kalkulasikan:

1. Jika asteroid bergerak ke arah yang sama, mereka takkan pernah bertabrakan, seperti bintang-bintang yang harmonis di orbit mereka.

2. Jika mereka bergerak berlawanan arah, maka yang lebih besar akan menghancurkan yang lebih kecil, seperti predator yang memangsa mangsanya.

3. Jika mereka memiliki ukuran yang sama dari arah yang berbeda, energi destruktif mereka akan meledak bersamaan, menghapus keduanya dari eksistensi.

4. Untuk setiap asteroid, suatu harga mutlak bilangan bulat merepresentasikan ukuran asteroid. Tanda positif mengartikan bahwa arah asteroid dari kanan serta negatif arah dari kiri. Tidak ada asteroid berukuran nol.

Buatlah algoritma struktur data yang menerima array atau list asteroid untuk mencari tahu kemungkinan asteroid mana saja yang menabrak bumi!

Berikut contoh input, output yang diinginkan.’

- Contoh 1

>>> collisions([1, 3, -2])
[1, 3]

Penjelasan 1:

Bandingkan 1 dengan 3, maka tidak ada yang hancur.

Bandingkan 3 dengan -2, maka -2 hancur.

- Contoh 2

>>> collisions([1, -1, -2, 2])
[]

Penjelasan 2:

Bandingkan 1 dengan -1, keduanya hancur.

Bandingkan -2 dengan 2, maka keduanya hancur.

- Contoh 3

>>> collisions([5, 10, -15, 2])
[-15]

Penjelasan 3:

Bandingkan 5 dengan 10, maka tidak ada yang hancur.

Bandingkan 10 dengan -15, maka 10 hancur.

Bandingkan 5 dengan -15, maka 5 hancur.

Bandingkan -15 dengan 2, maka 2 hancur.

[50] Soal 2

Event komik merupakan event yang sangat ditunggu-tunggu oleh pecinta komik dan buku. Salah satu event yang sangat besar di Jakarta yaitu Comifuro. Tiket dapat dibeli secara online dan onsite.

Pandu, seorang pecinta komik dan game, ingin mengikuti event tersebut bersama teman-temannya. Sayangnya tiket yang dijual secara online sudah habis terjual. Karena padatnya jadwal kuliah, Pandu tidak ingin mengantri secara langsung. Oleh karena itu, dia mempercayai temannya Fasya untuk mengantri dan membelikannya tiket.

Fasya menyetujuinya dengan syarat setiap detik Fasya mengantri, Pandu harus membayarnya sebesar 1000 rupiah. Hal ini karena Fasya juga membeli banyak tiket.

Antrian tersebut memiliki aturan:

1. Setiap orang hanya dapat membeli satu tiket. Jika orang tersebut ingin membeli tiket lagi, maka Ia harus mengantri lagi ke belakang antrian (asumsikan perpindahan ini instan).

2. Waktu seseorang untuk membeli tiket adalah tepat 1 detik.

3. Jika seseorang sudah selesai membeli tiketnya, maka orang tersebut akan keluar antrian dan bertemu dengan teman-temannya.

Misal terdapat \(n\) orang dalam suatu antrian, \(k\) (indeks-0) menandakan posisi Fasya pada antrian tersebut. Buatlah algoritma struktur data yang menerima input array berukuran \(n\) dan posisi Fasya \(k\) untuk menentukan waktu yang dibutuhkan Fasya untuk membeli semua tiketnya!

Berikut contoh input, output yang diinginkan.’

Contoh

>>> comifuro(tiket = [2, 3, 2], k = 2)
6

Penjelasan:

• Antrian dimulai dengan [2, 3, 2] di mana indeks k = 2 adalah posisi Fasya dalam antrian (ditandakan dengan cetak tebal).

• Setelah orang pertama membeli tiket antrian menjadi: [3, 2, 1] dalam satu detik.

• Lanjut, antrian menjadi: [2, 1, 2] dalam 2 detik.

• Lanjut, antrian menjadi: [1, 2, 1] dalam 3 detik.

• Lanjut, antrian menjadi: [1, 1] dalam 4 detik.

• Lanjut, antrian menjadi: [1] dalam 5 detik.

• Terakhir, Fasya keluar antrian dalam 6 detik. Output 6 antrian.