Trening z klawiaturą #3 – sekwencja zadań

Chciałbym przedstawić kolejne, proste ćwiczenie, z którym miałem do czynienia całkiem niedawno.

Załóżmy, że w pewnym systemie istnieje zestaw zadań (procesów) do wykonania. Niech każde zadanie opisane będzie pojedynczą literą (A,B,C itd…). Ponadto, pomiędzy zadaniami istnieją zależności. Na ten przykład powiedzmy, że zadanie A może być wykonane dopiero wówczas, gdy wykonane zostało zadanie C, a zadanie B może zostać wykonane tylko po skończeniu zadania D.

W symbolicznym zapisie prezentuje się to następująco:
A => C
B => D
C
D

Celem ćwiczenia jest napisanie narzędzia (klasa lub pojedyncza funkcja), która będzie w stanie przyjąć konfigurację zależności w ustalonym formacie oraz dla podanej sekwencji zadań, zwróci te same zadania ale uporządkowane w jednej z poprawnych kolejności (może być kilka), biorąc pod uwagę zależności pomiędzy zadaniami. Dla uproszczenia przyjmijmy, że lista to zadań to ciąg znaków (string), a zależności to lista par klucz => wartość (ang. key => value).

Czyli posługując się pseudokodem:

jobManager->setup(A => C, B => D); // ustaw zaleznosci
jobManager->resolve("ABCD"); // powinno zwrócić np. CDAB

Dodatkowe informacje:

  • Jeżeli nie ma żadnych zależności, podany ciąg zadań nie powinien ulec zmianie
  • Jeżeli podana sekwencja jest pusta (pusty ciąg znaków), również pusty powinien być wynik
  • Jeżeli podana struktura zależności jest cykliczna (np. C zależy od samego siebie lub C zależy od A, A zależy od B, które znów zależy od C), program powinien w jakiś sposób poinformować użytkownika o błędzie. (np. zgłosić wyjątek)

Bonus: Ulepsz algorytm, który bierze pod uwagę kilka zależności dla jednego zadania, np. C może być wykonane dopiero, gdy wykonane zostanie zarówno A jak i B. (C => AB)

— — — — — — — — — — — —

Opis rozwiązania.

Osobiście tego typu problemy zwykle podchodzę od strony testów. Mamy rozpisaną listę wymagań i scenariuszy, które musimy spełnić, więc warto zacząć od napisania testu jednostkowego sprawdzający każdy z nich. Tym razem użyję C# i paczki nUnit.

 

[TestFixture]
public class GivenTheJobberInstanceAndNoStructure
{
	IJobber _subject;

	[SetUp]
	public void SetUpTheStructure()
	{
		_subject = new Jobber();
	}

	[Test]
	public void WhenPassingAnEmptyStringItResolvesWithEmptySequence()
	{
		var result = _subject.Resolve(string.Empty);

		Assert.That(result == string.Empty, Is.True, "The resolved sequence is not empty.");
	}

	[Test]
	public void WhenPassingOneJobSequenceItShouldResolveWithThisOneJob()
	{
		var result = _subject.Resolve("A");

		Assert.That(result == "A", Is.True, "The resolved sequence is not the same as input.");
	}

	[Test]
	public void WhenPassingSequenceOfFewJobsItShouldResolveWithoutAffectingTheOrder()
	{
		var result = _subject.Resolve("ABC");

		Assert.That(result == "ABC", Is.True, "The resolved sequence is not the same as input.");
	}
}

W sekcji SetUp tworzymy po prostu obiekt naszego Jobbera (tak nazwałem klasę rozwiązującą kolejność zadań).
Powyższe testy pokrywają interesujące scenariusze przy założeniu, że zależności pomiędzy zadaniami nie zostały sprecyzowane. Mamy więc pusta sekwencję zadań i pusty wynik, a w przypadku sekwencji wejściowej z jednym lub więcej znaków, dane wyjściowe nie ulegają zmianie. To podstawowe działanie naszego przyszłego algorytmu ale i podstawy warto zadbać!

Warto zaznaczyć, że testowane wyniki są często tylko jednymi z poprawnych rozwiązań, jako, że w tego typu scenariuszu nie ma znaczenia zwracana kolejność zadań.

 


	[TestFixture]
	public class GivenTheJobberInstanceAndSingleDependency
	{
		IJobber _subject;

		[SetUp]
		public void SetUpTheStructure()
		{
			_subject = new Jobber();
			_subject.Setup(new Dictionary<char, string> { { 'B', "C" } });
		}

		[Test]
		public void WhenPassingSequenceOfThreeJobsItResolvesTheCorrectOrder()
		{
			var result = _subject.Resolve("ABC");

			Assert.That(result == "CAB", Is.True, "The resolved order is incorrect.");
		}
	}

