Lingkaran Warna

October 30, 2006 at 5:23 pm | Posted in ACM Contest, Algorithms | 8 Comments

By: Mpu Gondrong

Kali ini kita membahas soal di http://acm.uva.es/p/v8/899.html tentang permainan menggunakan lingkaran berwarna. Di sini bermain 2 orang yang saling bergantian berpindah arah. Tujuannya sederhana, yaitu mencapai lingkaran tujuan dengan pergerakan minimal.

Meskipun soal ini tampak biasa-biasa saja, tapi cukup baik sebagai contoh penggunaan fungsi / prosedur rekursif. Rekursif berarti memanggil dirinya sendiri. Pada banyak bahasa pemrograman kemampuan untuk rekursif ini sangat membantu dalam menyederhanakan logika program.

Dari soal yang disajikan kurang lebih ada aturan berikut:

  • Terdapat lingkaran dari 1 s/d 100.
  • Tiap lingkaran memiliki warna dan dimungkinkan terdapat duplikasi.
  • Terdapat panah-panah yang menghubungkan dari satu lingkaran ke lingkaran yang lain. Panah tersebut berisi data: dari, ke, dan warna.

Dalam melakukan pergerakan terdapat aturan berikut:

  • Lingkaran tujuan ditentukan oleh panah yang warnanya sesuai lingkaran di mana posisi lawan berada. Misal: ketika A di Lingkaran Merah dan B di Lingkaran Biru, maka A bergerak sesuai arah panah berwarna Biru, demikian sebaliknya B bergerak sesuai arah panah berwarna merah.
  • Perkecualian bila lingkaran yang dituju telah ditempati oleh lawan yang berarti arah tersebut tidak valid.
  • Dalam 1 giliran dapat terjadi banyak perpindahan hingga tidak dimungkinkan lagi untuk berpindah.

Format Input

Format input terdiri dari beberapa baris. Pada baris pertama terdiri dari N, R, S, T and M, yang artinya:

  • N: banyaknya lingkaran.
  • R dan S: lingkaran awal dari pemain A dan B.
  • T: lingkaran tujuan.
  • M: banyaknya panah.

Pada baris selanjutnya adalah warna dari tiap-tiap lingkaran. Sebanyak M baris berikutnya adalah data masing-masing panah.

Data input ini berulang hingga semua baris selesai dibaca. Misal untuk satu permainan dengan 4 panah, maka dibutuhkan 1 + 1 + 4 baris data. Input berakhir setelah pada baris pertama terdiri dari 5 angka 0.

