Advent of Code – hetedik nap

Már egy hete megy a kihívás, szépen lassan nehezednek a feladatok. Ma mégis egy viszonylag gyorsan megoldható került terítékre. Nézzük is meg!

Feladatleírás – első rész

Egy óriásbálna úgy döntött, hogy a tengeralattjáród lesz a vacsorája. Sokkal gyorsabb mint te, nincs hova menekülnöd!

Hirtelen egy rákraj (mindegyik a saját apró tengeralattjárójában) közelít, hogy megmentsen! Úgy tűnik, lyukat készülnek robbantani az óceán fenekén; a hajód érzékelői egy hatalmas földalatti barlangrendszert észlelnek.

Közben azt figyeled meg, hogy a rákok tengeralattjárói csak egy tengely mentén tudnak mozogni.

Gyors készítesz egy listát a rákok pozícióiról. A rákok tengeralattjáróinak kicsi az üzemanyagtartálya. Egy pozícióba kell, hogy kerüljenek a robbantáshoz. A te feladatod megtalálni azt a pozíciót, ahova az összes rák eljutása a lehető legkevesebb üzemanyag felhasználásával jár.

Vegyük például, ha az alábbi pozíciókat veszik fel a rákok:

16,1,2,0,4,2,7,1,2,14

Ezt azt jelenti, hogy az első rák a 16-os, a második a 1-es pozíciót veszi fel, és így tovább…

Minden egyes pozíció váltás 1 egységnyi üzemanyagba kerül. Választhatnád, hogy a rákok bármelyik pozícióra menjenek, de ebben az elrendezésben a 2-es pozícióra való eljutás kerül a legkevesebbe:

• Mozgás a 16-ról 2-re: 14 egység üzemanyag
• Mozgás a 1-ről 2-re: 1 egység üzemanyag
• Mozgás a 2-ről 2-re: 0 egység üzemanyag
• Mozgás a 0-ról 2-re: 2 egység üzemanyag
• Mozgás a 4-ről 2-re: 2 egység üzemanyag
• Mozgás a 2-ről 2-re: 0 egység üzemanyag
• Mozgás a 7-ről 2-re: 5 egység üzemanyag
• Mozgás a 1-ről 2-re: 1 egység üzemanyag
• Mozgás a 2-ről 2-re: 0 egység üzemanyag
• Mozgás a 14-ről 2-re: 12 egység üzemanyag

Ez összesen 37 egységnyi üzemanyagba kerül. Ez a lehető legkevesebb, amit ki lehet hozni. Például az 1-es pozícióra való rendezés 41 egység, a 10-es pozíció pedig 71 egység üzemanyagba kerülne.

A kapott rákpozíció input alapján keresd meg azt a pozíciót, ami a lehető legkevesebbe kerül. Hány egység üzemanyagot használnál fel?

Megoldás

A file beolvasása után mentsük ki két változóba a legkisebb és a legnagyobb pozíciót. Abban biztosak lehetünk, hogy a megfelelő pozíció ezek között lesz.
Mivel minimumot akarunk majd vizsgálni, a result változót állítsuk be a legnagyobb értéknek, amit egy int felvehet. Vizsgálat során azt fogjuk nézni, hogy ha az éppen kapott üzemanyagfelhasználás kisebb, mint az addig tárolt eredmény, akkor a result változó értékét lecseréljük a kisebb értékre.

Végig iterálunk minden egész számon az előre meghatározott minimum és maximum érték között. Egy lambda hívás segítségével kiszámoljuk minden rákra, hogy mennyi üzemanyagba kerülne oda eljutni.

Select(n => Math.Abs(n - i))

Majd ezután egy egyszerű Sum() hívással összeadjuk ezeket az értékeket. Ezután következhet az a minimumvizsgálat, amit feljebb tárgyaltunk.

public class Day07 : IPuzzleSolution
{
	public void Execute()
	{
		int[] numbers = FileReader.ReadLinesOfFile<int>("inputs\\07.txt", ',').ToArray();
		(int minimum, int maximum) = numbers.GetMinMax();

		int result = int.MaxValue;
		for (int i= minimum; i<= maximum; i++)
		{
			int diff = numbers.Select(n => Math.Abs(n - i)).Sum();
			if (diff < result)
			{
				result = diff;
			}
		}
		Console.WriteLine(result);
	}
}

Feladatleírás – második rész

Úgy tűnik, a rákoknak nem tetszik a megoldásod, lehet félreértetted a rákmérnökséget?!

Kiderült, hogy a rák tengeralattjáró motorja nem fogyaszt állandóan üzemanyagot. Ehelyett viszont lépésenként 1 egységgel nő a fogyasztása. Azaz az első lépés 1, a második lépés 2, a harmadik lépés 3 egységnyi üzemanyagba kerül. Tehát 3 helyett (amivel az előző feladatban számoltál) 6 egységnyi üzemanyagba kerül 3 pozícióváltás.

Ha így számolunk, akkor az előző példára nem a 2-es, hanem az 5-ös pozíció fog a legkevesebbe kerülni:

• Mozgás a 16-ról 5-re: 66 egység üzemanyag
• Mozgás a 1-ről 5-re: 10 egység üzemanyag
• Mozgás a 2-ről 5-re: 6 egység üzemanyag
• Mozgás a 0-ról 5-re: 15 egység üzemanyag
• Mozgás a 4-ről 5-re: 1 egység üzemanyag
• Mozgás a 2-ről 5-re: 6 egység üzemanyag
• Mozgás a 7-ről 5-re: 3 egység üzemanyag
• Mozgás a 1-ről 5-re: 10 egység üzemanyag
• Mozgás a 2-ről 5-re: 6 egység üzemanyag
• Mozgás a 14-ről 5-re: 45 egység üzemanyag

Így a teljes fogyasztás 168 egység, a 2-es pozícióra ez 206 egység lenne.

Számold újra a menekülés útvonalát az új tudást felhasználva és határozd meg, mennyi üzemanyagra van szükség hozzá!

Megoldás

Érzésre nem kell sokat alakítani az előző megoldásunkon, keressünk valamilyen összefüggést. Eddig a két szám közötti különbség abszolút értékét használtuk, most pedig eddig az értékig szeretnénk összeadni a számokat. Érettségire készülve találkozhattunk az első n darab szám összegével ami n(n+1)/2. Ezt felhasználva, az előző Select-ünket csak ki kell egészíteni a következő módon:

Select(num => Math.Abs(num - i)).Select(dis => dis * (dis + 1) / 2)

Az előző megoldáshoz képest semmi mást nem kell változtatnunk.

public class Day07B : IPuzzleSolution
{
	public void Execute()
	{
		int[] numbers = FileReader.ReadLinesOfFile<int>("inputs\\07.txt", ',').ToArray();
		(int minimum, int maximum) = numbers.GetMinMax();

		int result = int.MaxValue;
		for (int i = minimum; i <= maximum; i++)
		{
			var diff = numbers
				.Select(num => Math.Abs(num - i))
				.Select(dis => dis * (dis + 1) / 2)
				.Sum();
			if (diff < result)
			{
				result = diff;
			}
		}
		Console.WriteLine(result);
	}
}