登录查看更多内容

Advent of Code 2022 via C#

Andrea Angella

Technical Lead @ Redgate Software | ?Former Six-Times MVP on C# | ?? Grow Software Engineering Leaders | ?? Trainer, Mentor and Coach @ productivecsharp.com | ?? Host of The Productive C# Podcast | ?? Books Reader

发布日期: 2022年12月13日

The Advent of Code is a very popular event in the software development community, attended by hundreds of thousands of developers worldwide and it's gradually even becoming a tradition for employees in companies to participate (we certainly do in Redgate Software).

You don't need a computer science background to solve the problems! It's an excellent opportunity to practice problem solving and increase your fluency in your programming language of choice.

To add some fun, you can create internal personal leaderboards but ultimately the goal is to have fun and do some deliberate practice.

If you also stepped into engineering management or senior technical leadership positions where you no longer code on a daily basis, participating in these contests can be a great way to keep your skills sharp and mantain your reputation with the engineers you're directly or indirectly responsible for.

This year, I would like to share my solutions so that we can all learn from each others. Solving problems can take a considerable amount of time, especially harder problems later in the event. I believe sharing raw solutions and struggles also help to understand how people solve problems before refactoring the code to make it cleaner and more readable. Too many engineers edit their git history to make their code looks great but it's not how they wrote it in the first place and it often creates massive impostor syndrome to junior engineers getting in the profession.

In this article (which I will keep up to date as the competition progress), I am sharing all my solutions so far with a brief description of the interesting things I've learnt while solving the various problems.

If you like the article, consider following me on LinkedIn. I regularly share news on C#, .NET, technical leadership, management and anything related to software development.

Day 1: Calorie Counting

The main thing I've learn in solving Day 1 is my desire to have a function to split a collection into chunks based on a predicate.

totalCaloriesByElf = File.ReadAllLines("Input.txt"
                         .ChunkBy(x => x == "")
                         .Select(x => x.Select(int.Parse).Sum())
                         .ToList();

So I created the ChunkBy method to make this easier. I am glad I did because I have used this function a lot in later days.

    
    public static IEnumerable<IEnumerable<T>> ChunkBy<T>(this IEnumerable<T> list, Func<T, bool> predicate
    {
        var chunk = new List<T>();


        foreach (var item in list)
        {
            if (predicate(item))
            {
                yield return chunk.ToList();
                chunk.Clear();
                continue;
            }


            chunk.Add(item);
        }


        yield return chunk;
    })

I also went a step further and created an API request to add ChunkBy into .NET. It wasn't very well received and in retrospect what I created was more a version of Split but it was quite exciting to creat my first .NET proposal.

Check out my complete Day 1 solution here.

Day 2: Rock Paper Scissors

C# pattern matching and switch expressions were very useful in this problem.


private static int RoundScore(string myHand, string opHand) => 
(myHand, opHand) switch
{
    ("R", "S") or ("P", "R") or ("S", "P") => 6,
    _ when (myHand == opHand) => 3,
    _ => 0
};;

Check out my complete Day 2 solution here.

Day 3: Rucksack Reorganization

This one was fun. Using C# ranges and the LINQ Intersect method was the key for an elegant compact solution. Chunk is also an extremely useful method in .NET.

 rucksacks.Sum(x => Priority(x[..(x.Length / 2)].
Intersect(x[(x.Length / 2)..].First())););

Check out my complete Day 3 solution here.

Day 4: Camp Cleanup

This was required a bit of simple math to determine segments overlap. Creating a record class to encapsulate that logic was a nice touch.

    
    private record Assignment(int Start, int End
    {
        public bool Overlap(Assignment a) => End < a.Start || Start > a.End;
        public bool FullyContains(Assignment a) => Start <= a.Start && End >= a.End;
        public static Assignment Parse(string a) => new(int.Parse(a.Split("-")[0]), int.Parse(a.Split("-")[1]));
    })

Check out my complete Day 4 solution here.

Day 5: Supply Stacks

I created ToStack method to hardcode the input values as I cound't bother parsing.

    
    public static Stack<char> ToStack(this string s)
    {
        var result = new Stack<char>();


        foreach (var a in s)
        {
            result.Push(a);
        }


        return result;
    })

Also Regex.Match is quite handy when you want to capture values from a string.


Regex.Match(line, @"move (\d+) from (\d+) to (\d+)").Groups

