Yeni Yılın İlk Scripti

Adamlar - Öyle Normal (Akorlor & Tab)

|====================== Intro =========================|

Acoustic Guitar:

G#m - C#m - Bdim7 - C#m
G#m - C#m - Bdim7 - C#m
G#m -  E  -   B   - Gdim7 
G#m - C#m - Bdim7 - C#m

Electric Guitar:

e|------------------------------------------------------------------
B|-----------------------------------5--4--5--4--5/7/5--4-----4v----
D|---------------------------------------------------------6--------
G|------------------------------------------------------------------
A|------------------------------------------------------------------
E|------------------------------------------------------------------

e|------------------------------------------------------------------
B|--5--4--5--4--5/7/5--4-----4v------5--4--5--4--5/7/5--4-----------
D|------------------------6--------------------------------6--4v----
G|------------------------------------------------------------------
A|------------------------------------------------------------------
E|------------------------------------------------------------------

e|------------------------------------------------------------------
B|------------------------------------------------------------------
D|--4--3--4--3--4/6-/4----3/4---------------------------------------
G|-----------------------------6-----6^8^6\5------------------------
A|------------------------------------------------------------------
E|------------------------------------------------------------------


|======================= Verse =========================|

Acoustic Guitar: G#m - E - D# - F#

Electric Guitar:

e|----------------------------------------------------
B|--5--4---------------------5--4---------------------
D|--------6--4--6/-8v--------------6--4--6/-3v--------
G|----------------------------------------------------
A|----------------------------------------------------
E|----------------------------------------------------


|===================== Pre-Chorus ======================|

Acoustic Guitar: E - B - Gdim7

e|------------------------3---------------------
B|-------0----------4-----2---------------------
D|----------1--4-------4--3---------------------
G|--2----------4----------2---------------------
A|--2----------2--------------------------------
E|--0-------------------------------------------


|====================== Chorus =========================|

Acoustic Guitar:

G#m - C#m - Bdim7 - C#m
G#m - C#m - Bdim7 - C#m
G#m -  E  -   B   - Gdim7 
G#m - C#m - Bdim7 - C#m

Electric Guitar:

* Bu bölümdeki slidelar çok kısa 

e|--3/4--3/4--3/4----6/7-6----4--3-----------------------
B|----------------------------------5--4-----------------
D|----------------------------------------6--4v----------
G|-------------------------------------------------------
A|-------------------------------------------------------
E|-------------------------------------------------------

e|--6/7-6----4-6/9--7--6----3--4v------------------------
B|-------------------------------------------------------
D|-------------------------------------------------------
G|-------------------------------------------------------
A|-------------------------------------------------------
E|-------------------------------------------------------

e|------------------3-----4------------------------------
B|-------4-----2-------2--4-----5--4--5--4--5/7/5--4-----
D|--4-------4--3----------4---------------------------6--
G|--4----------2-----------------------------------------
A|--2----------------------------------------------------
E|-------------------------------------------------------


|======================= Solo ==========================|

~ let ring

e|--------------------------------------------------
B|-----5-----5-----5-----5-----5-----5--7--5--------
D|-/8-----8-----8-----8-----8-----8-----------8--6--
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------

e|--------------------------------------------------
B|-----5-----5-----5-----5-----4-----4-----4-----4--
D|--8-----8-----8-----8-----6-----6-----4-----4-----
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------

e|--------------------------------------------------
B|-----0-----0-----0-----0-----0-----0-----0-----0--
D|--3-----3-----3-----3-----3-----3-----3-----3-----
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------

e|--------------------------------------------------
B|--------------------------------------------------
D|-----3-----3-----3-----3-----1--------------------
G|--6-----6-----6-----6-----5-----5-----------------
A|--------------------------------------------------
E|--------------------------------------------------

