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
backpropagation step by step

Contoh Perhitungan Algoritma Backpropagation

Beberapa waktu lalu saya dapat kesempatan untuk mengasisteni kegiatan kemkominfo di UGM seputar AI. Salah satu topik yang dibicarakan adalah Backpropagation pada Jaringan Saraf Tiruan (JST). Di postingan ini saya akan mencontohkan perhitungan Backpropagation langkah per langkah, menggunakan arsitektur yang sederhana dan dilanjutkan implementasi menggunakan Python.

Artikel ini diupdate pada 8 Agustus 2020

Sebelum memulai, sebaiknya kita mengerti terlebih dahulu dasar-dasar untuk:

Jika masih dirasa banyak yang lupa, silakan refresh kembali materi tersebut.

Overview

model / arsitektur JST sederhana

Sebelum kita mulai, kita ingat kembali beberapa poin penting dalam JST pada ilustrasi di atas.

Continue reading

Implementasi Greedy -Codeforces 1131B

CONTEST

Soal berjudul Draw! iniĀ merupakan bagian dari contestĀ  Codeforces Round #541 (Div 2). Pembahasan pada post kali ini dibuat menurut pemahaman penulis, sedangkan pembahasan official dari tim pembuat soal bisa dicek diĀ  Official Editorial Codeforces. Soal ini termasuk dalam jenis soal implementasi greedy dengan solusi berfokus pada cara implementasi untuk mencari solusi jawaban. Meskipun berkode B, yang biasanya merupakan soal mudah pada contest Codeforces, namun soal ini cukup menantang.

SOAL

Diketahui dalam sebuah pertandingan sepak bola, panitia mencatatkan informasi skor kedua tim sebanyak beberapa kali, sesuai waktu yang telah ditentukan (momen). Informasi tersebut dicatat sebanyak $n$ kali dengan penulisan berpasangan $(a_i,b_i)$. Ini menunjukkan bahwa pada saat tertentu dalam pertandingan, skornya adalah $a_i : b_i$. Jika diketahui skor sekarang adalah $(x : y)$, maka apabila sebuah gol terjadi, skor di papan saat itu berubah menjadi $x+1 : y$ atau $x : y+1$.

Berapakah banyak kemungkinan skor seri terjadi selama pertandingan tersebut berlangsung?

Input

Baris input pertama terdiri dari sebuah integer $n$ $(1 \leq n \leq 10000)$Ā  ā€” banyaknya pencatatan yang dilakukan panitia (banyak momen).

Setiap baris dari total $n$ baris berikutnya terdiri dari integer $a_i$ dan $b_i$Ā  $(0 \leq a_i,b_i \leq 109)$, yang menyatakan skor pertandingan pada momen tersebut (jumlah gol dari tim pertama dan gol dari tim kedua).

Semua momen diinputkan secara terurut, sehingga sekuens $x_i$ dan $y_j$ non-decreasing. Skor terakhir yang tercatat merupakan skor final dari pertandingan tersebut.

Output

Print banyak kemungkinan skor seri terjadi selama pertandingan tersebut berlangsung. Skor $(0:0)$ pada awal pertandingan juga dihitung seri.

Contoh dan pembahasan

Contoh Pertama
input $n$ dan skor tiap momen:

3
2 0
3 1
3 4

output banyak skor seri:

2

Pada momen ke-1 skor tim $a$ adalah 2 dan skor tim $b$ adalah 0. Pada momen tersebut jika dijabarkan semua skor yang mungkin terjadi sebelum pencatatan adalah $\{(0,0),(1,0),(2,0)\}$, sehingga skor seri yang pernah terjadi adalah $(0,0)$. Pada momen ke-2 skor berubah untuk tim $a$ menjadi $3$ dan tim $b$ skor menjadi $1$. Pada momen ini, skor yang mungkin terjadi adalah $\{(2,1),(3,1)\}$ dimana tim $b$ mencetak gol lebih dulu atau sebaliknya tim $a$ duluan yang mencetak gol dengan skor $\{(3,0),(3,1)\}$. Dari kedua opsi tersebut diketahui bahwa tidak ada skor seri yang mungkin terjadi. Terakhir, momen ke-3 terjadi penambahan gol untuk tim $b$ secara berturut-turut yang dibuktikan dengan tidak bertambahnya skor tim $a$ dari momen terakhir pencatatan. Maka dari itu skor yang terjadi sebelum pencatatan pada momen ini adalah $\{(3,2),(3,3),(3,4)\}$ dimana terjadi skor seri yakni $(3,3)$.

Total dari 3 momen pencatatan tersebut ada sebanyak 2 kali skor seri, seperti yang terlihat di tabel berikut.

