Advent of Code – ötödik nap
A történet az 5. napon egy kis hidrotermikus kalanddal és koordináta geometriával folytatódik.
A tengeralattjárónk egy hidrotermikus kürtőkből álló mezőre téved. Az ezekből kiáramló felhőket jobb elkerülni. Ehhez egy térképet kell készítenünk és meg kell határoznunk a térképen a veszélyes pontok számát. A veszélyes pontok száma lesz a feladat megoldása.
Veszélyes pontnak számít az, ahol kettőnél több ilyen kiáramló felhő keresztezi egymást. A felhők áramlásáról kapunk információt koordinátapárok formájában, ami a következőképpen néz ki:
0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2
Tehát adott egy kétdimenziós vonal kezdő- és végpont koordináta párja. Az első feladatban a vertikális és a horizontális vonalak metszéspontjait kell számolnunk. A megoldás pedig azon pontok száma lesz, ahol kettőnél több ilyen metszi egymást.
Ahhoz, hogy horizontális vagy vertikális a vonal, segítséget is ad a feladat, mivel azt kell figyelni, hogy a kezdő- és vég x vagy y koordináták megegyeznek. Sőt, arra is kapunk példát, hogy hogyan számoljuk ki, hogy egy vonal milyen koordináta párokat fed le.
Megkapjuk segítségnek, hogy a 1,1 -> 1,3 vonal lefedi a 1, 1, 1, 2 és 1, 3 koordinátákat, illetve a 9,7 -> 7,7 páros pedig lefedi a 9, 7, 8, 7 és 7, 7 pontokat.
A fenti vonal listából egy ilyen térkép készíthető:
.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....
A térképen a . olyan területeket jelöl, ahol 0db vonal metszi egymást, a számok pedig az aktuális ponton metsző vonalak számát jelölik, méghozzá úgy, hogy a bal felső pont x = 0, y = 0 koordinátának felel meg, a jobb alsó pedig jelen esetben a x = 9, y = 9 koordinátának.
A megadott példa alapján itt 5 lesz a helyes megoldás, mivel 5db olyan pont van, ahol kettő vagy több vonal metszi egymást.
A feladat megoldás első lépéseként készítettem egy osztályt, ami a vonalunkat írja le:
internal class Day05Line
{
public (int x, int y) StartPoint { get; set; }
public (int x, int y) EndPoint { get; set; }
public int MaxX => Math.Max(StartPoint.x, EndPoint.x);
public int MaxY => Math.Max(StartPoint.y, EndPoint.y);
public override string ToString()
{
return $"{StartPoint} -> {EndPoint}";
}
}
A ToString metódus könnyebb hibakeresés miatt lett felülírva, a MaxX és MaxY tulajdonság pedig majd a térkép maximális méretének megkeresésében fog bennünket segíteni.
A fájl beolvasás a mai feladatban könnyebb. A 2. nap használt ReadLinesOfFile<T> egy újabb változatával könnyen megvalósítható. Csupán annyit kell módosítani, hogy a metódus tokenizer paramétere az elválasztó karakter helyett egy karakter tömböt jelöljön, ami a vágó karaktereket adja meg:
public static IEnumerable<T> ReadLinesOfFile<T>(string filename,
char[] tokenizer,
Func<string[], T> objectFactory)
{
using (var file = File.OpenText(filename))
{
string? line;
do
{
line = file.ReadLine();
if (!string.IsNullOrEmpty(line))
{
string[] parts = line.Split(tokenizer, StringSplitOptions.RemoveEmptyEntries);
yield return objectFactory.Invoke(parts);
}
}
while (line != null);
}
}
Ezek segítségével a megoldás a következő:
public virtual void Execute()
{
Day05Line[] lines = ReadInputFile();
int gridSizeX = lines.Max(x => x.MaxX) + 1;
int gridSizeY = lines.Max(x => x.MaxY) + 1;
var grid = new int[gridSizeY, gridSizeX];
var horizontalOrVerticalLines = lines
.Where(line => line.StartPoint.y == line.EndPoint.y
|| line.StartPoint.x == line.EndPoint.x);
foreach (var line in horizontalOrVerticalLines)
{
foreach (var point in CoveredPoints(line))
{
grid[point.y, point.x]++;
}
}
int solution = Count(grid);
Console.WriteLine(solution);
}
A fájl beolvasása után meghatározzuk a térkép maximális méretét egy kis LINQ varázslattal a típusunk MaxX és MaxY tulajdonságai alapján. Ez alapján létrehozunk egy kétdimenziós egész tömböt, ami a metsző vonalak számát tartalmazza. Ezt követően szintén LINQ segítségével leszűrjük a vonalakból a vízszinteseket és horizontálisokat, majd ezeken végigiterálva megnézzük, hogy milyen pontokat fednek le. A lefedett pontok számosságát pedig növeljük. Végezetül megszámoljuk azon pontokat, amelyek kettő vagy nagyobb értékkel rendelkeznek.
A térkép készítésénél trükkös, hogy mi x és y koordinátában gondolkodunk, de a tömb valójában y és x koordinátában kell, hogy legyen. Ez a „triviális” kis apróság közel 20 percnyi hibakeresést eredményezett.
A fájl beolvasása itt is külön metódusba került, mivel a 2. feladatban is szükségünk lesz rá:
protected static Day05Line[] ReadInputFile()
{
return FileReader.ReadLinesOfFile<Day05Line>(
"inputs\\05.txt",
new char[] { ',', ' ', '-', '>' },
(tokens) =>
{
return new Day05Line
{
StartPoint = (x: int.Parse(tokens[0]), y: int.Parse(tokens[1])),
EndPoint = (x: int.Parse(tokens[2]), y: int.Parse(tokens[3])),
};
}).ToArray();
}
A lefedett pontok megállapítására a CoveredPoints metódus szolgál, aminek a bemenő paramétere egy vonal:
protected static IEnumerable<(int x, int y)> CoveredPoints(Day05Line line)
{
if (line.StartPoint.x <= line.EndPoint.x
&& line.StartPoint.y <= line.EndPoint.y)
{
for (int i = line.StartPoint.x; i <= line.EndPoint.x; i++)
{
for (int j = line.StartPoint.y; j <= line.EndPoint.y; j++)
{
yield return (i, j);
}
}
}
else
{
for (int i = line.StartPoint.x; i >= line.EndPoint.x; i--)
{
for (int j = line.StartPoint.y; j >= line.EndPoint.y; j--)
{
yield return (i, j);
}
}
}
}
A számolást pedig a Count metódus végzi:
protected static int Count(int[,] grid)
{
int count = 0;
for (int i = 0; i < grid.GetLength(0); i++)
{
for (int j = 0; j < grid.GetLength(1); j++)
{
//string debug = grid[i, j] == 0 ? "." : grid[i, j].ToString();
//Console.Write(debug);
if (grid[i, j] >= 2)
{
++count;
}
}
//Console.WriteLine();
}
return count;
}
A metódus kikommentelt részei a térkép rajzolására szolgálnak. Ezzel ellenőriztem, hogy jó úton járok-e a minta bemenetek alapján.
Második feladat
A második feladat ugyanez, kiegészítve azzal, hogy a 45 fokos meredekséggel rendelkező vonalakat is számolni kell. Ez alapján a minta bemenetek hatására rajzolt térkép a következőre módosul:
1.1....11.
.111...2..
..2.1.111.
...1.2.2..
.112313211
...1.2....
..1...1...
.1.....1..
1.......1.
222111....
Így már 12 darab olyan pont van a minta bemenetben, ahol kettőnél több vonal metszi egymást. Itt nehézség a 45 fokos meredekség megállapítása lehet, de egy szögfüggvényekkel ez gyerekjáték, illetve az egyenes egyenletét felhasználva megkaphatjuk az egyenesre illeszkedő pontokat. Ezek alapján a második feladat megoldása:
public override void Execute()
{
Day05Line[] lines = ReadInputFile();
int gridSizeX = lines.Max(x => x.MaxX) + 1;
int gridSizeY = lines.Max(x => x.MaxY) + 1;
var grid = new int[gridSizeY, gridSizeX];
var horizontalOrVerticalLines = lines
.Where(line => line.StartPoint.y == line.EndPoint.y
|| line.StartPoint.x == line.EndPoint.x);
var linesWith45degrees = lines
.Where(line => IsDiagonalLine(line))
.ToArray();
foreach (var line in horizontalOrVerticalLines)
{
foreach (var point in CoveredPoints(line))
{
grid[point.y, point.x]++;
}
}
foreach (var line in linesWith45degrees)
{
foreach (var point in CoveredDiagonalPoints(line))
{
grid[point.y, point.x]++;
}
}
int solution = Count(grid);
Console.WriteLine(solution);
}
A 45 fokos meredekség megállapításáért a IsDiagonalLine metódus felel, ami a következőképpen néz ki:
private static bool IsDiagonalLine(Day05Line line)
{
int x = line.EndPoint.x - line.StartPoint.x;
int y = line.EndPoint.y - line.StartPoint.y;
int angle = (int)Math.Abs(Math.Atan2(y, x) * 180 / Math.PI);
return angle == 45
|| angle == 135
|| angle == 225
|| angle == 315;
}
Az egyenes által lefedett pontokat pedig a CoveredDiagonalPoints metódus szolgáltatja:
//f(x) = a*x + b;
//https://en.wikipedia.org/wiki/Linear_function
private static IEnumerable<(int x, int y)> CoveredDiagonalPoints(Day05Line line)
{
int ydiff = line.EndPoint.y - line.StartPoint.y;
int xdiff = line.EndPoint.x - line.StartPoint.x;
int a = (ydiff) / (xdiff);
int b = (line.StartPoint.y - (a * line.StartPoint.x));
if (xdiff < 0)
{
for (int x = line.StartPoint.x; x >= line.EndPoint.x; x--)
{
yield return (x, (a * x) + b);
}
}
else
{
for (int x = line.StartPoint.x; x <= line.EndPoint.x; x++)
{
yield return (x, (a * x) + b);
}
}
Holnap folytatása következik 😎