Advent of Code Macerası – Gün 7

Herkese merhabalar! Bugün 7. gün ile birlikteyiz. Bugun maalesef çok vatim olmadığı için hikayeyi kısa tutup, kodumu paylaşıcam ve kısa açıklamasını yapacağım. Cihazda boş alan kalmadı isimli bu bulmaca kısaca şu şekildedir:

$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k

Yukarıdaki gibi dosya sistem komutları olarak verilen inputumuz var. Yukarıdaki örnekteki komutlar ve çıktılar göz önüne alındığında, dosya sisteminin görsel olarak aşağıdaki gibi göründüğünü belirleyebilirsiniz:

- / (dir)
  - a (dir)
    - e (dir)
      - i (file, size=584)
    - f (file, size=29116)
    - g (file, size=2557)
    - h.lst (file, size=62596)
  - b.txt (file, size=14848514)
  - c.dat (file, size=8504156)
  - d (dir)
    - j (file, size=4060174)
    - d.log (file, size=8033020)
    - d.ext (file, size=5626152)
    - k (file, size=7214296)

Yukarıdaki dizinlerin toplam boyutları aşağıdaki gibi bulunabilir:

• e dizininin toplam boyutu 584’tür çünkü 584 boyutunda tek bir i dosyası içerir ve başka dizin içermez.
• a dizininin toplam boyutu 94853’tür çünkü f (boyut 29116), g (boyut 2557) ve h.lst (boyut 62596) dosyalarını ve dolaylı olarak i dosyasını içerir (a, i’yi içeren e’yi içerir).
• d dizininin toplam boyutu 24933642’dir.
• En dış dizin olarak / her dosyayı içerir. Toplam boyutu 48381165’tir, bu da her dosyanın boyutunun toplamıdır.

Bizden istenen toplam boyutu en fazla 100000 olan tüm dizinleri bulmak ve bu dizinlerin toplam boyutlarının toplamı nedir?

İkinci bölümde ise bulmaca şu şekilde ilerliyor, dosya sistemi için kullanılabilir toplam disk alanı 70000000’dir. Güncellemeyi çalıştırmak için en az 30000000 kullanılmayan alana ihtiyacınız var. Güncellemeyi çalıştırmak için yeterli alanı boşaltacak silebileceğiniz bir dizin bulmanız gerekir. Silindiği takdirde dosya sisteminde güncellemeyi çalıştırmaya yetecek kadar yer açacak en küçük dizini bulun. Bu dizinin toplam boyutu nedir?

Ben bu iki problemi de çözün kodu bu sefer tek python scriptinde yazdım. Kod aşağıdaki gibidir:

from collections import defaultdict

data = open('filesystem.txt').read().strip() 
lines = [x for x in data.split('\n')]

# directory path -> total size of that directory (including subdirectories)
SZ = defaultdict(int)
path = [] # current directory path
for line in lines: # for each line in the filesystem
    words = line.strip().split()
    if words[1] == 'cd': 
        if words[2] == '..': 
            path.pop() # remove the last directory from the path
        else:
            path.append(words[2])
    elif words[1] == 'ls': 
        continue # ignore this line
    elif words[0] == 'dir':
        continue # ignore this line
    else:
        sz = int(words[0]) 
        # Add this file's size to the current directory size *and* the size of all parents
        for i in range(1, len(path)+1):
            SZ['/'.join(path[:i])] += sz

max_used = 70000000 - 30000000
total_used = SZ['/']
need_to_free = total_used - max_used

p1 = 0
p2 = 1e9
for k,v in SZ.items():
    #print(k,v)
    if v <= 100000:
        p1 += v
    if v>=need_to_free:
        p2 = min(p2, v)
print(p1)
print(p2)

