Jump to content
Ogen Dogen

DailyProgrammer Challenge

7 posts in this topic

Recommended Posts

Witam, żeby zmotywować się do regularnego odświeżania szarych komórek i swoich umiejętności postanowiłem wziąć udział w wyzwaniu w serwisie Reddit, gdzie codziennie są publikowane zadania do wykonania na różnym poziomie trudności. O ile będzie czas pozwalał, będę również starał się codziennie publikować swoje rezultaty. Głównym celem zadań jest rozwijanie myślenia algorytmicznego, dlatego w kodzie nie będę się skupiał na innych kwestiach np. walidacji wejścia. Językiem, który będę najczęściej używał będzie C#, chociaż postaram się czasami też użyć innych :)

 

Do każdego zadania będę podać link i krótki opis po Polsku.

 

Zadanie na dziś - "Sztuczne monety"

W skarbcu znajdują się monety. Każda z nich ma unikalny symbol, jednakże część z nich jest fałszywa. Możemy je rozpoznać po wadze - wszystkie prawdziwe monety ważą tyle samo, jak i wszystkie fałszywe monety ważą tyle samo. Jednakże fałszywe monety są lżejsze.

Na wejście otrzymujemy częściowe informacje o wybranych monetach - czy dwie monety ważą tyle samo lub czy pierwsza moneta jest cięższa od drugiej. Naszym zadaniem jest wskazanie wśród wszystkich wymienionych monet fałszywki np. dostając taką informację na wejście:

a x equal
b x equal
y a left

Powinniśmy dostać informację, że a,b,x są fałszywe. Dlaczego ? Ważą tyle samo i są lżejsze od y :)

Link do tematu: https://www.reddit.com/r/dailyprogrammer/comments/4utlaz/20160727_challenge_277_intermediate_fake_coins/?st=j09ypxnb&sh=909fc261

Moja propozycja implementacji: (na razie tylko dla pojedynczych monet)

// collecting input
string input = "";
List<string> inputs = new List<string>();
while (true)
{
	input = Console.ReadLine();
	if (input == "0") break;
	inputs.Add(input);
}

// parsing
Dictionary<string, int> coins = new Dictionary<string, int>();

string[] parts;
List<List<string>> groups = new List<List<string>>();
bool is_continue;
foreach (var line in inputs) // first looping - adding same coins and initializing dictionary
{
	parts = line.Split(' ');
	if (parts[0] == parts[1]) continue;
	is_continue = true;
	if (parts[2] == "equal") // adding coints
	{
		foreach (var group in groups) // first condition - joining
		{
			if (group.Contains(parts[0]))
			{
				group.Add(parts[1]);
				is_continue = false;
			}
			else if (group.Contains(parts[1]))
			{
				group.Add(parts[0]);
				is_continue = false;
			}
		}

		if (is_continue) // second condition - no group found, create new
		{
			groups.Add(new List<string>());
			groups.Last().Add(parts[0]);
			groups.Last().Add(parts[1]);
		}
	}

	// initializing dictionary
	if (!coins.ContainsKey(parts[0])) coins.Add(parts[0], 0);
	if (!coins.ContainsKey(parts[1])) coins.Add(parts[1], 0);
}

// second looping - counting heavier coins
for (int i=0; i<inputs.Count(); i++)
{
	parts = inputs[i].Split(' ');
	if (parts[2] == "left") coins[parts[0]]++;
}

// concluding
var tester = coins.First().Value;
if (coins.All(x => x.Value.Equals(tester) && tester == 0)) // all equal, can't say anything
{
	Console.WriteLine("Wszystkie sa prawdziwe lub wszystkie sa fałszywe");
	Console.ReadKey();
	return;
}

// real coins
var max_v = coins.Values.Max();
var max_k = coins.First(x => x.Value == max_v).Key;

// fake coins
var fakecoin_groups = groups.FindAll(x => !x.Contains(max_k));
if (fakecoin_groups.Count() > 0)
{
	Console.Write("Fałszywki: ");
	foreach (var fakecoin_group in fakecoin_groups)
	{
		foreach (var fakecoin in fakecoin_group)
		{
			Console.Write(fakecoin);
		}
		Console.WriteLine();
	}
}
else Console.WriteLine("Dane niespójne"); // assuming there's at least one fake coin
Console.ReadKey();

 

  • + rep 1

Share this post


Link to post
Share on other sites

Zadanie #2 - Odwrócony Regex

