Forum: SDL RSS
Kutu Arama Algoritması
Sayfa:  1  2  sonraki 
Avatar
Salih Dinçer #1
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Kutu Arama Algoritması
Merhaba,

Ekranda rasgele yerleştirilmiş renkli kutular var. Bunların hepsi de mouse hareketlerine duyarlı. Tıpkı Mahjong oyunu gibi üstteki taşlar daha öncelikli. Yani altta kalan bir kutunun tamamı başka kutular tarafından kapanıyorsa bunun üzerine tıklayarak kapatmanız mümkün değil. Belli bir sırayı takip etmelisiniz.

Şimdi bu konuda en iyi arama algoritmasını geliştirmeye çalışıyorum. Her ne kadar konuyu SDL'de açmış olsam da işin kuramsal kısmı diziler, hızlı sıralama algoritması gibi şeyler...:)

Sizce nereden başlamalı ve nasıl devam etmeli?
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #2
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Eklemeliyim; ihtiyacımız olabilecek ve/veya başlangıçta sahip olduğumuz veriler şöyle:
  • Mouse tıklama anındaki m(X, Y) bilgisi (m->mouse demek)
  • Ekrandaki kutuların sayısı
  • Her bir kutunun b(X, Y) ve W, H verisi (b-> box demek)
  • Kutuların ekranda oluşturma sırası L(evel)

Aklıma hızı arttırmak için ilk olarak şöyle bir süzgeç(filter) adımı geldi:
  • Tıklanan m(X, Y) noktasından büyük b(X, Y)'lerin hepsini yok farzetmek;
  • Aynı şekilde koorinat ekseninin 2 ve 3 bölgesinde olan ama b(X, Y) ile b(X+W, Y+H) arasında kalmayanları süzüp,
  • Son olarak en üstte olan kutudan başlamak suretiyle (dizi reverse edilebilir) tek tek uygun olanla eşleştirmek...

veee nihayetinde o kutuyu oluşturan nesneyi silip sahneyi yenilemek...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
mert #3
Üye Ara 2010 tarihinden beri · 194 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Mouse tıklama anındaki m(X, Y) bilgisi (m->mouse demek)
Her bir kutunun b(X, Y) ve W, H verisi (b-> box demek)

mouse fare demek olsa box demek de kutu olsa (yazıldığı gibi kısaltmalar değil ama.) Mahjong oynamadığım halde hiç nasıl çözümleneceğini izleyebilirdim sanki.
mert
Avatar
Salih Dinçer #4
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Şuradaki klasik sürümü güzeldir: http://cdn.gamepilot.com/data/1/6/1/16144.swf

Tavsiye ederim...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
mert #5
Üye Ara 2010 tarihinden beri · 194 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Hoşmuş. Teşekkür ederim Salih.
mert
Avatar
Salih Dinçer #6
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Merhaba,

Biraz kafam karıştı ben de olayı görselleştireyim istedim. Zaten algoritma görsel programlama da kullanılacak. Ancak zorlandığımı itiraf etmeliyim! Ortadaki ekran görüntüsünde şu kutular yer almakta:
  #      x    y    w    h
  1 - [ 155, 200, 150, 150 ]
  2 - [ 205, 255, 200, 150 ]
  3 - [ 240, 345, 175, 190 ]
  4 - [ 65, 30, 200, 200 ]
  5 - [ 120, 5, 125, 190 ]

[Resim: http://imageshack.us/scaled/thumb/546/kutular.png]

Buna göre ilk olarak 5. kutu (sonra 4) üzerine tıklanıyor. Bizim algıladığımız biçimde, bir altına ulaşabilmek için en üstte olanı kapamak gerekiyor. Tabi henüz algoritma bunu anlamıyor...:)

Her türlü fikire açığım, teşekkürler...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #7
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
İngilizce aramaya çalıştığımda "collision detection algorithm"a da rastladım. Belki bu konu da onunla çözülen bir problemdir. (?)

En hızlıca aklıma gelen yöntem şu: Düzlemdeki her nokta bir dilimden oluşur. Bu dilimin ilk elemanı o noktaya rastlayan nesnelerden en alttakinin numarasıdır.

Yeni şekil yerleştirildiğinde onun rastladığı bütün noktalara şeklin numarası eklenir. Sonuçta, bir noktaya tıklandığında orada hangi şeklin göründüğü o noktadaki dilimin son elemanıdır.