Check out my complete Day 5 solution here.

Day 6: Tuning Trouble

This was a pretty easy problem. The main fun was probably to find more efficient solutions.

I've used the LINQ Distinct method and SequenceEqual to find out if a sequence of characters contains only unique characters.


sequence.Distinct().SequenceEqual(sequence))

Check out my complete Day 6 solution here.

Day 7: No Space Left On Device

From Day 7, problem started to rise in complexity which doesn't necessary means they were more fun.

I created some abstractions to represent directories and files and to implement calculating Size() in a recursive way.


internal record Dir(string Name, List<F> Files, List<Dir> Dirs, Dir Parent)
{
    public static Dir Root = new("/");
    public Dir(string Name) : this(Name, new List<F>(), new List<Dir>(), null) { }
    public Dir(string Name, Dir Parent) : this(Name, new List<F>(), new List<Dir>(), Parent) { }
    public int Size() => Files.Sum(x => x.Size) + Dirs.Sum(x => x.Size());
}


record F(string Name, int Size);

The rest of the problem was mostly boring parsing. Withe the right abstractions, it's always nice and elegant to use LINQ to find the final result.

GetDirs(Dir.Root).OrderBy(x => x.Size()).First(x => x.Size() >= spaceToFree).Size()

Check out my complete Day 7 solution here.

Day 8: Treetop Tree House

This problem was fun. I had a bit of an headache with indexes in the second part.

I haven't used any particularly fancy C# feature in this exercise.

Check out my complete Day 8 solution here.

Day 9: Rope Bridge

This was quite a interesting problem and one that was easy to underestimate.

I found using HashSet of tuples to be an effective data structure to keep track of the knots. I also really like tutple decomposition when combined with foreach loops.


var tail = (X: 0, Y: 0)
var head = (X: 0, Y: 0);
var visited = new HashSet<(int, int)> { tail };


foreach (var (Direction, Steps) in moves)
{
    for (var i  = 0; i < Steps; i++)
    {
        if (Direction == "U")      head = (head.X, head.Y - 1);
        else if (Direction == "D") head = (head.X, head.Y + 1);
        else if (Direction == "L") head = (head.X - 1, head.Y);
        else if (Direction == "R") head = (head.X + 1, head.Y);
 
        UpdateTail();
    }
};

Part 2 was very hard and I spent a lot of time to figure out the edge case when two knots are too far apart (2 in each direction). The main problem was that my code returned the correct answer for the two examples but not the actual input so I had to create a Print function to visualize the knots.

领英推荐

Coding Challenge #50 - Build Your Own Xargs

John Crickett 1 年前

WHY FUNCTIONAL PROGRAMMING SHOULD BE THE FUTURE OF…

Motivity Labs Inc 2 年前

Importance of Low-Code and No-Code Development

Gopi Raghavendra 2 年前

That lead me to create a video recording the evolution of the knots as the simulation progress. It's not very pleasant to watch but cool. I have to zoom in/out as the knots get far from the start.

Check out my complete Day 9 Part 1 solution here.

Check out my complete Day 9 Part 2 solution here.

Day 10: Cathode-Ray Tube

I've really enjoyed this puzzle. I struggled a bit in part 2 in making sure to use the correct clock value. Math.Abs and the module operator were useful.


void Clock(
{
    cycle++;


    if (Math.Abs((cycle - 1) % 40 - x) <= 1)
    {
        screen[cycle - 1] = '#';
    }


    if ((cycle - 20) % 40 == 0)
    {
        signalStrength += cycle * x;
    }
})

Check out my complete Day 10 solution here.

Day 11: Monkey in the Middle

Parsing aside, the main logic was fairly concise. The key thing was using BigIntegers and in part 2, reducing the number using the modulo of the product of the tests values. This helped me refresh some of the properties of modular arithmetic. The modulo preserves the divisibility property so long as the modulus is some multiple of the test value!

for (var round = 0; round < 10000; round++
{
    for (var i = 0; i < n; i++)
    {
        inspections[i] += worries[i].Count;

        foreach (var worryLevel in worries[i])
        {
            var worry = ops[i] switch
            {
                "*" => worryLevel * (values[i] == "old" ?                                     
                                     worryLevel : 
                                     parsedValues[i]),
 
               "+" => worryLevel + (values[i] == "old" ? 
                                     worryLevel : 
                                     parsedValues[i]),
            };

            worry %= product;

            if (worry % tests[i] == 0)
            {
                worries[trueMonkey[i]].Add(worry);
            }
            else
            {
                worries[falseMonkey[i]].Add(worry);
            }
        }


        worries[i].Clear();
    }
})