Zadanie zostało oznaczone jako trudne, ale wydaje mi się że jest to mocno przesadzone.

Regex, czyli narzędzie do obsługi wyrażeń regularnych służy do weryfikowania czy dany ciąg znaków pasuje do wzorca (wyrażenia regularnego). Niezbędne narzędzie do walidacji formularzy.

Pisałem o tym już w dziale AMXX:

Dzisiejszym zadaniem jest napisanie programu, który będzie działał w drugą stronę - na wejściu otrzymujemy wzorzec a na wyjściu mamy wygenerować przykładowy ciąg znaków pasujący do wzorca. Link do zadania - https://www.reddit.com/r/dailyprogrammer/comments/5zxebw/20170317_challenge_306_hard_generate_strings_to/?st=j0fsd6rs&sh=7cbc9448

Oczywiście program jest ograniczony i nie interpretuje wszystkich słów alfabetu wyrażeń, tylko te najważniejsze:

  • Literały (alfa-numeryki)
  • + (1 lub więcej)
  • * (0 lub więcej)
  • . (dowolny znak)
  • Przedziały wartości np. [a-d] (dowolny znak z przedziału obustronnie zamkniętego a-d)
Console.WriteLine("Podaj regex'a");
string input = Console.ReadLine();
StringBuilder output = new StringBuilder();
StringBuilder group = new StringBuilder();
Random rand = new Random();
bool is_group = false; // czy grupa ?

// główna pętla
int tmp = 0;
for (int i=0; i<input.Length; i++)
{
	// wykrywanie grup
	if (input[i] == '[') // początek grupy
	{
		is_group = true;
		continue;
	}
	else if (input[i] == ']') // koniec grupy
	{
		is_group = false;
		if (i + 1 < input.Length) // coś jeszcze jest za grupą
		{
			if (input[i+1] == '+') // dopisz wygenerowaną grupę do ostatecznego wyjścia
			{
				tmp = rand.Next(1, 5);
				for (int k = 0; k < tmp; k++) output.Append(group.ToString());
			}
			else if (input[i+1] == '*')
			{
				tmp = rand.Next(0, 5);
				for (int k = 0; k < tmp; k++) output.Append(group.ToString());
			}
			else output.Append(group.ToString());
		}
        else output.Append(group.ToString()); // nic nie ma za grupą
		group.Clear(); // wyczyść grupę aby zwolnić miejsce na następną (jeśli istnieje)
		continue;
	}


	// parsowanie
	if ((input[i] >= 'a' && input[i] <= 'z') || (input[i] >= 'A' && input[i] <= 'Z') || (input[i] >= '0' && input[i] <= '9'))
	{
		if (i + 1 == input.Length)
		{
			if (is_group) group.Append(input[i]); else output.Append(input[i]);
			continue;
		}

		if (input[i+1] != '+' && input[i+1] != '*')
		{
			if (is_group) group.Append(input[i]); else output.Append(input[i]);
			continue;
		}
		else if (input[i+1] == '+')
		{
			tmp = rand.Next(1, 5);
			for (int k = 0; k < tmp; k++) if (is_group) group.Append(input[i]); else output.Append(input[i]);
		}
		else if (input[i+1] == '*')
		{
			tmp = rand.Next(0, 5);
			for (int k = 0; k < tmp; k++) if (is_group) group.Append(input[i]); else output.Append(input[i]);
		}
	}
	else if (input[i] == '.')
	{
		char sign = (char)rand.Next(33, 126); // zakres czytelnych znaków
		if ((i + 1 == input.Length) || (input[i+1] != '+' && input[i+1] != '*')) // każdy inny literał, razem z kropką (bez uwzględnienia grup)
		{
			if (is_group) group.Append(input[i]); else output.Append(input[i]);
			continue;
		}
		else if (input[i+1] == '+')// + lub *
		{
			tmp = rand.Next(1, 5);
			for (int k = 0; k < tmp; k++) if (is_group) group.Append(input[i]); else output.Append(input[i]);
		}
		else if (input[i+1] == '*')
		{
			tmp = rand.Next(0, 5);
			for (int k = 0; k < tmp; k++) if (is_group) group.Append(input[i]); else output.Append(input[i]);
		}
	}
	else if (input[i] == '-') // parsowanie grupy
	{
		int lower_bound = (int)input[i - 1];
		int higher_bound = (int)input[i + 1];
		group.Remove(group.Length - 1, 1); // usuwamy literał ograniczający dolny przedział, dodany w poprzedniej iteracji, przed myślnikiem
		char sign = (char)rand.Next(lower_bound, higher_bound);
		if (input[i+2] == '+') // jeśli za grupą jest + lub *
		{
			tmp = rand.Next(1, 5);
			for (int k = 0; k < tmp; k++) group.Append(sign);
		}
		else if (input[i+2] == '*')
		{
			tmp = rand.Next(0, 5);
			for (int k = 0; k < tmp; k++) group.Append(sign);
		}
		else group.Append(sign); // jeśli coś innego to normalnie stwórz
		if (i + 1 < input.Length) i++; // przeskocz literał ograniczający górny przedział, iteracja przeskoczy zamykający nawias
	}
}
Console.Write("Przykładowy string pasujący do wzorca: ");
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine(output.ToString());
Console.ReadLine();

 

  • + rep 1