O noktadan yola çıkarak bu sefer şekli oluşturan bütün noktalara bakılır. Eğer hepsinin de son elemanı aynı numaraya sahipse şekil serbest demektir.

Uyarı: Aklıma ilk gelen algoritma olduğu için büyük olasılıkla en hızlı algoritma değildir. :p

Aslında belki de bir eniyileştirme görülüyor: Şekillerin serbest olup olmamaları yalnızca şekil eklenmesi ve çıkartılması olaylarına bağlı olduğundan, bunu her tıklamada hesaplamak yerine her ekleme ve çıkarmada hesaplamak daha iyi olabilir. Yani her şeklin serbest olup olmadığını belirleyen bir bilgisi tutulur. Yeni şekil yerleştirildiğinde bu bilgisi true'dur. Ortamdan şekil kaldırıldıkça onun noktalarına rastlayan diğer şekillerin artık serbest olup olmadıkları o an hesaplanabilir.

Ali
Avatar
Salih Dinçer #8
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıt için çok teşekkür ederim...:)

Eniyileştirme konusuna başlangıçta çok umursamıyorum. Aksine herhangi bir algoritma benim için mihenk taşı olacağı için eniyileştirme için kılavuz anlamında işe yarayacaktır.

Nesnelerin diziye (sahne kümesine) girerken ve çıkarlarken işlem tekrarının azaltılması iyi fikir gibi görünüyor. Ancak resimde aslında iki tane tıklanabilecek resim var. Ben 5.'nin en üstte olduğunu biliyorum ama 3.'ü de en üstte aslında...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #9
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Salih Dinçer:
Ben 5.'nin en üstte olduğunu biliyorum ama 3.'ü de en üstte aslında...:)

Biliyorum. Bu algoritma verilen bir noktadan yola çıkıyor. O noktada en üstteki dörtgenin numarasına bakıyor. Sonra, o dörtgeni oluşturan bütün konumlardaki en üstteki nokta yine bu dörtgene aitse, dörtgen serbest (en üstte) demektir.

Şu programda uyguladım:

import std.stdio;
import std.array;
import std.string;
import std.conv;
 
struct Nokta
{
    size_t satır;
    size_t sütun;
}
 
struct Dörtgen
{
    Nokta solÜstKöşe;
    Nokta sağAltKöşe;
 
    int opApply(int delegate(Nokta nokta) işlem) const
    {
        int sonuç = 0;
 
        foreach (satır; solÜstKöşe.satır .. sağAltKöşe.satır + 1) {
            foreach (sütun; solÜstKöşe.sütun .. sağAltKöşe.sütun + 1) {
                sonuç = işlem(Nokta(satır, sütun));
 
                if (sonuç) {
                    return sonuç;
                }
            }
        }
 
        return sonuç;
    }
}
 
struct Kağıt
{
    alias size_t[] Konum;       // Her konum bir dörtgen numarası dilimi
    alias Konum[] Satır;        // Her satır Konum diliminden oluşuyor
    alias Satır[] Satırlar;     // Bütün düzlem
 
    Satırlar konumlar;          // Üç boyut: satır, sütun, ve dörtgen numaraları
 
    Dörtgen[size_t] dörtgenler; // Numaradan dörtgene eşleme tablosu
 
    this (size_t boy, size_t en)
    {
        konumlar = new Satırlar(boy, en);
    }
 
    void yerleştir(Dörtgen dörtgen, size_t numara)
    {
        // Her konumun en üstüne bu dörtgenin parçası gelir
        foreach (nokta; dörtgen) {
            konumlar[nokta.satır][nokta.sütun] ~= numara;
        }
 
        // Daha sonra numarasından dörtgen elde edebilmek için
        dörtgenler[numara] = dörtgen;
    }
 
    // Dörtgeni oluşturan konumların en üstünde 'numara' varsa true döndürür
    bool serbest_mi(Dörtgen dörtgen, size_t numara) const
    {
        foreach (nokta; dörtgen) {
            if (konumlar[nokta.satır][nokta.sütun].back != numara) {
                // Bu dörtgenin en üstte olmadığı bir konum bulduk
                return false;
            }
        }
 
        // Buraya geldiysek dörtgeni oluşturan bütün noktalarda en üstte
        // 'numara' var demektir. Yani dörtgen serbest.
        return true;
    }
 
