0

Daily Challenge #40

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #40
  • Autor: Facebook
  • Trudność: 2/5
  • Główny problem: rekurencja
Wpis ten należy do cyklu Daily Challenge. Od poniedziałku do piątku, codziennie, o 7:30 publikuję rozwiązanie jednego zadania. Zadania rozwiązywane w ramach tego cyklu są zadaniami przeznaczonymi na rozmowy kwalifikacyjne. Są treściwe, krótkie i wymagają jakichś konkretnych umiejętności. Przedstawione problemy realizuję właśnie w ten sposób. Nie wymyślam najlepszego algorytmu, nie optymalizuję ani refaktoryzuję kodu, tylko implementuję pierwszą myśl. Robię to dla zabawy i chęci sprawdzenia swoich możliwości. 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. Moje implementacje (również tego zadania) dostępne są na GitHubie. Pamiętaj, że implementacje przedstawione w ramach tego cyklu nie nadają się do kodu produkcyjnego, traktuj to bardziej jako ‘proof of concept’.

Treść

Given an unordered list of flights taken by someone, each represented as (origin, destination) pairs, and a starting airport, compute the person’s itinerary. If no such itinerary exists, return null. If there are multiple possible itineraries, return the lexicographically smallest one. All flights must be used in the itinerary.
For example, given the list of flights [(‘SFO’, ‘HKO’), (‘YYZ’, ‘SFO’), (‘YUL’, ‘YYZ’), (‘HKO’, ‘ORD’)] and starting airport ‘YUL’, you should return the list [‘YUL’, ‘YYZ’, ‘SFO’, ‘HKO’, ‘ORD’].
Given the list of flights [(‘SFO’, ‘COM’), (‘COM’, ‘YYZ’)] and starting airport ‘COM’, you should return null.
Given the list of flights [(‘A’, ‘B’), (‘A’, ‘C’), (‘B’, ‘C’), (‘C’, ‘A’)] and starting airport ‘A’, you should return the list [‘A’, ‘B’, ‘C’, ‘A’, ‘C’] even though [‘A’, ‘C’, ‘A’, ‘B’, ‘C’] is also a valid itinerary. However, the first one is lexicographically smaller.

Implementacja: testy

[TestMethod]
public void DailyChallenge40()
{
    DailyChallenge40 daily = new DailyChallenge40();
    CollectionAssert.AreEqual(new string[] { "YUL", "YYZ", "SFO", "HKO", "ORD" }, daily.Proceed(new[]
    {
        new  Tuple<string,string>("SFO", "HKO"), new  Tuple<string,string>("YYZ", "SFO"), new  Tuple<string,string>("YUL", "YYZ"), new  Tuple<string,string>("HKO", "ORD")
    }, "YUL"));
    Assert.IsNull(daily.Proceed(new[]
    {
        new  Tuple<string,string>("SFO", "COM"), new  Tuple<string,string>("COM", "YYZ"),
    }, "COM"));
    CollectionAssert.AreEqual(new string[] { "A", "B", "C", "A", "C" }, daily.Proceed(new[]
    {
        new  Tuple<string,string>("A", "B"), new  Tuple<string,string>("A", "C"), new  Tuple<string,string>("B", "C"), new  Tuple<string,string>("C", "A")
    }, "A"));
}

Implementacja: algorytm

private class Path
{
    public List<string> Ports;
    public bool IsDeath;
 
    public string Flat()
    {
        if (IsDeath)
        {
            return string.Empty;
        }
        return string.Join("", Ports);
    }
}
 
public List<string> Proceed(IEnumerable<Tuple<string, string>> list, string start)
{
    List<Path> result = ProceedIntern(list.ToList(), start);
    // remove deathends
    result = result.Where(x => x.IsDeath == false).ToList();
    if (result.Any() == false)
    {
        return null;
    }
    return result.OrderBy(x => x.Flat()).First().Ports;
 
}
 
private List<Path> ProceedIntern(List<Tuple<string,string>> list, string start)
{
    List<Path> result = new List<Path>();
    if (list.Count == 1)
    {
        if (start == list[0].Item1)
        {
            result.Add(new Path { Ports = new List<string>() { list[0].Item1, list[0].Item2 } });
        }
        else
        {
            result.Add(new Path { IsDeath = true });
        }
        return result;
    }
    foreach(Tuple<string,string> tuple in list.Where(x => x.Item1 == start))
    {
        var res = ProceedIntern(list.Except(new[] { tuple }).ToList(), tuple.Item2);
        if (res.Any() == false)
        {
            result.Add(new Path { IsDeath = true });
        }
        foreach (var p in res)
        {
            if (p.IsDeath)
            {
                result.Add(p);
                continue;
            }
            Path path = new Path() { Ports = new List<string>() { start } };
            path.Ports.AddRange(p.Ports);
            result.Add(path);
        }
    }
    return result;
}

Mission Completed

I kolejne zadanie od Facebook’a zrobione. Tym razem dosyć proste, gdyż wystarczyła zwykła rekurencja. Algorytm ten można jeszcze refaktoryzować, aby był bardziej czytelny, ale to jak wiesz, nie jest celem tego cyklu.

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.