Calculator the Game ve Çözümü (Function Pointers)

Merhaba. Bu yazı uzunca bir aradan sonra yine bir oyunla ilgili. Bir miktar yazılımdan bahsedeceğim ve Matlab kullanacağım. 

Yaz başında telefonuma "Calculator: The Game" adında bir oyun indirmiştim. Oyunun amacı bir sayıyla başlayıp verilen işlemler aracılığıyla ve sınırlı sayıda işlemle hedef sayıya ulaşmak. Oyunun videosu: https://www.youtube.com/watch?v=w5yyY341-4A Oyun, Google Play'de 5 milyondan fazla indirilmiş yani bilindik bir oyun olduğunu varsayıyorum.

Yandaki ekran görüntüsü ilk bölümden. Bu bölüm sıfırla başlıyor. Verilen işlem +1 ve amaç iki hamlede 2 elde etmek. Açık ki, başka da işlem olmadığından yapılması gereken iki kere +1'e basmak.

Bölüm 30

İlerleyen seviyelerde, dört işlem dışında işlemler ekleniyor. Örn. kaydırma '<<' işlemi 4321'i 432 yapıyor. Sayı ekleme, üzerinde sayı olan yan görüntüdeki gibi mor tuşlar. Mor 5, 432'den 4325 yapıyor. Yine yanda görülen dönüşüm tuşları sırayla sayının içindeki 1'leri 2 ( 1 => 2 ) ve 2'leri 3 yapıyor ( 2 => 3 ). Yandaki bölümün çözümü: 1, 2, 2=>3, 1=>2, 2, 1. SUM düğmesi sayının basamak değerlerinin toplamı olan sayıyı veriyor. Inv10 her basamağı 10'dan çıkarıyor. [+]1 bütün tuşların değerine 1 ekliyor. Store, aynı sayıyı birden fazla kullanmak için hafızaya alıyor. Shift, assembly'deki rotation'a karşılık geliyor. Mirror, sayının ayna görüntüsünü sayının sonuna ekliyor.

Örnekler:
4325 (SUM) -> 14 (SUM) -> 5
4325 (Inv10) -> 6785
4325 (Shift>) -> 5432 (<Shift) -> 4325
25 (Mirror) -> 2552 -> (Mirror) 25522552

Portallar, bir tuş olmayıp şunu yapıyor: Yüzler basamağından birler basamağına bir portal, işlem sonucu çıkan sayı 100'den büyükse yüzler basamağındaki sayıyı birler basamağına ekler.

Bölüm 60

Bu oyunu uzunca zaman oynadım. Oynarken bazı bölümlerin çözümü için bütün olasılıkları denemenin daha pratik olduğunu farkettim. Örneğin yukarıdaki ekran görüntüsü (Bölüm 30) ele alındığında, çözüm zor olmasa da denemek için 4 tuşa 6 kere basmak, 4⁶ = 4096 farklı kombinasyon gerektirir. Altmışıncı bölüm daha zor görünüyor ama iki tuşa 5 kere basmanın 2⁵ = 32 farklı kombinasyonu var. Bazı bölümleri akıl yürüterek çözmek yerine denemek daha hızlı sonuç veriyor.

Deneyerek (brute force) çözerken, bilgisayar kullanmamak düşünülemez, öyle ki 4096 çokmuş gibi görünse de bilgisayarda bir kaç saniyede denenebilir. Önemli olan soruna doğru şekilde yaklaşmak.

İşlemler kodun içinde yazılırsa, doğrusal olarak çalışan bir kod farklı sıralarla çağırılamaz. Tuşlara ait işlemlerin fonksiyon olarak tanımlanması gerekir. Tuş sayısı kadar fonksiyon bulunmalı veya başka bir deyişle her tuş fonksiyon olarak yazılmalı.

Tuşlara nasıl basılabilir? Örneğin beş tane tuş da olsa birine ardarda basmak sorunu çözüyor olabilir veya önce ilkine sonra ikincisine vs. Tuşların numaralandırıldığını düşünelim. Şimdilik tuş sıralamasının önemi olmasın. Beş tuş için beş farklı rakam kullanılsın. İşlem sayısı üçse, birinci tuşa ardarda basmak 111'e, tuşlara sırayla basmak 123'e karşılık gelir. Genellenirse, tuş sayısı kadar rakam ve hamle sayısı kadar basamak olur. Bu örnekte, tüm dizilimler 5³ = 125 olduğundan burada hepsini saymaya gerek yok ama 125, 134, 225, 334, 415, 531, 555 şeklinde örneklendirilebilir. Bu arada tuşlar numaralandırılırken 5 yerine 0 kullanılsaydı problemin 5lik sayı sistemiyle olan bağlantısı fark edilebilir.