...ve daha sonra şarkıdaki farklı kısımları tekrar çalarak
şarkıyı bitiriyorlar. Eminim hangi kısımda nereyi tekrar 
çaldıklarını kendiniz de anlayabilirsiniz. Ek olarak canlı 
performanslarında 2. versede bazen aşağıdaki kısmı çalıyorlar.
Ayrıca 2. pre-chorusu uzatarak çaldıklarını farketmişsinizdir.

e|------11----------11----------12----------12------
B|----------12----------12----------12----------12--
D|--13----------13----------13----------13----------
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------

e|------11----------11----------11----------11------
B|----------11----------11----------11----------11--
D|--12----------12----------12----------12----------
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------

|====================== Outro =========================|

~staccato

e|--------------------------------------------------
B|--------------------------------------------------
D|--------------------------------------------------
G|--6v----------------------------------------------
A|--------8/9---8---7---5---6/----------------------
E|--------------------------------------------------


Ayrıca Adamlar - Kapısı Kapalı tabı için tıklayın.

Pretty-Printing (Dynamic Programming)

Hepimiz bir metin yazarken satır uzunluklarının birbirine denk gelmemesine ara sıra gıcık olmuşuzdur. Doğrusu belki de herkes buna benim kadar takmıyordur. Yine de bu problem Algortihm Design kitabında karşılastığım en iyi hikayaye sahip egzersizlerden biriydi. Bu yüzden buna biraz zaman ayırdım. İşte kitapta problemin geçtiği kısım.

Problemi daha formal bir hale getirmek için, satır uzunluklarının olabildiğince eşit olmasına ölçüt olarak, kenar boşluklarının uzunluklarının karesinin toplamına bakılmış. Eğer kareleri alınmasaydı, her satıra yer kalmayana kadar kelime eklemek problemi çözmek için yeterli olurdu. Ama karelerine bakmamız gerektiğinde, problem greedy olarak çözülmesi pek mümkün görünmüyor. Bundan dolayı dynamic programming'e başvuruyoruz.

Problemi tam anlayamadıysanız bu wikipedia sayfasına bir göz atabilirsiniz.

Aslında, dynamic programming için gereken recurrence'i bulmak bu soru için çok zor değil.

Si,j wi, wi+1, ..., wj kelimelerinden oluşan satırının kenar boşluğu(slack) uzunluğudur. Eşitlikte (j - i) boşluk sayılarıdır. Satır uzunluğunun L'yi geçemeyeceği için Si,j 0'dan büyük eşittir. OPT(j) ise w1, w2, ..., wj kelimeleri için slacklerin kareleri toplamının mümkün olan en düşük değeridir. Optimum çözümdeki en son satır wi kelimesi ile başlar. Bu durumda son satır çözümü Si,j'nin karesi kadar arttırır. Son satırdan önceki kenar boşluklarının karesi ise OPT(i-1)'e eşittir.  

Ancak problemin amacı OPT(n) değelerini bulmanın yanı sıra, bu değere ulaşmak için her satırın hangi kelimelerden oluştuğunuda bulmak. Bundan dolayı OPT(j) değerin yanında i'nin yani en son satırın hangi kelime ile başladığını da hafızada tutmalıyız. Bunun için aşağıdaki python kodunda back_pointer isimli bir liste kullanıyorum. Daha sonra bu listeyi tersinden dolanarak, her satırın hangi kelime ile bittiğini sol adlı listeye ekliyorum.

Ayrıca slackleri her başlangıç ve bitiş değeri için ayrı ayrı hesaplamak çok zaman alacağından bir tablo oluşturdum. Yukarıdaki eşitlikten Si,i = L - ci  ve eklenen her kelime wk için kenar boşluğu ck+1  kadar azalır. Böylece tablodaki her bir eleman birim zamanda doldurulabilir. Toplamda tabloda n(n+1)/2 hücre doldurulduğundan O(n^2) zaman alır. OPT ve back-pointer değerleri hesaplamak her iterasyonda minumum alındığından O(n^2) zaman alır. Son kısın ise O(n) olduğuna göre algoritmanın time-complexitysi O(n^2)'dir.