Kod, filesystem.txt dosyasındaki verileri okuyarak dosya sistemi için kullanılan toplam disk alanını hesaplıyor. Kod, dosya sisteminde bulunan her bir dosya veya dizin için bir satır okuyarak, dosya veya dizinin boyutunu hesaplıyor. SZ adlı bir sözlük kullanılarak, her bir dosya veya dizin için kullanılan disk alanının toplamını hesaplıyor.

Kodun ilk bölümünde, defaultdict sınıfından bir nesne oluşturulur. Bu sınıf, int değerleri için varsayılan bir sözlük sağlar. Dosya sistemindeki dosyaların ve dizinlerin boyutlarının tutulacağı SZ adlı sözlük bu varsayılan sözlük nesnesi ile oluşturulur.

Daha sonra, filesystem.txt dosyası okunur ve dosyadaki satırlar diziye ayrıştırılır. Dizi, lines adlı bir değişkene atanır. Daha sonra, bu dizideki her bir satır için bir döngü yürütülür. Bu döngüde, her satır için ilk kelime komut tipini belirtir. Eğer bu kelime cd ise, satırdaki ikinci kelime komutun nereye uygulandığını belirtir. Bu komut .. ise, dosya sisteminde bir üst dizine geçilir. Eğer değilse, dosya sisteminde yeni bir dizine geçilir. ls komutu kullanılırsa, bir işlem yapılmaz. dir komutu kullanılırsa da bir işlem yapılmaz. Bu durumlarda döngünün ilerlemesi sağlanır.

Eğer satırdaki ilk kelime komut değilse, satırdaki ilk sayı dosyanın boyutunu ifade eder. Dosyanın boyutu, SZ sözlüğüne eklenir. Dosya sisteminde bulunan her bir dosya veya dizin için bu işlem tekrarlanır.

Döngü tamamlandıktan sonra, SZ sözlüğünde her bir dosya veya dizin için kullanılan disk alanı tutulmuş olur. Bu sözlük, dosya sisteminde bulunan her bir dosya veya dizin için kullanılan toplam disk alanını hesaplamak için kullanılabilir.

Kodun son bölümünde, max_used ve total_used adlı iki değişken tanımlanır. max_used değişkeni, dosya sisteminde kullanılabilecek maksimum disk alanını ifade eder. total_used değişkeni ise, SZ sözlüğünde tutulan toplam disk alanını ifade eder.

Daha sonra, need_to_free adlı bir değişken tanımlanır ve total_used ile max_used değişkenlerinin farkı bu değişkene atanır. Bu değişken, dosya sisteminde kullanılabilecek maksimum disk alanını aşan dosya ve dizinlerin boyutlarının toplamını ifade eder.

Son olarak, SZ sözlüğünde dolaşılır ve her bir dosya veya dizin için aşağıdaki koşullar kontrol edilir:

• Eğer dosya veya dizinin boyutu 100000’ten küçük veya eşitse, bu dosya veya dizinin boyutu p1 değişkenine eklenir.
• Eğer dosya veya dizinin boyutu need_to_free değişkeninden büyük veya eşitse, bu dosya veya dizinin boyutu p2 değişkenine küçük olan değer olarak eklenir.

Son olarak, p1 ve p2 değişkenleri ekrana yazdırılır. Bu değişkenler, dosya sisteminde kullanılabilecek maksimum disk alanını aşan dosya ve dizinlerin boyutlarının toplamını ve 100000’ten küçük veya eşit olan dosya ve dizinlerin boyutlarının toplamını ifade eder.

AoC’un yedinci günü de bu kadardı. Vakit ayırıp okuduğunuz için teşekkür ederim. Eğer yazıyı beğendiyseniz, kodlamaya meraklı arkadaşlarınızla paylaşmayı unutmayın 

Herhangi bir sorunuz olursa veya benimle iletişim kurmak isterseniz tüm sosyal medya hesaplarıma bu linke tıklayarak ulaşabilirsiniz. Ayrıca tüm çözümlerimi görebilmeniz için bir github reposu açtım. Bu repoya da bu linkten ulaşabilirsiniz.