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)