Aşağıda ise python'un curses modulü ile yazdığım, terminal üzerinde çalışan küçük bir editör var. Bu editör her yeni kelime girdiğiniz de yukarıdaki algoritmayı uyguluyor. Ne yazık ki trinket curses modülünü desteklemediğinden dolayı kendi terminalinizde çalıştırmanız gerekecek.

import curses
import curses.ascii

class PrettyTextBox:
    
    def __init__(self, win):
        self.win = win
        self.maxy, self.maxx = win.getmaxyx()
        self.maxy = self.maxy - 1
        self.maxx = self.maxx - 1
        win.keypad(1)

    def _end_of_line(self, y):
        last = self.maxx
        while True:
            if curses.ascii.ascii(self.win.inch(y, last)) != curses.ascii.SP:
                last = min(self.maxx, last + 1)
                break
            elif last == 0:
                break
            last = last - 1
        return last

    def do_command(self, ch):
        y, x = self.win.getyx()
        if ch == curses.ascii.SP:
            self._pretty_print()
        elif curses.ascii.isprint(ch):
            if y <= self.maxy and x <= self.maxx:
                try:
                    self.win.addch(ch)
                except curses.error:
                    pass
        elif ch == curses.KEY_LEFT:
            if x > 0:
                self.win.move(y, x - 1)
        elif ch == curses.KEY_RIGHT:
            if x < self.maxx:
                self.win.move(y, x + 1)
        elif ch == curses.KEY_UP:
            if y > 0:
                self.win.move(y - 1, x)
        elif ch == curses.KEY_DOWN:
            if y < self.maxy:
                self.win.move(y + 1, x)
        elif ch == curses.KEY_BACKSPACE:
            if x > 0:
                self.win.move(y, x - 1)
                self.win.delch()
        elif ch == curses.ascii.NL:
            if y < self.maxy:
                self.win.move(y + 1, 0)
        elif ch == curses.ascii.ESC:
            return 0
        return 1

    def gather(self):
        result = ""
        for y in range(self.maxy + 1):
            self.win.move(y, 0)
            stop = self._end_of_line(y)
            if stop == 0:
                continue
            for x in range(self.maxx + 1):
                if x > stop:
                    break
                result = result + chr(curses.ascii.ascii(self.win.inch(y, x)))
        return result

    def edit(self):
        while 1:
            ch = self.win.getch()
            if not ch:
                continue
            if not self.do_command(ch):
                break
            self.win.refresh()

    def _pretty_print(self):
        word = [None] + self.gather().split()
        slack = [[None for x in range(len(word))] for x in range(len(word))]
        table = [0] * len(word)
        back_pointer = [0] * len(word)

        for i in range(1, len(word)):
            slack[i][i] = self.maxx - len(word[i])
            for j in range(i + 1, len(word)):
                slack[i][j] = slack[i][j - 1] - (len(word[j]) + 1)

        for j in range(1, len(word)):
            table[j], back_pointer[j] = min(
                [ (table[i - 1] + slack[i][j]**2, i) for i in range(1, j + 1) if slack[i][j] >= 0 ] 
            )

        opt = []
        
        j = len(word) - 1
        while j > 0:
            opt.insert(0, j)
            j = back_pointer[j] - 1

        self.win.erase()
        self.win.move(0, 0)

        i = 1
        for j in opt[:len(opt) - 1]:
            for k in range(i, j + 1):
                self.win.addstr(word[k] + ' ')
            y, _ = self.win.getyx()
            self.win.move(y + 1, 0)
            i = j + 1

        for k in range(i, opt[len(opt) - 1] + 1):
            self.win.addstr(word[k] + ' ')

def main(stdscr):
    w = curses.newwin(100, 30, 1, 2)
    box = PrettyTextBox(w)
    box.edit()

curses.wrapper(main)

ETU ACM Java Kursu: 5. Hafta (Interval Scheduling)

