Advent of Code – hatodik nap

A hatodik napon a tengerfeneket pásztázod épp a kulcs után kutatva, amikor különleges lámpás halak haladnak el melletted.

Feladatleírás – első rész

Izzó lámpáshalak hatalmas csapata úszik el melletted. Biztos gyorsan szaporodnak – talán exponenciálisan, másképp hogy lehetnének ilyen sokan? Hogy erről megbizonyosodj, szimulálnod kell a szaporodási ütemüket.

Bár még semmit sem tudhatsz erről a különleges lámpás halfajról, néhány dolgot azért sejtesz róluk. Ami biztos, hogy minden hal 7 naponta hoz világra egy új halat.

Viszont ez a 7 napos ciklus nem feltétlenül van szinkronban. Lehet, hogy az egyik halnak már csak 2 napja van, egy másiknak pedig 4, mire elérik a 7. napot, amikor is egy új halat hoznak létre. Ezáltal minden halat modellezhetsz egy egész számként, ami azt az értéket veszi fel, ahány napja van még az adott halnak, hogy egy új halat hozzon létre.

Ezen felül egy „újszülött” lámpás halnak biztosan több napra van szüksége, mint egy felnőtt halnak. Az első 7-es ciklus minden halnál kitolódik 2 nappal.

Tegyük fel, hogy van egy lámpáshal, amelynek belső időzítője jelenleg 3:

• Egy nap elteltével a belső időzítője 2 lesz.
• Egy újabb nap elteltével a belső időzítője 1 lesz.
• Még egy nap elteltével a belső időzítő 0 lesz.
• Még egy nap elteltével a belső időzítője visszaáll 6-ra,valamint  létrehoz egy új lámpáshalat 8-as belső időzítővel.
• Egy új nap elteltével az első lámpáshal 5-ös, a második lámpáshal pedig 7-es belső időzítővel rendelkezik

Az új hal létrehozásának napján az időzítő 6-ra áll vissza, nem 7-re (mivel a 0 is érvényes időzítőérték). Az új lámpáshal 8-as belső időzítővel indul, és csak másnap kezdi el a visszaszámlálást.

A tengeralattjáró automatikusan képes elkészíteni egy listát több száz közeli lámpás hal állapotáról, amit használhatsz a modellezésben. Tegyük fel például, hogy a következő listát kaptad:

3,4,3,1,2

Ez a lista azt jelenti, hogy az első hal belső időzítője 3, a második hal belső időzítője 4, és így tovább egészen az ötödik halig, amelynek belső időzítője 2. A halak szaporodásának a szimulálása több napon keresztül a következőképpen történik:

Kezdő adatok: 3,4,3,1,2
1 nap elteltével:  2,3,2,0,1
2 nap elteltével: 1,2,1,6,0,8
3 nap elteltével: 0,1,0,5,6,7,8
4 nap elteltével: 6,0,6,4,5,6,7,8,8
5 nap elteltével: 5,6,5,3,4,5,6,7,7,8
6 nap elteltével: 4,5,4,2,3,4,5,6,6,7
7 nap elteltével: 3,4,3,1,2,3,4,5,5,6
8 nap elteltével: 2,3,2,0,1,2,3,4,4,5
9 nap elteltével: 1,2,1,6,0,1,2,3,3,4,8
10 nap elteltével: 0,1,0,5,6,0,1,2,2,3,7,8
11 nap elteltével: 6,0,6,4,5,6,0,1,1,2,6,7,8,8,8
12 nap elteltével: 5,6,5,3,4,5,6,0,0,1,5,6,7,7,7,8,8
13 nap elteltével: 4,5,4,2,3,4,5,6,6,0,4,5,6,6,6,7,7,8,8
14 nap elteltével: 3,4,3,1,2,3,4,5,5,6,3,4,5,5,5,6,6,7,7,8
15 nap elteltével: 2,3,2,0,1,2,3,4,4,5,2,3,4,4,4,5,5,6,6,7
16 nap elteltével: 1,2,1,6,0,1,2,3,3,4,1,2,3,3,3,4,4,5,5,6,8
17 nap elteltével: 0,1,0,5,6,0,1,2,2,3,0,1,2,2,2,3,3,4,4,5,7,8
18 nap elteltével: 6,0,6,4,5,6,0,1,1,2,6,0,1,1,1,2,2,3,3,4,6,7,8,8,8,8

