Advent of Code: 4. Gün
Advent of Code'un 4. gününün gönderisinden tekrardan selamlar!
3. güne kıyasla 4. gün gerçekten daha zordu diyebilirim. Hatta aslında optimal bir çözüm yapmadığımı düşünüyorum, her zamanki gibi girdiler yeterince küçük olduğu için düz çözüm ile sonuca ulaşabildim iki kısımda da.
Problem aslında bir tür Conway'in Hayat Oyunu simülasyonu denebilir. Elimizde bir ızgara var, her bir elemanı ya dolu ya boş olabiliyor. İlk kısımda sorduğu soru aslında basit bir hücresel otomatın tek nesil sonrası. Hatta bu hücresel otomatın kuralları zaten hâlihazırda basit olan Conway'in Hayat Oyunu'nun kurallarından bile daha basit. Tahminim, Conway'in Hayat Oyunu'nun aksine tam olarak Turing complete bile olmadığı yönünde çünkü hücre oluşturmak başlangıç sonrasında mümkün değil.
Ben de bütün ızgarada döngü dönüp bütün hücrelerin komşularına baktım. Zaten bu komşuları uygun şekilde sayınca cevap direkt çıkıyor. İkinci kısımda ise sistem stabil hâle gelene kadar simülasyonu devam ettirmemiz gerekiyor. Burada çift tamponlama kullandım ki önceki nesilde yaptığım değişiklikler yarı yolda sonraki nesli etkilemesin, herkes her zaman önceki nesli kullansın. Bu ikisi arasında gidip geldiğim için nesiller hafıza ayırmak zorunda da kalmadı. Yoksa her seferinde yeni nesil oluşturmak çok da mantıksız değil aslında, daha kolay olur nitekim.
Aslında düşününce algoritmik olarak bundan daha optimal bir çözüm olmayabilir. Belki kuralları çok basit olduğu için matematiksel bir yolu vardır ama bildiğim kadarıyla Conway'in Hayat Oyunu'nun nesil sonrasını arayı simüle etmeden bulmanın bir yolu yok. Varsa elbette bu probleme de benzeri bir yaklaşım gelebilir. Bu sayede 'dan 'e iner. Burada hücre sayısı ise durağanlaşma için gerekli nesil sayısı.
Çözdükten sonra Reddit'e biraz göz attığımda gerçekten de insanların çözümü sormaktan ziyade hemen görselleştirdiklerini gördüm. Hoş gerçi daha önceki günler de görselleştirilmişti bolca ama bu sefer gözüme daha çok çarptı. Belki ileride ben de yaparım, bu problem görselleştirmek için birebir nitekim.