Best Praktis Basic Golang -Part 1

Belajar Dasar Golang dengan Algoritma (Euler Project)

Published in

The Legend

9 min readJan 24, 2021

Saya berfikir apa yang bisa kita gunakan untuk mempelajari dasar-dasar pemograman golang dengan lebih cepat dengan hanya menyelesaikan beberapa soal. Dari sekian banyak pilihan, jatuh ke soal-soal penyelesaian dari problem-problem ilmu matematika yang merupakan ilmu yang mendasari ilmu komputer, khususnya pada algoritma pemograman.

Setelah beberapa kali mencari informasi akhirnya bertemu dengan sebuah situs bernama Project Euler. Apakah itu euler project? Apa kegunaan nya? Sesuai namanya, Euler adalah seorang ahli matematika dan fisika asal Swiss. Saya yakin pada euler project ini banyak soal-soal terkait algoritma yang bisa kita selesaikan untuk membantu memahami penggunaan bahasa pemograman golang atau bahasa-bahasa pemograman lainnya.

Project Euler adalah project serangkaian masalah matematika atau pemrograman komputer yang menantang yang akan membutuhkan penyelesaian lebih dari sekadar wawasan matematika untuk dipecahkan. Meskipun matematika akan membantu Anda mencapai metode yang elegan dan efisien, penggunaan komputer dan keterampilan pemrograman akan dibutuhkan untuk menyelesaikan sebagian besar masalah.

Motivasi untuk memulai proyek euler dan kelanjutannya adalah untuk menyediakan platform bagi pikiran yang ingin tahu untuk mempelajari area asing dan mempelajari konsep baru dalam konteks yang menyenangkan dan rekreasional.

*“Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics.”*

Disclaimer

Solusi-solusi yang dibuat bukanlah solusi algoritma paling bagus akan tetapi lebih ke solusi dengan algoritma yang umum digunakan walaupun bukan algoritma terjelek dalam deretan solusi berdasarkan Big O Notation.

Soal Pertama, Kelipatan 3 dan 5

Berikut adalah salah satu soal dalam euler project tetapnya soal pertama. Kita akan mencoba menyelesaikannya dengan Golang.

Jika kita mendaftar semua bilangan asli di bawah 10 yang merupakan kelipatan dari 3 atau 5, kita mendapatkan 3, 5, 6 dan 9. Jumlah dari kelipatan ini adalah 23.
Temukan jumlah dari semua kelipatan 3 atau 5 di bawah 1000.

Soal ini dapat di lihat pada link berikut dan jika kita telusuri sepertinya ini adalah permasalahan dari permainan Fizz dan Buzz.

fizz_buzz.go

Kode di atas cukup sederhana kita cuma melibatkan pengulangan, logika if , dan sisa bagi. Satu yang mungkin agak aneh adalah penggunakan tanda baca (_)pada penulisan angka seribu. Ini digunakan untuk memudahkan pembacaan. Lebih detil mengenai hal ini dapat di baca di link berikut.

Selanjutnya adalah penggunakan penugasan sumOf5 += i setara dengan sumOf5 = sumOf5+i.

Apabila code di atas kita eksekusi, menghasilkan output seperti berikut.

...
Data perelement adalah : 994
Data perelement adalah : Buzz
Data perelement adalah : Fizz
Data perelement adalah : 997
Data perelement adalah : 998
Data perelement adalah : Fizz
Jumlah data merupakan kelipatan 3 adalah : 133668
Jumlah data merupakan kelipatan 5  adalah : 99500
Jumlah Total kelipatan 3 dan 5 : 233168
Waktu eksekusi  2869000 nano second

Soal Kedua, Bilangan Fibonacci

Berikut adalah persoalan kedua pada euler project. Kita akan mencoba menyelesaikannya dengan Golang .

Setiap suku baru dalam deret Fibonacci dihasilkan dengan menjumlahkan dua suku sebelumnya. Dengan memulai dengan 1 dan 2, 10 suku pertama adalah:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Dengan mempertimbangkan suku-suku dalam deret Fibonacci yang nilainya tidak melebihi empat juta, temukan jumlah suku-suku yang bernilai genap.

