0

Daily Challenge #16

Cześć! Kolejny wpis w serii Daily Challenge! Dzisiaj rozwiążemy zadanie od firmy Google, które trochę złamało schemat poprzednich zadań od tej firmy i samo w sobie stanowiło lekkie wyzwanie. Zadanie wyceniłem na 3 gwiazdki, chociaż może nie do końca na tyle zasługuje, sam ocenisz.

Tak jak zawsze, kod jest dostępny na GitHubie.

Wpis ten należy do cyklu Daily Challenge. W cyklu tym rozwiązuję każdego dnia nowe zadanie. Zadanie te traktuję w taki sposób, jakbym dostał je na rozmowie kwalifikacyjnej i miał coś wymyślić. Implementuję pierwszą myśl jaka przyjdzie mi do głowy. Nie musi być ona (zazwyczaj nie będzie) najlepszym rozwiązaniem. Chodzi po prostu o zabawę i sprawdzenie jakbym sobie poradził z podobnym wyzwaniem. Zaimplementowane rozwiązanie nie jest z reguły tłumaczone, jeżeli masz pytania możesz je zadawać w komentarzach. Wszystkie zadania udostępniane są subskrybentom Daily Coding Problem.

Zadanie

Dzisiejsze zadanie ma bardzo długą treść, brzmi następująco

Suppose we represent our file system by a string in the following manner:
The string “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext” represents:

  • dir
    • subdir1
    • subdir2
      • file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.
The string “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext” represents:

  • dir
    • subdir1
      • file1.ext
      • subsubdir1
    • subdir2
      • subsubdir2
        • file2.ext

The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is “dir/subdir2/subsubdir2/file2.ext”, and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

Note:
The name of a file contains at least a period and an extension.
The name of a directory or sub-directory will not contain a period.

Sam widzisz, długaśne to zadanie ;). Samo zrozumienie już trochę zajmuje, ale w gruncie rzeczy nie jest to jakoś skomplikowane. Trzeba zbudować drzewo odzwierciedlające strukturę folderów i plików, a następnie wybrać najdłuższą ścieżkę. Do pracy więc.

Testy

Utworzyłem tylko jest jeden przypadek testowy, ale za to bardzo dobrze sprawdzający algorytm, więc nie pisałem więcej. Kod testowy wygląda tak:

[TestMethod]
public void DailyChallenge16()
{
    DailyChallenge16 daily = new DailyChallenge16();
    Assert.AreEqual(32, daily.Proceed("dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"));
}

Implementacja

Z implementacją się trochę biłem, w sensie, że utworzyłem coś co działa, a następnie było trzeba skrócić kod. Finalnie udało mi się osiągnąć jakiś przyzwoity poziom, a sam kod wygląda tak:

public int Proceed(string strPath)
{
    if (string.IsNullOrWhiteSpace(strPath))
    {
        return 0;
    }
    // spearate for lines
    IEnumerable<string> lines = strPath.Split(new string[] { "\n" }, StringSplitOptions.RemoveEmptyEntries);
    IEnumerable<string> paths = GetFilePaths(lines);
    if (paths.Any() == false)
    {
        return 0;
    }
    return paths.OrderByDescending(x => x.Length).First().Length;
}
 
private List<string> GetFilePaths(IEnumerable<string> lines)
{
    List<string> files = new List<string>();
    LinkedList<string> currentPath = new LinkedList<string>();
 
    int currentLevel = -1;
    foreach(string line in lines)
    {
        int level = Regex.Matches(line, "\t").Count;
        string formatedLine = line.Substring(level);
        // Prepare levels
        if (level <= currentLevel)
        {
            for (int i = currentLevel; i >= level; --i)
            {
                if (currentPath.Any())
                {
                    currentPath.RemoveLast();
                }
            }
            currentLevel = level;
        }
        // Add file or folder
        if (formatedLine.Contains('.') == false)
        {
            currentLevel = level;
            currentPath.AddLast(formatedLine);
        }
        else
        {
            string file = string.Join(@"/", currentPath.ToArray());
            file += $@"/{formatedLine}";
            files.Add(file);
        }
    }
    return files;
}

Oczywiście sam kod można dalej refaktoryzować, ale to nie było istotą zadania, więc już tego nie robiłem. Przykładowo sekcję “prepare levels” i “add file or folder” można podzielić na dwie funkcje, co znacznie poprawiłoby czytelność, zostawmy jednak jak jest.

Mission Complete

No i zrobione. Zadanko ciekawe, chociaż trochę nagłówkowałem się nad algorytmem, a dokładniej ułożeniu warunków (być może tego nie widzisz, ale np. możemy spaść w poziomie folderów o kilka do góry, nie tylko o jeden). Koniec końców, zadanie rozwiązane, testy przechodzą, wszyscy zadowoleni ;).

Jeżeli Ty chciałbyś podesłać jakieś ciekawe zadanie, to nie krępuj się proszę i ślij na p.bogdanski@devmight.pl. Pamiętaj, że zadanie powinno nadawać się na rozmowę kwalifikacyjną, więc nie może to być problem, którego rozwiązanie zajmuje kilka godzin. Dzięki!

Pozdro!

Patryk Bogdański

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.