Advent of Code – harmadik nap
Folytatódik tovább a történet a harmadik napi feladatban is. A tengeralattjáró furcsa, csikorgó hangokat ad ki. A biztonság kedvéért lefuttatsz egy diagnosztikai vizsgálatot.
Feladatleírás – első rész
Az a jelentés, amit a lefuttatott diagnosztika után kapsz, bináris számok listájából áll, amelyek megfelelő dekódolás után sok hasznos dolgot elárulhatnak a tengeralattjáró állapotáról. Az első paraméter, amit ki kell derítened, az energiafogyasztás.
A kapott bináris számokat két új bináris szám létrehozásához (gamma és epszilon) kell használnod. Az energiafogyasztás ezután úgy határozható meg, hogy a gammát megszorzod az epszilonnal.
A gamma bitjei úgy határozhatóak meg, hogy a diagnosztikai jelentésben szereplő összes szám megfelelő pozíciójában a leggyakoribb bitet választod. Feltételezheted, hogy sosem lesz egyenlőség a számosságok között, ha a teljes listát vizsgálod.
Vegyük például a következő diagnosztikai jelentést:
00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010
A listában a számoknak csak az első bitjét tekintve öt 0 bit és hét 1 bit van. Mivel 5 < 7, a gamma első bitje 1. A diagnosztikai jelentésben szereplő számok második bitje leggyakrabban 0, tehát a gamma második bitje 0. A harmadik, negyedik és ötödik bit leggyakoribb értéke rendre 1, 1 és 0, így a gamma utolsó három bitje 110. Tehát a gamma a 10110 binárisan, ami 22 lenne decimálisan.
Az epszilon meghatározása során pont fordítva kell gondolkodnod, a legritkább érték lesz a fontos a leggyakoribb helyett. Így az epszilon 01001, ami decimálisan 9.
Az energiafogyasztáshoz már csak össze kell szoroznod ezt a két számot, ami 22*9 = 198 az adott példán.
A kapott inputon határozd meg az energiafogyasztást és az eredményt bináris számként add meg.
Megoldás
Először is gondolnunk kell arra, hogy míg valójában sorokat olvasunk be, nekünk oszlopokkal kellene dolgoznunk. A beolvasott string tömböt transzponáljuk úgy, hogy a kapott listában egy sor az eredeti inputon egy oszlop volt. Egyszerűsítve ami sor volt, oszlop lesz, ami pedig oszlop volt, az értelemszerűen sor.
private static List<string> TransposeRows(string[] numbers, int digits)
{
var bitPositions = new List<string>(numbers[0].Length);
StringBuilder row = new StringBuilder(numbers.Length);
for (int i = 0; i < digits; i++)
{
row.Clear();
for (int j = 0; j < numbers.Length; j++)
{
row.Append(numbers[j][i]);
}
bitPositions.Add(row.ToString());
}
return bitPositions;
}
Egy másik segédfüggvényt is készítsünk a 0-ák és 1-esek számosságának meghatározásához. Mivel előzőleg már megfordítottuk az oszlopokat a sorokkal, itt paraméterben egyszerűen egy sort kell megadnunk. Azért, hogy ne kelljen két különböző függvényt készíteni, valamint, hogy egyetlen hívással meghatározzuk mindkét érték (0 és 1) számosságát, használhatjuk a C# 7-ben bevezetett Tuple szintaxist. Ahogy a forráskódban is látható, két értéket adunk vissza egyszerre. Ilyenkor nem csak a típust, de változónevet is meghatározzuk a függvény fejlécében a visszatérési értékeknek.
private static (int zero, int one) CountZeroAndOne(string datarow)
{
int zero = 0;
int one = 0;
foreach (var chr in datarow)
{
if (chr == '0')
zero++;
else if (chr == '1')
one++;
}
return (zero, one);
}
Most már van egy előfeldolgozó függvényünk és egy, ami meghatározza az 0-ák és 1-esek számosságát. Készítsük el azt a metódust, ami meghatározza a gammát és epszilont. Valójában nagyon hasonló a két algoritmus, egyetlen dologban tér el: hogy a leggyakoribb vagy a legritkább értéket szeretnénk használni az új bináris létrehozásában. Készítsünk egy enumot, aminek szűrésével majd ezt a leggyakoribb/legritkább elágazást tudjuk megvalósítani.
internal enum BitPosition
{
MostCommon,
LeastCommon,
}
A 0-ák és 1-esek számosságát és egy ilyen leggyakoribb vagy legritkább enum értéket paraméterben megkapva már triviális elkészíteni a gamma és az epszilon meghatározásának logikáját. Végigiterálunk a számosságokon és attól függően, hogy paraméterben mit határoztunk meg, vagy a leggyakoribb vagy a legritkább értéket fűzzük hozzá a string-hez, amivel visszatér a függvény.
private static string GetRateString(List<(int zero, int one)> counts, BitPosition whattoCount)
{
var sb = new StringBuilder();
foreach (var (zero, one) in counts)
{
int common = Math.Max(zero, one);
int leastCommon = Math.Min(zero, one);
if (whattoCount == BitPosition.MostCommon)
{
if (common == zero)
sb.Append('0');
else
sb.Append('1');
}
else if (whattoCount == BitPosition.LeastCommon)
{
if (leastCommon == zero)
sb.Append('0');
else
sb.Append('1');
}
}
return sb.ToString();
}
A fő logikában a GetRateString-et megfelelően paraméterezve már tudjuk használni a gammát és az epszilont a későbbiekben, ugyanis itt még nem ért véget a feladat. Mivel végig string-ekkel dolgoztunk, alakítsuk át az értékeket egész számmá. A Convert.ToInt32 beépített függvénynek paraméterben megadhatjuk, milyen számrendszert használjon. Ezután, mivel két kettes számrendszerbeli számot szorzunk, így az eredmény is bináris lesz.
string[] numbers = FileReader.ReadLinesOfFile<string>("inputs\\03.txt").ToArray();
int digits = numbers[0].Length;
List<string> bitPositions = TransposeRows(numbers, digits);
var counts = new List<(int zero, int one)>(bitPositions.Count);
foreach (var Datarow in bitPositions)
{
counts.Add(CountZeroAndOne(Datarow));
}
string gammaRateString = GetRateString(counts, BitPosition.MostCommon);
string epsilonRateString = GetRateString(counts, BitPosition.LeastCommon);
int gamma = Convert.ToInt32(gammaRateString, 2);
int epsilon = Convert.ToInt32(epsilonRateString, 2);
Console.WriteLine(gamma * epsilon);
Feladatleírás – második rész
Ezután ellenőrizned kell az életfenntartó besorolást is, amely úgy határozható meg, hogy az oxigéngenerátor besorolását megszorozzuk a CO2 gázmosó besorolásával.
Mind az oxigéngenerátor, mind a CO2 gázmosó besorolása olyan értékek, amelyek egyértelműen megtalálhatók a diagnosztikai jelentésben – ezek megtalálása a bonyolult rész. Mindkét értéket hasonló eljárással találjuk meg, amely során addig szűrünk ki értékeket, amíg csak egy marad.
Vedd figyelembe a diagnosztikai jelentésben a bináris számok első bitjét és hajtsd végre rajta a bitkritérium szűrést. Csak azokat a számokat tartsd meg a listából, amelyeket megfelelnek ennek a szűrésnek, és dobd el azokat melyek nem.
Ha csak egy szám maradt, állj meg; ez az az érték, amit kerestél.
Ellenkező esetben ismételd meg a folyamatot a jobbra soron következő bittel (Első után a második bitek, azok után a harmadik biték és így tovább…).
A bitkritérium feltételei attól függnek, hogy melyik minősítést szeretnéd megtalálni a jelentésből:
- Az oxigéngenerátor besorolásának meghatározásához határozd meg a leggyakoribb értéket (0 vagy 1) az aktuális bitpozícióban, és csak azokat a számokat tartsa meg, amelyekben az adott bit található. Ha a 0 és az 1 egyforma számosággal rendelkezik, akkor az eredmény az 1-es javára görbüljön.
- A CO2 gázmosó besorolásának meghatározásához határozd meg a legritkább értéket (0 vagy 1) az aktuális bitpozícióban, és csak azokat a számokat tartsa meg, amelyekben az adott bit található. Ha a 0 és az 1 egyforma számosággal rendelkezik, akkor az eredmény az 0 javára görbüljön.
Például az oxigéngenerátor besorolási értékének meghatározásához a fenti példa alapján:
- Kezdjük mind a 12 számmal a listából, mindegyik számnak csak az első bitjét vegyük figyelembe. Több 1 bit (7) van, mint 0 bit (5), ezért 7 db számot tartunk meg, amelyeknek 1-es áll első biten: 11110, 10110, 10111, 10101, 11100, 10000 és 11001.
- Ezután ennek a 7 számnak szűrünk a második bitje alapján: több 0 bit (4) van, mint 1 bit (3), ezért csak azt a 4 számot tartsuk meg aminek 0 van a második helyen: 10110, 10111, 10101 és 10000.
- A harmadik helyen a négy szám közül háromban 1-es szerepel, ezért maradjon meg ez a három: 10110, 10111 és 10101.
- A negyedik helyen a három szám közül kettőnek 1-es van, ezért tartsuk meg ezt a kettőt: 10110 és 10111.
- Az ötödik helyen egyenlő számosságú 0 bit és 1 bit található (egy-egy). Tehát az oxigéngenerátor értékének meghatározásához azt válasszuk, amelyiknek 1-es szerepel az ötödik bitjén: 10111.
- Mivel már csak egy számunk maradt a listából, megállhatunk: az oxigéngenerátor besorolásának értéke 10111, azaz 23 decimálisan.
Megoldás
Az előző feladat megoldásából a TransposeRows-t és a CountZeroAndOne-t változtatás nélkül tudjuk majd itt is használni. Egyedül az érték meghatározását kell lecserélnünk egy szűrő függvényre, aminek az eredeti, nem transzformált tömböt is át kell adnunk paraméterben, valamint az alapján, hogy az 1-es vagy a 0-ás felé görbül-e a a bit kritérium, tudunk arra szűrni, hogy a leggyakoribb vagy a legritkább bitet preferáljuk.
private static int ExtraxtRating(string[] numbers, int digits, List<(int zero, int one)> counts, bool ones)
{
List<string> bitPositions;
var filteredNumbers = numbers;
int digitIndex = 0;
do
{
var digitCount = counts[digitIndex];
if (ones)
{
if (digitCount.one >= digitCount.zero)
filteredNumbers = filteredNumbers.Where(n => n[digitIndex] == '1').ToArray();
else
filteredNumbers = filteredNumbers.Where(n => n[digitIndex] == '0').ToArray();
}
else
{
if (digitCount.zero <= digitCount.one)
filteredNumbers = filteredNumbers.Where(n => n[digitIndex] == '0').ToArray();
else
filteredNumbers = filteredNumbers.Where(n => n[digitIndex] == '1').ToArray();
}
bitPositions = TransposeRows(filteredNumbers, digits);
counts.Clear();
foreach (var Datarow in bitPositions)
{
counts.Add(CountZeroAndOne(Datarow));
}
++digitIndex;
}
while (filteredNumbers.Length > 1);
return Convert.ToInt32(filteredNumbers[0], 2);
}
Mielőtt visszatérünk a fő függvénybe, már a segéd függvényben bináris számmá alakíthatjuk a kapott string-et. Ezáltal a fő függvényben nincs más dolgunk, mint ugyanúgy meghívni ezeket a függvényeket, ahogy a feladat első részében, kivéve a konvertálást, mert már alapból konvertált értékekkel tudunk tovább dolgozni a szorzás során.
string[] numbers = FileReader.ReadLinesOfFile<string>("inputs\\03.txt").ToArray();
int digits = numbers[0].Length;
List<string> bitPositions = TransposeRows(numbers, digits);
var counts = new List<(int zero, int one)>(bitPositions.Count);
foreach (var Datarow in bitPositions)
{
counts.Add(CountZeroAndOne(Datarow));
}
int oxigenGenRating = ExtraxtRating(numbers, digits, counts, ones: true);
int co2rating = ExtraxtRating(numbers, digits, counts, ones: false);
Console.WriteLine(oxigenGenRating * co2rating);
Bár maguk a szűrések tűnnek a legvaskosabbnak ebben a feladatban, a nehézséget mégis az okozta inkább, hogy sorokat kaptunk, de oszlopokkal kell dolgoznunk.
Holnap folytatása következik. 🎁