125, sırayla 1., 2. ve 5. tuşlara basmak veya 1., 2. ve 5. fonksiyonları çağırmak anlamına gelir. O halde sayının değerlerine göre fonksiyonlar belirli sıralarla nasıl çağırılmalı? Bunu yapmanın en kolay yolu fonksiyonların kendisiyle değil göstericileriyle (pointer) çalışmak. Bu biraz karışık gelebilir. Hazır karışık demişken, C'de bu aşağıdaki gibi yapılır: 

#include<stdio.h>

void fonk1(int i)    {
  fprintf(stdout, "Fonk1: %d\n", i);
}

void fonk2(int i)    {
  fprintf(stdout, "Fonk2: %d\n", i);
}

void fonk3(int i)    {
  fprintf(stdout, "Fonk3: %d\n", i);
}


int main(int argc, char* argv[])    {
  void (*fparray[3])(int i);
  int i;
 
  fparray[0] = fonk1;
  fparray[1] = fonk2;
  fparray[2] = fonk3;
 
  for(i = 0; i < 3; i++)    {
    (*fparray[i])(i);
  }
 
  return 0;
}

Yukarıda tamsayı argüman alan basit üç fonksiyon tanımlanıyor. main() içinde bu fonksiyonlar için üç elemanlı void fonksiyon pointer dizisi oluşturulup göstericiler bu diziye atanıyor. C'de fonksiyonun adı zaten o fonksiyonun göstericisi yani ilk komutunun adresi olduğu düşünülürse atamalar için herhangi bir operatöre (*, &) gerek olmadığı görülür. For döngüsünde dizinin elemanları sırayla i argümanıyla çağırılır.

Bölüm 192

C'de fonksiyon göstericileri biraz zor (en azından benim için). Hangi parantez nerede olmalı kafa karıştırıcı olabiliyor. Ben çözüm için C yerine Matlab kullandım. Matlab'de bunu kodlamak daha kolay. C'deki & operatörü benzeri, Matlab'de fonksiyon göstericiler için @ bulunuyor. Göstericiler için matris değişken yerine hücre (cell) değişken ve argümanların fonksiyona uygulanması için feval komutunu kullanmak gerekiyor. Ben kodda sayı sistemleriyle uğraşıp tek for döngüsünde halletmek yerine tuş sayısı kadar içiçe for döngüsü kullandım.

Örneğin 192. seviye zordu. Bunun için kod yazmam gerekti. Bu bölümde beş tuş ve altı hamle var yani çok sayıda dizilim var. Binler basamağından birler basamağına bir portal bulunuyor. Önce tuşlara fonksiyon yazmakla başladım. Hatırlatma: Matlab'de fonksiyonlar kendi adlarını taşıyan dosyalara kaydedilmeli. İlk fonksiyon tus1.m dosyasında, ikinci fonksiyon tus2.m dosyasında vb.

function deger = tus1(deger)
  % +8
  deger = deger + 8;
endfunction

function deger = tus2(deger)
  % *4
  deger = deger * 4;
endfunction

function deger = tus3(deger)
  % Inv10
  s_deger = int2str(deger); % Sayiyi string'e donustur
  for k1 = 1:length(s_deger)
    if (s_deger(k1) != '0')
      s_deger(k1) = int2str(10 - str2num(s_deger(k1))); % karakterleri 10dan cikar
    endif
  endfor

  deger = str2num(s_deger); % tekrar sayıya dönüştür.

endfunction

function deger = tus4(deger)
  % sonuna 9 ekle
  deger = deger * 10 + 9;
endfunction

function deger = tus5(deger)
  % 7 => 0
  if( floor(deger / 100) == 7 )
    deger = deger - 700;
  endif
 
  if( mod(floor(deger / 10), 10) == 7 )
    deger = deger - 70;
  endif
 
  if(mod(deger, 10) == 7)
    deger = deger - 7;
  endif
 
endfunction

Portalı, her fonksiyondan dönen değerin girdiği ayrı bir fonksiyon olarak düşündüm. Fonksiyonun sonucu portal fonksiyonuna giriyor ve düzenlenmiş olarak çıkıyor. Portal fonksiyonuna "girdicikti" adını verdim:

function deger = girdicikti(deger)
  if(deger > 999)
    binler = floor(deger / 1000);
    deger = mod(deger, 1000) + binler;
    if(deger > 999)
      girdicikti(deger)
    endif
  endif
endfunction

Ana fonksiyon aşağıdaki gibi:

ilkdeger = 189;

% Function array
f_a = { @tus1, @tus2, @tus3, @tus4, @tus5 };

