Advent of Code – negyedik nap
A negyedik napon a telemetria visszafejtése után találkoztunk 1.5 km mélységben egy polippal, aki Bingót szeretne velünk játszani. Nincs mese, vessük bele magunkat a feladat megoldásába.
A bingó egy faék egyszerű játék. Minden játékosnak van egy 5×5 elemű táblája számokkal és van egy véletlenszerűen generált szám. A szám kihúzása után ha a szám megtalálható a táblán, akkor a játékos megjelöli. A játékot az a játékos nyeri, akinek a tábláján először jön ki egy olyan sor vagy oszlop ami 5db megjelölt számot tartalmaz.
Szinte minden kódolós kihívásban szerepel a Bingó valamilyen formában. Jelenleg a feladatunk az, hogy megkeressük a megadott táblák között az első nyerőt, majd számoljuk ki a táblában a ki nem húzott számok összegét, amit meg kell szoroznunk azzal a számmal, ami a táblát nyerő táblává változtatta.
A feladatban a fájl beolvasása lesz a nehézség, mivel az első sor a kihúzandó számokat tartalmazza, majd ezt követően n darab tábla következik.
7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1
22 13 17 11 0
8 2 23 4 24
21 9 14 16 7
6 10 3 18 5
1 12 20 15 19
3 15 0 2 22
9 18 13 17 5
19 8 7 25 23
20 11 10 24 4
14 21 16 12 6
14 21 17 24 4
10 16 15 9 19
18 8 23 26 20
22 11 13 6 5
2 0 12 3 7
A fájl beolvasása előtt érdemes egy Bingó tábla implementációval kezdeni. Ez a megoldásomban a Day04BingoTable nevet kapta és a következőképpen néz ki:
internal class Day04BingoTable : IEnumerable<(int number, bool hasbeenDrawn)>
{
private readonly (int number, bool hasbeenDrawn)[,] _table;
public int FilledRows { get; private set; }
public Day04BingoTable()
{
_table = new (int number, bool hasbeenDrawn)[5, 5];
FilledRows = 0;
}
public void AddRow(int[] numbers)
{
for (int i = 0; i < 5; i++)
{
_table[FilledRows, i] = (numbers[i], false);
}
++FilledRows;
}
public void DrawNumber(int number)
{
for (int i=0; i<5; i++)
{
for (int j=0; j<5; j++)
{
if (_table[i, j].number == number)
{
_table[i, j].hasbeenDrawn = true;
break;
}
}
}
}
public IEnumerable<bool> GetRowDrawnData(int row)
{
for (int i=0; i<5; i++)
{
yield return _table[row, i].hasbeenDrawn;
}
}
public IEnumerable<bool> GetColumnDrawnData(int column)
{
for (int i = 0; i < 5; i++)
{
yield return _table[i, column].hasbeenDrawn;
}
}
public IEnumerator<(int number, bool hasbeenDrawn)> GetEnumerator()
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
yield return _table[i, j];
}
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
A típus belsőleg egy 5×5 elemű ValueTuple tömb, ami tárolja a szám értékét és azt, hogy az adott szám ki lett-e már húzva. Az AddRow metódus majd a beolvasásnál lesz használva. Ezzel soronként fel tudjuk tölteni a táblát. A DrawNumber metódus egy számot kihúz, ha az megtalálható a táblában. Ez majd a kihúzás idején lesz használva. A GetRowDrawnData és a GetColumnDrawnData metódusok pedig segítenek ellenőrizni majd, hogy egy tábla nyerő-e vagy sem. A típus továbbá implementálja az IEnumerable<T> interfészt is, hogy majd LINQ metódusokat tudjunk használni.
A feladat algoritmikus megoldása egyszerű:
- Beolvassuk a fájlt
- Végig iterálunk a számokon, amiket ki kell húzni.
- Ha a szám, amit kihúztunk valamelyik táblát nyerővé változtatja, akkor kiszámoljuk a táblában ki nem húzott számok összegét, amit megszorzunk a számmal.
Ez kódra fordítva:
public virtual void Execute()
{
List<Day04BingoTable> bingoTables = new List<Day04BingoTable>();
int[] numbersToDraw = ReadFile(bingoTables);
foreach (var number in numbersToDraw)
{
DrawNumber(bingoTables, number);
if (TryGetWinningBingoTable(bingoTables, out Day04BingoTable winningTable))
{
int sumOfWinningTable = CalculateSumOfTable(winningTable);
Console.WriteLine(sumOfWinningTable * number);
break;
}
}
}
A fájlbeolvasás:
protected static int[] ReadFile(List<Day04BingoTable> bingoTables)
{
var currentTable = new Day04BingoTable();
int[] numbersToDraw = Array.Empty<int>();
using var f = File.OpenText("inputs\\04.txt");
string? line = null;
do
{
line = f.ReadLine();
if (!string.IsNullOrEmpty(line))
{
if (numbersToDraw.Length < 1)
{
numbersToDraw = line
.Split(',', StringSplitOptions.RemoveEmptyEntries)
.Select(n => Convert.ToInt32(n))
.ToArray();
}
else
{
var row = line
.Split(' ', StringSplitOptions.RemoveEmptyEntries)
.Select(n => Convert.ToInt32(n))
.ToArray();
if (currentTable.FilledRows > 4)
{
bingoTables.Add(currentTable);
currentTable = new Day04BingoTable();
}
currentTable.AddRow(row);
}
}
}
while (line != null);
bingoTables.Add(currentTable);
return numbersToDraw;
}
A fájlebolvasás picit trükkös, mivel számon kell tartanunk, hogy most épp a kihúzott számokat olvassuk be, vagy egy tábla sorát, illetve számolni kell a tábla sorok számát, hiszen minden 5. sor sor után új táblát kell kezdeni.
A számhúzás ennél jóval egyszerűbb, mivel itt csak annyi a feladat, hogy minden táblán meghívjuk a DrawNumber metódust:
protected static void DrawNumber(List<Day04BingoTable> bingoTables, int number)
{
foreach (var table in bingoTables)
{
table.DrawNumber(number);
}
}
A TryGetWinningBingoTable szolgál az első nyerő tábla megállapítására.Ez a metódus végigmegy a táblákon és ha a tábla nyerő, akkor visszaadja azt egy out paraméterben, illetve igaz értékkel tér vissza. Ha nem volt nyerő tábla, akkor pedig egy hamis értékkel tér vissza. A tábla nyerőségének megállapítására az IsWinningTable metódus szolgál, ami két dolog miatt lett külön metódus: egyrészt a Single responsibility miatt, másrészt pedig azért, hogy felhasználható legyen a napi második feladatban.
protected static bool IsWinningTable(Day04BingoTable table)
{
for (int i = 0; i < 5; i++)
{
bool rowWin = table.GetRowDrawnData(i).All(x => x);
if (rowWin)
{
return true;
}
bool columnWin = table.GetColumnDrawnData(i).All(x => x);
if (columnWin)
{
return true;
}
}
return false;
}
protected static bool TryGetWinningBingoTable(IEnumerable<Day04BingoTable> bingoTables,
out Day04BingoTable winningTable)
{
foreach (var table in bingoTables)
{
if(IsWinningTable(table))
{
winningTable = table;
return true;
}
}
winningTable = new Day04BingoTable();
return false;
}
Ezt követően a szumma számítás egy kis LINQ segítségével könnyen megoldható:
protected static int CalculateSumOfTable(Day04BingoTable winningTable)
{
return winningTable
.Where(x => !x.hasbeenDrawn)
.Sum(x => x.number);
}
Második feladat
Az első feladat komplikáltsága után kicsit meg voltam ijedve, hogy mi vár ránk a második részben, de szerencsére semmi komoly. Az első feladatban az első nyerő táblát kellet megtalálnunk, míg a másodikban az utolsóra lesz szükségünk. Az utolsó táblával ugyanazt kell tennünk, mint előzőleg: a nyerő számmal megszorozzuk a táblában nem kihúzott számok összegét.
A feladat jellegéből adódóan az első feladat megoldásához használt algoritmusok nagy része felhasználható. A megoldás a következő:
public override void Execute()
{
List<Day04BingoTable> bingoTables = new List<Day04BingoTable>();
int[] numbersToDraw = ReadFile(bingoTables);
Stack<int> toDelete = new Stack<int>();
Day04BingoTable lastTable = bingoTables[0];
for (int i = 0; i < numbersToDraw.Length; i++)
{
int number = numbersToDraw[i];
DrawNumber(bingoTables, number);
toDelete.Clear();
for (int j = 0; j < bingoTables.Count; j++)
{
if (IsWinningTable(bingoTables[j]))
{
toDelete.Push(j);
lastTable = bingoTables[j];
}
}
while (toDelete.Count > 0)
{
bingoTables.RemoveAt(toDelete.Pop());
}
if (bingoTables.Count == 0)
{
int sumOfWinningTable = CalculateSumOfTable(lastTable);
Console.WriteLine(sumOfWinningTable * number);
break;
}
}
}
Itt komplikált az utolsó tábla megtalálása, mivel egy szám több táblában is szerepelhet és a kihúzása után több táblát is nyerővé tud tenni. Itt azt a megoldást választottam, hogy minden egyes szám kihúzása után ellenőrzöm a táblákon végigiterálva, hogy lett-e nyerő. Ha igen, akkor a tábla indexét eltárolom egy veremben (toDelete), illetve a táblát magát a lastTable változóban. A számhúzás után a veremben tárolt indexek eltávolításra kerülnek a táblák közül, így szépen sorjában el fognak fogyni a táblák. Ha ez megtörtént és nincs már tábla, amit meg kellene nézni, akkor eljutottunk az utolsó táblához, amin ugyanúgy lefuttatjuk az első feladatban is szükséges számítást és meg is van a nyerő kombinációnk.
A kód mennyisége alapján ez egy bonyolult feladatnak tűnhetett, de valójában nem volt vészes. A legnagyobb nehézség az adatábrázolásban és a fájl beolvasásában volt. Holnap folytatjuk. ✨