Google Treasure Hunt 2008 Problems #1

Baru saja nemuin puzzle dari Google, namanya Google Treasure Hunt 2008, pertanyaan pertamanya adalah (afwan, ane langsung capture dari situsnya) :

 

pertanyaan ini mirip dengan pertanyaan pada project Euler no. 15 , karena saya sudah tahu, yag langsung ane hajar deh :P , denganjimat sakti mandraguna yang baru ane pelajari yaitu F# plus sedikit jurus yang juga sakti :), dan hasilnya, sepuluh menit kemudian (konfirmasi diberikan setelah 10 menit kemudian):

clue bagi yang mau nyoba: Combinatorics/ kombinatorial

 

soal puzzle nya keluar tiap minggu, dan saya kelihatannya sudah telat untuk soal pertama, soalnya sekarang sudah ada soal yang ke dua, dan ane belum menjawabnya, nanti pas saya sudah jawab untuk soal kedua akan saya posting source code untuk jawaban pertama, InsyaaAllah :) . perlu dicatat, ane mencoba ini bukan untuk hadiah, just for fun, jadi ya gak masalah gak dapat hadiah (meskipun pengen dapat hadiah juga, hihi :P )

Asynchronous Workflow di F#

kali ini saya tidak sedang membahas salah satu jawaban pada Projec Euler seperti sebelumnya, tapi kali ini saya ingin turut membantu memberikan jawaban dari sebuah pertanyaan yang ada di Yahoo! answer berikut:

The sum of all of the digits of all the whole numbers from 1 to 1,000,000?

What is the sum of all of the digits of all the whole numbers from 1 to 1,000,000 (inclusive?
Thanks for any answers in advance. :)  ~cf_al_bs

jadi ceritanya ditanyakan jumlah digit – digit dari bilangan 1 sampai sejuta , sebagai ilustrasi jika rangenya adalah 10 – 15, maka perhitungannya adalah:

sumAllDigit(10) = (1 + 0) = 1

sumAllDigit(11) = (1 + 1) = 2

sumAllDigit(12) = (1 + 2) = 3

sumAllDigit(13) = (1 + 3) = 4

sumAllDigit(14) = (1 + 4) = 5

sumAllDigit(15) = (1 + 5) = 6

———————————–+

sumAllDigitDari(10-15)  = 21

jadi jawabannya 21, sedangkan persoalannya adalah rangenya besar yaitu 1 sampe satujuta.

karena ini merupakan pertanyaan yang menarik, dan baru saja membaca tentang asynchronous workflow di F# (masih sedikit sih :)), langsung saja saya pengen mencoba mempraktekkannya untuk mencari solusi permasalahan tersebut:

strategi saya adalah sebagai berikut:

1. karena jumlah bilangan dari 1 sampe 1 juta itu sangat banyak (sejuta :D), jadi saya pecah deret bilangan tersebut menjadi 5 bagian masing – masing 200 ribu

2. masing – masing pecahan tersebut kemudian di proses untuk menghasilkan jumlahnya masing – masing secara asinkron,

3. terus jumlahkan semua hasil perhitungan tiap partisi pada langkah 2

ilustrasinya adalah sebagai berikut:

 

adapun kode programnya adalah sebagai berikut:

4. saya juga mencoba dengan cara serial, tentu saja dengan kode program yang lebih pendek :)

setelah dieksekusi bareng maka hasil eksekusinya adalah sebagai berikut:

jadi hasil algoritmanya bener karena nilai yang diperoleh sama = 27000001, sedang waktu eksekusinya beda, kali ini asynchronous menang, karena berhasil mencatat waktu 1,5858360 detik, sedangkan serial kalah terpaut 0.419895 detik pada catatan waktu 2.0057310, jadi juara motogp di sirkuit phi si ku (PC-ku)adalah Caseyncronous Stoner, sedangkan Valentino Roserial kalah :D .

Jumlahno Digite

kali ini saya menerapkan teknik menulis yang baik (aneh), he..he, yaitu membuat judul yang membuat orang selain orang jawa nggak ngeh, dan akhirnya ingin membaca dan melihat isi postingan saya kali ini :D. ok, kali ini saya ingin mencatat perjalanan saya yang sampai pada projek Euler (yang eksplor F# sejak dulu pasti sudah tahu ini), salah satu pertanyaanya adalah berapa hasil penjumlahan dari 2 pangkat 1000, ini pertanyaan ke-16, nah akhirnya saya coba menjawabnya dengan F# , itung – itung sambil belajar F#, begini:

let duaPangkat1000 = (powi 2I 1000)
let rec sumAllDigitFrom x =
    match x with
    | x when (x < 10I) -> x
    | _ -> (x % 10I) + (sumAllDigitFrom (x/10I))

let dpx = (sumAllDigitFrom duaPangkat1000)
printf “2^1000 = %A\nHasil Penjumlahan tiap digit = %A” duaPangkat1000 dpx

nah, uniknya disini setelah kita bisa mejawab kita dapat melihat cara menjawab orang lain, nah saya lihatlah jawaban orang lain itu; orang pertama menjawab pake assembly (codenya panjang, padahal biasanya orang itu jawabannya pendek/singkat banget meski pake assembly), terus lihat agak kebawah lagi ada yang pake ruby (duh tadi kenapa gak pake ruby) kaya gini ():

sum = 0
(2**1000).to_s.each_byte {|b| sum+=b.chr.to_i}
puts sum

pendek banget kan :), kemudian saya lihat Haskell (oh, saya belum pernah mrogram pake Haskell, tapi dia peserta GSoC juga :) ) begini:

sum (map (digitToInt) (show (2^1000)))

nah lho, ini sama – sama functional kenapa bisa singkat gini, sebenarnya masih ada sebelas halaman lagi untuk dilihat, tapi saya malas :), kayak search engine cukup halaman pertama, akhirnya saya mencoba mengkompress kode saya di atas, dan setelah cukup lama (harus baca manual F# lagi bo!) dan akhirnya saya mentok disini, ini dia kode saya yang baru:

List.of_array(((powi 2I 1000).ToString()).ToCharArray())
        |> List.map(fun x -> int(x.ToString())) |> List.fold1_left(+) |> print_any

 

semua kode selengkapnya saya ini:

tuh, saya tulis kode dalam haskellnya juga untuk membandingkan, dan ternyata saya tidak bisa mengkompress kode program saya seperti itu, karena masih kurang ilmu :(

dan hasil eksekusinya:

tiga baris pertama itu merupakan hasil perhitungan 2 pangkat 1000 dan baris terakhir adalah jawabannya, versi perhitungan panjang dengan fungsi rekursif, dan yang diperoleh dari kode program yang kayaknya lebih pendek = 1366 (hooray! kali ini saya pake visual studio)

iya kan, (saya) masih kalah saja dengan haskell, pertanyaan saya adalah, adakah solusi yang lebih pendek dalam F# ? (giliran anda menjawab di bagian komentar postingan ini :D )