Menu
Advent of Code – 9. nap

Advent of Code – 9. nap

, , ,

A kilencedik nap a barlangban rájövünk, hogy az vulkanikus eredetű és a barlang bizonyos részein még van aktivitás hidrotermikus formában, amit egy korábbi nap alapján tudunk, hogy kerülni kellene. Nincs más hátra, ismételt navigációra fel!

Az első és második feladat megoldásához kapunk egy magasság térképet az alábbi formában:

2199943210
3987894921
9856789892
8767896789
9899965678

A térkép minden pontja egy adott koordináta magasságát jelképezi és 0 jelöli a legmélyebb pontot, 9 pedig a legmagasabbat. Az első feladatban az lesz a dolgunk, hogy meghatározzuk a szomszédokhoz viszonyítva a mély pontokat.

Itt trükkös, hogy mi számít szomszédnak. Pl. Az első 2-es szomszédja a mellette található 1-es és az alatta lévő hármas. Viszont a 2. sorban található 9-es szomszédja már a felette lévő 1-es, alatta lévő 8-as és a vele egy sorban lévő két szomszédja a 3-as és 8-as. Vagyis a szomszédok meghatározásánál az átlók nem számítanak.

A fenti példa esetén az alábbi kiemelt pontok lesznek a mélypontok:

2199943210
3987894921
9856789892
8767896789
9899965678

Az első feladatban ezen mélypontok összegére van szükségünk úgy, hogy minden egyes mélypont értékéhez hozzáadunk egyet. A korábbi napok által használt beolvasó metódusokkal könnyen beolvashatjuk a fájlt egy egész számokból álló tömbök tömbjévé, amit kvázi kezelhetünk úgy, mint egy kétdimenziós tömböt.

int[][] numberMap = FileReader
    .ReadLinesOfFile<string>("inputs\\09.txt")
    .Select(row => GetNumbersFromRow(row))
    .ToArray();

A ReadLinesOfFile egy sort olvas be. A sorban található karakterekből számot a GetNumbersFromRow készít, ami LINQ-t használ és azt a tényt, hogy a karakterkód táblában a számok egymást követik. Tehát ha a karakterünk értékéből kivonjuk a ‘0’ karakter szám értékét, akkor pont egy 0 és 9 közé eső egészet kapunk:

protected static int[] GetNumbersFromRow(string row)
{
    return row.Select(chr => chr - '0').ToArray();
}

Ezután már „csak” meg kell találnunk a pontokat és össze kell számolnunk az összegüket. Erre készítettem egy GetSumOfLowPoints metódust, ami a következőképpen néz ki:

private static int GetSumOfLowPoints(int[][] map)
{
    int sum = 0;
    for (int i = 0; i < map.Length; i++)
    {
        for (int j = 0; j < map[i].Length; j++)
        {
            if (CheckLeft(map, i, j)
                || CheckRight(map, i, j)
                || CheckTop(map, i, j)
                || CheckBottom(map, i, j))
            {
                continue;
            }
            sum += map[i][j] + 1;
        }
    }
    return sum;
}

A metódus fordított logikát alkalmaz, mivel jelen esetben átláthatóbb kódot eredményez, ha a feltételeknek nem megfelelő pontokat eleve kizárjuk. A kizárásokért a CheckLeft, CheckRight, CheckTop és CheckBottom metódusok felelnek. Ezek implementációi a következőek:

private static bool CheckLeft(int[][] map, int i, int j)
{
    return j - 1 >= 0 && map[i][j] >= map[i][j - 1];
}

private static bool CheckRight(int[][] map, int i, int j)
{
    return j + 1 < map[i].Length && map[i][j] >= map[i][j + 1];
}

private static bool CheckTop(int[][] map, int i, int j)
{
    return i - 1 >= 0 && map[i][j] >= map[i - 1][j];
}

private static bool CheckBottom(int[][] map, int i, int j)
{
    return i + 1 < map.Length && map[i][j] >= map[i + 1][j];
}

2. feladat

A 2. feladatban rájövünk, hogy a mélypontok lényegében kürtőket reprezentálnak. Kürtőnek számít minden olyan kiterjedés, ami végül egy mélypont felé áramlik. Tehát nem elég tudnunk, hogy hol és mennyi mélypont van, tudnunk kell ezek kiterjedését is. Könnyítés, hogy azt tudjuk, hogy a 9-es magassággal rendelkező pontok nem részei egyetlen egy kürtőnek sem, viszont minden más szám valahogy köthető egy kürtőhöz. A korábbi példa bemenet alapján a bal felső sarokban találunk egy kürtőt 3-as mérettel:

2199943210
3987894921
9856789892
8767896789
9899965678

A jobb felső sarokban lévő kiterjedése viszont 9:

2199943210
3987894921
9856789892
8767896789
9899965678

A második feladatban ezen kürtők méretei közül a legnagyobb három szorzatára vagyunk kíváncsiak. Az első feladat megoldásához használt algoritmusaink részben újrahasználhatóak. Ugyanúgy beolvassuk a fájlt, végigmegyünk minden ponton és meghatározzuk a kürtő méretet.

Ezután LINQ segítségével fordított sorrendben (legnagyobbtól legkisebbig) rendezzük őket, kivesszük az első hármat és azokat összeszorozzuk. A szorzat megállapítására szintén LINQ-t vettem igénybe, méghozzá a talán kevésbé ismert Aggregate metódust.

var numberMap = FileReader
    .ReadLinesOfFile<string>("inputs\\09.txt")
    .Select(row => GetNumbersFromRow(row))
    .ToArray();

var basins = new List<int>();

for (int i=0; i<numberMap.Length; i++)
{
    for (int j=0; j<numberMap[i].Length; j++)
    {
        int basinSize = CalculateBasinSize(numberMap, i, j);
        basins.Add(basinSize);
    }
}

var largestThreeSize = basins
    .OrderByDescending(x => x)
    .Take(3)
    .Aggregate((x, y) => x * y);

Console.WriteLine(largestThreeSize);

Kérdés már csak az, hogy hogyan állapítjuk meg az egyes kürtők méretét? Erre egy rekurzív megoldást találtam ki, mivel jobban olvasható a megoldás így, mint ciklusokkal:

private int CalculateBasinSize(int[][] numberMap, int i, int j)
{
    if (i < 0
        || i >= numberMap.Length
        || j < 0
        || j >= numberMap[0].Length 
        || numberMap[i][j] == 9)
    {
        //túl és alul indexelés elleni védelem
        return 0;
    }
    numberMap[i][j] = 9;
    return 1
        + CalculateBasinSize(numberMap, i - 1, j) 
        + CalculateBasinSize(numberMap, i + 1, j)
        + CalculateBasinSize(numberMap, i, j - 1)
        + CalculateBasinSize(numberMap, i, j + 1);
}

Jelen megoldás azért működőképes és azért nem száll el kivétellel, mert bekorlátozzuk a keresést és a rekurzív hívások mélységét azzal, hogy az éppen vizsgált pontot 9-esnek tekintjük. Igazából meg lehetett volna írni ezt ciklusokkal is, de úgy sokkal bonyolultabb. Mondjuk sokat segít, ha tudjuk, hogy amit itt kell csinálnunk, az egy flood fill algoritmusszerűség. Erről a https://en.wikipedia.org/wiki/Flood_fill címen lehet olvasni és pár jó vizualizáció is tartozik hozzá.

A holnapi és a hétvégi feladatok megoldásaival valószínűleg csak jövő héten fogunk tudni jelentkezni, mert elég sűrű hétvége áll előttünk.

Related Posts