Check out my complete Day 11 solution here.

Day 12: Hill Climbing Algorithm

This was a classic search problem. I've reused my general A* Search implementation from last year advent of code and adapted it. A* is an amazing algorithm.


int AStar(int start, int goal
{
    var hashSet = new HashSet<int>();
    var openSet = new PriorityQueue<int, int>();
    openSet.Enqueue(start, 0);
    hashSet.Add(start);

    var gScore = new Dictionary<int, int>
    {
        [start] = 0
    };

    var fScore = new Dictionary<int, int>
    {
        [start] = h(start)
    };

    while (openSet.TryDequeue(out var current, out var priority))
    {
        if (current == goal)
        {
            return priority;
        }

        hashSet.Remove(current);

        var neighbors = GetNeighbors(current);

        foreach (var neighbor in neighbors)
        {
            var tentative_gScore = g(current) + d(current, neighbor);

            if (tentative_gScore < g(neighbor))
            {
                gScore[neighbor] = tentative_gScore;
                fScore[neighbor] = tentative_gScore + h(neighbor);

                if (!hashSet.Contains(neighbor))
                {
                    openSet.Enqueue(neighbor, f(neighbor));
                    hashSet.Add(neighbor);
                }
            }
        }
    }

    return int.MaxValue; // no path found

    IEnumerable<int> GetNeighbors(int i)
    {
        var r = i / cols;
        var c = i % cols;

        var current = lines[r][c];

        if (InBound(r - 1, c) && lines[r - 1][c    ] - current <= 1) yield return Index(r - 1, c);
        if (InBound(r + 1, c) && lines[r + 1][c    ] - current <= 1) yield return Index(r + 1, c);
        if (InBound(r, c - 1) && lines[    r][c - 1] - current <= 1) yield return Index(r, c - 1);
        if (InBound(r, c + 1) && lines[    r][c + 1] - current <= 1) yield return Index(r, c + 1);
    }


    int g(int current) => gScore.ContainsKey(current) ? gScore[current] : int.MaxValue;
    int f(int current) => fScore.ContainsKey(current) ? fScore[current] : int.MaxValue;


    int h(int i)
    {
        var r = i / cols;
        var c = i % cols;


        return Math.Abs(er - r) + Math.Abs(ec - c);
    }


    int d(int current, int neighbor) => Cost(neighbor);


    bool InBound(int r, int c) => r >= 0 && r < rows && c >= 0 && c < cols;
}


int Index(int r, int c) => r * cols + c;
int Cost(int i) => 1;)

Check out my complete Day 12 solution here.

Day 13:

I struggled a lot in solving this problem because I decided to do a very raw string manipiulation and parsing .

I've learnt about Regex.Replace that can take a lambda expression to reuse captures in the new value. Very handy.


result = Regex.Replace(result, @"\[(\d+),", m => $"[[{m.Groups[1].Value}],");
result = Regex.Replace(result, @",(\d+)\]", m => $",[{m.Groups[1].Value}]]");
result = Regex.Replace(result, @",(\d+),", m => $",[{m.Groups[1].Value}],");

Calculating if a pair was in order was quite involved and really need a massive refactoring.

bool? IsInOrder(string left, string right
{
? ? if (TryParseValue(left, out var leftNumber) && TryParseValue(right, out var rightNumber))
? ? {
? ? ? ? return leftNumber == rightNumber ? null : leftNumber < rightNumber;
? ? }

? ? left = WrapAllIntegers(left);
? ? right = WrapAllIntegers(right);

? ? var leftList = Unwrap(left);
? ? var rightList = Unwrap(right);

? ? for (var i = 0; i < Math.Min(leftList.Count, rightList.Count); i++)
? ? {
? ? ? ? var inOrder = IsInOrder(leftList[i], rightList[i]);

? ? ? ? if (inOrder.HasValue) return inOrder;
? ? }

? ? return leftList.Count < rightList.Count ? true : rightList.Count < leftList.Count ? false : null;
})

Check out my complete Day 13 solution here.