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

0

Wydaje mi się, że z treści zadania nie wynika, że trzeba poruszać się po konkretnej ścieżce, chodzi chyba tylko o wyznaczenie punktu ze skarbem i drogi do niego, dlatego zrobiłbym to po prostu tak:

//generowanie mapy

for($i=0; $i<100; $i++){
	
	$mapa[$i]=array(rand(0,3),rand(1,100));
	// echo $mapa[$i][0]." ".$mapa[$i][1]."<br/>"; // wyświetlenie punktow
}
foreach($mapa as $p){
	$kroki[$p[0]]+=$p[1];  // sumujemy kroki zrobione w kazdym z kierunków.
}

$NS = $kroki[0] - $kroki[1]; // zmienna $kroki[0] zawiera wszystkie kroki zrobione na północ, $kroki[1] na południe
$WE = $kroki[2] - $kroki[3]; // analogicznie wshod/zachod



if($NS < 0){    //sprawdzmay w jakim kierunku N/S  i  zapisujemy liczbę kroków do zorbienia
	$wynik[0][0]=1;
	$wynik[0][1]=-1*$NS;
}
else{
	$wynik[0][0]=0;
	$wynik[0][1]=$NS;
}


if($WE < 0){    //sprawdzmay w jakim kierunku W/E  i  zapisujemy liczbę kroków do zorbienia
	$wynik[1][0]=3;
	$wynik[1][1]=-1*$WE;
}
else{
	$wynik[1][0]=2;
	$wynik[1][1]=$WE;
}


//jeżeli nie zrobimy zadnego kroku to znaczy że skarb jest pod głazem
if($wynik[0][1]==0 && $wynik[1][1] == 0){
	echo "GŁAZ"."<br/>";
}

echo $wynik[0][0]." ".$wynik[0][1]."<br/>";
echo $wynik[1][0]." ".$wynik[1][1]."<br/>";
//return $wynik; // 
0

Jeśli nie umiesz rozwiązać tego zadania to jaki sens ma przedstawić im gotowca nienapisanego przez ciebie? To znak ze się nienadajesz ale to nic zlego. Lepiej chyba isc do pracy gdzie wiesz ze twoje umiejetnosci sa wystarczajace. Czy ktos z nas chcialby isc do chirurga na operacje wiedzac ze koles nie wie co ma robic ?

0

Wiecie, że odpowiadacie na pytanie zadane ponad rok temu?

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