Minden nap a 0-ákból 6 lesz, és egy új 8-as kerül a lista végére, míg a többi szám 1-gyel csökken.

Ebben a példában 18 nap után összesen 26 hal van. 80 nap után összesen 5934 lenne.

Találj egy módszert a lámpás halak szaporodásának modellezésére. Hány lámpás hal lesz 80 nap után a kapott inputon?

Megoldás

Ha a feladatleírást átfogalmazzuk kicsit, levonhatjuk a konklúziót, hogy minden hal objektum rendelkezik egy belső időzítővel. A mondat második fele erősen sugallja, hogy egy-egy halat lehetne egy osztállyal reprezentálni, aminek egy darab belső tulajdonsága lenne. Egy hal objektum létrehozásakor, azaz a default konstruktorban ez a tulajdonság 8-ra áll. Kell egy paraméterrel rendelkező konstruktor is, mivel a tengeralattjáró által beszkennelt halaknak nem 8-cal szeretnénk indítani az időzítőjét.

Ezen felül kell még egy, az osztályon elvégezhető publikus művelet, ami csökkenti az időzítő értékét, de miután eléri a nullát, akkor 6-ra állítja vissza. Ezzel a módszerrel minden nap szimulálásakor csak az osztályon végezhető műveleteket kell meghívni.

A ToString() metódus felülírásával tudjuk specializálni, pontosan mit és hogy szeretnénk látni, amikor kiíratunk egy ilyen hal objektumot a konzolra.

internal class Day06LanternFish
{
    private sbyte _timer;

    public Day06LanternFish(int startValue)
    {
        _timer = (sbyte)startValue;
    }

    public Day06LanternFish()
    {
        _timer = 8;
    }

    public bool RunTimer()
    {
        _timer--;
        if (_timer < 0)
        {
            _timer = 6;
            return true;
        }
        return false;
    }

    public override string ToString()
    {
        return _timer.ToString();
    }
}

Az előző napokhoz képest az input file olvasását egy kicsit ki kell bővítenünk, mivel a tárolandó elemek száma folyamatosan nő, így a tömb nem a legoptimálisabb tároló, a lista annál inkább. Ezen felül arra is ügyelnünk kell, hogy nem soronként vannak elválasztva az adatok, hanem egyetlen sorba rendezve vesszővel.

Első lépésben készítsünk egy metódust, ami a megszokott módon beolvassa az inputot, azt szétdarabolja a vesszők mentén és a közte lévő karaktereket számmá alakítja. Itt tudunk a végén ToArray() segítségével tömbben tárolni. Létrehozunk egy üres listát, majd a tömbön végigiterálva egyesével új elemeket adunk hozzá ehhez a listához.

private static List<Day06LanternFish> ReadFile()
{

    var initialStates = FileReader.ReadLinesOfFile<IEnumerable<int>>("inputs\\06.txt", ',', (tokens) =>
    {
        return tokens.Select(x => Convert.ToInt32(x));

    }).SelectMany(x => x).ToArray();
    List<Day06LanternFish> fishes = new List<Day06LanternFish>(initialStates.Length);
    foreach (var state in initialStates)
    {
        fishes.Add(new Day06LanternFish(state));
    }
    return fishes;
}

Pár segédműveletre még szükségünk van, az egyik ilyen az új halak létrehozása. Paraméterben megkapva a hal kollekciót és egy egész számot, adjunk hozzá annyi új hal objektumot a kollekcióhoz, ami a paraméterben kapott egész szám értéke.

private static void CreateNewFishes(ICollection<Day06LanternFish> fishes, int newFishesToCreate)
{
    for (int i=0;i< newFishesToCreate; i++)
    {
        fishes.Add(new Day06LanternFish());
    }
}

Egy másik ilyen metódusban járjuk be a kapott hal kollekciót és hívjuk meg minden egyes hal objektumon a belső RunTimer() műveletet, ami updateli az adott hal belső időzitőjét. A RunTimer() igazat ad vissza, ha épp 0-ról 6-ra vált a hal belső időzítője, azaz ha új halat hoz létre. Számoljuk össze, hány hal objektum ad vissza igazat és térjünk vissza ezzel az egész számmal.

private static int RunFishStates(ICollection<Day06LanternFish> fishes)
{
    int newCount = 0;
    foreach (var fish in fishes)
    {
        bool createsNew = fish.RunTimer();
        if (createsNew)
        {
            ++newCount;
        }
    }
    return newCount;
}

