Herkese Merhabalar,

Google bir kaç senedir tüm dünyada programlama ve algoritmalar üzerine bir yarışma düzenliyor. Bu yarışma kapsamında, yarışmanın katılımcılarına karmaşık algoritmik problemler veriliyor ve istenilen data kümeleri için yine verilen formatta sonuçlar oluşturacak algoritmalar yazılması gerekiyor. Son olarak bu sonuç dosyaları Google’ın sistemine yükleniyor ve skor hesaplanıyor. Yarışma 2 aşamadan oluşuyor 1. aşama online eleme. İkinci aşama ise ilk 30’a giren gruplar bir merkezde yarışıyor. Ben de yarışmaya 2016 ve 2017 yıllarında katıldım. Bu yazıda 2017 yılındaki online eleme sorusu ve pratik sorusu hakkında paylaşımlar yapmak istiyorum. Bu arada bu soruları 4 saat içerisinde çözememiz gerekiyor bu nedenle kodlar hızlı yazıldı hata içerebilir fakat her iki kod da google’ın sisteminde oldukça iyi puanlar alıyordu.

*Yarışmada yazdığımız çözümlere yarışma sorularına ve örnek datalara bu bağlantıdan ulaşabilirsiniz *

Pratik Sorusu: Pizza

İlk soru “Pizza” sorusu. Bu soruda bir pizzayı istenilen maddelerden en az içerek şekilde parçalamamız isteniyor. Amaç pizzanın mümkün olduğunca fazla kısmını kullanmak. Pizzamız dikdörtgen ve ilk kısımda pizza sınıfı oluşturuluyor. Bunun için dosyadan ilk satır okunuyor ve bu satır, sütun ve içerik bilgisi dosyadan ‘parse’ edilip sınıfıun özellikleri olarak bir matrise kopyalanıyor. Kodun devamında ise belirlenen özelliklerde dilimler oluşturmak üzerine. Dilim geçerli bir dilim mi? Dilim içerisindeki domates, mantar sayısı kaç şeklinde sorulara cevap veren methodlar var. Dilim hakkında verileri alan fonksiyonlar eklendikten sonra algoritmayı oluşturduk. Amacı en köşeden başlayarak gerekli dilimi oluşturduktan sonra sonraki dilime geçiyor. Daha sonra ikinci bir tur atıp genişletilebilecek dilimlere göz atıyor. Ve eğer dilim genişletilebilir durumdaysa genişletiyor pizzanın daha büyük bir kısmını kullanabilmek için. ‘Commit’ fonksiyonu ile de değişlikler matrise kaydediliyor. Böylece zaten kullanımda olan parçalar diğer dilimlerde kullanılamıyor. İkinci tur dolaşımda anlık olarak o dilimi ‘decommit’ yapıp o çevrede daha büyük bir dilim oluşturmaya çalışıyor. Son olarak başarı oranını hesaplayan bir fonksiyon var. Eğer algoritma üzerinde değişiklik yaparsanız bu fonksiyonu kullanarak performansını deneyebilirsiniz.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

