0

Daily Challenge #18

Witaj! W dniu dzisiejszym rozwiążemy zadanie od firmy Facebook, które wyceniłem na 3 gwiazdki. Zastanawiałem się, czy nie dać 2, ale to byłoby chyba za mało. Sam ocenisz, zapraszam do przeczytania i rozwiązania!

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 następująco treść:

A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighboring houses are of the same color.
Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color, return the minimum cost which achieves this goal.

Wspomnę od razu o dwóch rzeczach:

  1. nie jest napisane, co ma być wynikiem funkcji tj. czy koszt, czy kolory. W takim razie przyjąłem kolory, aby lepiej testować algorytm,
  2. jaka może być złożoność algorytmu. Po najmniejszej linii oporu wybrałem złożoność O(n*k), czyli najgorszą z możliwych.

Testy

Tak… testy. Dzisiaj bez rewelacji, jeden przypadek testowy. Przypadek powstał na podstawie prostej macierzy 3×3, rozrysowanej na tablicy:

Jak widzisz wynik to [1][0][2] (w znaczeniu indeksów) i tak też został napisany kod testowy:

[TestMethod]
public void DailyChallenge18()
{
    DailyChallenge18 daily = new DailyChallenge18();
    int[] result = daily.Proceed(
        new int[][]
        {
            new int[]{1,2,3 },
            new int[]{1,3,3},
            new int[]{3,4,2},
        });
    int[] expected = new int[] { 1, 0, 2 };
    for(int i = 0; i < expected.Length; ++i)
    {
        Assert.AreEqual(expected[i], result[i]);
    }
}

Implementacja

Implementacja opiera się na znalezieniu wszystkich możliwych ścieżek i wyznaczenia najtańszej. Najłatwiej to zrobić za pomocą rekurencji:

private class Res
{
    public int Position;
    public int Cost;
}
 
public int[] Proceed(int[][] matrix)
{
    List<List<Res>> results = GetResult(-1, matrix.ToList());
    return results.OrderBy(x => x.Sum(k => k.Cost)).First().Select(x => x.Position).ToArray();
}
 
private List<List<Res>> GetResult(int excluded, List<int[]> matrix)
{
    List<List<Res>> results = new List<List<Res>>();
    for (int k = 0; k < matrix[0].Length; ++k)
    {
        if (k == excluded)
        {
            continue;
        }
        if (matrix.Count != 1)
        {
            List<List<Res>> current = GetResult(k, matrix.Skip(1).ToList());
            foreach(var c in current)
            {
                c.Insert(0, new Res { Position = k, Cost = matrix[0][k] });
            }
            results.AddRange(current);
        }
        else
        {
            results.Add(new List<Res>() { new Res { Position = k, Cost = matrix[0][k] } });
        }
    }
    return results;
}

Mission Completed

Zadanko samo w sobie proste, ale wymagało zaimplementowania jakiegoś tam algorytmu. Już po implementacji, przyszło mi do głowy, że ten problem można rozwiązać za pomocą algorytmu A* albo przeszukiwania grafu. Czy byłby to lepszy algorytm? Na pewno wydajniejszy i bardziej efektowny, ale z założenia implementuję pierwszą myśl i tak też zrobiłem w tym przypadku.

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.