Blognya Riza

Untuk menyambut semakin dekatnya Olimpiade sains Nasional, saya pengen berbagi sedikit solusi soal OSN Komputer. Semoga bisa membantu adik2 sekalian yang hendak berkompetisi di OSN nanti. Kali ini saya mau membahas soal favorit saya, Kata Spiral, soal OSN 2005.

Deskripsi

Suatu sistem sandi menyandikan kalimat yang diberikan dalam bantuk spiral.

Penyusunan tersebut dilakukan membentuk matriks spiral yang dimulai pusat matriks

1 karakter pertama, lalu 1 karakter berikutnya ke kanan, lalu 1 karakter berikutnya ke

bawah, lalu 2 karakter berikutnya ke kiri, lalu 2 karakter berikutnya ke atas, 3 karakter

berikutnya ke kanan, 3 karakter berikutnya ke bawah, dan seterusnya hingga semua

karakter dalam kalimat termasuk dalam spiral. Khususnya, karakter spasi di ganti

dengan “_” (underscore), dan jika ada baris/kolom tersisa setelah karakter terakhir

maka elemen-elemen matriks diisi juga dengan “_” (underscore) tsb. Misalnya

kalimat “Seluruh peserta OSN bidang komputer harus mengerjakan soal-soal sebaikbaiknya

untuk mendapatkan peringkat terbaik.” Dikodekan kedalam matriks sebagai

berikut.

b a i k . _ _ _ _ _ _
r a i k n y a _ u n t
e b m e n g e r j a u
t - _ b i d a n g k k
_ k s _ h _ p e _ a _
t i u N u S e s k n m
a a r S r u l e o _ e
k b a O _ a t r m s n
g e h _ r e t u p o d
n s _ l a o s - l a a
i r e p _ n a k t a p

Masukan

Program membaca satu baris teks paling panjang 250 karakter.

Keluaran

Program harus menghasilkan sejumlah baris sesuai dengan matriks yang dibentuk.

Setiap baris keluaran berisikan karakter-karakter dari baris yang sama berturut-turut

dari kolom paling kiri ke paling kanan tanpa pemisahan (karakter-karakter dituliskan

bersambungan menjadi satu string serta jangan lupa setiap spasi menjadi underscore).

Contoh 1

Masukan

Seluruh peserta OSN bidang komputer harus mengerjakan soal-soal sebaik-baiknya untuk mendapatkan peringkat terbaik.

Keluaran

baik.______
raiknya_unt
ebmengerjau
t-_bidangkk
_ks_h_pe_a_
tiuNuSesknm
aarSruleo_e
kbaO_atrmsn
geh_retupod
ns_laos-laa
irep_naktap

Algoritma saya begini, kita ibaratkan matriks itu sebagai suatu bidang koordinat kartesius dengan pusat (0,0). Karena panjang stringnya hanya 250, maka bisa kita gunakan bidang kartesius itu sebagai array berukuran 15×15 dengan indeks [-7..7,-7..7] (tapi biar aman, pake[-8..8,-8..8] aja yak! :p ). Nah, setahap demi setahap, masukkan karakter string input ke bidang kartesius. Mulai dari indeks (0,0) lalu perlahan lahan bergerak melingkar. Untuk simulasinya saya lebih suka membayangkannya sebagai sebuah pointer bergerak yang menghadap ke atas, kanan, bawah dan kiri bidang kartesius. Langkah-langkahnya sebagai berikut :

• Pointer awalnya berada pada koordinat (0,0) dan menghadap ke atas.
• Untuk setiap karakter, lakukan seperti berikut :
  • Letakkan karakter pada koordinat pointer
  • Cek, jika cell di sebelah KANAN pointer adalah cell kosong, maka ubah arah pointer ke KANAN (misal, kalo kondisi sebelumnya menghadap atas, sekarang berubah menghadap kanan)
  • Majukan pointer satu langkah
  • Catat koordinat kiri bawah dan kanan atas yang baru dari matriks yang terbentuk

Source Code saya seperti ini :

var kata:string;
    i,j:integer;
    x1,y1,x2,y2,xkanan,ykanan:integer;
    matriks:array[-8..8,-8..8] of char;
    addx:array[0..3] of integer=(0,1,0,-1);
    addy:array[0..3] of integer=(1,0,-1,0);
    pointer:record
            x,y,arah:integer;
            end;

begin
  readln(kata);

  //inisialisasi pointer
  pointer.x:=0;
  pointer.y:=0;
  pointer.arah:=0;

  for i:=1 to length(kata) do
    begin
      //letakkan karakter ke matriks
      matriks[pointer.x,pointer.y]:=kata[i];

      //cek cell kanan pointer
      xkanan:=pointer.x+addx[(pointer.arah+1) mod 4];
      ykanan:=pointer.y+addy[(pointer.arah+1) mod 4];
      if matriks[xkanan,ykanan]=#0 then
        pointer.arah:=(pointer.arah+1) mod 4;

      //ubah koordinat pointer
      pointer.x:=pointer.x+addx[pointer.arah];
      pointer.y:=pointer.y+addy[pointer.arah];

      //update koordinat kiri bawah dan kanan atas matriks
      if x1>pointer.x then x1:=pointer.x;
      if y1>pointer.y then y1:=pointer.y;
      if x2<pointer.x then x2:=pointer.x;
      if y2<pointer.y then y2:=pointer.y;
    end;

  //tulis matriks
  for j:=y2 downto y1 do
    begin
      for i:=x1 to x2 do
        if (matriks[i,j]='') or (matriks[i,j]=' ') then write('_')
        else write(matriks[i,j]);
      writeln;
    end;
end.