Terdapat solusi deret fibonacci ini yang sangat beragam, mulai dari yang termudah sampai yang paling susah. Pembahasan yang lebih dalam mengenai deret finobanacci ini dapat dibaca pada artikel berikut.

Cara termudah untuk menghasilkan deret fibonacci adalah sebagai berikut.

func main() {
   firstNumber := 0
   secondNumber := 1
   for i := 0; i < 10; i++ {
      fib := firstNumber
      firstNumber = secondNumber
      secondNumber = firstNumber+fib
      fmt.Println(fib)
   }
}

Untuk dapat menjumlahkan semua deret angka fibonacci yang bernilai genap dan kurang dari 4 juta adalah seperti berikut.

fibonacci_number.go

Apabila code di atas kita eksekusi menghasilkan output seperti berikut.

Bilangannya Ganjil dari FIB : 514229
Bilangannya Genap dari FIB : 832040
Bilangannya Ganjil dari FIB : 1346269
Bilangannya Ganjil dari FIB : 2178309
Bilangannya Genap dari FIB : 3524578
==========================================
Jumlah dari bilangan ganjil : [4613732]
Jumlah dari bilangan genap : [4613732]
Waktu eksekusi  151000 nano second

Penjelasan code di atas hampir sama dengan pembahasan code sebelumnya kita menggunakan pengulangan, logika if, dan sisa bagi tetapi kita gunakan const untuk memberikan perbedaan antara variable dan konstanta.

Kedua kita gunakan loop dengan pendekatan berbeda dari sebelumnya. Pengulangan akan berjalan terus menerus sampai batas angkat mendekati 4 juta. Teknik loop ini lebih dikenal sebagai while loop.

Ada yang menarik dari waktu eksekusi yang diperlukan untuk Soal 1 dan Soal 2. Apabila jumlah pengulang sama, misalkan sampai 1000 maka lama ekseskusi untuk Soal 1 rata-rata adalah 3820000 nano sekon dan waktu eksesui untuk Soal 2 adalah rata-rata sekitar 81000 nano sekon. Apabila Soal 1 logic if terakhir dihilangkan maka waktu rata-rata sekitar 1392000 nano sekon. Di sini terlihat bahwa cost dari logic if itu lumayan sangat significan walau dalam ukuran nano sekon akan tetapi bagi sebuah proses dalam CPU waktu selama itu lumayan sangat berasa.

Dari sini dapat diambil kesimpulan logic if itu harus di gunakan sebijak mungkin dalam membuat logical pemograman karena memberikan dampak besar bagi performance.

Soal Ketiga, Faktorisasi Prima Terbesar

Berikut adalah soal ketiga dalam project euler.

Faktor prima dari 13195 adalah 5, 7, 13 dan 29. Berapakah faktor prima terbesar dari bilangan 600851475143?

Algoritma yang umum digunakan unutk membahas mengenai faktorisasi prima adalah Trial Devision atau dapat difahami sebagai mencoba-coba dengan pembagian.

Biasanya pembagian dicoba dengan angka prima terkecil yaitu angka 2 sampai sisa baginya habis atau nol. Apabila dengan angka 2 tidak bisa maka akan mencoba dengan angka prima diatasnya yaitu 3 dan begitu seterusnya,

Pertama kita coba dahulu solusi untuk mengeluarkan semua faktorisasi prima .

package mainimport (
    "fmt"
    "math"
)func printPrimes(n int) {
   for i := 2; i <= int(math.Sqrt(float64(n))); i++ {
      if n%i == 0 {
         fmt.Println(i)
         n /= i
         i--
      }
   }
   if n > 0 {
      fmt.Println(n)
   }
}func main() {
   before := time.Now()
   n := 13195
   printPrimes(n)
   after := time.Now()
   fmt.Println("Waktu eksekusi ", after.Nanosecond()-before.Nanosecond(), "nano second")
}

Apabila kita eksekusi kode di atas maka output nya adalah sebagai berikut.

5
7
13
29
Waktu eksekusi 33000 nano second

