Advent of Code: 10. Gün
Advent of Code'un çift basamaklı ilk gününden herkese selamlar!
İki basamaklı günlere girerken dahi problem çok zor gelmedi. Özellikle önceki günün problemine göre. İlk kısımda basit bir dinamik programlama ile, hatta tek boyutlu bir dinamik programlama "tablo"su ile, sorunu çözdüm diyebilirim. Aslında genişlik-öncelikli gezinti (breadth first search) yapmak gerektiği ile ilgili Reddit'ten ufak bir spoiler yedim. Ben başta derinlik-öncelikli gezinti (depth first search) ile çözmüştüm ama zaten kolaydı genel olarak.
Her şey bu problemin ikinci kısmına gelene kadar güzeldi. Problemin tanımı basit, fakat çözmesi bir o kadar zordu. Nitekim teknik olarak çözemedim. Kafamı gün boyu kurcalayıp durdu. Ta ki Reddit'e bakana kadar. Kurcalamasının normal olduğunu anladım baktığımda. Soru aslında bir doğrusal programlama (linear programming) sorusuymuş! Hesapsal geometri dersinde doğrusal programlama ve dışbükey gövde (convex hull) arasındaki bağlantıyı görmüştük fakat burada boyut sayısı görmüş olduğumuz 2'nin çok üzerinde çıkıyordu. Sonuç olarak SCIP isminde bir doğrusal programlama çözücü buldum. Her ne kadar C arayüzünden bağlanabilecek olsam da kütüphane işleriyle uğraşmak yerine kendi LP dosya biçiminde girdi olarak vermeyi düşündüm soruları. Biraz kabuklarla (shell) uğraştıktan sonra sonuca vardım, fakat yanlıştı. En son pes edip başka birinin kodunu indirip çözdürüp cevabı yolladım fakat sonrasında uğraşmaya başladım. Bütün her şey doğru, başkalarının doğru çalışan kodlarıyla da aynı gözükmesine rağmen benim sonucum farklıymış. En son bir daha pes edip Gemini'ye sordum sebebini, cevap olarak da SCIP'in varsayılan olarak tamsayı değil reel sayı çözdüğünü söyledi. Zaten simplex algoritması reel sayıları güzel çözebiliyor, kendim de yazabilirdim. Sırf tamsayı doğrusal programlama (integer linear programming, ILP) yapsın diye indirmiştim SCIP'i! SCIP'e sonuçların tamsayı olduğunu söyleyince ben de aynı sonucu alır oldum nitekim.
Demek ki neymiş, her problem elle çözülmeyebiliyormuş. Bazen kendimizden daha büyük bir programdan yardım almak işe yarayabiliyormuş. Şu ana kadarki problemlere göre insanın kibrini biraz kırabilen bir problemdi açıkçası. "Ben bunu nasıl yapacağım ya şimdi?" sorusunu sordurdu cidden.