Bugünki dersde, sınıfları işledik ve egzersiz olarak Interval Scheduling Problem'ini çözdük.

Interval.java

public class Interval {
 
 public int beg;
 public int end;
 
 public Interval(int a, int b) {
  if (a > b) 
   throw new IllegalArgumentException();
  
  beg = a;
  end = b;
 }
 
 public int len() {
  return end - beg;
 }
 
 public boolean overlaps(Interval other) {
  return this.beg < other.end && other.beg < this.end; 
 }
 
 public String toString() {
  return "(" + beg + ", " + end + ")";
 }

}

Scheduler.java

public class Scheduler {
 
 public Interval[] request;
 
 public Scheduler(Interval[] arr) {
  request = arr;
 }
 
 private Interval firstEnding() {
  Interval firstEnding = request[0];
  for (int i = 0; i < request.length; i++) {
   if (request[i].end < firstEnding.end) 
    firstEnding = request[i];
  }
  return firstEnding;
 }
 
 private void remove(Interval removing) {
  Interval[] update = new Interval[request.length - 1]; 
  for (int i = 0, j = 0; i < request.length; i++, j++) {
   if (request[i] != removing)
    update[j] = request[i];
   else
    j--;
  }
  request = update;
 }
 
 private void removeOverlapsWith(Interval interval) {
  for (int i = 0; i < request.length; i++) {
   if (request[i].overlaps(interval)) {
    remove(request[i]);
    i--;
   }
  }
 }
  
 public void schedule() {
  while (request.length != 0) {
   System.out.println(firstEnding());
   removeOverlapsWith(firstEnding());
  } 
 }
 
 public static void main(String[] args) {
  Interval[] reqs = { new Interval(3, 8),
       new Interval(9, 16),
       new Interval(13, 18),
       new Interval(20, 32),
       new Interval(26, 30)};
  
  new Scheduler(reqs).schedule();; 
 }
}

Ayrıca isteyenler için, küçük bir ödev vermiştim: firstEnding'i her defasında bütün arrayi dolanarak, tekrar tekrar bulmak yerine; array'i başlangıçta end'e göre küçükten büyüğe sıralayarak programı hızlandırın. Array'i başlangıçta interval'ların end'ine göre sıralarsak, end'i en küçük olan Interval array'in ilk elamanı olacaktır. Böylece firstEnding methodunda, tüm arrayi taramak yerine array'in sadece ilk elamanını dönmek yeterli olacaktır.

Kriptoloji Semineri: ETU Cipher

Geçen hafta ETU ACM'den arkadaşlar bugün düzenlenen Kriptografi ve Haberleşme Güvenliği Semineri için küçük bir şifreleme oyunu hazırlamamı istemişti Eğer çözümü öğrenmeden önce bir denemek isterseniz, soru bu linkte.  

Yarışmaya 20 küsür kişi mail yoluyla katılmış ancak bize ulaşan cevaplardan sadece 3 tanesi doğruydu. Zaten ilk 3'e hediye verildiği için, iyi denk geldi. Katılım oranını yüksek, doğru cevabın ise düşük olması için uğraşırken ortaya değişik şeyler çıktı. Shift cipher mı, substitution cipher mı diye soranlar oldu. Hayır, değildi ama şifreleyici her harfi başka bir harfe map ediyordu, bundan dolayı frekans analizi kullanarak da çözenler olmuş. 

Örneğe tekrar bakarsak:
"ETU şifreleyecisi, “ETU ACM’e hoşgeldiniz” metnini, ‘ş’ anahtarı kullanarak “ımn ceti laşjısgöuöz” metnine çevirmiştir."

Belki  anahtar olan 'ş' harfinin aynı kaldığını farketmişsinizdir, ancak kritik olan kısım z harfinin de değişmemiş olması. Doğrusu şifrenin kendisini çözmek çok zor değildi, eğer verilen örnekte eşleşmelerin tıpa tıp aynısı kullanırsanız, şifrenin ne olduğunu tahmin etmek mümkündü.