Pada solusi di atas kita melakukan pengulangan untuk melakukan pengecekan hasil bagi dari angka yang akan ditentukan faktorisasi primanya. Mungkin ada pertanyaan kenapa batas atas dari loop yang dilakukan adalah hasil akar kuadrat dari angka yang di hitung (math.Sqrt(float64(n)) bukan angkanya sendiri atau nilai tengah antara 2 dan angka yang dihitung?

Berdasarkan Fermat’s Factorization Method menyatakan bahwa faktorisasi dari suatu bilangan akan memiliki nilai terdekat dengan akar kuadrat dari angka tersbut.

Pada kondisi tertentu Fermat methode ini kadang lebih buruk daripada algoritma coba-coba. Akan tetapi, penggabungan antara algoritma coba coba dan algoritma fermat akan memberikan solusi terbaik. Penggabungan dua algoritma ini adalah yang kita gunakan di atas.

Terdapat sebuah algoritma lain yang cukup terkenal dan memberikan waktu eksekuysi tersingkat untuk mengetahui faktorisasi prima adalah Quadratic Sieve. Jika penasaran Anda dapat mencoba mempelajarinya dan membuat kodenya juga 😐.

Selanjutnya untuk mengetahui nilai terbesar dari faktorisasi prima kita dapat memperbaiki code diatas menjadi sebagai berikut.

func primeFactors(n int) []int {
   factors := make([]int, 0)
   for i := 2; i <= int(math.Sqrt(float64(n))); i++ {
      if n%i == 0 {
         factors = append(factors, i)
         n /= i
         i--
      }
   }
   if n > 0 {
      factors = append(factors, n)
   }
   return factors
}

Kode diatas hampir sama dengan kode sebelumnya, cuma data faktorisasi kita simpan ke dalam array of integer. factors := make([]int, 0) untuk membuat dan inisialisasi arrray 1 dimensi dengan type data int. Data akan dimasukan lewat perintah factors = append(factors, i).

Untuk mencari nilai terbesar kita buat code seperti berikut.

func largest(factors []int) int {
   max := factors[0]
   for _, factor := range factors {
      if factor > max {
         max = factor
      }
   }
   return max
}

Kode diatas mencari nilai terbesar dari data berupa array menggunakan pengulangan for each. seperti berikut.

for _, factor := range factors

Hal ini mengandung arti kita akan melakukan pengulangan sebanyak data array factors dan akan mengesktraks masing-masing nilainya yang disimpan pada variable factor. Apabila untuk kondisi tertentu membutuhkan index dari pengulangan kita bisa mendapatkannya dengan menambakan variable di depan for seperti ini.

for i, factor := range factors

Kita gabungkan semua kode di atas sehingga solusi untuk pencarian faktori sasi terbesar dari suatu bilangan adalah sebagai berikut.

prime_factor.go

Berikut adalah output dari code di atas.

Nilai faktorisasi prima terbesar :  6857
Waktu eksekusi 55000 nano second

Soal Ke Empat, Palindrom Terbesar Hasil Perkalian

Bilangan palindrom adalah bilangan yang dilihat dari kanan dan kiri memiliki nilai sama. Misalnya 9009 atau 4554. Adapun soal mengenai bilangan palindrom yang ada pada euler project adalah sebagai berikut.

Bilangan palindromik sama di kedua sisi. Palindrom terbesar yang terbuat dari hasil perkalian dua bilangan 2 digit adalah 9009 = 91 × 99.
Temukan palindrom terbesar yang merupakan hasil perkalian dua angka 3-digit.

Solusi yang akan diberikan saya menyebutnya sebagi solusi palindrom sindrom, dikarenakan sampai saat ini belum dapat menemukan solusi yang bukan brute force.

Idenya kita akan mencoba melakukan loop dua dimensi dan mengalikan dua pasangan bilangan yang terjadi, lalu mengecek apakah bilangan tadi palindrom atau bukan.

Untuk itu pertama kita buat dahulu solusi untuk mengecek apakah suatu bilangan palindrom atau bukan.

func isPalindrome(n int) bool {
   reverse :=0
   originalNumber :=n
   for n !=0 {
      reverse =(reverse*10)+(n%10)
      n/=10
   }
   return originalNumber==reverse
}

Fungsi kode ini reverse =(reverse*10)+(n%10) adalah untuk melakukan proses reverse angka yang akan kita cek polindrom atau bukan. n%10 akan mengambil angka satu persatu dari belakang.

Terakhir adalah kode utama yang perfungsi mengkalkulasi semua kemungkinan hasil perkalian tiga digit angka dan mengecek palindrom terbesar atau bukan.

palindrome.go

Jika kita eksekusi kode diatas berikut adalah solusi nya

906609
Waktu eksekusi  10  millisecond

Soal Ke Lima, Kelipatan Terkecil

Berikut adalah soal kelima pada euler project.

2520 adalah angka terkecil yang dapat dibagi dengan masing-masing angka dari 1 sampai 10 tanpa sisa.
Berapa bilangan positif terkecil yang habis habis dibagi semua bilangan dari 1 sampai 20?

Soal ini dikenal ketika kita masih duduk di sekolah dasar dengan istilah KPK. atau kelipatan persekutuan terkecil. Misalnya, KPK 2 dan 3 adalah 6 bukannya 12. Persoalan euler project pada dasarnya adalah persoalan KPK tetapi d bawa ke ranah yang lebih luas.

Ciri utama persoalan yang mesti dibantu dengan komputasi adalah sebuah persoalan yang ketika ruang lingkupnya kecil lalu dibawa ke ruang lingkup besar, disanalah komputasi komputer akan membantu.

Berikut adalah teori mengenai KPK ini mulai dari yang sederhana sampai teori yang lebih kompleks.

Saya definisikan sesuai dengan teorinya adalah sebagai berikut.

KPK(a,b) = (a.b)/PPB (a,b)

Contoh manual.

KPK (21,6) = (21*6)/PPB(21,6) = 21*6/PPB(3,6) = 21*6/3=7*6 = 42

PPB = Pembagi persekutuan terbesar ingat bukan FPB (faktor persekutuan terbesar)

Algoritma terbaik sepanjang sejarah mengenai hitung PPB adalah Algoritma Euclidean sebuah algoritma yang sudah cukup sangat tua karya Euclid dari Alexandria. Terbit atau di buat pada 300 BC. (300 tahun sebelum masehi!!!).

Bagian tedepan Buku Euclid’s Element dalam bahasa Ingris terbit tahun 1570

Salah satu fragmen tertua dari Euclid ‘s *Elements* , ditemukan di Oxyrhynchus dan bertanggal sekitar 100 M ( P. Oxy. 29 ). Diagram menyertai Buku II, Proposisi 5. [16]

Karena data yang kita cari kelipatan terkecilnya banyak mulai dari 1 sampai 20 maka kita akan melakukan loop dan mengkalkukasi 2 pasang data secara beruturan.

Berikut kode untuk mencari nilai pembagi terbesar yang merupakan versi yang sudah diperbaiki dari versi awalna. Lebih mudah karena algoritma awal dari euclidian adalah berbasiskan pengurangan.

func kpk(a int, b int)int  {
   return((a*b)/ppb(a,b))

}
func ppb(a int, b int) int {
   for b != 0 {
      t := b
      b = a % b
      a = t
   }
   return a
}

Lalu kita gabungkan semua code nya menjadi.

smallest_multiple.go

Test pengecekan untuk bilangan dari 1 sampai 10 adalah.

Bilangan kelipatan terkecil dari 1 s.d. 10 adalah :  2520
Waktu eksekusi 35000 nano second

Test pengecekan untuk bilangan dari 1 sampai 20 adalah

Bilangan kelipatan terkecil dari 1 s.d. 20 adalah :  232792560
Waktu eksekusi 62000 nano second

Pembahasan Euler project akan kita cukupkan sampai d sini, lima soal berikutnya akan kita analisis dan buatkan solusi di artikel selanjutnya, Best Praktis Basic Golang — Part 2.

References

Sponsor

Membutuhkan kaos dengan tema pemrograman :

Kafka T-shirt

Elastic T-shirt

Dapat menghubungi The Legend.