Locked DailyProgrammer Challenge

Ogen Dogen · March 14, 2017

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();

Ogen Dogen · March 18, 2017