Ne_e_e / g_tt___n_ / __şm__o__an / he_ / ___ / _en_ / __a_a / git__ecelt__

İlk kelimenin "nereye" ve ikincisinin "gittiğini" olduğunu tahmin ederek bu kelimelerin içinde geçen harflerin, hangi harflere karşılık geldiği bulunabilir. Karşılıklarını bulduğumuz bu harfleri, kalan diğer kelimelerde yerine koyarak ve biraz  daha tahminle şifrenin,"Nereye gittiğini bilmiyorsan, her yol senin oraya götürecektir" olduğu ortaya çıkıyor. 

Şimdi gelelim işin zor kısmına, peki bu metin hangi anahtarı kullanarak şifrelenmış olabilir? Örnekte anahtar harfin aynı kaldığından yola çıkabiliriz. Bu şifreli metinde y, ö ve ü harfleri aynı kalmış. Örnekte ise ş'nin yanı sıra z harfi de aynı kalmıştı. Yani şifreliyici de anahtar dışında bazı harflerin de aynı kalabildiğini biliyoruz. 

ö, ü, y ve z: Bunların ortak noktası ne? ü, y "ve" z, alfabenin son 4 harfi. (Tamam "ve" de ki kelime oyunun kimsenin farkettiğini sanmıyorum ama bahsetmeden geçemedim, aslında anahtarı bulmak için gerekmiyor). Evet, uydurduğum şifreleyicinin en büyük zaafı buydu. Aslında anahtarı ne seçerseninz seçin ü, v, y, z harfleri kendine eşleniyor. Heralde artık şifreleyicinin gerçekte nasıl çalıştığını anlatma sırası gelmıiştir.

ETÜ ŞİFRELİYİCİSİ

1) Anahtar olarak Türk alfabesinden bir harf seç. Anahtar harfi her zaman kendisine eşle.

Diyelim ki anahtar 'ş' olsun.

2) Anahtar harfi, alfabeden çıkar ve alfabeyi satırlarda sırasıyla asal sayılar olacak şekilde yaz:

ab

cçd

efgğh

ıijklmn

oöprstuüyvz

Gördüğünüz gibi satırlarda sırasıyla 2, 3, 5, 7, 11 sayıda harf var ve ş harfi atlanılmış. Belki tam denk gelmesi, dikkatinizi çekmiştir. Aynı zamanda tesadüfe bakın ki alfabedeki harf sayısı olan 29'da asal. Başka bir tesadüf ise 29'un aynı zamanda ilk 3 asal sayının çarpımından bir eksik olması. (bkz. Primorial Prime).

3) Her harfi, bir altındakiyle eşlestir. (Yukarıdaki önrek için artık, g yerine j kullanılacak). En alt satırdaki harfleri için en üstten tekrar başla. (Tekrar yukarıdaki örnek için o -> a, s -> h, y -> y).

Gördüğünüz üzere ü, y, v, z harfleri en sonda kaldıkları için altlarında kendileri var. Bu yüzden kendileri ile eşleniyorlar.

Bundan dolayı şifrenin anahtarı ö idi. Gördüğünüz gibi ş ile aynı satırda olduğundan yukarıdaki harflerin karşılıkları aynı kaldı. Bu yüzden şifreyi çözmek biraz daha kolaydı. 

Şifrenin nereden geldiğine merak edenlere:

Ayrıca, unutmadan seminer sırasında Ali Hoca'nın bahsettiği bazı konularla ilgili, bir kaç güzel video'yu paylaşmak istiyorum.

Man in the Middle Attack
RSA Encryption
Eliptic Curve Crpytography

Bu ise paşa fanlarına gelsin!