    void kaldır(Nokta nokta)
    {
        Konum konum = konumlar[nokta.satır][nokta.sütun];
 
        if (konum.empty) {
            writefln("%s konumunda dörtgen yok", nokta);
 
        } else {
            auto dörtgenNumarası = konum.back// En üstteki dörtgenin numarası
            auto dörtgen = dörtgenNumarası in dörtgenler;
 
            // Daha önce yerleştirdiğimize göre eşleme tablosunda bulunmalı.
            assert(dörtgen, format("%s numaralı dörtgen bulunamadı"));
 
            if (serbest_mi(*dörtgen, dörtgenNumarası)) {
                sil_(*dörtgen, dörtgenNumarası);
                writefln("%s numaralı dörtgen silindi", dörtgenNumarası);
 
            } else {
                writefln("%s numaralı dörtgen serbest değil", dörtgenNumarası);
            }
        }
    }
 
    // Bu işlev arayüzün parçası değil; yalnızca bu yapı çağırsın diye...
    private void sil_(Dörtgen dörtgen, size_t dörtgenNumarası)
    {
        foreach (nokta; dörtgen) {
            konumlar[nokta.satır][nokta.sütun].popBack();
        }
 
        dörtgenler.remove(dörtgenNumarası);
    }
 
    void çiz() const
    {
        foreach (satır; konumlar) {
            foreach (konum; satır) {
                // Her konumda en üstte olanı çizeceğiz
                auto görünüm = !konum.empty ? konum.back.to!string : ".";
                writef(" %s", görünüm);
            }
 
            writeln();
        }
    }
}
 
void doldur(ref Kağıt kağıt)
{
    kağıt.yerleştir(Dörtgen(Nokta(3, 3), Nokta(7, 7)), 1);
    kağıt.yerleştir(Dörtgen(Nokta(8, 15), Nokta(10, 18)), 2);
    kağıt.yerleştir(Dörtgen(Nokta(5, 5), Nokta(9, 10)), 3);
    kağıt.yerleştir(Dörtgen(Nokta(4, 4), Nokta(6, 6)), 4);
}
 
void main()
{
    auto kağıt = Kağıt(20, 20);
 
    doldur(kağıt);
    kağıt.çiz();
 
    kağıt.kaldır(Nokta(0, 0));    // Boş bir nokta
    kağıt.kaldır(Nokta(8, 8));    // Kaldırılamaz çünkü serbest değil
    kağıt.kaldır(Nokta(4, 4));    // Serbest
    kağıt.kaldır(Nokta(8, 8));    // Şimdi kaldırılabilir çünkü artık serbest
    kağıt.çiz();
}

Program iki kere çiz() diyor. Çıktısı şöyle:


 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . 1 1 1 1 1 . . . . . . . . . . . .
 . . . 1 4 4 4 1 . . . . . . . . . . . .
 . . . 1 4 4 4 3 3 3 3 . . . . . . . . .
 . . . 1 4 4 4 3 3 3 3 . . . . . . . . .
 . . . 1 1 3 3 3 3 3 3 . . . . . . . . .
 . . . . . 3 3 3 3 3 3 . . . . 2 2 2 2 .
 . . . . . 3 3 3 3 3 3 . . . . 2 2 2 2 .
 . . . . . . . . . . . . . . . 2 2 2 2 .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
Nokta(0, 0) konumunda dörtgen yok
3 numaralı dörtgen serbest değil
4 numaralı dörtgen silindi
3 numaralı dörtgen silindi
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . 1 1 1 1 1 . . . . . . . . . . . .
 . . . 1 1 1 1 1 . . . . . . . . . . . .
 . . . 1 1 1 1 1 . . . . . . . . . . . .
 . . . 1 1 1 1 1 . . . . . . . . . . . .
 . . . 1 1 1 1 1 . . . . . . . . . . . .
 . . . . . . . . . . . . . . . 2 2 2 2 .
 . . . . . . . . . . . . . . . 2 2 2 2 .
 . . . . . . . . . . . . . . . 2 2 2 2 .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .


Ali
Avatar
Salih Dinçer #10
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Anlıyorum, anlamaya çalışıyorum...:)

