0

Daily Challenge #22

Witaj! Dzisiaj dosyć ciekawe zadanie od Google, zapraszam do czytania i rozwiązywania.

  • Zadanie numer: #22
  • Autor: Google
  • Trudność: 4/5
  • Główny problem: znajdowanie najkrótszej ścieżki
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ść

You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on.
Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board.
For example, given the following board:
[[f, f, f, f],
[t, t, f, t],
[f, f, f, f],
[f, f, f, f]]
and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps required to reach the end is 7, since we would need to go through (1, 2) because there is a wall everywhere else on the second row.

Implementacja: testy

[TestMethod]
public void DailyChallenge22()
{
    DailyChallenge22 daily = new DailyChallenge22();
    Assert.AreEqual(7, daily.Proceed(new bool[][]
    {
        new bool[]{false,false,false,false },
        new bool[]{true,true,false,true },
        new bool[]{false,false,false,false },
        new bool[]{false,false,false,false },
    }, new Point { Row = 3, Col = 0 }, new Point { Row = 0, Col = 0 }));
}

Implementacja: algorytm

public class Point : IEquatable<Point>
{
    public int Row;
    public int Col;
 
    public bool Equals(Point other)
    {
        return other.Row == Row && other.Col == Col;
    }
}
 
private class PointComparer : IEqualityComparer<Point>
{
    public bool Equals(Point x, Point y)
    {
        return x.Equals(y);
    }
 
    public int GetHashCode(Point obj)
    {
        int hash = 23;
        hash = hash * 31 + obj.Col;
        hash = hash * 31 + obj.Row;
        return hash;
    }
}
 
private List<Point> _visited;
private List<Point> _toVisit;
private Dictionary<Point, double> _score;
private Dictionary<Point, double> _fScore;
private Dictionary<Point, Point> _path;
 
public int Proceed(bool [][] map, Point start, Point end)
{
    _visited = new List<Point>();
    _toVisit = new List<Point>();
    _score = new Dictionary<Point, double>(new PointComparer());
    _fScore = new Dictionary<Point, double>(new PointComparer());
    _path = new Dictionary<Point, Point>(new PointComparer());
    _toVisit.Add(start);
    _score[start] = 0;
    _fScore[start] = Distance(start, end);
    while(_toVisit.Any())
    {
        Point current = _toVisit.OrderBy(x => _fScore[x]).First();
        _toVisit.Remove(current);
        _visited.Add(current);
        foreach (int row in new int[] { -1, 1 })
        {
            Visit(current, new Point() { Row = current.Row + row, Col = current.Col },end, map);
        }
        foreach (int column in new int[] { -1, 1 })
        {
            Visit(current, new Point() { Col = current.Col + column, Row = current.Row },end, map);
        }
    }
    if (_path.ContainsKey(end))
    {
        return ReconstructPath(end);
    }
    return -1;
}
 
private void Visit(Point current, Point toVisit, Point end, bool[][] map)
{
    if (toVisit.Col < 0 || toVisit.Col >= map.Length || toVisit.Row < 0 || toVisit.Row >= map.Length)
    {
        return;
    }
    if (map[toVisit.Row][toVisit.Col])
    {
        // wall
        return;
    }
    if (_visited.Any(x => x.Equals(toVisit)))
    {
        return;
    }
    double newScore = _score[current] + Distance(current, toVisit);
    if (_toVisit.Any(x => x.Equals(toVisit)) == false)
    {
        _toVisit.Add(toVisit);
    }
    else if (newScore >= _score[toVisit])
    {
        return;
    }
    _path[toVisit] = current;
    _score[toVisit] = newScore;
    _fScore[toVisit] = newScore + Distance(toVisit, end);
}
 
private int ReconstructPath(Point point)
{
    int result = 0;
    while (_path.TryGetValue(point, out point))
    {
        ++result;
    }
    return result;
}
 
private double Distance(Point current, Point end)
{
    return Math.Sqrt(Math.Pow(end.Row - current.Row, 2) + Math.Pow(end.Col - current.Row, 2));
}

Mission Completed

Zadanie z gatunku trudniejszych. Ja do rozwiązania wybrałem zachłanny algorytm A* (modyfikacja A* szukająca najlepsze drogi, nie pierwszej znalezionej). Oczywiście, mogłeś wybrać inny algorytm np. alfa/beta cięcia albo jakieś przeszukiwanie grafu. Aby rozwiązać zadanie wymagana była znajomość jakiegoś algorytmu, którego pewnie dużo programistów nie zna, dlatego zadanie wyceniłem na 4 gwiazdki.

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.