Tesadüfe bakınkı tam  bir hafta sonra, son 2 video'daki matematikçi Prof. Edward Frenkel ODTÜ'nün 60. yıl etkinliklerinde bir konuşma yapacak. Ancak yine tesadüfe bakın ki, tam da Ali Hoca'nın Otomata dersiyle çakışıyor.

Neyse, bugünlük bu kadar tesadüf yeter. Eğer bugün seminere gelmiş, attığım videoları sonuna kadar izlemiş ve hala daha fazlası için kıvranıyorsanız, Youtube'daki The Art of The Problem kanalının kriptoloji hakkındaki yaklaşık 1 saatlik playlistine göz atmanızı öneririm.
  

ETU ACM Java Kursu: 4. Hafta (Max, Median and Sorting)

Merhaba, arkadaşlar. Geçen hafta sizlerle ders notlarını paylaşmaya ne yazık ki vakit bulamadım. Ders notlarının amacı genel olarak ilk 1-2 dersi kaçıranların derse yetişebilmelerini sağlamaktı. Bu noktadan sonra derse hiç gelmeyen birinin, bize yetişmesi zor. Ondan dolayı, bu hafta neler yaptığımızı uzun uzun anlatmayacağım.

Bu hafta, dizilerden, fonksiyonlaradan (static methodlardan) ve döngülerden egzersizler yaptık. Dersin sonunda ise yazdığımız fonksiyonları kullanarak tüm elemanları farklı bir diziyi sıralayan bir fonksiyon yazdık. Dersden sonra ise C++ dersi iptal olduğundan biraz vaktimiz kalmıştı, ve bir diziyi ters çeviren özyinelemeli (recursive) bir fonksiyon yazdık.

public class Ders4 {
 
 static void ekranaBas(int[] dizi) {
  for (int i = 0; i < dizi.length; i++) {
   System.out.println(dizi[i]);
  }
 }
 
 static int maksimum(int[] dizi) {
  int maks = dizi[0];
  
  for (int i = 0; i < dizi.length; i++) {
   int suanki = dizi[i];
   
   if (suanki > maks) 
    maks = suanki;
  }
  
  return maks;
 }
 
 static int kacinci(int[] dizi, int k) {
  int sayac = 0;
  for (int i = 0; i < dizi.length; i++) {
   int suanki = dizi[i];
   if (suanki < k)
    sayac++;
  }
  return sayac;
 }
 
 static int medyan(int dizi[]) {
  for (int i = 0; i < dizi.length; i++) {
   int suanki = dizi[i];
   
   if (kacinci(dizi, suanki) == dizi.length / 2)
    return suanki;
  }
  
  throw new IllegalArgumentException();
 }
 
 static int ninci(int dizi[], int n) {
  for (int i = 0; i < dizi.length; i++) {
   int suanki = dizi[i];
   
   if (kacinci(dizi, suanki) == n)
    return suanki;
  }
  
  throw new IllegalArgumentException();
 }
 
 static int[] sirali(int[] dizi) {
  int[] siralanmis = new int[dizi.length];
  for (int i = 0; i < dizi.length; i++) {
   int suanki = dizi[i];
   siralanmis[kacinci(dizi, suanki)] = suanki;
  }
  return siralanmis;
 }
 
 static void swap(int[] dizi, int a, int b) {
  int tmp = dizi[a];
  dizi[a] = dizi[b];
  dizi[b] = tmp;
 }
 
 static void reverseBetween(int[] str, int beg, int end) {
  if (beg > end) 
   return;
  swap(str, beg, end); 
  reverseBetween(str, beg + 1, end - 1);
 }
 
 static void reverse(int[] str) {
  reverseBetween(str, 0, str.length - 1);
 }
 
}

George Boole'nin 200. Doğum Günü

Bugün, Goerge Boole'nin 200. doğum günü olduğunu Google sayesinde öğrendim ve yayınladıkları doodle çok hoşuma gitti. Bu yüzden sizinle yanıp sönen bu harflerin ne anlama geldiğini ve birkaç ilginç bilgiyi paylaşmak istiyorum.