SDL'ye uyarladıktan sonra tekrar yazacağım....
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #11
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Şu satıra bakalım (iginç olanları harflerle isimlendiriyorum):

 . . . 1 4 4 4 3 3 3 3 . . . . . . . . .
       a b c ç d e f g


a dilimi şu: [ 1 ]

b diliminde en sonda 4 var ama onun altında 1'in parçası var: [ 1, 4 ]

c diliminde en önce 1 vardı; sonra üstüne 3 gelmişti; en sonunda da 4 geldi: [ 1, 3, 4 ]

ç de aynı [ 1, 3, 4 ]

d'deki 3'ün altında 1'in parçası var: [ 1, 3 ]

e, f, ve g'nin altında hiçbir dörtgen yok. Hepsi de yalnızca 3'ten oluşuyor: [ 3 ]

Bu dilimlerin elemanlarını aşağıdan yukarıya kule gibi üst üste düşünürsek aslında şöyleler:

          4 4
        4 3 3 3
. . . 1 1 1 1 1 3 3 3 . . . . . . . . .


4 numaralı dörtgen silinince şu kalıyor:


          3 3 3
. . . 1 1 1 1 1 3 3 3 . . . . . . . . .


Sonra 3 numaralı dörtgen silinince de şu kalıyor:


. . . 1 1 1 1 1 . . . . . . . . . . . .


Ali
Avatar
Salih Dinçer #12
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Ali hocam öncelikle iyi ki varsın...

Tabi bir de küçük bir sitem, böyle güzel bir ortamda herkes olsaydı madem...:)

Belli ki bayram arefesi telaşı; malum Kurban Bayramı. Bu vesileyle herkesin bayramlarını da tebrik ederim. Çünkü hemen akabinde 29 Ekim Cumhuriyet Bayramı da var. Büyüklerin ellerinden, küçüklerin gözlerinden...:D

Böyle bir renkli girişten sonra konuya tekrar dönelim. Çünkü anlayamayınca bir süre ara verdim; bir de bilgisayar değiştirdim. Tavsiye de ederim çünkü önceki yaptıklarımın tümünü bir kenara ittim. Her şeye sıfırdan başladım ve yeni bir temel oturttum. O temelin ekran görüntüleri ve kodu hemen aşağıda:

salih@NB:~/d.ders$ ./kutular                  salih@NB:~/d.ders$ ./kutular
#0 [ 50, 30 ]      [ 250, 120 ] blue          #0 [ 150, 0 ]       [ 150, 10 ]  blue
#1 [ 190, 0 ]      [ 110, 100 ] cyan          #1 [ 170, 0 ]       [ 130, 60 ]  cyan
#2 [ 150, 0 ]      [ 150, 30 ]  green         #2 [ 10, 40 ]       [ 90, 100 ]  green
#3 [ 0, 30 ]       [ 140, 120 ] yellow        #3 [ 180, 0 ]       [ 120, 120 ] yellow
#4 [ 100, 0 ]      [ 200, 110 ] red           #4 [ 190, 10 ]      [ 110, 10 ]  red
#5 [ 50, 40 ]      [ 210, 60 ]  white         #5 [ 30, 20 ]       [ 270, 130 ] white

             TEST 1                                        TEST2

