Explosive Sum, codewars problemi

Herkese merhabalar;

Ilk basta fazla zor durmayan ama basina gecince zorlugunu anlayabildiginiz bir codewars sorusu var:

Soru kisaca sunu istiyor bizden. N sayisi veriliyor, pozitif sayilar arasinda sonucu N olacak butun toplama kombinasyonlari isteniyor. Ornekler:

exp_sum(1) # 1
exp_sum(2) # 2  -> 1+1 , 2
exp_sum(3) # 3 -> 1+1+1, 1+2, 3
exp_sum(4) # 5 -> 1+1+1+1, 1+1+2, 1+3, 2+2, 4
exp_sum(5) # 7 -> 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 5, 2+3

exp_sum(10) # 42

Benim yontemim ise soyleydi. Mesela ornek olarak 5 sayisi icin 2, 3, 4 ve 5 derinliklerinde ayri ayri [1, 2, 3, 4] sayilarinin permutasyonunu hesapladim, daha sonra bu butun derinliklerdeki permutasyonlari alip icinden toplami N(5) yapanlari sectim. Daha sonra sectiklerimin uzunlugunu hesapladim, o uzunluga 1 ekleyip return ettim cunku sayinin kendisi de dahil ediliyor, mesela 5 sayisi icin 5 de bir toplama kombinasyonu sayiliyor.

Kisaltilmis ve sikistirilmis kodumu acarsam soyle bir sey:

from itertools import product

def exp_sum(n):
    if n == 1: return 1
    elif n == 2: return 2

    repeats = range(2, n+1)
    possible_numbers = []
    
    for repeat in repeats:
        possible_numbers += list(product(list(range(1, n)), repeat=repeat))
    
    result = []
    for x in possible_numbers:
        x = sorted(x)
        if sum(x) == n and x not in result:
            result.append(x)
    
    return len(result)+1

Sorun su ki bu yontem asiri derecede performanssiz. O kadar performanssiz ki 10 sayisina geldigimde zsh koruma olarak process’i olduruyor.

    ~  python hello.py    #10                                                                                        ✔  1m 11s  
zsh: killed     python hello.py
    ~  vim hello.py                                                                                             KILL ✘  14s  
    ~  time python hello.py        #7                                                                                   ✔  4s  
python hello.py  0,37s user 0,05s system 91% cpu 0,460 total
    ~                                                                                                                        ✔ 

Aklima gelen performans iyilestirmeleri:

  • N-1 derinligindeki deger, butun sayilar icin 1’lerin toplami oluyor. N=5 dersek 4 icin hic hesaplamadan cikan sonuca direk 1 eklenebilir.

Birkac tane daha iyilestirme yapsam bu da hizli calisabilir ama ben farkli yontemler ariyorum. Bu isi yapabilecek en hizli kod nedir?

1 Beğeni

Selam,

Bu problem subset sum’a benziyor.

Kullandigimiz sayilar her adimda ayni oldugu icin (mi?) guzel recursive cozumler mevcut:

a) Onceki toplamin her setine +1 ekle
b) Onceki toplamin her setinin her ozgun sayisina +1 ekle

Veya, notasyonu biraz degistirecek olursak:

  1. Sayi (19) kadar 1 ile basla: [(1, 19)]
  2. Iki tanesini topla: [(1, 17), (2, 1)]
  3. Setlerin kombinasyonlarini topla: 1+1 → [(1, 15), (2, 2)], 1+2 → [(1, 16), (3, 1)]
  4. Setlerin kombinasyonlarini topla: …
  5. repeat

Multisetlerin tekrar etmesini engellemek icin ekstra is gerekir mi veya ilk formulden daha mi hizli calisir bilmiyorum. Implement edip bakmak lazim aslinda.

Bi ihtimal de Pascal ucgeni gibi bir sekli urettikten sonra onun uzerinde formulatif bi sekilde yurunebilir gibi geliyor.

Tahminlerimi yazdim, simdi literature bakabilirim :slight_smile:

2 Beğeni

Dikkatsiz insanlar hic bir linkin nereye gittigini fark etmez ki.

1 Beğeni