$$
\begin{array}{c|lcr}
i& x_i & y_i & \text{kemungkinan skor seri} \\
\hline
1 & 2 & 0 & \{(0,0)\} \\
2 & 3 & 1 & \{ \} \\
3 & 3 & 4 & \{(3,3)\}
\end{array}
$$

Contoh Kedua
input $n$ dan skor tiap momen:

3
0 0
0 0
0 0

output banyak skor seri:

1

Pada contoh ini, skor kedua tim tidak berubah/bertambah dari awal momen sampai akhir. Maka skor seri yang memungkinkan hanya 1 kali, yakni $(0,0)$ itu sendiri.

$$
\begin{array}{c|lcr}
i& x_i & y_i & \text{kemungkinan skor seri} \\
\hline
1 & 0 & 0 & \{(0,0)\} \\
2 & 0 & 0 & \{\text{ } \} \\
3 & 0 & 0 & \{\text{ } \}
\end{array}
$$

Contoh Ketiga
input $n$ dan skor tiap momen:

1
5 4

output banyak skor seri:

5

Pada contoh ini hanya terjadi satu kali momen pencatatan dengan skor $(5,4)$. Dengan melihat minimal skor di antara kedua tim kita dapat menentukan bahwa skor seri yang mungkin terjadi adalah semua skor yang dimulai dari $0$ sampai dengan skor minimal di momen tersebut $\min{(5,4)} = 4$, sehingga ada sebanyak 5 kali skor seri seperti pada tabel di bawah ini.

$$
\begin{array}{c|lcr}
i& x_i & y_i & \text{kemungkinan skor seri} \\
\hline
1 & 5 & 4 & \{(0,0),(1,1),(2,2),(3,3),(4,4)\}
\end{array}
$$

Pembahasan

Cara menghitung banyaknya skor seri dalam suatu pertandingan dapat disederhanakan dengan mencari kemungkinan skor seri di setiap momen pencatatan. Di setiap momen pencatatan, hal yang perlu diperhatikan adalah minimal skor pada momen saat ini yakni $\min{(x_i,y_i)}$ dan maksimal skor pada momen sebelumnya yakni $\max{(x_{i-1},y_{i-1})}$. Nilai yang menjadi patokan tiap momen adalah nilai $\min{(x_i,y_i}) – \max{(x_{i-1},y_{i-1})}$ yang pada langkah-langkah di bawah ini kemudian ditulis dengan $s$. Nilai $s$ ini merupakan banyaknya skor seri yang mungkin pada tiap momen.

n = int(input())
T = 0
minSkorLast = 0
maxSkorLast = 0
for moment in range(n):
    skor = [int(item) for item in input().split(" ")]
    minSkor = min(skor[0],skor[1])
    maxSkor = max(skor[0],skor[1])
    s = minSkor-maxSkorLast+1
    if s > 0:
        if maxSkorLast != minSkorLast:
            T = T + s
        else:
            T = T + s - 1
    minSkorLast = minSkor
    maxSkorLast = maxSkor
print(T+1)

Pertama, kita akan menyimpan total banyaknya skor seri pada suatu variabel $T$ tentunya di awal inisialisasi dengan 0 (baris 2 kode python).

Perlu diingat bahwa permulaan pertandingan skor $(0,0)$ merupakan seri sehingga inisialnya kita sudah menyimpan 1 nilai seri. Untuk mempermudah, asumsi bahwa skor yang tercatat pada momen $(i-1)$ adalah seri diterapkan di perhitungan tiap momen, ditunjukkan dengan penambahan nilai $s$ dengan $1$ di awal perhitungan tiap momen (baris 9 kode python).

Kedua, jika $s$ adalah positif, maka ada perubahan skor pada momen $(i)$ sekarang dibanding dari momen $(i-1)$ sebelumnya, yang memungkinkan adanya skor seri di momen $i$ ini (baris 10 kode python).

Ketiga, jika skor yang dicatat pada momen $(i-1)$ sebelumnya merupakan skor seri, maka pada momen sekarang $(i)$ tidak perlu dihitung ulang. Sehingga penyimpanan skor seri dikurangi, yakni dengan mengkurangkan nilai $s$ dengan $1$ (baris 14 kode python). Selain itu, maka total banyaknya skor seri $T$ ditambahkan dengan nilai $s$ pada momen $(i)$ ini (baris 12 kode python). Proses ini diulangi sampai sejumlah momen pencatatan pada input atau sejumlah $n$.

Geometri – Codeforces 1100C

CONTEST