Kolejna porcja testów sprawdza jak nasz algorytm zachowuje się w momencie, gdy ustawimy pojedynczą zależność między zadaniami. Projektujemy w ten sposób metodę Setup, która jako argument przyjmuje Dictionary (struktura w C#, która jest zestawem par klucz => wartość). To powinno wystarczyć by opisać nawet najbardziej skomplikowane zależności.
Nie ma problemu jeśli masz lepszy lub alternatywny pomysł na opisanie tych zależności, chętnie poznam inny tok myślenia!
Tak więc w tym przypadku mamy trzy zadania (A,B i C), przy czym do wykonania B potrzeba mieć skończone zadanie C. Nasz pilnuje żeby klasa Jobber poprawnie rozwiązywała taki przypadek.

Przejdźmy dalej…

[TestFixture]
	public class GivenTheJobberInstanceAndSingleDependencyOnItself
	{
		IJobber _subject;

		[SetUp]
		public void SetUpTheValidStructure()
		{
			_subject = new Jobber();
			_subject.Setup(new Dictionary<char, string> { { 'C', "C" } });
		}

		[Test]
		public void WhenResolvingTheIncorrectJobsStructureItThrowsAnError()
		{
			var result = _subject.Resolve("AC");
			Assert.Throws<CircularJobDependencyException>(() => { }, "The circular dependency has not been detected when expected!");
		}
	}

Wspominałem wcześniej, że nasze rozwiązanie musi być wrażliwe na punkcie niepoprawnych, to jest cyklicznych zależności. Bez tego nasz system zawieszał by się w nieskończonej pętli, a to nigdy nie jest dobre. Także zapewniamy, że algorytm zostaje przerwany a program jest w stanie wychwycić taką sytuację. Ja posłużyłem się klasycznym wyjątkiem, którego implementację pozostawiam Tobie. W razie kłopotów i tak cały kod rozwiązania jest na moim githubie. 🙂

Podsumowując powyższy fragment, jeżeli podamy Jobberowi niewłaściwe dane i spróbujemy rozwiązać oparte o nie zależności, program wyrzuci odpowiedni wyjątek, a nasz test zapewni nas o istnieniu takiej funkcjonalności.

 

Dalej…

	[TestFixture]
	public class GivenTheJobberInstanceAndMultipleValidDependenciesBetweenJobs
	{
		IJobber _subject;

		[SetUp]
		public void SetUpTheStructure()
		{
			_subject = new Jobber();
			_subject.Setup(new Dictionary<char, string> {
				{ 'B', "C" },
				{ 'C', "F" },
				{ 'D', "A" },
				{ 'E', "B" }
			});
		}

		[Test]
		public void WhenResolvingMultipleJobsDependenciesItReturnsTheCorrectOrderOfJobs()
		{
			var result = _subject.Resolve("ABCDEF");
			
			Assert.That(result == "AFCDBE" || result == "FACDBE" || result == "AFDCBE" || result == "FADCBE", Is.True, "The resolved order is incorrect.");
		}
	}

Przypadek ten pokrywa sytuację, gdy mamy kilka pojedynczych zależności pomiędzy zadaniami. Nie do końca podoba mi się, że wypisałem prawie wszystkie poprawne wyniki, ale zostawiam to dla uproszczenia. W zależności od rozwiązania, test może być niezdany bo akurat nie wymieniłem jednego z poprawnych rozwiązań. W takim przypadku należy je po prostu dodać lub opracować coś bardziej zmyślnego.

Oczywiście testy nawet się nie skompilują, bo klasa na ten moment jeszcze nie istnieje. Stwórzmy ją więc, co pozwoli na zdanie jednego czy dwóch pierwszych testów.

 

	public interface IJobber
	{
		void Setup(Dictionary<char, string> structure);
		bool IsValid();
		string Resolve(string jobSequence);
	}

    public class Jobber : IJobber
    {
		private Dictionary<char, string> _structure;

		private bool GotDependencies
		{
			get { return (_structure != null && _structure.Count > 0); }
		}

		public void Setup(Dictionary<char, string> structure)
		{
			_structure = structure;
		}

		public bool IsValid()
		{
			return true;
		}

		public string Resolve(string jobSequence)
		{
			return string.Empty;
		}
    }

Interfejs IJobber nie jest nam niezbędny, ale to zawsze dobry nawyk opisywać klasy w ten sposób. Klasa Jobber implementuje teraz wszystkie używane metody i dzięki domyślnemu działaniu zdaje przynajmniej jeden test, ten z pustą sekwencją wejściową. 🙂 Małymi kroczkami…!

Moim pomysłem na rozwiązanie tego problemu jest zacząć od wykonania wszystkich zadań wolnych od zależności, co zwiększa następnie szanse, że kolejne zadania będą już gotowe do wykonania.

Przygotujmy najpierw jakiś szkielet logiki…

public string Resolve(string jobSequence)
{
	if (jobSequence == string.Empty)
		return string.Empty;
	else if (jobSequence.Length == 1 || !GotDependencies)
		return jobSequence;
	else {
		return null; // na razie nic
	}
}

To modyfikacja pozwala na niezmienianie danych wejściowych, jeżeli nie ma zależności, zyskujemy w ten sposób kolejny zdany test.

 

Kontynuujemy nasz pusty blok else

			else {
				string jobsDone = string.Empty;
				string workingQueue = jobSequence;

				while (!string.IsNullOrEmpty(workingQueue)) {
					bool removedSomething = false;
					
					for (int idx = 0; idx < workingQueue.Length; idx++) {
						var curr = workingQueue[idx];

						if (!_structure.ContainsKey(curr)) {
							jobsDone += curr;
							workingQueue = workingQueue.Remove(idx, 1);
							removedSomething = true;
						} else {
							// zaleznosci na koniec
						}
					}

					if(!removedSomething)
						break;
				}
			}

Czyli na początku zajmujemy się takimi zadaniami, które nie są kluczami w słowniku zależności. Dorzucamy każdy taki kolejny przypadek do listy obsłużonych zadań (jobsDone, usuwamy zadanie z kolejki (workingQueue) i oznaczamy, że w danym przebiegu co najmniej jedno zadanie zostało zdjęte z kolejki, czyli wykonane. (removedSomething) Na pierwszy rzut oka może pojawić się pytanie po co właściwie to oznaczać. Odpowiedź jest prosta, pozwala nam się to zabezpieczyć na wypadek gdyby pewnych zadań nie dało się wykonać nigdy i wówczas skończylibyśmy z nieskończoną pętlą! 🙁

Skupmy się teraz na głównej części naszej metody i dopiszmy obsługę zadań obarczonych zależnościami:

public string Resolve(string jobSequence)
{
	if (jobSequence == string.Empty)
		return string.Empty;
	else if (jobSequence.Length == 1 || !GotDependencies)
		return jobSequence;
	else {
		string jobsDone = string.Empty;
		string workingQueue = jobSequence;

		while (!string.IsNullOrEmpty(workingQueue)) {
			bool removedSomething = false;
			
			for (int idx = 0; idx < workingQueue.Length; idx++) {
				var curr = workingQueue[idx];

				if (!_structure.ContainsKey(curr)) {
					jobsDone += curr;
					workingQueue = workingQueue.Remove(idx, 1);
					removedSomething = true;
				} else {
					bool readyToGo = true;
					foreach (var dependency in _structure[curr]) {
						if (!jobsDone.Contains(dependency.ToString()))
							readyToGo = false;
					}

					if (readyToGo) {
						jobsDone += curr;
						workingQueue = workingQueue.Remove(idx, 1);
						removedSomething = true;
					}
				}
			}

			if (!removedSomething) {
				// this will break the infinite loop when needed
				throw new CircularJobDependencyException();
			}
		}

		return jobsDone;
	}
}

Dla przypomnienia, pod zmienną curr znajduje się aktualnie sprawdzane zadanie. Przeglądamy więc listę zależności dla naszego zadania i sprawdzamy, czy jest ono już w „zrobionych”. Jeżeli każde z nich jest już wykonane (flaga readyToGo pozostaje nienaruszona), możemy zrobić to co ze zwykłymi zadaniami. Czyli wyrzucamy z kolejki, dorzucamy do zakończonych i tak w kółko, aż do opróżnienia kolejki. Jeżeli w przestajemy wykonywać zadania w danym przebiegu, oznacza to, że zależności nie udaje się rozwiązać i prawdopodobnie będziemy błądzić w nieskończoność. Dlatego w takim przypadku wyrzucamy odpowiedni wyjątek (własny, wspomniany wyżej), który przerwie syzyfową pracę i powiadomi resztę aplikacji o zaistniałej sytuacji.

To by było na tyle, test zdane, problem rozwiązany.

Trudne? Nie! Zapraszam do zapoznania się z pełną wersją mojego rozwiązania na githubie, do eksperymentowania oraz do zgłaszania cennych uwag i być może lepszych, własnych pomysłów!