You descend into the ocean trench and encounter some snailfish. They say they saw the sleigh keys! They'll even tell you which direction the keys went if you help one of the smaller snailfish with his math homework.

Snailfish numbers aren't like regular numbers. Instead, every snailfish number is a pair - an ordered list of two elements. Each element of the pair can be either a regular number or another pair.

Read the full puzzle.

using System.Collections.Generic;
using System.Linq;

namespace AdventOfCode.Y2021.Day18;

[ProblemName("Snailfish")]
class Solution : Solver {

    // WARNING: What follows is obscure nonsense.
    //
    //     .-""-.
    //    /,..___\
    //   () {_____}
    //     (/-@-@-\)
    //     {`-=^=-'}
    //     {  `-'  } Max
    //      {     }
    //       `---'

    public object PartOne(string input) {
        // sum up all the 'numbers' in the input
        return input.Split("\n").Select(ParseNumber).Aggregate(
            new Number(),
            (acc, number) => !acc.Any() ? number : Sum(acc, number),
            Magnitude
        );
    }

    public object PartTwo(string input) {
        // get the highest magnitude resulted from adding any two 'numbers' in the input:
        var numbers = input.Split("\n").Select(ParseNumber).ToArray();
        return (
            from i in Enumerable.Range(0, numbers.Length)
            from j in Enumerable.Range(0, numbers.Length)
            where i != j
            select Magnitude(Sum(numbers[i], numbers[j]))
        ).Max();
    }

    long Magnitude(Number number) {
        var itoken = 0; // we will process the number tokenwise

        long computeRecursive() {
            var token = number[itoken++];
            if (token.kind == TokenKind.Digit) {
                // just the number
                return token.value;
            } else {
                // take left and right side of the pair
                var left = computeRecursive();
                var right = computeRecursive();
                itoken++; // don't forget to eat the closing parenthesis
                return 3 * left + 2 * right;
            }
        }

        return computeRecursive();
    }


    // just wrap A and B in a new 'number' and reduce:
    Number Sum(Number numberA, Number numberB) => Reduce(Number.Pair(numberA, numberB));

    Number Reduce(Number number) {
        while (Explode(number) || Split(number)) {
            ; // repeat until we cannot explod or split anymore
        }
        return number;
    }

    bool Explode(Number number) {
        // exploding means we need to find the first pair in the number 
        // that is embedded in 4 other pairs and get rid of it:
        var depth = 0;
        for (var i = 0; i < number.Count; i++) {
            if (number[i].kind == TokenKind.Open) {
                depth++;
                if (depth == 5) {
                    // we are deep enough, let's to the reduce part

                    // find the digit to the left (if any) and increase:
                    for (var j = i - 1; j >= 0; j--) {
                        if (number[j].kind == TokenKind.Digit) {
                            number[j] = number[j] with { value = number[j].value + number[i + 1].value };
                            break;
                        }
                    }

                    // find the digit to the right (if any) and increase:
                    for (var j = i + 3; j < number.Count; j++) {
                        if (number[j].kind == TokenKind.Digit) {
                            number[j] = number[j] with { value = number[j].value + number[i + 2].value };
                            break;
                        }
                    }

                    // replace [a b] with 0:
                    number.RemoveRange(i, 4);
                    number.Insert(i, new Token(TokenKind.Digit, 0));

                    // successful reduce:
                    return true;
                }
            } else if (number[i].kind == TokenKind.Close) {
                depth--;
            }
        }

        // couldn't reduce:
        return false;
    }

    bool Split(Number number) {

        // spliting means we neeed to find a token with a high value and make a pair out of it:
        for (var i = 0; i < number.Count; i++) {
            if (number[i].value >= 10) {

                var v = number[i].value;
                number.RemoveRange(i, 1);
                number.InsertRange(i, Number.Pair(Number.Digit(v / 2), Number.Digit((v + 1) / 2)));

                // successful split:
                return true;
            }
        }
        // couldn't split:
        return false;
    }

    // tokenize the input to a list of '[' ']' and digit tokens
    Number ParseNumber(string st) {
        var res = new Number();
        var n = "";
        foreach (var ch in st) {
            if (ch >= '0' && ch <= '9') {
                n += ch;
            } else {
                if (n != "") {
                    res.Add(new Token(TokenKind.Digit, int.Parse(n)));
                    n = "";
                }
                if (ch == '[') {
                    res.Add(new Token(TokenKind.Open));
                } else if (ch == ']') {
                    res.Add(new Token(TokenKind.Close));
                }
            }
        }
        if (n != "") {
            res.Add(new Token(TokenKind.Digit, int.Parse(n)));
            n = "";
        }
        return res;
    }

}

// we will work with a list of tokens directly
enum TokenKind {
    Open,
    Close,
    Digit
}
record Token(TokenKind kind, int value = 0);

class Number : List<Token> {
    public static Number Digit(int value) =>
        new Number(){
            new Token(TokenKind.Digit, value)
        };

    public static Number Pair(Number a, Number b) {
        var number = new Number();
        number.Add(new Token(TokenKind.Open));
        number.AddRange(a);
        number.AddRange(b);
        number.Add(new Token(TokenKind.Close));
        return number;
    }
};

Please ☆ my repo if you like it!