class pizza:
    def __init__(self, file):
        f = open(file, 'r')
        fline = f.readline()
        [R, C, L, H] = fline.split(' ')
        self.L = int(L)
        self.H = int(H)
        self.R = int(R)
        self.C = int(C)
        self.Matrix = []
        self.Matrix2 = []
        self.result = []
        self.resultS = []
        for index, line in enumerate(f):
            self.Matrix.append([])
            self.Matrix2.append([])
            for i in range(0, self.C):
                self.Matrix[index].append(line[i])
                self.Matrix2[index].append(False)

    def calculate(self):
        # print('Calculating')
        for i in range(0, self.R):
            for j in range(0, self.C):
                if self.Matrix2[i][j] is False:
                    self.trycreateSlice(i, j)
        
        for index,curSlice in enumerate(self.result):
            self.decommitResult(curSlice)
            for i in [3,2,1,0]:
                for j in [3,2,1,0]:
                    trySlice = slice(curSlice.r1, curSlice.c1, curSlice.r2 + i, curSlice.c2 + j)
                    if self.testSlice(trySlice) is True:
                        #print 'updated'
                        self.result[index].r1 = trySlice.r1
                        self.result[index].c1 = trySlice.c1
                        self.result[index].r2 = trySlice.r2
                        self.result[index].c2 = trySlice.c2
                        for i in range(trySlice.r1, trySlice.r2 + 1):
                            for j in range(trySlice.c1, trySlice.c2 + 1):
                                self.Matrix2[i][j] = True
                        break
        

    def trycreateSlice(self, r, c):
        # print(r,c),'start'
        for i in range(0, 15):
            for j in range(0, 15):
                trySlice = slice(r, c, r + i, c + j)
                if self.testSlice(trySlice) is True:
                    # print 'finded'
                    self.commitResult(trySlice)
                    break
        return (r, c)

    def testSlice(self, slice):
        test = False
        if (((slice.r2 - slice.r1 + 1) * (slice.c2 - slice.c1 + 1)) > self.H) | ((slice.r2 + 1) > self.R) | ((slice.c2 + 1) > self.C):
            # print '>boundries'
            a = 5
        else:
            tNum, mNum = self.getNumbers(slice)
            avaible = self.getAvaible(slice)
            if avaible is True:
                if(mNum >= self.L) & (tNum >= self.L):
                    test = True
            else:
                # print 'not Avaible'
                a = 5
        return test

    def getAvaible(self, slice):
        avaible = True
        for i in range(slice.r1, slice.r2 + 1):
            for j in range(slice.c1, slice.c2 + 1):
                if self.Matrix2[i][j] == True:
                    avaible = False
        return avaible

    def getNumbers(self, slice):
        tNum = 0
        mNum = 0
        for i in range(slice.r1, slice.r2 + 1):
            for j in range(slice.c1, slice.c2 + 1):
                if self.Matrix[i][j] == 'T':
                    tNum += 1
                elif self.Matrix[i][j] == 'M':
                    mNum += 1
        return tNum, mNum

    def commitResult(self, slice):
        self.result.append(slice)
        # print 'done',str(r1)+" "+str(c1)+" "+str(r2)+" "+str(c2)
        for i in range(slice.r1, slice.r2 + 1):
            for j in range(slice.c1, slice.c2 + 1):
                self.Matrix2[i][j] = True

    def decommitResult(self, slice):
        # print 'done',str(r1)+" "+str(c1)+" "+str(r2)+" "+str(c2)
        for i in range(slice.r1, slice.r2 + 1):
            for j in range(slice.c1, slice.c2 + 1):
                self.Matrix2[i][j] = False

    def convertRestultString(self):
        for slice in self.result:
            self.resultS.append(str(slice.r1) + " " + str(slice.c1) +
                           " " + str(slice.r2) + " " + str(slice.c2))    

    def printSucces(self):  
        trueC = 0
        falseC = 0
        for i in range(0, self.R):
            for j in range(0, self.C):
                if self.Matrix2[i][j] == True:
                    trueC += 1
                else:
                    falseC += 1
        print "Score: ", trueC, " / ", trueC+falseC

class slice:
    def __init__(self,r1,c1,r2,c2):
        self.r1 = r1
        self.c1 = c1
        self.r2 = r2
        self.c2 = c2


mypizza = pizza('medium.in')
# print mypizza.Matrix
# print mypizza.Matrix2
mypizza.calculate()
mypizza.convertRestultString()
s = str(len(mypizza.resultS))+"\n"
for res in mypizza.resultS:
    s += res + "\n"
file = open("medium.txt","w")
file.write(s)
file.close()


mypizza.printSucces()

Online eleme sorusu: Streaming Videos

Bu soruda ise video izleme gecikmesini azaltmak için videoları ‘cache’ sunuclara yerleştirmemiz isteniyor. Yüksek puan almak için toplam gecikme süresi minimum olmalı. Bu kapsam da ilk aşamada gerekli sınıflar oluşturuldu. Daha sonrasında bu sınıflar arasında bağlantılar oluşturuldu. Algoritmanın amacı herhangibir bir cache serverın bütün videoları için latency hesaplayıp sonra bunları skorlayarak bir optimizasyon yapmak. Burda tabi bağlantıları yapmak biraz zor oldu benim açımdan. Pizza sorusuyla karşılaştırınca çok daha fazla farklı sınıf olduğunu farketmişsiniz. Burda çözümü anlatmanın çok bir anlamı olmadığını düşünüyorum. Daha çok yarışma hakkında bir kaç izlenimimden bahsetmek isterim. Yarışmada farkettiğiniz üzere aslında tam olarak çözümü belli olmayan sorular soruluyor. Daha doğrusu mutlak doğru sonuç var ama onu hesaplamak imkansız bir seviyede. Yani Brute force ile neredeyse sonsuz olasılıkla karşı karşıya kaldığımız sorular soruluyor. Lütfen soruları çözerken hep onu dikkat alın. Sürekli algoritmanınızın karmaşıklığına dikkat ederek geliştirin. Ben de bu konuda yeterince tecrübeli olmadığım için bir kaç kere büyük data kümelerinde sonsuz işleme doğru giden algoritmalar yazdım. İkinci önerim ise kesinlikle verilen datalara bakarak çözümünüzü üretin. Çünkü bütün sorularda genelde 3 4 adet farklı data kümesi verilliyor ve genelde her bir data farklı bir şeyi ölçüyor. Biri için geliştirdiğiniz algoritma diğerlerine uymayabiliyor. Bugünlük bu kadar daha ayrıntılı sorularınızı her zaman sorabilirsiniz. Görüşmek üzere

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

