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.