[Resim: http://imageshack.us/a/img255/1390/1kutular.png]                  [Resim: http://imageshack.us/a/img707/4006/2kutular.png]
    import std.string, std.random, std.range;
    import std.stdio, sdlmini;
 
    immutable genişlik  = 30;         /* Hesabın kolay olması için */
    immutable yükseklik = 15;         /* gerçeğin onda biridir!    */
 
    class Kutu {
        size_t id;                    /* 1, 2, 3 ... n+1 */
        SDL_Rect rect;                /* x, y, w, h      */
        clr renk;                     /* uint enums      */
     
      private:
        static size_t _id;
        static size_t nextId() {            /* sıralı sayı üreteçi */
            immutable id = _id++;
            return id;
        }
      public:
        this(clr color, short[] noktalar ...) {
            renk = color;
            rect.x = noktalar[0];
            rect.y = noktalar[1];
            rect.w = cast(ushort)(noktalar[2]);
            rect.h = cast(ushort)(noktalar[3]);
            this.id = nextId();
        }
        
       void exec(SDL_Surface * screen) @property {   /* kutu çizer */
            SDL_FillRect(screen, &rect, renk);
       } 
       
       override
       string toString() const { /* kutunun özelliklerini döndürür */
            auto r = appender!string();
            std.format.formattedWrite(r, "%s", renk);
            return format("#%d [ %d, %d ]\t[ %d, %d ]\t( %s )",
                   id, rect.x, rect.y, rect.w, rect.h, r.data);
       }
    }
 
void main() {
  clr[6] renkler; with(clr) {
         renkler = [ blue, cyan, green, yellow, red, white ];
  }
  Kutu[renkler.length] kutular; /* renk adeti kadar nesne oluşturur */
  
  with( new scene(genişlik*10, yükseklik*10, "Kutular...", clr.black) ) {
      
      assert(scr != null);        // Sahne kuruldu mu?
      
      foreach(i, c; renkler) {
          auto solüst = [ uniform(0, genişlik-10),
                          uniform(0, yükseklik-10)];
          auto sağalt = [ uniform(solüst[0], genişlik),
                          uniform(solüst[1], yükseklik) ];   
         
          short[] noktalar;
                  noktalar ~= cast(short)(solüst[0] * 10);
                  noktalar ~= cast(short)(solüst[1] * 10);
                  noktalar ~= cast(short)(sağalt[0] * 10);
                  noktalar ~= cast(short)(sağalt[1] * 10);
          kutular[i] = new Kutu(c, noktalar);
      }
      /* Yukarıda, rasgele sayılarda (sahne ölçülerinin onda biri)
       * kutu başlangıç (solüst) ve büyüklük (sağalt) değerleriyle
       * nesneler oluşturulurken;
       * Aşağıda bunlar, sırasıyla sahneye alınmaktadır...
       */
      do {
          foreach(kutu; kutular) {
               kutu.exec(scr);
               kutu.writeln;
               kutu.clear;
          }
      } while(escEvent(0)); // ESC için bekle ve çık...
  }
}
Bu kodun bir özelliği olabildiğince sade oluşu. Öyle ki SDL kütüphanesinin tüm özelliklerine başvurulmuş (SDL_Rect ve SDL_FillRect) ve temsilcilerden uzak durulmuştur. Şimdi Ali hocamın emeklerini buna uyarlamaya çalışacağım...

Teşekkürler...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #13
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Hakikaten kafayı yetirtecek bir şey bu...:)

Sanırım istediğimiz gibi çalışmıyor çünkü 3 ile 2 numara aynı satırda (iki_numara = 1) ise önce, "3 numaralı dörtgen silindi" diyor ama 2 numarayı silmeye çalışması gerekiyor ve sonra 3 numara olmadığı için "Nokta(1, 10) konumunda dörtgen yok" hatası veriyor ve son aşamada doğru bir şekilde 2 numaralı kutuyu siliyor... :rolleyes:
    immutable genişlik  = 30;
    immutable yükseklik = 15;
    immutable iki_numara = 1;
    
void doldur(ref Kağıt kağıt)
{
    kağıt.yerleştir(Dörtgen(Nokta(1, 16), Nokta(14, 20)), 1);
    kağıt.yerleştir(Dörtgen(Nokta(iki_numara, 15), Nokta(4, 26)), 2);
    kağıt.yerleştir(Dörtgen(Nokta(1, 10), Nokta(12, 24)), 3);
}
 
void çiz(ref Kağıt kağıt) {
    writeln(replicate(" 0 1 2 3 4 5 6 7 8 9", genişlik/10)); 
    kağıt.çiz();
}
 
void main()
{
    auto kağıt = Kağıt(yükseklik, genişlik);
    doldur(kağıt);
    çiz(kağıt);
 
    kağıt.kaldır(Nokta(iki_numara, 15)); çiz(kağıt); // 2 numara
    kağıt.kaldır(Nokta(1, 10)); çiz(kağıt);          // 3 numara
    kağıt.kaldır(Nokta(iki_numara, 15)); çiz(kağıt); // 2 numara
}
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #14
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Ben bir yanlışlık görmüyorum.
    kağıt.kaldır(Nokta(iki_numara, 15)); çiz(kağıt); // 2 numara 
diyorsun ama o anda Nokta(1, 15) 3 numaralı dörtgene ait. O yüzden 3 numaralı dörtgen siliniyor. Ondan sonra gerçekten de Nokta(1, 10) konumunda dörtgen yok.

Doldurma adımlarından sonra da çiz() koyunca daha iyi anlaşılıyor.