class scoring:
    def __init__(self,video,score):
       self.video= video
       self.score = score
    def __lt__(self, other):
         return self.score > other.score + 5 
         
class connection:
    def __init__(self,ep,cacheNum,latency):
        self.ep = ep
        self.cacheNum = cacheNum
        self.latency = latency

class video:
    def __init__(self, id , size):
        self.id = id
        self.size = size

class cache:
    def __init__(self, id , capacity):
        self.id = id
        self.capacity = capacity
        self.videos = []
        self.endpoints = []

    def addVideo(self,video):
        if self.capacity >= video.size: 
            self.videos.append(video)
            self.capacity = self.capacity - video.size
            return True
        else:
            return False
        

class endpoint:
    def __init__(self,id,latencyDataC,connectionNumber):
        self.id = id 
        self.latencyDataC= latencyDataC
        self.connections = []
        self.requests = [] 

class request:
    def __init__(self,reqNumber, videoID, endpointID,count):
        self.reqNumber = reqNumber
        self.videoID = videoID
        self.endpointID = endpointID
        self.count = count


class solver:
    def __init__(self, file):
        self.videos = []
        self.eps = []
        self.requests = []
        self.caches= []
        f = open(file, 'r')
        fline = f.readline()
        [V, E, R, C, X] = fline.split(' ')
        self.videoCount = int(V)
        for indexC in range(0,int(C)):
            c = cache(indexC, int(X))
            self.caches.append(c)
        fline = f.readline()
        for index, size in enumerate(fline.split(' ')):
            v = video(index,int(size))
            self.videos.append(v)
        for currentEpID in range(0,int(E)):
            fline = f.readline()
            [latencyDataC, connectionNumber] = fline.split(' ')
            ep = endpoint(currentEpID,int(latencyDataC),int(connectionNumber))
            self.eps.append(ep)
            for i in range(0,int(connectionNumber)):
                [cNUm,latency] = f.readline().split(' ')
                c = connection(ep,int(cNUm),int(latency))
                ep.connections.append(c)
                self.caches[int(cNUm)].endpoints.append(self.eps[currentEpID])
        for curReqId in range(0,int(R)):
            [reqVideoID,reqEpID,reqCount] = f.readline().split(' ')
            r = request(curReqId,int(reqVideoID),int(reqEpID),int(reqCount))
            self.requests.append(r)
            self.eps[int(reqEpID)].requests.append(r)


    def getvideosofcache(self,cache):
        #print "cache id:", cache,
        scoreList = []
        for i in self.videos:
            s = scoring(i,0)
            scoreList.append(s)
        for ep in cache.endpoints:
            for req in ep.requests:
                curLat = self.getlatency(cache,ep)
                score = (req.count*(ep.latencyDataC-curLat))
                #print "videoid : ", req.videoID, "ep: ", ep.id, "req count", req.count, "dc latiency: ", ep.latencyDataC, "connect latency",curLat, "puan", score)
                scoreList[req.videoID].score += score
                #print "videoid : ", req.videoID, scoreList[req.videoID].score
        scoreList.sort()
        #for a in scoreList:
            #print a.video.id, a.score, a.video.size
        return scoreList

    def getlatency(self,cache,endpoint):
        ali = 0
        for i in endpoint.connections:
            if i.cacheNum == cache.id:
                ali = i.latency
                break
        return ali

    def solve(self):
        for curCache in self.caches:
            print curCache.id
            scoreList = mysolver.getvideosofcache(curCache)
            for curVideo in scoreList:
                if curVideo.score == 0:
                    break
                curCache.addVideo(curVideo.video)
    
    def result(self):
        result = str(len(self.caches))
        for curCache in self.caches:
            result += "\n"+str(curCache.id)  
            for curVideo in curCache.videos:
                result += " "+str(curVideo.id)
        #print result 
        file = open("videos_worth_spreading.txt","w")
        file.write(result)
        file.close()  



mysolver = solver('videos_worth_spreading.in')
mysolver.solve()
mysolver.result()