Soal berjudul NN and the Optical Illusion iniĀ merupakan bagian dari contestĀ  Codeforces Round #532 (Div 2). Pembahasan pada post kali ini dibuat menurut pemahaman penulis, sedangkan pembahasan official dari tim pembuat soal bisa dicek diĀ  Official Editorial Codeforces.

Soal ini di Codeforces termasuk ke dalam tag jenis soal geometri dan binary search. Soal ini berkode C yang berarti memiliki tingkat kesulitan yang cukup mudah sampai sedang. Pada artikel ini, penulis mencoba melihat dengan pendekatan geometri dan menggunakan rumus trigonometri untuk memecahkan problem.Ā 


Perbandingan penyusunan lingkaran menghasilkan optical illusion
RINGKASAN SOAL

NN berselancar di media sosial dan selalu melihat suatu gambar yang terdiri dari sebuah lingkaran di tengah (inner circle) dan sejumlah $n$ lingkaran di luar (outer circle). Semua outer circle berukuran sama dengan jari-jari $R$ dan bersinggungan dengan inner circle yang memiliki jari-jari $r$. Gambar di atas merupakan contoh dua buah gambar yang pernah dilihat NN.

Bantu NN untuk menghitung jari-jari outer circle $R$, jika diketahui jari-jari inner circle $r$ dan jumlah outer circle $n$.

Input

Terdiri dari satu baris dengan dua angka terpisahkan oleh spasi. Masing-masing secara berurutan adalah nilai $n$ dan $r$ dimana $(3 \leq n \leq 100, 1 \leq n \leq 100)$, yakni jumlah outer circle dan jari-jari inner circle.

Output

Terdiri dari sebuah nilai $R$ ā€” jari-jari outer circle yang dibutuhkan untuk membentuk gambar (agar semua outer circle) bersinggungan dengan inner circle. Jawaban diterima jika nilai error absolutnya tidak melebihi 10-6

Jika jawaban NN adalah $a$, dan jawaban juri adalah $b$, maka jawaban NN diterima jika dan hanya jika $\frac{\quad \lvert a-b\rvert \quad}{\max{(a, \lvert b\rvert)}} \le 10^{-6}$

Contoh dan pembahasan

input $n$ dan $r$:

3 1

output $R$:

6.4641016

Input di atas dapat diilustrasikan pada gambar di bawah ini. Setiap titik pusat dari outer circle jika dihubungkan dapat membentuk segi-$n$ sama sisi. Dikarenakan $n$ pada contoh ini adalah 3, maka yang terbentuk adalah segi tiga sama sisi $ABC$, di mana sisinya merupakan dua kali panjang jari-jari outer circle yakni sebesar $2R$. Kemudian, dari segitiga sama sisi tersebut dapat digambar lagi sebuah segitiga sama kaki $BCD$ (warna biru) untuk mencari nilai $R$.

Dari segitiga sama kaki $BCD$ di atas dapat dicari nilai $R$ dengan menerapkan salah satu rumus trigonometri:

Rumus trigonometri:
$\sin{\angle\text{BDt}} = \frac{\text{Bt}} {\text{BD}}$

Rumus mencari R:
$\sin{\angle\text{BDt}} = \frac{\text{R}} {\text{R+r}}$
$(\text{R}*\sin{\angle\text{BDt}}) + (\text{r}*\sin{\angle\text{BDt}}) = \text{R}$
$\text{R}*(\sin{\angle\text{BDt}} – 1) = -\text{r}*\sin{\angle\text{BDt}}$
$\text{R} = \frac{-\text{r} \; * \; \sin{\angle\text{BDt}}} {\sin{\angle\text{BDt}} \;- \;\text{1}}$
$\text{atau}$
$\text{R} = \frac{\text{r} \; * \; \sin{\angle\text{BDt}}} {\text{1} \;- \;\sin{\angle\text{BDt}}}$

Besar $\angle \text{BDC}$ diperoleh dari hasil bagi sudut lingkaran yakni $\text{360}^\circ$ dengan jumlah outer circle yakni $n$. Setelah diketahui besaran sudut, maka dengan menggunakan rumus di atas dapat dihitung nilai $R$. 

Nilai R:
$\angle \text{BDC} = \frac{360^\circ}{ \text{n}}$
$\angle \text{BDt} = \frac{\angle \text{BDC}}{\text{2}}$
$\angle \text{BDt} = \frac{120^\circ} {\text{2}} = 60^\circ$ 

$\text{R} = \frac{\text{1} \; * \; \sin{\text{60}^\circ}} {\text{1} \;- \;\sin{\text{60}^\circ}}$
$\text{R} = \frac{0.8660254}{0.1339745}$
$\text{R} = \text{6.46410161514}$
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