Trudne zadanie - rekrutacyjne

0

Witam. Dostałem trudne zadanie programistyczne (algorytmy).
Jest ktoś może na tyle łebski żeby to ogarnąć?

Poniżej Przedstawiam treść:

Pewien poszukiwacz skarbów odkrył mapę ze wskazówkami do odnalezienia skarbu. Jednak mapa była bardzo specyficzna, zawierała długa listę par liczb.
przy czym pierwsza liczba w parze była z zakresu <0,3> natomiast druga <1,100>. Po kilku tygodniach poszukiwania wskazówek do odczytania mapy, poszukiwaczowi udało się odszyfrować,
znaczenie listy par liczb wypisanych na mapie. Okazało się że pierwszą liczbą w wierszu jest kierunek świata a drugą, liczba kroków do przebycia we wskazanym kierunku.

0 -> północ
1 -> południe
2 -> zachód
3 -> wschód

Na mapie był również zaznaczony punk, który wskazywał na duży głaz umieszczony po środku dużego pustkowia. Poszukiwacz doszedł do wniosku, iż skarbu musi szukać zgodnie ze wskazówkami
przedstawionymi na liście par liczb, rozpoczynając swoją wędrówkę od głazu na pustkowiu. Niestety pojawił się spory problem ponieważ ilość wskazówek na mapie mogła sięgać nawet kilku tysięcy ¯_(ツ)_/¯.
Poszukiwać, aby nie krążyć bez ładu i składu po pustkowiu, postanowił poprosić cię o pomoc aby wytyczyć jak najkrótszą drogę do skarbu na podstawie wskazówek z mapy.
Poprosił cię o napisanie programu który rozwiąże mu ten problem ヽ(•‿•)ノ.

Zadanie polega na napisaniu funkcji która zwróci najkrótszą drogę do skarbu, od wskazanego głazu, w postaci takiej jak wskazówki na mapie.
Funkcja jako argumenty otrzymuje tablicę wektorów dwuelementowych, a na wyjściu zwraca mapę w tej samej strukturze z najkrótszą drogą do skarbu, w przypadku gdyby skarb znajdował się pod głazem,
funkcja ma wypisać na ekranie słowo "GŁAZ".

Przykład:

$mapa = [[0,5],[3,24],[1,13],[3,45],[1,34],[2,5]...];

function poszukiwacz(array $mapa): ?array{
....
return $fastMap;
}

0

Ale czego nie umiesz zbudować grafu czy znaleźć najkrótszej ścieżki w grafie ?

0

i jednego i drugiego

0

Narysuj sobie ten przykład na kartce w kratkę, następnie przeczytaj jak zapisać graf w strukturze danych i o alogrytmie na najkrótszą ścieżkę w grafie.

0

Niestety nie bedzie latwo - w sensie, ze nie obejdzie sie bez wlozenia w to troche pracy :(

Bedziesz niestety musial ogarnac: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm - jest to w miare ok wytlumaczone w wiekszosci ksiazek o algorytmach.

0

To nie jest trudne zadanie. Do jego rozwiązania nie potrzebujesz Dijkstry...
Kiedy nauczycie się programować?

2

Jest to dość proste zadanie - mamy tu jedną ścieżkę która zawsze prowadzi do celu (nie ma tu więc mowy o ślepej ścieżce), jedyną trudnością są zbędne kroki których trzeba się pozbyć.

Algorytm wygląda następująco:

  1. Czytając po kolei poszczególne wskazówki mapujemy dany punkt [x, y]
  2. Sprawdzamy czy dany punkt był odwiedzony, jeśli nie -> patrz punkt 3. jeśli tak -> patrz punkt 4.
  3. Dodajemy dany punkt [x, y] do tablicy odwiedzonych, a daną wskazówkę do tablicy zapisanych wskazówek
  4. Za pomocą pętli cofamy się (kasując wszystkie napotkane punkty) aż trafimy do punktu [x, y] w tablicy odwiedzonych. Analogicznie przeprowadzamy czystki w tablicy zapisanych wskazówek.

Dzięki temu otrzymujemy najkrótszą ścieżkę do celu.

Dla ułatwienia można użyć canvas'a i wyświetlić ścieżkę w htmlu:
screenshot-20210203112020.png

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0