Advent of Code: 8. Gün
Advent of Code blog gönderi serimin 8. gününden tekrardan merhabalar!
8. günde Eric Wastl'ın gerçekten işi zorlaştırmaya başladığını görebilmek güzel oldu açıkçası. Bu sefer gerçekten biraz zor bir soru vardı: dinamik ayrık küme (disjoint set) oluşumu. Bunun en belirgin örneğini Kruskal'ın asgari kapsam ağacı (minimum spanning tree) algoritmasında görüyorduk, burada da aslında benzer bir soru var. Farklı olarak tek bir ağaç oluşturmak yerine birbirine bağlı bileşenlerin durumunu 1000 kenar (edge) sonrasında bulmamız gerekiyor. Fakat şimdiye kadar çokça dediğim gibi girdiler çok büyük değil, dolayısıyla görece verimsiz bir ayrık küme yapısı ile de iş çözülebilir. Ben bir hash kümesi dizisi kullandım, her bir hash kümesi birer bağlı bileşen (connected component) oluyor burada. Her aşamada eklenen kenarın başı ve sonundaki köşelere bakıyor, eğer herhangi birisi mevcutta bakılan bağlı bileşen içerisinde yer alıyorsa iki ihtimal doğuyor. Eğer daha önce bu kenara temas eden başka bir bağlı bileşen yoksa mevcut bağlı bileşene kenarın köşelerini ekleyip devam ediyor ve bu bileşeni kaydediyor. Bu kaydedilen bileşen bizim "akümülatör" bileşenimiz oluyor, yani bu kenar sayesinde bağlanan bileşenlerin hepsi (yanlış hesaplamıyorsam bir seferde ancak iki tane olabiliyor bunlardan) bu ilk bağlı bileşen ile birleşiyor. Yani eğer daha önce bir bağlı bileşen bulunmuşsa kenarın köşelerini eklemek yerine akümülatör bileşen ile küme birleşimi yapıyor mevcut bağlı bileşeni ve sonrasında da diziden bu bileşeni siliyor.
İkinci kısımda da 1000 kenar denemek yerine aslında Kruskal'ı bitiriyoruz, tek bir bağlı bileşen çıkana kadar devam ettiriyoruz.
Fakat ilk kısımdan itibaren sonucum hep yanlış çıkıyordu. C3'te düzgün bir hata ayıklama deneyimi olmadığı için sorunu da tam anlayamıyordum. Aynı kodu Python'da yazdım ve doğru sonuca ulaştım. Ertesi gün ancak çözebildim sorunu, bileşen boyutları çarpımının negatif olduğu durumlar çıkıyordu! Negatif boyutta bağlı bileşen olamayacağına göre tek bir şüpheli kalıyor ortada: tamsayı taşması. Bütün kodu int yerine long kullanacak şekilde değiştirdiğimde (C3'te long her zaman 64 bit, int ise her zaman 32 bit) nitekim C3 çözümümün de aynı sonuca vardığını gördüm. Python çözümünde bu sorun olmuyor tabii ki Python'daki tamsayılar sınırsız boyutlu olabildiği için. Bu problemden sonra nitekim hep long kullandım eğer gerçekten daha küçük bir tamsayının yeteceğine %100 emin değilsem.
Sözün özü, aritmetik işlemler riskli şeyler. C veya C++ ile yazıyor olsam aslında tanımsız davranış (undefined behavior) temizleyicileri (sanitizer) günümü kurtarabilirdi. C3'te bazı temizleyicilerin desteği var fakat tam nasıl çalışıyor bilmiyorum, ve zaten Windows'ta da her temizleyici çalışmıyor.