Advent of Code – 10. nap

A 10. napon a tengeralattjáró navigációs rendszerét segítségül hívva megpróbálunk kijutni a barlangból, de a navigációs rendszer egy Sytax error-al jutalmaz bennünket.

A fordítóprogramok Syntax error üzenetet adnak, ha egy adott programsor hibás. Nincs ez másként a navigációs rendszerrel sem, de szerinte az összes utasítássor hibás.

Az elsÅ‘ feladatban a dolgunk, hogy kiválogassuk a hibás sorokat a navigációs rendszer programjából. Egy ilyen sor (), [], {}, <> zárójeleket tartalmazhat. Minden zárójelet a neki megfelelÅ‘ zárójellel kell bezárni. Ez azt jelenti, hogy az ilyen komplex példák, mint a ([]) vagy a [<>({}){}[([])<>]] helyesek, de a {()()()> már nem, mivel a > helyett egy } jellel kellene záródnia.

A feladatot tovább nehezíti, hogy egyes sorok nem befejezettek, hiányosak. Ezeket is szimplán ki kell hagynunk a feldolgozásból.

A kiválogatás után a hibás sorokra számolnunk kell egy pontot. Az első feladat megoldása ezeknek a pontoknak az összege lesz. A hibás sorból a pontot a sort elrontó zárójel alapján kapjuk meg:

• ): 3 pont
• ]: 57 pont
• }: 1197 pont.
• >: 25137 pont

A megoldás a következő lesz:

var lines = FileReader.ReadLinesOfFile<string>("inputs\\10.txt");
var scores = new Dictionary<char, int>()
{
    { ')', 3 },
    { ']', 57 },
    { '}', 1197 },
    { '>', 25137 },
    { '\0', 0 }
};

long solution = 0;
foreach (var line in lines)
{
    if (!TryParseLine(line, out char error))
    {
        solution += scores[error];
    }
}

A lényegi részt a TryParseLine metódus végzi, ami eldönti egy sorról, hogy helyes-e, vagy sem, illetve visszaadja a hibát okozó karaktert. A zárójelek megfelelÅ‘ sorrendezése könnyen megállapítható egy verem segítségével. Ha a a zárójel nyitó felét találjuk meg, akkor betesszük a verembe. EllenkezÅ‘ esetben pedig kiveszünk egy elemet és megnézzük, hogy az utoljára nyitott zárójelet zárja-e le. Ezt a matches nevű összerendelési táblázat adja meg:

protected readonly Dictionary<char, char> matches = new()
{ 
    { '}', '{' },
    { ')', '(' },
    { '>', '<' },
    { ']', '[' },
};

A TryParseLine forrása:

private bool TryParseLine(string line, out char error)
{
    var stack = new Stack<char>();
    foreach (var chr in line)
    {
        if (chr == '{' || chr == '[' || chr == '<' || chr == '(')
        {
            stack.Push(chr);
        }
        else
        {
            char toMatch = stack.Pop();
            if (matches[chr] != toMatch)
            {
                error = chr;
                return false;
            }
        }
    }
    error = '\0';
    return true;
}

2. feladat

A 2. feladatban ki kell egészítenünk a nem teljes sorokat a megfelelÅ‘ zárójelek sorozatával és ezek alapján kell számolnunk egy összeget. ElÅ‘ször is el kell döntenünk, hogy teljes-e a sor, vagy nem. Ha nem teljes, akkor ki kell egészíteni. A helytelen sorokkal természetesen nem kell foglalkoznunk. Ezek alapján a TryParseLine átírásával megkapjuk, hogy milyen karakterek is hiányoznak valójában:

private bool TryGetMissingClosers(string line, out Stack<char> missingClosers)
{
    var stack = new Stack<char>();
    foreach (var chr in line)
    {
        if (chr == '{' || chr == '[' || chr == '<' || chr == '(')
        {
            stack.Push(chr);
        }
        else
        {
            char toMatch = stack.Pop();
            if (matches[chr] != toMatch)
            {
                missingClosers = stack;
                return false;
            }
        }
    }
    missingClosers = stack;
    return true;
}

Ezt segítségül hívva könnyen tudunk kreálni egy metódust, ami a verem adatai alapján meghatározza a záró karaktersorozatot:

private string CompleteLine(string line)
{
    StringBuilder closingSequence = new ();
    if (TryGetMissingClosers(line, out Stack<char> missing))
    {
        while (missing.Count > 0)
        {
            closingSequence.Append(completers[missing.Pop()]);
        }
        return closingSequence.ToString();
    }
    return string.Empty;
}

A metódus üres szöveget ad vissza abban az esetben, ha a sor hibás volt. Abban az esetben pedig,ha hibátlan volt a sor, akkor üres vermet kapunk, ami alapján üres szöveg a visszatérési értékünk. A megfelelÅ‘ zárójel párok tárolását a completers összerendelési táblázat tartalmazza:

private readonly Dictionary<char, char> completers = new ()
{ 
    { '{', '}' }, 
    { '(', ')' }, 
    { '<', '>' }, 
    { '[', ']' }
};

Az, hogy a CompleteLine üres szöveget ad vissza akkor is, ha nem volt kiegészítés nem baj, mert csak az általunk helyrehozott sorokkal kell foglalkoznunk.

A feladat megoldása az lesz, hogy minden általunk kiegészített sorra ki kell számolnunk egy pontszámot, amihez ezt az algoritmust kell használni:

private readonly Dictionary<char, int> points = new()
{
    { ')', 1 },
    { ']', 2 },
    { '}', 3 },
    { '>', 4 },
};

private long CalculateLineScore(string line)
{
    long total = 0;
    foreach (var chr in line)
    {
        total *= 5;
        total += points[chr];
    }
    return total;
}

A metódus long visszatérési értéke nem véletlen, mivel egyes sorok esetén bÅ‘ven nagyobb szám fog kijönni, mint amit az int típus kezelni tud. Ez az aprócska malÅ‘r részemrÅ‘l egy jó 20 perces fejtörést okozott, mivel az összes mintára, ami a feladatkiírásban van, működött a programom, de a tényleges bemenetre meg nem.

A számított pontokat rendeznünk kell, majd a kapott lista középső eleme lesz a megoldásunk. Annyi könnyítés van, hogy minden esetben páros lesz a kiegészített sorok száma, így extra logika nem kell a tömb középső elemének meghatározásához.

Ezek alapján a megoldás:

public override void Execute()
{
    var lines = FileReader.ReadLinesOfFile<string>("inputs\\10.txt");

    var completedLines = lines
        .Select(line => CompleteLine(line))
        .Where(line => !string.IsNullOrEmpty(line));

    List<long> scores = new List<long>();
    foreach (var line in completedLines)
    {
        scores.Add(CalculateLineScore(line));
    }

    scores.Sort();
    var solution = scores[scores.Count / 2];
    Console.WriteLine(solution);

}