0

Daily Challenge #31

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #31
  • Autor: Jane Street
  • Trudność: 3/5
  • Główny problem: przeszukiwanie grafu / przeszukiwanie macierzy
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ę kodu do granic możliwości, 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.

Treść

Suppose you are given a table of currency exchange rates, represented as a 2D array. Determine whether there is a possible arbitrage: that is, whether there is some sequence of trades you can make, starting with some amount A of any currency, so that you can end up with some amount greater than A of that currency.
There are no transaction costs and you can trade fractional quantities.

Implementacja: testy

[TestMethod]
public void DailyChallenge31()
{
    DailyChallenge31 daily = new DailyChallenge31();
    Assert.IsFalse(daily.Proceed(new float[,]
    {
        {1, .5f, .25f },
        {2,   1, .5f },
        {4,   2, 1 },
    }));
    Assert.IsTrue(daily.Proceed(new float[,]
    {
        {1, 5, .2f, 10 },
        {2, 1, .5f, .25f },
        {5, 2, 1, .5f },
        {1, 4, 2, 1 },
    }));
}

Implementacja: algorytm

public bool Proceed(float[,] table)
{
    for(int i = 0; i < table.GetLength(0) - 1;++i)
    {
        for (int k = 0; k < (table.GetLength(0) - (i + 1)); ++k)
        {
            float sum = 1;
            int lastJ = i;
            for (int j = i + k + 1; j < table.GetLength(1); ++j)
            {
                sum *= table[lastJ, j];
                lastJ = j;
                float res = sum * table[j, i];
                if (res < 1 - 10 * float.Epsilon || res > 1 + 10 * float.Epsilon)
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Mission Completed

Zrobione. Zadanie dosyć skomplikowane, można je było rozwiązać rozpisując tabelę na graf i przeszukiwać graf. Ja wolałem przelecieć się zwykłymi forami po tablicy. Jest to swoisty Brute Force, ale spełnia swoje zadanie, w treści nigdzie nie było wzmianki o optymalizacji. Trzeba sprawdzić każde możliwe przejście w tablicy, na każdym kroku sprawdzając czy wymiana z otrzymanej waluty, na bazową walutę da przelicznik inny niż 1. Czyli przykładowo dla tablicy 4×4 (A:D) dla waluty A możliwe są takie drogi (pamiętać, że na każdej strzałce sprawdzać czy przypadkiem nie mamy lepszej wymiany):

  • A->B->C->D – dokonywane sprawdzania: B->A, C->A, D->A
  • A->C->D – dokonywane sprawdzania: C->A, D->A
  • A->D – dokonywane sprawdzania: D->A
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.