Bu arada, herhalde o kadar önemli değil ama ben bu kodla biraz oynamıştım. Bence aşağıdaki gibi daha iyi oldu. Önemli bir fark, artık sağ alt noktası Dörtgen'e dahil değil. Böylece D dilimleriyle filan daha tutarlı oldu:
import std.stdio;
import std.array;
import std.string;
import std.conv;
 
struct Nokta
{
    size_t satır;
    size_t sütun;
}
 
struct Dörtgen
{
    Nokta solÜst;
    Nokta sağAlt;
 
    int opApply(int delegate(Nokta nokta) işlem) const
    {
        int sonuç = 0;
 
        foreach (satır; solÜst.satır .. sağAlt.satır) {
            foreach (sütun; solÜst.sütun .. sağAlt.sütun) {
                sonuç = işlem(Nokta(satır, sütun));
 
                if (sonuç) {
                    return sonuç;
                }
            }
        }
 
        return sonuç;
    }
}
 
struct Düzlem(T)
{
    T[][] konumlar;          // Üç boyut: satır, sütun, ve dörtgen numaraları
 
    this (size_t boy, size_t en)
    {
         konumlar = new T[][](boy, en);
    }
 
    auto ref opIndex(Nokta nokta)
    {
        return konumlar[nokta.satır][nokta.sütun];
    }
 
    auto ref opIndex(Nokta nokta) const
    {
        return konumlar[nokta.satır][nokta.sütun];
    }
 
    int opApply(int delegate(const(T)[] satırElemanları) işlem) const
    {
        int sonuç = 0;
 
        foreach (satır; konumlar) {
            sonuç = işlem(satır);
 
            if (sonuç) {
                return sonuç;
            }
        }
 
        return sonuç;
    }
}
 
struct Kağıt
{
    Düzlem!(size_t[]) konumlar;
    Dörtgen[size_t] dörtgenler; // Numaradan dörtgene eşleme tablosu
 
    this (size_t boy, size_t en)
    {
        this.konumlar = Düzlem!(size_t[])(boy, en);
    }
 
    void yerleştir(Dörtgen dörtgen, size_t numara)
    {
        // Her konumun en üstüne bu dörtgenin parçası gelir
        foreach (nokta; dörtgen) {
            konumlar[nokta] ~= numara;
        }
 
        // Daha sonra numarasından dörtgen elde edebilmek için
        dörtgenler[numara] = dörtgen;
    }
 
    // Dörtgeni oluşturan konumların en üstünde 'numara' varsa true döndürür
    bool serbest_mi(size_t numara) const
    {
        auto dörtgen = numara in dörtgenler;
        // Daha önce yerleştirdiğimize göre eşleme tablosunda da bulunmalı.
        assert(dörtgen, format("%s numaralı dörtgen bulunamadı"));
 
        foreach (nokta; *dörtgen) {
            if (konumlar[nokta].back != numara) {
                // Bu dörtgenin en üstte olmadığı bir konum bulduk
                return false;
            }
        }
 
        // Buraya geldiysek dörtgeni oluşturan bütün noktalarda en üstte
        // 'numara' var demektir. Yani, dörtgen serbest.
        return true;
    }
 
    enum Kaldırıldı { evet, hayır };
 
    Kaldırıldı kaldır(Nokta nokta)
    {
        Kaldırıldı sonuç = Kaldırıldı.hayır;
        auto konum = konumlar[nokta];
 
        if (konum.empty) {
            writefln("%s konumunda dörtgen yok", nokta);
 
        } else {
            auto dörtgenNumarası = konum.back// En üstteki dörtgenin numarası
            auto dörtgen = dörtgenNumarası in dörtgenler;
 
            // Daha önce yerleştirdiğimize göre eşleme tablosunda bulunmalı.
            assert(dörtgen, format("%s numaralı dörtgen bulunamadı"));
 
            if (serbest_mi(dörtgenNumarası)) {
                sil_(dörtgenNumarası);
                writefln("%s numaralı dörtgen silindi", dörtgenNumarası);
                sonuç = Kaldırıldı.evet;
 
            } else {
                writefln("%s numaralı dörtgen serbest değil", dörtgenNumarası);
            }
        }
 
        return sonuç;
    }
 