Share this post


Link to post
Share on other sites

Zadanie #3 - Problem Scrabble

Zadanie polega na odnalezieniu najdłuższego słowa, które można zbudować z danej frazy np. "la" Słowa badamy na podstawie słownika Scrabble - https://raw.githubusercontent.com/dolph/dictionary/master/enable1.txt

https://www.reddit.com/r/dailyprogrammer/comments/611tqx/20170322_challenge_307_intermediate_scrabble/?st=j0rzfpim&sh=c7180e47

 

Z racji, że kandydatów spełniających wymagania jest nieokreślona ilość, postanowiłem użyć struktury drzewa n-arnego. W tym celu implementujemy prostą klasę reprezentującą węzeł w takim drzewie. Każdy obiekt zawiera węzeł, który jest rodzicem oraz listę węzłów, które reprezentują potomków. Jeśli węzeł nie ma rodzica to nazywamy go korzeniem (na samej górze).

Jeśli węzeł nie ma potomków to nazywamy go liściem (na samym dole). Powiązując w ten sposób węzły tworzymy drzewo z różnymi ścieżkami możliwości.

class Node<T>
{
	private T data;
	private List<Node<T>> children;
	private Node<T> parent;

	public Node(T data, int planned_children = 2, Node<T> parent = null)
	{
		this.data = data;
		this.parent = parent;
		children = new List<Node<T>>(planned_children);
	}

	public void setParent(Node<T> parent)
	{
		if (parent == null) throw new NullReferenceException("Null given, node expected");
		this.parent = parent;
	}

	public Node<T> getParent()
	{
		return parent;
	}

	public void addChild(Node<T> child)
	{
		if (child == null) throw new NullReferenceException("Null given, node expected");
		children.Add(child);
	}

	public List<Node<T>> getChildren()
	{
		return children;
	}

	public T getData()
	{
		return data;
	}

	public bool isRoot()
	{
		if (parent == null) return true;
		return false;
	}

	public bool isLeaf()
	{
		if (children.Count() == 0) return true;
		return false;
	}
}

 

Główny program. Rekurencyjnie budujemy drzewo. Do każdego węzła dodajemy potomków spełniających kryteria (zawiera aktualny tekst i jest o 1 dłuższy), następnie wywołujemy metodę budującą na wszystkich potomkach. Rekurencja zatrzymuje się gdy dotrzemy do liścia.

Po zbudowaniu drzewa, również rekurencyjnie przeszukujemy drzewo w poszukiwaniu najdłuższego wyrażenia. Aby mieć pewność, że lokalne rozwiązania nie będą nam się nadpisywać to używamy statycznej zmiennej.

class Program
{
	private static string[] lines = File.ReadAllLines("enable1.txt");
	private static string longest = "";

	static void Main(string[] args)
	{
		Console.WriteLine("Podaj frazę");
		string letters = Console.ReadLine();

		Node<string> root = new Node<string>(letters); // korzeń
		buildTree(root);
		findAnswer(root);

		Console.WriteLine("Wynik: " + longest);
		Console.ReadKey();
	}

	private static void buildTree(Node<string> parent)
	{
		string data = parent.getData();
		foreach (var line in lines) // dla każdej znalezionej możliwości, dodawaj nowy węzeł
		{
			if (line.Length == data.Length + 1 && line.Contains(data))
			{
				try
				{
					parent.addChild(new Node<string>(line));
				}
				catch(NullReferenceException)
				{
					Console.WriteLine("Empty child");
				}
			}
		}

		if (parent.isLeaf()) return; // jeśli liść to przerwij
		var children = parent.getChildren();
		foreach (var child in children) buildTree(child);
	}

