Codewars: Bir Dikdörtgen İçerisindeki Karelerin Çevreleri

JavaScript
1

Merhabalar.

Sorunun linki burada:

Ben çözüm için şöyle bir şey yaptım:

function perimeter(n) {
  const squareCount = n + 1;
  let perimeters = [1, 1];
  let i1 = 0;
  let i2 = 1;

  while (squareCount !== perimeters.length) {
    perimeters.push(perimeters[i1] + perimeters[i2]);
    i1++;
    i2++;
  }
  return perimeters.reduce((a, b) => a + b) * 4; // sum(perimeters) * 4
}

Çok büyük sayılar argüman olarak girildiğinde sonucu science notation’la göstermesi ve çok çok çok çok büyük sayılar girildinde sonucu Infinity göstermesi dışında her şey yolunda. Ancak görünen o ki iyi bir optimizasyona ihtiyaç var çünkü Codewars:

<--- Last few GCs --->

[1:0x55d412b60000]       41 ms: Scavenge 3.6 (7.3) -> 3.5 (8.3) MB, 1.1 / 0.0 ms  allocation failure 
[1:0x55d412b60000]       75 ms: Scavenge 7.2 (10.9) -> 6.9 (13.4) MB, 0.8 / 0.0 ms  allocation failure 
[1:0x55d412b60000]      107 ms: Scavenge 8.7 (13.4) -> 7.8 (14.4) MB, 1.2 / 0.0 ms  allocation failure 
[1:0x55d412b60000]      132 ms: Scavenge 9.5 (14.4) -> 8.6 (15.4) MB, 0.9 / 0.0 ms  allocation failure 


<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x37bd4be257c1 <JSObject>
    1: perimeter [/home/codewarrior/index.js:~5] [pc=0x31bbc4c0b2bf](this=0x3e31cff0c211 <JSGlobal Object>,n=0)
    2: /* anonymous */ [/home/codewarrior/index.js:23] [bytecode=0xbe76afe3429 offset=20](this=0x3e31cff0c211 <JSGlobal Object>)
    3: arguments adaptor frame: 1->0
    4: begin [/runner/frameworks/javascript/cw-2.js:203] [bytecode=0xbe76afe2a49 offset=141](this=0x3e31cff0c211 <JSGlob...

FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory

diyor.
Açıkçası optimizasyon sorunlarıyla ilk kez Codewars’ta yüzleşmeye başladığım için bu konuda henüz beceriksizim. Optimizasyon için ne yapılabilir ? Ya da en hızlı ve doğru çözüm yolu ne olabilirdi ?

2 Beğeni
2

Merhaba, sitede sol tarafta bir ipucu var, onu kullanabilirsiniz belki… Yoksa pek bir işe yaramadı mı :ğ

3

“See Fibonacci sequence”
Bundan mı bahsediyorsunuz ?

Evet :D

Fibonacci sequence’ı biraz kurcaladım, bu ipucu çevreleri bulabilmemiz için verilmiş anladığım kadarıyla ancak ben çevreleri bulmak için kendi algoritmamı yaratmak istedim çünkü dediğim gibi pek işe yaramadı :smiley: Muhtemelen ben kullanamamışımdır. Açıkçası çok da aydınlatıcı, nokta atışı yaptırtacak bir ipucu olduğunu düşünmüyorum.

4

Evet

Aslında kullanıyorsunuz; perimeters listesinin elemanları sanki o dizinin elemanları, değil mi?

Siz while her döndüğünde listenizi genişletiyorsunuz, ama ne için? En son o listenin elemanlarının toplamını bulmak için! Yani koskoca liste (ki allocation error’den baya büyük olduğunu söyleyebiliriz :ğ) en son bir sayıya indirgeniyor… Acaba liste tutmasanız mı bu iş için?

Yanii… aslında biraz nokta atışına gönderebilir biraz matematikle ama ona pek gerek yok belki en son paylaşılır şimdi spoiler olmasın. Sizin algoritmanızın temeli doğru ama hafızayı düzeltirseniz hallolur diye düşünüyorum…

3 Beğeni
5

Başardım :sunglasses:

Çözümüm 
function range(start, end) {
  return Array.apply(0, Array(end - 1)).map((element, index) => index + start);
}

function fibonacci(num) {
  let a = 1,
    b = 0,
    temp;

  while (num >= 0) {
    temp = a;
    a = a + b;
    b = temp;
    num--;
  }
  return b;
}

function perimeter(n) {
  return 4 * [1, ...range(1, n + 1)].reduce((a, b) => a + fibonacci(b), 0);
}

Fibonacci’nin olayını çözdükten sonra bir aydınlanma geldi :D

Yardım için teşekkürler :blush:

4 Beğeni
6

Elinize sağlık. Ekstra olarak: Fibonacci dizisinin kendisi ile kısmi toplamları arasında bir bağlantı olabilir mi? “Kısmi toplam” havalı duruyor ama o da bir dizi aslında: kendisine verilen dizinin ilk n elemanının toplamı o dizinin n’inci elemanı oluyor. Yani F_n Fibonacci dizisi olsun:

F_n = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...}

Kısmi toplam (S_n diyelim) kendisi de bir dizi olarak şuna eşit oluyor:

S_n = {1, 1 + 1, 1 + 1 + 2, 1 + 1 + 2 + 3, 1 + 1 + 2 + 3 + 5, ...}
    = {1, 2, 4, 7, 12, ...}

(Bu arada kısmi toplamlar karelerin kenarları toplamına denk geliyor.)

Acaba S_k ile (yani S_n dizisinin k’inci elemanı ile) Fibonacci dizisinin elemanları arasında herhangi bir bağ var mı? Varsa belki kenarda bir “summation” değişkeni tutmadan (sizdeki reduce'ün perde arkasında yaptığı) da sonuca erişebiliriz?

spoiler 
sub perimeter(Int $n) {
    4 * ((1, 1, * + * ... *)[$n + 2] - 1)
}

say .&perimeter for [0, 5, 7, 20, 30]

https://glot.io/snippets/g47ltduchk

  • ... dizi operatörü oluyor, ayaküstü Fibonacci’yi yazıveriyoruz :ğ
    • (1, 1, * + * ... *) kısmı 1’den sonsuza Fibonacci dizisini veriyor
  • .&f herhangi bir fonksiyonu metot olarak çağırabilmeye yarıyor. Peki kimin metodu .'dan öncesi boş?! “topic variable”'ın :d
  • Evet, Raku’nun reklamını yapmaya çalışıyorum :d
3 Beğeni
7

Bu ikisi ayni sey degil cunku burada gereken optimizasyon hafiza kullaniminin dusurulmesi. Cozumun hizi veya dogruluguyla alakasi yok.

Toplamak istedigin sayilari kocaman bir array’e koyup sonradan toplamaktansa toplamlarini tutabilirsin.

Son 2 elemana erisim oldugunu goruyorum. Onlari da array disinda tutmak gerekebilir.

Baska bir deyisle/benzer bir sekilde, her iterasyon sonrasinda array’in artik ise yaramayan kisimlarini katlayabilirsin.

3 Beğeni