0

Daily Challenge #24

Witaj! Dzisiaj Facebook, z zadaniem najgorszej możliwej kategorii: parsowanie tekstu…

  • Zadanie numer: #24
  • Autor: Facebook
  • Trudność: 3/5
  • Główny problem: wyrażenia regularne / parsowanie tekstu
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ść

Implement regular expression matching with the following special characters:

  • . (period) which matches any single character
  • * (asterisk) which matches zero or more of the preceding element

That is, implement a function that takes in a string and a valid regular expression and returns whether or not the string matches the regular expression.
For example, given the regular expression “ra.” and the string “ray”, your function should return true. The same regular expression on the string “raymond” should return false.
Given the regular expression “.*at” and the string “chat”, your function should return true. The same regular expression on the string “chats” should return false.

Implementacja: testy

[TestMethod]
public void DailyChallenge24()
{
    DailyChallenge24 daily = new DailyChallenge24();
    Assert.IsTrue(daily.Proceed("ray", "ra."));
    Assert.IsTrue(daily.Proceed("ray", "ra*"));
    Assert.IsTrue(daily.Proceed("ray", "ray*"));
 
    Assert.IsFalse(daily.Proceed("raymond", "ra."));
    Assert.IsTrue(daily.Proceed("chat", ".*at"));
    Assert.IsFalse(daily.Proceed("chats", ".*at"));
}

Implementacja: algorytm

public bool Proceed(string text, string regex)
{
    return ProceedIntern(text, regex);
}
 
private bool ProceedIntern(string text, string regex)
{
    if (regex.Length == 0)
    {
        return text.Length == 0;
    }
    if (regex.First() == '.')
    {
        return ProceedIntern(text.Substring(1), regex.Substring(1));
    }
 
    if (regex.First() == '*')
    {
        if (regex.Length == 1)
        {
            return true;
        }
        int nextSpecial = regex.IndexOfAny(new char[] { '.', '*' },1);
        if (nextSpecial < 0)
        {
            return text.EndsWith(regex.Substring(1));
        }
        if (nextSpecial == 1)
        {
            int nextDot = regex.IndexOf('.');
            if (nextDot == nextSpecial)
            {
                if (text.Length == 0)
                {
                    return false;
                }
                // *. => * (with skip one)
                return ProceedIntern(text.Substring(1), "*" + regex.Substring(2));
            }
            else
            {
                // ** => *
                return ProceedIntern(text, regex.Substring(1));
            }
        }
        int inText = text.IndexOf(regex.Substring(1, nextSpecial - 1));
        if (inText < 0)
        {
            return false;
        }
        return ProceedIntern(text.Substring(inText), regex.Substring(1, nextSpecial - 1));
    }
    else
    {
        int nextSpecial = regex.IndexOfAny(new char[] { '.', '*' });
        if (nextSpecial < 0)
        {
            return text == regex;
        }
        if (text.StartsWith(regex.Substring(0, nextSpecial)))
        {
            return ProceedIntern(text.Substring(nextSpecial), regex.Substring(nextSpecial));
        }
        return false;
    }
}

Mission Completed

Zadanie zrobione, chociaż do najprzyjemniejszych nie należało. Ten mój if również nie powala, ale zgodnie z zasadą: “pierwsza myśl, bez refaktoryzacji” zostawiłem, jak jest. Parsowania tekstu nigdy nie lubiłem i za takimi zadaniami też nie będę przepadał.

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.