	private static void findAnswer(Node<string> parent)
	{
		if (parent.getData().Length > longest.Length) longest = parent.getData();
		if (parent.isLeaf()) return; // jeśli liść to przerwij
		var children = parent.getChildren();
		foreach (var child in children) findAnswer(child);
	}
}

 

Share this post


Link to post
Share on other sites

Zadanie #4 - Prosta symulacja pożaru

https://www.reddit.com/r/dailyprogrammer/comments/61ub0j/20170327_challenge_308_easy_let_it_burn/

Zadanie jest obszernie opisane, ale stosunkowo proste. Naszym zadaniem jest zasymulowanie pożaru, który rozprzestrzenia się według określonych zasad.

Na wejściu otrzymujemy planszę do gry (np. plan domu), gdzie każdy znak oznacza coś innego oraz pozycje (x,y), na których będzie umieszczany dym.

Symbole:

S <- dym
F <- ogien 
# <- sciana 
| <- zamkniete drzwi
/ <- otwarte drzwi 
= <- zniszczona sciana
_ <- zniszczona sciana lub drzwi
 <- otwarta przestrzen

Skrócone zasady:

  • Dym umieszczony na dym zamienia się w ogień
  • Dym umieszczony na ogniu powoduje eksplozje (opis później)
  • Zniszczony drzwi i ściany przekazują ogień na drugą stronę
  • Jeżeli ogień znajduje się obok dymu to dym również zaczyna się palić

Zasady eksplozji:

  • Eksplozja następuje gdy dym zostanie naniesiony na ogień
  • Ekspozycja powoduje, że ogień pojawia się na polach nad, pod, po lewej, po prawej od pola eksplozji
  • Jeżeli eksplozja trafi na ogień to przekazuje ogień dalej
  • Jeżeli ekspozja trafi na zamknięte drzwi lub ścianę to zostają zniszczone
  • Jeżeli eksplozja trafi na otwarte drzwi, rozwalone drzwi lub ścianę to ogień zostaje przekazany dalej

Główny program - tworzy obiekt klasy "House" i przekazuje ścieżki do plików z danymi

class Program
{
	static void Main(string[] args)
	{
		try
		{
			House house = new House("map.txt", "coords.txt");
			while (true) // main loop
			{
				if (!house.burn()) break;
				Console.ReadKey();
			}
		}
		catch(Exception e)
		{
			Console.WriteLine(e.Message);
			Console.WriteLine();
		}
		finally
		{
			Console.WriteLine();
			Console.WriteLine("Program executed. Press any key to continue...");
			Console.ReadKey();
		}
	}
}

 

Klasa House - Każde zadanie zostało wydzielone na osobną metodę. Część wykonuje się iteracyjnie (np. rysowanie planszy) a część rekurencyjnie.