Pembacaan angka dalam Pascal sangat mudah, yaitu dengan ReadLn(Angka) atau Read(Angka). Batas pemisah dari tiap-tiap angka adalah while space, yaitu spasi (#32), Tab (#9), CR (#13), atau LF (#10). Bila pembacaan deretan angka menggunakan Read telah sampai akhir baris, dia secara otomatis akan naik ke baris berikutnya.

Struktur Data

Penyelesaian dari soal ini dimulai dengan penyusunan struktur data yang baik. Dari aturan-aturan di atas kita buat 2 jenis record, yaitu mewakili Panah dan Lingkaran. Banyaknya lingkaran dan panah ditentukan secara statis lewat konstanta.

const 
  MaxLingkaran = 100; 

type 
  TPanah = record 
    Warna, Arah: Byte; 
  end; 
  TLingkaran = record 
    Warna: Byte; 
    Banyak: Integer; 
    Panah: array[1..MaxLingkaran+1] of TPanah; 
end; 

var 
  Lkr: array[1..MaxLingkaran] of TLingkaran;

Warna dalam record tersebut hanya berukuran 1 byte karena maksimal lingkaran adalah 100. Begitu pula dengan Arah yang hanya berukuran 1 byte yang menentukan tujuan tidak lebih dari 100 lingkaran. Namun dalam penerjemahan kode TPanah ini akan berukuran minimal 4 byte karena default dari record alignment adalah 4 byte.

Dalam tiap-tiap lingkaran terdapat array Panah yang menunjukkan kemungkinan arah dari lingkaran tersebut menuju lingkaran yang lain. Array Panah ini lebih banyak 1 dari maksimal lingkaran sebagai batas arah yang valid. Dalam procedure Susur digunakan Warna = 0 untuk menunjukkan bahwa itu adalah akhir dari array Panah dalam sebuah Lingkaran.

Untuk menandai suatu Panah telah digunakan, dalam proses mencari kemungkinan arah menuju Lingkaran tujuan, digunakan bit ke-7 (susunan 0..7, nilainya 128) dari Warna, yaitu dengan meng-or-kan sebelum melakukan penelusuran, dan meng-and-kan setelah penelusuran. Dengan begitu dari pengecekan Warna sudah mencukupi apakah arahnya sesuai dan dapat digunakan.

Prosedur Rekursif

Inti dari penyelesaian soal ini terletak dalam procedure Susur, dengan parameter:

  • Cah, untuk banyaknya pergerakan. Setiap kali pemanggilan maka parameter ini akan dinaikkan dengan 1.
  • Ca, untuk posisi A saat ini.
  • Cb, untuk posisi B saat ini.

Yang perlu diperhatikan dalam pemakaian fungsi / prosedur rekursif adalah penggunaan variabel lokal yang efisien. Prosedur rekursif menggunakan stack sebagai penampung variabel lokal termasuk alamat kembali dari prosedur itu. Stack besarnya terbatas dan ditentukan pada saat kompilasi program.

Hal lain dalam prosedur rekursif adalah akhir dari prosedur tersebut untuk tidak melakukan perulangan lagi atau berhenti memanggil dirinya sendiri. Bila hal ini dilupakan maka prosedur akan terus berulang tanpa batas atau hingga kehabisan stack. Dalam procedure Susur ini akhir dari perulangan adalah apabila lingkaran tujuan tercapai atau banyaknya pergerakan lebih besar dari hasil sebelumnya.

Rutin yang berulang terdapat dalam procedure Susur, yaitu mewakili pergerakan A dan pergerakan B. Digunakan pointer Panah (^TPanah) sebagai wujud dari panah yang menunjukkan warna dan arah. Panah ini akan berubah-ubah sesuai penelusuran lingkaran hingga sampai ke lingkaran tujuan.

Program Lengkap

Bentuk lengkap dari penyelesaian soal 899 ini sebagai berikut.

program color_circle; 

const 
  MaxLkr = 100; 

type 
  TPanah = record 
    Warna, Arah: Byte; 
  end; 
  TLkr = record 
    Warna: Byte; 
    Banyak: Integer; 
    Panah: array[1..MaxLkr+1] of TPanah; 
  end; 

var 
  Lkr: array[1..MaxLkr] of TLkr; 
  BnLkr, BnPan, CahMax: Integer; 
  Tuju: Byte; 

procedure Susur(Cah, Ca, Cb: Integer); 
var 
  P: ^TPanah; 
  Warna: Byte; 
begin 
  P := @Lkr[Ca].Panah; 
  Warna := Lkr[Cb].Warna; 
  while P^.Warna <> 0 do begin 
    if (P^.Warna = Warna) and (P^.Arah <> Cb) then begin 
      if P^.Arah = Tuju then begin 
        CahMax := Cah; Exit; 
      end; 
      if Cah < CahMax then begin 
        P^.Warna := P^.Warna or 128; 
        Susur(Cah+1, P^.Arah, Cb); 
        P^.Warna := P^.Warna and 127; 
      end; 
    end; 
    Inc(P); 
  end; 
  P := @Lkr[Cb].Panah; 
  Warna := Lkr[Ca].Warna; 
  while P^.Warna <> 0 do begin 
    if (P^.Warna = Warna) and (P^.Arah <> Ca) then begin 
      if P^.Arah = Tuju then begin 
        CahMax := Cah; Exit; 
      end; 
      if Cah < CahMax then begin 
        P^.Warna := P^.Warna or 128; 
        Susur(Cah+1, P^.Arah, Ca); 
        P^.Warna := P^.Warna and 127; 
      end; 
    end; 
    Inc(P); 
  end; 
end; 

var 
  I, J, Cah1, Cah2: Integer; 
begin 
  Readln(BnLkr, Cah1, Cah2, Tuju, BnPan); 
  while BnLkr > 0 do begin 
    for I := 1 to BnLkr do begin 
      Read(Lkr[I].Warna); 
      Lkr[I].Banyak := 0; 
    end; 
    for I := 1 to BnPan do begin 
      Read(J); 
      with Lkr[J] do begin 
        Inc(Banyak); 
        Read(Panah[Banyak].Arah, Panah[Banyak].Warna); 
      end; 
    end; 
    for I := 1 to BnLkr do 
      Lkr[I].Panah[Lkr[I].Banyak+1].Warna := 0; 
    CahMax := MaxInt; 
    Susur(1, Cah1, Cah2); 
    if CahMax = MaxInt then Writeln('0') else Writeln(CahMax); 
    Readln(BnLkr, Cah1, Cah2, Tuju, BnPan); 
  end; 
end.

Demikian selamat mencoba.

8 Comments »

RSS feed for comments on this post. TrackBack URI

  1. Uhmm…. kalau kita menghilangkan penggunaan pointer seperti pada Java, salah tidak sih? Pointer sulit dipahami, setidaknya buat saya….

  2. haloo mpu gondrong………
    aq dah nyoba programnya dan berhasil..
    aq mmau minta tolong nichh..
    kebetulan aq ada tugas dari sekolah membuat program game dari pascal.
    tolong kirimin dong mpu gondrong program game pascal apa saja .. yachh..
    ke e-mail : theboy_khan@yahoo.co.id
    tanks…..

  3. tolong minta virus laen tapi yang aktif kirim ke e-mail koe deyan_pjkr@yahoo.co.id
    n’ minta cewek donk yah

  4. setelah baca soalnya lagi..

    ternyata persoalan ini merupakan penyederhanaan dari pembagian suatu proses (program) menjadi n buah thread. lingkaran berarah itu state machine. intinya adalah melakukan verifikasi otomatis terhadap konfigurasi thread (dalam hal ini disederhanakan menjadi dua thread) apakah dengan konfigurasi tersebut program ‘akan’ berhenti (halting problem).

    pake pure DFS aja bisa yah? kompleksitasnya gimana mas?

  5. hi, aq juga mohon bantuannya dong. Minta contoh program pascal game sederhana. aq udah seminggu cari-cari diinternet,tapi ga dapet. Jadi please yaaa…

  6. mas, tolongin saya dong, saya disuruh untuk buat program sederhana ( game ) dari pascal, tapi saya tidak mengerti, mas tolong dong berikan contoh lain program sederhana ( game ) yang dari pascall

  7. mas, boleh minta tolong dong….!
    saya di suruh buat game dari pascal juga tapi sudah cari2 dapat tapi error…! boleh ga bantuin saya…..thanks before….!

  8. makasih ya bang….!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: