Advent of Code: 2. Gün
Tekrardan merhabalar! Advent of Code'un ikinci günü!
Bu seferki problemi gördüğümde şaşırmıştım. Dün de dediğim gibi, AoC gün geçtikçe zorlaşması gereken bir etkinlik olmalıyken ilk güne kıyasla çok daha kolay bir soru geldi bu sefer.
İkinci günde de Teal kullandım. Lua'nın cidden hoş bir hissiyatı var. Girdiyi alması da görece kolay oluyor.
İlk kısımda girdiyi aldıktan sonra verilen aralıklardaki bütün sayıları denedim, ve sonuç doğru oldu!
local input = io.read("*a")
local sum = 0
local function part1(n: integer, m: integer)
for i=n,m do
local str = tostring(i)
if #str % 2 == 0 and str:sub(1, #str // 2) == str:sub(#str // 2 + 1, #str) then
sum = sum + i
end
end
end
input:gsub("(%d*)%-(%d*)%,?", function(n: string, m: string) part1(tonumber(n) as integer, tonumber(m) as integer) end)
print(sum)
Evet bütün kod bu kadar. Bütün aralıklardaki tam sayıları ikiye bölüp iki parçası birbirine eşit mi diye bakıyor. Yeterince hızlı da çalışıyor nitekim.
Bu şekilde ilk yıldızımı aldıktan sonra ikinci kısım geldi. İkinci kısım da aslında tek tek deneyerek çok rahat çözülebilen bir kısım. Nitekim ilk başta öyle yaptım:
local n, m = tonumber(ns) as integer, tonumber(ms) as integer
for i=n,m do
local str = tostring(i)
local length = #str
for prefix_length=1,(length // 2) do
if length % prefix_length == 0 then
local rep = length // prefix_length
local prefix = str:sub(1, prefix_length)
local repeated = prefix:rep(rep)
if repeated == str then
sum = sum + i
break
end
end
end
end
Burada ns bir aralığın başı, ms ise sonu. Bu şekilde ikinci yıldızımı da almış oldum!
Fakat bu günün sonu değil bu elbette. İşkillendim baya: bunun daha hızlı bir yöntemi olması lazım diye. Fakat düşünecek çok zaman bulamadım ve sonuç olarak işin hilesine kaçtım. Reddit'e göz attım. Bulduğum yöntem ilginçti ama bir o kadar da akla yatkındı. Temel prensip, aralığı tamamen gezmek yerine aralıktaki tekrarlı sayıların doğrudan kendilerini bulmak, yani sonucu 'den 'ya indirmek bir bakıma. Çıktı hassasiyeti algoritmalarda istenen bir özellik, en azından derslerde gördüğümüz bu şekildeydi. Bunun için de basitçe elimizdeki aralığın basamak sayısı n iken n'in çarpanlarını tek tek sayıyoruz. Her bir çarpan bizim önek uzunluğumuz oluyor. Bu çarpanlar da her ne kadar çalışma zamanında hesaplanabiliyor olsa da, muhtemelen asal sayı bulma algoritmasına benzer olacaktır, basitçe elle girilebilir. Bunun sebebi verilen basamak sayısının çok da abartı büyük olmaması. Bu öneklerin üzerinde döngüyü dönüp gerekli uzunlukta değerleri oluşturup bunları toplayarak sonuca erişebiliyoruz.
Peki ya aralığın başı ve sonundaki basamak sayısı farklıysa? Bunun da çözümünü içeriyordu Reddit'te gördüğüm yorum, çözüm de basitçe aralığı eş basamak sayılı parçalara bölmekti. Mesela 210-5603 aralığı 210-999 ve 1000-5603 olarak değerlendirilmeli. Bu tabii ki teknik olarak aralık sayımızı arttırıyor ama gerçekten arada devasa bir hız farkı oluyor. Ölçümlerimi tam hatırlamıyorum, test de edemiyorum şu anda, ama arada birkaç 10 kat fark olması lazım. Yine de normal kod da saniyeden kısa sürede çalıştığı için sıkıntı yok. Optimizasyona gerek yok yani, kodun kendisini karışıklaştırmaya çok da gerek yok. Kodun kendisi şu şekle geliyor:
local function fast(ns: string, ms: string)
if #ns ~= #ms then
fast(ns, ("9"):rep(#ns))
for i=#ns+1,#ms-1 do
fast("1" .. ("0"):rep(i), ("9"):rep(i + 1))
end
fast("1" .. ("0"):rep(#ms - 1), ms)
return
else
local n, m = tonumber(ns) as integer, tonumber(ms) as integer
local length = #ns -- #ns == #ms due to the else
for _,prefix_length in ipairs(FACTORS[length]) do
local low_prefix, high_prefix = tonumber(ns:sub(1, prefix_length)), tonumber(ms:sub(1, prefix_length))
for prefix=low_prefix,high_prefix do
local repeated = tonumber(tostring(prefix):rep(length // prefix_length)) as integer
if n <= repeated and repeated <= m and not invalids[repeated] then
invalids[repeated] = true
sum = sum + repeated
end
end
end
end
end
Özyineleme, tablo ezberleme, tuhaf metin manipülasyonları... Gerek var mı? Bence yok.
Bu günden öğrendiğim en büyük şey muhtemelen optimize koda muhtemelen ihtiyaç olmadığıdır eğer girdilerimizi tanıyorsak ve girdilerimizin boyutu müsaitse. Yıldızı almak için saatlerce optimizasyon düşünmeye gerek yok sonuç olarak!