Advent of Code: 3. Gün
Üçüncü günün gönderisinden herkese tekrardan merhabalar!
Üçüncü günde canım başka dil çekti aslında. Teal dışında yazdığım, daha iyi öğrenmek istediğim ve yine niş olan bir başka dil olan C3 geldi aklıma. Standart kütüphanesi geniş ama genel olarak oldukça toy bir dil olduğu için denemek mantıklı geldi C3'ü. Aynı zamanda bir tür test de oluyor derleyici için bu sayede. Arada bir iki issue açtığım oluyor sonuçta C3'te.
Problem önceki güne kıyasla daha da kolay çıktı aslında. Gördüğümde pek inanamadım diyebilirim. Zaten ikinci gün ilkinden daha kolaydı, üçüncü gün ikincisinden de kolay olmuştu! Basitçe çözüm, basamak dizisinin en büyük rakamını bulduktan sonra o rakamdan sonra gelen en büyük basamağı bulmaktı. Tek 9 varsa ve ondan sonra sadece 1 olsa da elde ettiğimiz sayı 91 oluyor, bu da bu 9'dan önce 8 olduğu takdirde elde edeceğimiz 89'dan yine de daha büyük. Yani ilk basamağı en büyük aldıktan sonra ikinci basamağı ne alırsak alalım sayının değeri ilk basamağa daha çok bağlı olacak, ikinci basamağın değeri sadece ilk basamağı aynı olan sayılar arasındaki kıyasta fark yaratacak. Buradaki tek sıkıntı en büyük ilk basamağın sonda olması. Bunun için de girdinin son değerini dahil etmiyoruz ilk aramaya.
İkinci kısımda aslında çok az sayıda değişiklik yetti. Artık 2 değil 12 basamaklı olabiliyor. Aslında 12 tane azami değer bulma işlemi ile iş çözülebilirdi ama ben işi daha da genelleştirip herhangi bir n için bulmaya çevirdim. Mantık tamamen aynı kaldı: başımız hep önceki adımda bulduğumuz basamağın hemen sonrası, sonumuz ise girdiden toplam adım sayısı ile adım numarası arasındaki fark kadar öncesi. İkinci işlemi tam anlatamamış olabilirim ama yaptığı şey geriye kalan adımlarda en az bir basamak kalmasını sağlamak aslında.
Bu kadar basit bir çözüm görünce daha hızlı bir çözüm bulmaya çalıştım. Fark ettim ki pencere kaydırarak 12 değil tek gezintide işi çözebilirim, yani işlemi 'den 'e çekmiş olurum. Fakat bunun için hangi basamaktan kaçar tane kalmış olduğunu ve mevcut penceredeki azami değeri bilmem gerekiyordu. Histogram diye ufak bir tür oluşturdum bu değerleri tutan ve birkaç fonksiyon ile bu değerlerin pencereye sayı eklenmesi veya pencereden sayı çıkarılması durumlarında invaryant kalmasını sağladım. Eğer pencerenin solundaki sayı mevcut azami değere eşitse bir basamağı bulmuş oluyoruz demek oluyor, dolayısıyla sağdan bir basamak daha dahil ediyoruz. En başta n-1 basamağı eksik dahil ediyoruz nitekim. Her adımda pencereyi kaydırdığımız için de soldaki basamağı sayıya dahil etsek de etmesek de çıkarıyoruz histogramdan.
İyi hoş güzel ama test ettiğimde bu verimli yöntemin aslında birkaç kat daha verimsiz çalıştığını gördüm! Aslında çok da mantıksız değil, histogramı çok verimli yazmadığım için doğal olarak sabitesi büyük ihtimalle çok daha yüksek bu yöntemin. Nitekim çok da büyük değil, topu topu 12 oluyor, dolayısıyla aslında yine denebilir ilk yazdığım düz algoritma da.
Sonuç olarak neymiş, asimptotik optimizasyonlar her zaman en iyisi değilmiş, girdi boyutunun yeterince büyük olması gerekiyormuş. Belki daha büyük bir girdide dizileri tekrar tekrar dolaşmak pahalı olurdu, fakat AoC'deki girdi boyutları seviyesinde dolaşmak çok da pahalı bir işlem değil.