    // Bu işlev arayüzün parçası değil; yalnızca bu yapı çağırsın diye...
    private void sil_(size_t dörtgenNumarası)
    {
        auto dörtgen = dörtgenNumarası in dörtgenler;
        // Daha önce yerleştirdiğimize göre eşleme tablosunda bulunmalı.
        assert(dörtgen, format("%s numaralı dörtgen bulunamadı"));
 
        foreach (nokta; *dörtgen) {
            konumlar[nokta].popBack();
        }
 
        dörtgenler.remove(dörtgenNumarası);
    }
 
    void çiz() const
    {
        foreach (satır; konumlar) {
            foreach (konum; satır) {
                // Her konumda en üstte olanı çizeceğiz
                auto görünüm = konum.empty ? "." : konum.back.to!string;
                writef(" %s", görünüm);
            }
 
            writeln();
        }
    }
}
 
void doldur(ref Kağıt kağıt)
{
    kağıt.yerleştir(Dörtgen(Nokta(3, 3), Nokta(8, 8)), 1);
    kağıt.yerleştir(Dörtgen(Nokta(8, 15), Nokta(11, 19)), 2);
    kağıt.yerleştir(Dörtgen(Nokta(5, 5), Nokta(10, 11)), 3);
    kağıt.yerleştir(Dörtgen(Nokta(4, 4), Nokta(7, 7)), 4);
}
 
void main()
{
    auto kağıt = Kağıt(20, 20);
 
    doldur(kağıt);
    kağıt.çiz();
 
    kağıt.kaldır(Nokta(0, 0));    // Boş bir nokta
    kağıt.kaldır(Nokta(8, 8));    // Kaldırılamaz çünkü serbest değil
    kağıt.kaldır(Nokta(4, 4));    // Serbest
    kağıt.kaldır(Nokta(8, 8));    // Şimdi kaldırılabilir çünkü artık serbest
    kağıt.çiz();
}
Ali
Avatar
Salih Dinçer #15
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
acehreli:
Ben bir yanlışlık görmüyorum.
    kağıt.kaldır(Nokta(iki_numara, 15)); çiz(kağıt); // 2 numara 
diyorsun ama o anda Nokta(1, 15) 3 numaralı dörtgene ait. O yüzden 3 numaralı dörtgen siliniyor. Ondan sonra gerçekten de Nokta(1, 10) konumunda dörtgen yok.
Sanırım eksik ifade etmişim, yorgunluk işte...

Öncelikle iki_numara değişkeni (2. dikdörtgenin solüst noktasını değiştirir) 0 yaptığınızda algoritma istediğimiz gibi çalışıyor. Çünkü "2 numaralı dörtgen serbest değil" yazıyor. Belki de ilk noktalar (solüst) dörtgen altında kalınca böyle oluyor, değil mi?

Değiştirdiğim kodu, ilk kodun yapıları ile birlikte çalıştırırsanız her aşamada ekrana kağıdı (sütun değeri 0..9 ile birlikte) bastığını göreceksiniz. Bahsettiğim iki_numara ile oyayınca bir satır yukarı aldığımızı ve aynı sütunları paylaşmadığını görebilirsiniz:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
 . . . . . . . . . . . . . . . 2 2 2 2 2 2 2 2 2 2 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
2 numaralı dörtgen serbest değil
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
 . . . . . . . . . . . . . . . 2 2 2 2 2 2 2 2 2 2 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
3 numaralı dörtgen silindi
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
 . . . . . . . . . . . . . . . 2 2 2 2 2 2 2 2 2 2 2 2 . . .
 . . . . . . . . . . . . . . . 2 2 2 2 2 2 2 2 2 2 2 2 . . .
 . . . . . . . . . . . . . . . 2 2 2 2 2 2 2 2 2 2 2 2 . . .
 . . . . . . . . . . . . . . . 2 2 2 2 2 2 2 2 2 2 2 2 . . .
 . . . . . . . . . . . . . . . 2 2 2 2 2 2 2 2 2 2 2 2 . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
 . . . . . . . . . . . . . . . . 1 1 1 1 1 . . . . . . . . .
2 numaralı dörtgen silindi

Henüz yeni kodu denemedim. Sanırım daha lezzetli ve müsait bir vakitte satır satır incelemeye can atıyorum...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Sayfa:  1  2  sonraki 
Forum: SDL RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-21, 09:15:38 (UTC -08:00)