Dodatkowym problem jaki tu się pojawił (przynajmniej w C#) to odczytanie odwróconej planszy. Aby przywrócić ją do pierwotnego stanu należy wykonać operacje znaną z zastosowania przy macierzach - transpozycja.

 

class House
{
	private List<string> map;
	private List<Coord> coords;
	public House(string path_map, string path_coords)
	{
		try
		{
			List<string> map = File.ReadAllLines(path_map).ToList();
			this.map = Transpose(map);

			string[] str_coords = File.ReadAllLines(path_coords);
			coords = new List<Coord>(str_coords.Count());
			foreach(var coord in str_coords) // parse coords
			{
				string[] tmp = coord.Split(' ');
				try
				{
					coords.Add(new Coord(Int32.Parse(tmp[0]), Int32.Parse(tmp[1])));
				}
				catch
				{
					throw;
				}
			}
		}
		catch
		{
			throw;
		}
	}

	private struct Coord
	{
		public int x;
		public int y;
		public Coord(int x, int y)
		{
			this.x = x;
			this.y = y;
		}
	}

	private List<string> Transpose(List<string> input)
	{
		List<string> transposed = new List<string>(input.Count());
		StringBuilder builder = new StringBuilder();

		int first_size = input.First().Length;
		foreach (var item in input)
		{
			if (item.Length != first_size) throw new Exception("Matrix isn't rectangular");
		}

		int max_len = 0;
		foreach (var item in input) { if (item.Length > max_len) max_len = item.Length; }

		int iterator = 0;
		do
		{
			for (int i = 0; i < input.Count(); i++)
			{
				try
				{
					builder.Append(input[i][iterator]);
				}
				catch (IndexOutOfRangeException)
				{
					continue;
				}
			}

			transposed.Add(builder.ToString());
			builder.Clear();

			iterator++;
		}
		while (iterator < max_len);

		return transposed;
	}

	private string ReplaceAtIndex(int i, char value, string word)
	{
		char[] letters = word.ToCharArray();
		letters[i] = value;
		return string.Join("", letters);
	}

	private void repaintHouse()
	{
		Console.Clear();
		Console.SetCursorPosition(0, 0);

		for (int x=0; x<map.Count(); x++)
		{
			for (int y=0; y<map[x].Length; y++)
			{
				Console.SetCursorPosition(x, y);
				if (map[x][y] == 'F') Console.ForegroundColor = ConsoleColor.Red;
				else if (map[x][y] == 'S') Console.ForegroundColor = ConsoleColor.Gray;
				else Console.ForegroundColor = ConsoleColor.White;
				Console.Write(map[x][y]);
			}
		}
	}

	private void propagateFire()
	{
		for (int i=0; i<map.Count(); i++)
		{
			for (int j=0; j<map[i].Length; j++)
			{
				try
				{
					if (map[i][j] == 'F')
					{
						for (int x = i - 1; x <= i + 1; x++)
						{
							for (int y = j - 1; y <= j + 1; y++)
							{
								if (x == i && y == j) continue;
								if (map[x][y] == 'S')
								{
									map[x] = ReplaceAtIndex(y, 'F', map[x]);
									propagateFire();
									return;
								}
							}
						}
					}
					else if (map[i][j] == '_')
					{
						for (int x = i - 1; x <= i + 1; x++)
						{
							for (int y = j - 1; y <= j + 1; y++)
							{
								if (x == i && y == j) continue;
								if (map[x][y] == 'F')
								{
									// x,y -> Fire
									// i,j -> Broken Doors
									if (i - 1 == x && j - 1 == y) map[i+1] = ReplaceAtIndex(j+1, 'F', map[i+1]);
									else if (i == x && j - 1 == y) map[i] = ReplaceAtIndex(j+1, 'F', map[i]);
									else if (i+1 == x && j - 1 == y) map[i-1] = ReplaceAtIndex(j+1, 'F', map[i-1]);
									else if (i-1 == x && j == y) map[i+1] = ReplaceAtIndex(j, 'F', map[i+1]);
									// i won't check myself, besides it would be unreachable code, because of statement above
									else if (i+1 == x && j == y) map[i-1] = ReplaceAtIndex(j, 'F', map[i-1]);
									else if (i-1 == x && j+1 == y) map[i+1] = ReplaceAtIndex(j-1, 'F', map[i+1]);
									else if (i == x && j+1 == y) map[i] = ReplaceAtIndex(j-1, 'F', map[i]);
									else if (i+1 == x && j+1 == y) map[i-1] = ReplaceAtIndex(j-1, 'F', map[i-1]);
								}
							}
						}
					}
				}
				catch(IndexOutOfRangeException)
				{
					continue;
				}
			}
		}
	}

	private void doExplosion(int x, int y, bool first=true, char direction=' ') // todo
	{
		try
		{
			Debug.WriteLine("Explosion at " + x + "," + y);
			if (map[x][y] == 'S') return;
			if (first)
			{
				doExplosion(x + 1, y, false, 'R'); // right
				doExplosion(x - 1, y, false, 'L'); // left
				doExplosion(x, y - 1, false, 'U'); // up
				doExplosion(x, y + 1, false, 'D'); // down
			}
			else
			{
				if (map[x][y] == '#') map[x] = ReplaceAtIndex(y, '=', map[x]);
				else if (map[x][y] == '|') map[x] = ReplaceAtIndex(y, '_', map[x]);
				else if (map[x][y] == '=') map[x] = ReplaceAtIndex(y, '_', map[x]);
				else if (map[x][y] == ' ') map[x] = ReplaceAtIndex(y, 'F', map[x]);
				else if (map[x][y] == 'F' || map[x][y] == '/' || map[x][y] == '_') doTraverse(x, y, direction);
			}
		}
		catch(IndexOutOfRangeException)
		{
			return;
		}
	}

	private void doTraverse(int x, int y, char direction)
	{
		try
		{
			if (direction == 'L') x--;
			else if (direction == 'U') y--;
			else if (direction == 'D') y++;
			else if (direction == 'R') x++;
			Debug.WriteLine("Traverse at " + x + " " + y);

			switch(map[x][y])
			{
				case 'F':
					doTraverse(x, y, direction);
					break;
				case '/':
					if (direction == 'L') x--;
					else if (direction == 'U') y--;
					else if (direction == 'D') y++;
					else if (direction == 'R') x++;
					doTraverse(x, y, direction);
					break;
				case '_':
					if (direction == 'L') x--;
					else if (direction == 'U') y--;
					else if (direction == 'D') y++;
					else if (direction == 'R') x++;
					doTraverse(x, y, direction);
					break;
				case ' ':
					map[x] = ReplaceAtIndex(y, 'F', map[y]);
					return;
				default:
					return;
			}
		}
		catch(IndexOutOfRangeException)
		{
			return;
		}
	}

	public bool burn()
	{
		if (coords.Count() == 0) return false;
		int x = coords.First().x;
		int y = coords.First().y;

		try
		{
			char item = map[x][y];
			if (item == ' ') map[x] = ReplaceAtIndex(y, 'S', map[x]);
			else if (item == 'S') map[x] = ReplaceAtIndex(y, 'F', map[x]);
			else if (item == 'F') doExplosion(x, y);
		}
		catch(IndexOutOfRangeException) // ignore coords out of range
		{
			Debug.WriteLine("Ignored at " + x + " " + y);
			return true;
		}
		finally
		{
			coords.RemoveAt(0);
			propagateFire();
			repaintHouse();
		}

		return true;
	}
}

Główną metodą jest tu metoda "burn", która wykonuje się dotąd aż zwróci fałsz co oznacza, że odczytane zostały wszystkie koordynaty na wejściu.

Dla ułatwienia aby uniknąć podania błędnego wejścia (pozycja spoza tablicy) wszędzie została dodana obsługa wyjątku IndexOutOfRangeException.

Przykład - dla planszy:

#############/#
#     |       #
#     #       #
#     #       #
#######       #
#     _       #
###############

Oraz pozycji:

1 1
1 2
1 3
5 6
7 5
1 1
5 5
5 5
9 1
5 7
2 2
7 1
8 1
9 1
10 1
10 1

Otrzymujemy taki wynik:

15197f73cf.png

Share this post


Link to post
Share on other sites

Zadanie #5

 

"Droga do Filozofii"

Na angielskiej Wikipedii wybierając dowolny artykuł i klikając w kolejne linki prawie zawsze dojdziemy do artykułu "Philosophy". Według badań w 2011 roku dotyczy to około 95% stron na wikipedii.

Zadanie polega na zaimplementowaniu programu, który wykona ten proces automatycznie i wskaże nam ścieżkę jaką przebył. (optymalnie powinien wybierać najlepszą) Tutaj zostało przedstawione to zjawisko -

 

 

Moje rozwiązanie jest nie co uproszczone, ponieważ przeszukuje całe artykuły w poszukiwaniu hasła związanego z filozofią.

Użyłem w nim biblioteki HtmlAgilityPack z pakietu NuGet do parsowania kodu HTML. Ścieżka do danego elementu jest zapisana w formacie XPath.

Console.WriteLine("Write name of an article");
string title = Console.ReadLine();
Console.WriteLine();
Console.WriteLine(title);
title = title.Replace(" ", "_");

string content = String.Empty;
WebClient client = new WebClient();

HtmlDocument doc = new HtmlDocument();

while (title != "Philosophy")
{
    string page = client.DownloadString("http://en.wikipedia.org/wiki/" + title);
    if (page.Contains("/wiki/Philosophy")) break;
    doc.LoadHtml(page);

    // get title of next article
    HtmlNode node = doc.DocumentNode.SelectSingleNode("//body/div[@id='content']/div[@id='bodyContent']/div[@id='mw-content-text']/div[@class='mw-parser-output']/p/a[1]");
    title = node.Attributes["href"].Value.Split('/')[2];

    Console.WriteLine(title.Replace("_", " "));
}

Console.WriteLine();
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine("Done! You have found Philosophy article !");
Console.ReadLine();

 

  • + rep 1

Share this post


Link to post
Share on other sites

Zadanie #6

Tym razem nie z reddita, a proste zadanie algorytmiczne z zbioru zadań pisane z nudów :D - "Problem ośmiu hetmanów"

Zadanie w skrócie: Umieścić na szachownicy 8 hetmanów (damek) w taki sposób aby się nie biły nawzajem.

Szczegóły: https://pl.wikipedia.org/wiki/Problem_ośmiu_hetmanów

 

W tym zadaniu będziemy szukać wszystkich możliwych układów.

Rozwiązanie w formie klasy, składa się na nią kilka metod rozwiązujących pod problemy jak np. sprawdzenie czy dany hetman jest w konflikcie z innym ? (bije innego)

Główną metodą jest metoda "iterate", która idzie po wszystkich możliwych ustawieniach według kodowania zaproponowanego na wikipedii (numery wierszy licząc od skrajnie prawej kolumny).

Ponad to, bierze pod uwagę tylko kody składające się z unikalnych znaków np. 12345678 (nie trzeba brać innych, ponieważ oznaczają wtedy że w rzędzie znajduje się więcej niż jeden hetman co automatycznie dyskwalifikuje rozwiązanie).

namespace eight_queens_problem
{
    class Chessboard
    {
        private bool[,] board;
        public Chessboard()
        {
            board = new bool[8, 8];
        }

        public void init()
        {
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    board[i, j] = false;
                }
            }
        }

        public void reset()
        {
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    board[i, j] = false;
                }
            }
        }

        public string iterate(string start_code)
        {
            string code = start_code;
            reset();
            put_queen(0, 0); // ustaw celowo złą konfigurację aby zapobiec natychmiastowemu rozwiązaniu i umożliwić wejście do pętli
            put_queen(1, 1);
            while (!is_solved())
            {
                reset();
                while (!is_string_chars_unique(code))
                {
                    code = doStep(code);
                    if (code == "77777777") return "77777777";
                }
                for (int i = 0; i < 8; i++) put_queen(i, Int32.Parse(code[i].ToString()));
                code = doStep(code);
            }

            int i_code = Int32.Parse(code);
            Console.WriteLine("Problem solved: " + tabCodeToHuman(code));
            visualize_board();
            return code;
        }

        private bool is_conflict(int x, int y)
        {
            if (is_free(x, y)) throw new Exception("There is no queen !");
            int start_x = x;
            int start_y = y;

            x--;
            for (int i = x; i >= 0; i--) // w lewo
                if (board[i, start_y])
                    return true;

            x = start_x + 1;
            y = start_y;
            for (int i = x; i < 8; i++) // w prawo
                if (board[i, y])
                    return true;

            x = start_x;
            y = start_y - 1;
            for (int j = y; j >= 0; j--) // w górę
                if (board[x, j])
                    return true;

            x = start_x;
            y = start_y + 1;
            for (int j = y; j < 8; j++) // w prawo
                if (board[x, j])
                    return true;

            x = start_x - 1;
            y = start_y;
            int tmp_j = start_y;
            for (int i = x; i >= 0; i--) // skos lewo góra (x--, y--)
            {
                tmp_j--;
                if (tmp_j < 0 || tmp_j > 7) break;
                if (board[i, tmp_j])
                    return true;
            }

            x = start_x + 1;
            y = start_y;
            tmp_j = y;
            for (int i = x; i < 8; i++) // skos prawo góra (x++, y--)
            {
                tmp_j--;
                if (tmp_j < 0 || tmp_j > 7) break;
                if (board[i, tmp_j])
                    return true;
            }

            x = start_x - 1;
            y = start_y;
            tmp_j = y;
            for (int i = x; i >= 0; i--) // skos lewo dół (x--, y++)
            {
                tmp_j++;
                if (tmp_j < 0 || tmp_j > 7) break;
                if (board[i, tmp_j])
                    return true;
            }

            x = start_x + 1;
            y = start_y;
            tmp_j = y;
            for (int i = x; i < 8; i++) // skos prawo dół (x++, y++)
            {
                tmp_j++;
                if (tmp_j < 0 || tmp_j > 7) break;
                if (board[i, tmp_j])
                    return true;
            }

            return false;
        }

        private int count()
        {
            int counter = 0;
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    if (board[i, j]) counter++;
                }
            }
            return counter;
        }

        private void put_queen(int x, int y)
        {
            board[x, y] = true;
        }

        private void visualize_board()
        {
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    if (board[i, j])
                    {
                        Console.ForegroundColor = ConsoleColor.Red;
                        Console.Write("1");
                    }
                    else
                    {
                        Console.ForegroundColor = ConsoleColor.White;
                        Console.Write("0");
                    }
                }
                Console.WriteLine();
            }
            Console.ResetColor();
        }

        private bool is_free(int x, int y)
        {
            return !board[x, y];
        }

        private bool is_solved()
        {
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    if (!is_free(i, j) && is_conflict(i, j)) return false; // jeżeli przynajmniej jedno pole jest zajęte i ma konflikt to brak rozwiązania
                }
            }
            return true;
        }

        private string tabCodeToHuman(string code)
        {
            if (code.Length != 8) return String.Empty;
            StringBuilder builder = new StringBuilder();
            for (int column = 7; column >= 0; column--)
            {
                for (int row = 0; row < 8; row++)
                {
                    if (board[row, column])
                    {
                        row++;
                        builder.Append(row);
                        break;
                    }
                }
            }

            for (int i = 0; i < builder.Length; i++)
            {
                switch (builder[i])
                {
                    case '3':
                        builder[i] = '6';
                        break;
                    case '6':
                        builder[i] = '3';
                        break;
                    case '4':
                        builder[i] = '5';
                        break;
                    case '2':
                        builder[i] = '7';
                        break;
                    case '8':
                        builder[i] = '1';
                        break;
                    case '5':
                        builder[i] = '4';
                        break;
                    case '7':
                        builder[i] = '2';
                        break;
                    case '1':
                        builder[i] = '8';
                        break;
                }
            }

            return builder.ToString();
        }

        private string doStep(string queens)
        {
            StringBuilder builder = new StringBuilder(queens);
            for (int i = 7; i >= 0; i--)
            {
                if (builder[i] == '7')
                {
                    builder[i] = '0';
                }
                else
                {
                    builder[i]++;
                    break;
                }
            }
            return builder.ToString();
        }

        private bool is_string_chars_unique(string s)
        {
            bool[] array = new bool[256];

            foreach (char value in s)
            {
                if (array[(int)value]) return false;
                else array[(int)value] = true;
            }

            return true;
        }
    }
}

