flowchart

Belajar dasar Algoritma dengan Flowchart

Jika diminta mengajar pemrograman dasar, langkah pertama yang saya ajarkan bukanlah mulai langsung membuat program di depan komputer, melainkan mulai dengan pembiasaan menyusun suatu algoritma. Menurut saya pribadi, pembiasaan menyusun algoritma ini penting untuk mengenalkan proses Computational Thinking ke calon-calon programmer. Dan proses penyusunan algoritma bisa dilakukan menggunakan flowchart tanpa harus mengerti program komputer.

Apa itu Algoritma?

Algoritma itu mirip resep masakan. Apa isi dari resep masakan? isinya menceritakan langkah per langkah suatu proses se-spesifik mungkin sehingga suatu bahan masakan menjadi masakan jadi. Perlu digaris bawahi bagian “se-spesifik mungkin”. Tidak mungkin di resep hanya tertulis “masukkan telur”, karena bisa memunculkan pertanyaan: telur ayam atau bebek? berapa buah? putihnya atau kuningnya?

algoritma nasi goreng

Dalam dunia pemrograman, dari analogi di atas bisa diartikan bahwa algoritma adalah sekumpulan perintah (resep) yang digunakan untuk memproses input (bahan masakan) menjadi output yang sesuai harapan (masakan). BTW, bicara tentang algoritma selalu mengingatkan saya dengan video seru ini 🙂

Continue reading
A* algorithm for puzzle

A* Algorithm in Python to solve 8 puzzle problem

My team got this as A* algorithm assignment in Artificial Intelligence class few years ago taught by Mrs. Afiahayati, Ph.D. We should create an implementation of A* algorithm (read: “A” Star) to solve 8 puzzle problem. This puzzle problem is the small version of 15 sliding puzzle game.

A* Algorithm

In my opinion A* Algorithm (read more about it here) is looks like combination of Breadth First Search (BFS) and Depth First Search (DFS) algorithm (or maybe Dijkstra’s too(?)). It’s using Heuristic scoring to estimate the step from vertex to goal so make the system may running faster, and like Dijkstra’s, it’s a complete search which always finding a best solution. Read this to get better explanation.

My team agreed to use Manhattan distance to estimate distance between the current state and the goal state (h) and count the number of step as exact cost (g).

Implementation

I wrote the code using Python. And after several hours coding I found python have a “magical” function that make easy to write 🙂 My first implementation was not using any class at all and it made the code hard to read. After I saw this implementation, I realize that code is much prettier than mine, so I rewrite my code using Node class with similar class concept from that code.

See the complete source code on Github