Innen az első feladat megoldása már triviális, mivel az egész működést lefedtük a segédfüggvényekkel. A fő programban hozzunk létre egy változót, ami azt fogja jelenteni, hogy hány napot szeretnénk modellezni. Egy for ciklusban a számlálót növeljük egészen addig, amíg el nem éri ezt a számot, ami jelen esetben 80, valamint hívja meg a segédmetódusainkat.

public void Execute()
{
    const int DaysToSimulate = 80;
    List<Day06LanternFish> fishes = ReadFile();

    for (int i=0; i< DaysToSimulate; i++)
    {
        int newFishesToCreate = RunFishStates(fishes);
        CreateNewFishes(fishes, newFishesToCreate);
        //PrintDebugInfo(i, fishes);
    }
    Console.WriteLine(fishes.Count);

}

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

Tegyük fel, hogy a lámpáshalak örökké élnek és korlátlan táplálékuk, illetve helyük is van. Egyszer csak átveszik az egész óceánt?

A fenti példában, ahol 5 hallal kezdődik a modellezés, 256 nap után összesen 26984457539 lámpás hal lenne!

Hány lámpás hal lenne 256 nap után a kapott inputon?

Megoldás

Elsőre gondolhatnánk, hogy az első feladatban a 80-at átirjuk 256-ra és készek is vagyunk. Viszont, ha elolvassuk a a rövidke kis leírását a második feladatnak, rögtön szemet üthet az az óriási szám, amit 5-ös létszámú kezdéssel érnek el lámpáshalak. Mivel a lista belső működésében indexelésre intet használ, így a maxiumum elemszám, amit hozzá tudunk adni, az 2147483647, amit már 5 elemszámú kezdőlistával is túllépnénk, így át kell gondolni a modellezést. Mi lenne, ha nem state machine megoldás felé gondolkodnánk, hanem a napokhoz rendelnénk a halak számát?

Így a megoldásunk teljesen más lesz, mint az első részé. Egyedül a file beolvasását tudjuk újrahasználni, viszont elég belőle csak a vessző szeparálós rész, nem kell objektumok listájává alakítani.

private static int[] ReadFile()
{
     var initialStates = FileReader.ReadLinesOfFile<IEnumerable<int>>("inputs\\06.txt", ',', (tokens) =>
    {
        return tokens.Select(x => Convert.ToInt32(x));

    }).SelectMany(x => x).ToArray();
     return initialStates;
}

Szükségünk lesz egy int tömbre, ami 9 elemet tárol (0-8 közötti időzítő érték). Ha mondjuk 15 hal van, aki 2 nap múlva fog új halat létrehozni, az azt jelenti, hogy timers[2] = 15. Ez alapján először iteráljunk végig a beolvasott tömbbön. Ilyenkor mindig lesz egy input értékünk, amit indexként fogunk használni. Az adott indexű tömb elem értékét növeljük eggyel, ezzel modellezve, hogy az adott hal azt az időzítős csoportot bővíti.

Az előző megoldáshoz hasonlóan most is készítünk egy for ciklust ami most 256-szor fog lefutni és cserélgetjük az indexek értékeit. Ha jelenleg timers[2] = 15 és timers[3] = 8, akkor egy ciklus mulva timers[1] értéke lesz a 15 és a timers[2] pedig az előző timers[3] értékét veszi fel, azaz 8 lesz. Amire fontos figyelnünk, az a 0-ás, 6-os és 8-as indexek kezelése.

public void Execute()
{
	const int daysToSimulate = 256;
	long[] timers = new long[9]; //0-8 -ig tart a belső timer 
	var initial = ReadFile();
	
	//timerek előre futtatása
	foreach (var fish in initial)
	{
		timers[fish]++;
	}

	for (int day = 1; day <= daysToSimulate; day++)
	{
		long newFishToCreate = timers[0]; //
		for (int i = 0; i <= timers.Length - 2; i++)
		{
			timers[i] = timers[i + 1];
		}
		// 7 -> 6 váltás külön tárolása
		timers[6] += newFishToCreate;
		timers[8] = newFishToCreate; //új halak

	}

	long count = 0;
	foreach (long fish in timers)
	{
		count += fish;
	}

	Console.WriteLine(count);
}