for k1 = 1:5
  for k2 = 1:5
    for k3 = 1:5
      for k4 = 1:5
        for k5 = 1:5
          %for k6 = 1:5
           
            adim1 = girdicikti( feval (f_a{k1}, ilkdeger) );
            adim2 = girdicikti( feval (f_a{k2}, adim1) );
            adim3 = girdicikti( feval (f_a{k3}, adim2) );
            adim4 = girdicikti( feval (f_a{k4}, adim3) );
            adim5 = girdicikti( feval (f_a{k5}, adim4) );

            if(adim5 == 500)
              printf("%d %d %d %d %d\n", k1, k2, k3, k4, k5);
              break
            endif
          %endfor
        endfor
      endfor
    endfor
  endfor
endfor

ilkdeger değişkeni bir fonksiyona giriyor. Bir tuşa basılması (fonksiyon) sonucu adim1 değişkeni oluşuyor. Sonra adim1'den ikinci fonksiyonla adim2 oluşuyor... İlginç bir şekilde bu bölüm iki farklı şekilde ve 6 yerine 5 işlemle çözüldü. Benim bilgisayarımda çözüm ortalama 15.96 sn sürdü. Program iki farklı çıktı üretiyor:

Bölüm 199

2 5 4 1 5: 189 (x4) -> 756 (7 => 0) -> 056 (9) -> 569 (+8) -> 577 (7 => 0) -> 500
4 2 1 4 2: 189 (9) -> 900 (x4) -> 603 (+8) -> 611 (9) -> 125 (x4) -> 500

199. seviye için de bir kod yazdım. Bu bölümde 4⁶ = 4096 kombinasyon var. tus3 bir öncekiyle aynı olduğundan yazmadım.

function deger = tus1(deger)
  % sonuna 7 ekleme
  deger = deger * 10 + 7;
endfunction

function deger = tus2(deger)
  % 3 => 5
  deger = str2num(strrep(num2str(deger), '3', '5'));
endfunction

function deger = tus4(deger)
  % shift >          3002 => 2300
  if(deger > 999)
    deger = mod(deger, 10) * 1000  +  floor(deger / 10);
  elseif(deger > 99)
    deger = mod(deger, 10) * 100  +  floor(deger / 10);
  elseif(deger > 9)
    deger = mod(deger, 10) * 10  +  floor(deger / 10);
  endif
endfunction

Onbinler basamağından birler basamağına portal:

function deger = girdicikti(deger)
  if(deger > 9999)
    onbinler = floor(deger / 10000);
    % onbinler basamagini al
    deger = mod(deger, 1000) + onbinler;
    % birler basamagina ekle
    if(deger > 9999)
      girdicikti(deger)
    endif
  endif
endfunction

Ana fonksiyonda bir öncekinden farklı olarak tuş sayısını değişkene atayıp for'ları bu değişkene kadar çalıştırdım:

clc
clear

ilkdeger = 3002;

f_a = { @tus1, @tus2, @tus3, @tus4 };
lfa = length(f_a);

for k1 = 1:lfa
  for k2 = 1:lfa
    for k3 = 1:lfa
      for k4 = 1:lfa
        for k5 = 1:lfa
          for k6 = 1:lfa
            adim1 = girdicikti( feval (f_a{k1}, ilkdeger) );
            adim2 = girdicikti( feval (f_a{k2}, adim1) );
            adim3 = girdicikti( feval (f_a{k3}, adim2) );
            adim4 = girdicikti( feval (f_a{k4}, adim3) );
            adim5 = girdicikti( feval (f_a{k5}, adim4) );
            adim6 = girdicikti( feval (f_a{k6}, adim5) );
            if(adim6 == 3507)
              printf("%d %d %d %d %d %d\n", k1, k2, k3, k4, k5, k6);
              return
            endif
          endfor
        endfor
      endfor
    endfor
  endfor
endfor

Bu bölüm altı adımda çözüldü. Çözüm "1 1 2 3 4 1" ve ortalama 0.68 sn'de çözülüyor:

3002 (7) -> 30 (7) -> 307 (3 => 5) -> 507 (Inv10) -> 503 (Shift>) -> 350 (7) -> 3507

Bu bölümle birlikte oyun bitiyor ve oyun sonu videosu başlıyor. Bu yazıda anlattığım yaklaşım oyunun bir çok bölümüne uygulanabilir ama Store ve daha önemlisi [+]2 gibi tuşlara uygulamak zor. İkinci tuş için global bir artım değişkeni tanımlanarak her fonksiyondaki değerler buna göre düzenlenebilir. Benim zorlandığım sorularda bu tür tuşlardan bulunmadığından kodunu yazmam gerekmedi.