W main proste wywołanie, rozpoczynamy iteracje od 0000000 (wszystkie hetmany w pierwszym rzędzie) aż do 77777777 (wszystkie hetmany w ostatnim rzędzie).

Mimo, że kombinacji ułożenia jest sporo (8^8) to wygenerowanie wszystkich 92 możliwości nie trwa długo (kilka sekund).

Chessboard board = new Chessboard();
board.init();
board.reset();

string start_code = "00000000";
int counter = 0;
while (start_code != "77777777")
{
	start_code = board.iterate(start_code);
	counter++;
}
Console.WriteLine("Liczba rozwiązań: " + --counter); // pomniejszone o 1, ponieważ ostatni krok pętli jest nieważny
Console.ReadKey();

Przykładowe rozwiązanie:

18365e498c.png

Share this post


Link to post
Share on other sites

Zadanie #7 - "99 bottles of beer on the wall"

Dzisiaj coś prostego. Już oklepane zadanie na wszystkie możliwe strony, mianowicie wyświetlenie tekstu piosenki z tytułu zadania.

Jest to jedno z pierwszych zadań dla początkującego programistów. Tym razem dla odmiany zrobiłem w Pythonie.

Zadanie nie bez powodu jest oklepane, ponieważ przyjęło się że internauci próbują je zaimplementować w wszystkich możliwych językach - http://www.99-bottles-of-beer.net/lyrics.html

 

 

Tutaj mój kod i jego działanie. Już prościej się chyba nie dało :D

import time

for bottles in range(99,1,-1):
	print(str(bottles) + " bottles of beer on the wall, " + str(bottles) + " bottles of beer.")
	print("Take one down and pass it around, " + str(bottles) + " bottles of beer on the wall.\n")
	time.sleep(0.1)
	
print("1 bottle of beer on the wall, 1 bottle of beer.\nTake one down and pass it around, no more bottles of beer on the wall.\n")
print("No more bottles of beer on the wall, no more bottles of beer.\nGo to the store and buy some more, 99 bottles of beer on the wall.")

b381091730.gif

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.

  • Recently Browsing   0 members

    No registered users viewing this page.

O Nas

CSKatowice.com powstało dnia 28 lipca 2012 roku. Jesteśmy prężnie rozwijającą się siecią serwerów Counter-Strike. Nasza młoda i uzdolniona kadra Administratorów pozwala nam się szybko rozwijać!

Społeczność

Reklama

cskatowice
×