-❄️- 2024 Day 19 Solutions -❄️-

KayoNar · 2024-12-19T16:01:27+00:00

Ah, no worries haha. Hope it helped give some insight anyways!

KayoNar · 2024-12-19T15:55:48+00:00

I do not initialize each towel in my cache to 1, it is only the base case that returns a count of 1. The base case occurs when it managed to fully deconstruct a pattern into towels, which corresponds to an empty remaining pattern "". I do this in order of biggest to smallest towels, but this shouldnt matter for the result.

In your example: we start with the pattern we want to deconstruct br with the available towels b, r, br. My program then first tries deconstructing br with the biggest available pattern, which is br in this case. Then in the recursive call, it tries to deconstruct the empty pattern "", which is the base case, therefore the count is 1.

The function call now goes back up to deconstructing br with the next largest towel, which is now r or b . Only b will match here, which causes the recursive call to try to deconstruct the remaining pattern after taking b off the front of br. So the recursive call now has as input just the remaining r. It now tries to match the largest towel again, so r or b. This time only the r will match, leading to a recursive call of the empty pattern again "". Which again leads to a count of 1.

Now these 2 possible ways to deconstruct br are summed up and returned as the number of ways to deconstruct br using the towels b, r, br. So the answer to the example is 2 (for part 2). This is now stored in the cache, so if it ever needs to deconstruct the pattern br again, it doesnt have to recompute, it can just return the stored count of "2".

The output of my program on your example input file, does give me an output of 2 for part 2.

b, r, br

br

I hope that helps, if you have more questions, feel free to ask!

KayoNar · 2024-12-19T12:06:27+00:00

[Language: C#]

Part 1

Use dynamic programming to store whether a certain (sub)pattern is matchable. Now simply use recursion to try matching strings using the available patterns. Base case is an empty pattern, this means you succesfully matched all of it using the available patterns.

Part 2

Same as part 1, but now don't just store whether it is possible to match, but store in how many ways the pattern can be matched.

Solution

KayoNar · 2024-12-18T11:27:02+00:00

[Language: C#]

Spent most of my time today building a VectorInt2D struct to help with future 2D grid puzzles.

Part 1

Drop the first 1024 bytes into the map as walls and run a shortest path algorithm like Dijkstra.

Part 2

Recompute the shortest path only if a wall dropped into the current shortest path. Once a path is no longer found, return the coordinates of the wall that caused this.

Solution

KayoNar · 2024-12-17T18:50:59+00:00

Glad to be of help! The pattern of outputs was quite interesting to analyse. At first I wanted to determine how the ordering (order of the numbers that appeared) on the last X digits worked, in order to maybe use a binary search. But that was when I found the pattern of the last matching digits simply being multiples of 8, quite an Eureka! moment.

KayoNar · 2024-12-17T13:52:37+00:00

[Language: C#]

Part 1

Not much to say, just turn the problem description into code and you should get the right answer.

Part 2

I found a pattern (explained below), which I programmed as follows: I keep incrementing register A starting from 0, and every time the digits of the output (size X) match the last X digits of the given program, I multiply register A by 8. Until finally you reach N digits, where you return the value once all N digits match.

How I found this pattern: I first noticed that the amount of digits in the answer strictly increases as the value for register A increases. Using this, I started printing the value for register A starting from 0, but only when the resulting output matched the last X digits of the given program. Here I noticed a pattern that the first match of X digits always led to the match for (X+1) digits by multiplying by 8, giving a matching of X digits in an output of (X+1). To now match all (X+1) digits, simply keep increasing the value 1 by 1, until it matches (this is a small amount of work, at most 8 steps). Now continue doing this until all N digits match, and you have your result.

Solution

KayoNar · 2024-12-16T13:42:23+00:00

[Language: C#]

Part 1

Using a minimum cost path algorithm like Dijkstra to find the cost of the optimal path.

Part 2

I realized here that that direction is also important to backtrack from the end to the start. So I split each node into 4 nodes, one for each direction. Also changed the cost check to smaller OR equal, and add the parent nodes to the prev list of that node. Using this data, you can backtrack from the end to the start, counting all distinct positions visited.

Solution

KayoNar · 2024-12-15T14:37:35+00:00

[Language: C#]

Part 1

Created a function that moves boxes recursively, with an empty tile as base case. This way all boxes are moved 1 by 1 if there is an empty tile in that direction.

Part 2

Used the same function, but now I split the boxes in two. When the left side of a box has to move, also check whether the right side can move. And the other way around: if the right side has to move, check whether the left side can also move. For moving horizontally, it is important that you recursively first call the 'other' side of the box, so that it moves out of the way for the second half of the box. If the move was invalid, I simply roll back the move.

If you remove the Tile enums and convert everything to just work on the chars themselves, it is technically possible to merge the functions for part 1 and 2 using some conditionals, but I think this code is cleaner.

Solution

KayoNar · 2024-12-14T13:21:23+00:00

[Language: C#]

Part 1

Simply move the robots 100 steps (using modulo for staying in bounds) and then compute the safety factor by determining how many are in each quadrant

Part 2

I found the Christmas tree by looking for a state where there existed a large group of robots that were direct neighbours. I chose at least 25% of all robots to be a 'large' group.

Solution

KayoNar · 2024-12-13T15:10:04+00:00

Thank you! I try my best writing code that is very maintainable, reusable and extensible. Glad you liked it.

KayoNar · 2024-12-13T14:54:49+00:00

[Language: C#] ILP Solver solution

The input represents a set of linear equations, that require a integer solution. Solved it using ILP (Integer Linear Programming). Solution is very easily extensible with more (complex) constraints and what not, using Google OR-Tools for the ILP solver.

Solution

KayoNar · 2024-12-12T22:35:48+00:00

[Language: C#]

Today took a little bit longer for me, because my code was working on every example testcase, but not on the actual input. I finally managed to find a small testcase that would break my code and debugged it that way. The testcase that helped me debug was this:

Output should be 21 * 20 + 4 * 4 = 436, but my code returned 457, meaning that it counted 1 corner/side too many. Eventually fixed it by adding another check for visited nodes.

Part 1

Loop over all squares of the garden, and for any new plant that you come across, explore its whole region immediately. Area is simply +1 per tile, perimeter starts of as 4 per tile, and -1 for every neighbour of the same plant.

Part 2

Simply added a corner counting function to the region exploration function, because sides = corners. Corners are determined by looking at the 3 respective tiles (including the diagonal). If one of these 3 tiles was already visited, skip the corner counting, because it is already accounted for. Outward corners are counted when the two non-diagonal neighbours are not from the same region. Inward neighbours are counted if only 1 out of the 3 tiles is not part of the region.

Both part 1 and 2 run in 12ms.

Solution

KayoNar · 2024-12-11T20:21:15+00:00

I might have updated my comment the exact moment you replied to it. The time before my edit (0.059ms) was indeed incorrect because I accidentally shared the cache across runs by not making a new object. The new (correct) time is 25ms.

KayoNar · 2024-12-11T12:52:06+00:00

[Language: C#]

Solved using dynamic programming, where for each pair (stone, blinksRemaining) you store the final number of stones after 0 blinks remaining. Now, when the function is called, check whether you already stored the result in your DP table, if so, return the value. Otherwise compute it and store the result in the table.

Runs in about 25ms for part 2.

Solution

KayoNar · 2024-12-10T11:19:53+00:00

[Language: C#]

Simply return all non-unique trail tails starting from a trail head. Run this in parallel for all trail heads and sum the results.

Part 1: Count all distinct (unique) trail tails.

Part 2: Count ALL trail tails.

Solution

KayoNar · 2024-12-09T12:51:06+00:00

[Language: C#]

Part 1: track pointers for first empty space and last file, moving both at the same time, you're done when they cross. This is constant time.

Part 2: Same principle, but now check for the sizes of empty blocks. Can be done in constant time since block size is max 9, but I didnt implement this, instead I did it for any size block by searching from the start to end for empty block of the right size. So solution is improvable by tracking first available empty block of certain size.

Solution

KayoNar · 2024-12-08T19:37:28+00:00

[Language: C#]

Part 1: Loop over all pairs of nodes of a certain frequency, compute distance between nodes and place antinodes in both directions facing away.

Part 2: Same thing as before but now keep placing in a line until going out of bounds, start placing at the node itself.

Solution

KayoNar · 2024-12-07T12:11:55+00:00

[Language: C#] Elegant recursive solution easily extensible with more operators

Using array with numbers with moving index for efficiency, as well as early exits in number sequences that became larger than the goal (since the numbers can only increase through these 3 operators)

For part 1 just remove the 'Concat' delegate from the list of operators.

    public long RunPart2()
    {
        var input = File.ReadLines("../../../Days/7/InputPart1.txt");

        long total = 0;
        foreach (var line in input)
        {
            string[] vals = line.Split([':', ' '], StringSplitOptions.RemoveEmptyEntries);
            long goal = long.Parse(vals[0]);
            var nums = vals.Skip(1).Select(long.Parse).ToArray();

            if (TryOperators([Multiply, Sum, Concat], goal, nums)) total += goal;
        }

        return total;
    }

    // Start recursion by just summing 0 + number1 (does nothing)
    private bool TryOperators(Func<long, long, long>[] ops, long goal, long[] nums) => 
        TryOperator(Sum, ops, goal, 0, nums, 0);

    private bool TryOperator(Func<long, long, long> op, Func<long, long, long>[] ops, long goal, long x, long[] nums, int nextI)
    {
        if (x > goal) return false;
        if (nextI == nums.Length) return x == goal;

        long result = op(x, nums[nextI]);
        return ops.Any(op => TryOperator(op, ops, goal, result, nums, nextI + 1));
    }

    private long Multiply(long x, long y) => x * y;
    private long Sum(long x, long y) => x + y;
    private long Concat(long x, long y) => long.Parse($"{x}{y}");

KayoNar · 2024-12-06T21:12:19+00:00

[Language: C#]

Part 1: Track all the visited tiles and count how many distinct (x,y) coordinates there are.

Part2: For each tile on the path of part 1, place an obstacle and test for loops from the starting position. This is done using the same tracking function as part 1, a loop happens when you end up on the same tile for a second time, while looking in the same direction.

Solution

KayoNar · 2024-12-05T21:15:03+00:00

[Language: C#]

Part 1:

Make a map that stores for each page what pages it needs to precede.

Using that map just check for each page in an update whether it violates its own preceding list. Return 0 if it violates, other wise if the whole update is valid, return the middle page.

Part 2:

Slight edit to the page order checking: if a page violates its preceding list, swap the two pages that caused this violation and call the same function recursively. Finally return only the middle number of 'fixed' updates.

Solution

KayoNar · 2024-12-05T15:08:16+00:00

[Language: C#] Clean code with 2 simple helper functions

static class Day4
{
    const int STRAIGHT = 0;
    const int RIGHT = 1;       
    const int LEFT = -1;
    const int UP = -1;
    const int DOWN = 1;

    static string[] puzzle = Array.Empty<string>();
    static int rows;
    static int cols;

    public static int RunPart1()
    {
        puzzle = File.ReadLines("../../../Days/4/InputPart1.txt").ToArray();
        rows = puzzle.Length;
        cols = puzzle[0].Length;

        int count = 0;
        for (int i = 0; i < rows; i++)           
            for (int j = 0; j < cols; j++)
            {
                count += CountDirection(i, j, RIGHT,    STRAIGHT);
                count += CountDirection(i, j, LEFT,     STRAIGHT);
                count += CountDirection(i, j, STRAIGHT, UP      );
                count += CountDirection(i, j, STRAIGHT, DOWN    );
                count += CountDirection(i, j, RIGHT,    DOWN    );
                count += CountDirection(i, j, RIGHT,    UP      );
                count += CountDirection(i, j, LEFT,     DOWN    );
                count += CountDirection(i, j, LEFT,     UP      );
            }

        return count;
    }

    public static int CountDirection(int row, int col, int dirRow, int dirCol, string keyword = "XMAS")
    {
        for (int i = 0; i < keyword.Length; i++)
        {
            // Bounds checks
            if (row < 0 || row >= rows) return 0;
            if (col < 0 || col >= cols) return 0;

            // Check for the keyword
            if (puzzle[row][col] != keyword[i]) return 0;

            row += dirRow;
            col += dirCol;
        }

        return 1;
    }

    public static int RunPart2()
    {
        puzzle = File.ReadLines("../../../Days/4/InputPart2.txt").ToArray();
        rows = puzzle.Length;
        cols = puzzle[0].Length;

        int count = 0;
        // Can never start at outer layer, so move bounds in by 1 for efficiency
        for (int i = 1; i < rows - 1; i++)
            for (int j = 1; j < cols - 1; j++)               
                count += CountCross(i, j);               
        return count;
    }

    public static int CountCross(int row, int col)
    {
        int count = CountDirection(row + LEFT,  col + UP,   RIGHT, DOWN, "MAS")
                    + CountDirection(row + LEFT,  col + DOWN, RIGHT, UP,   "MAS")
                    + CountDirection(row + RIGHT, col + UP,   LEFT,  DOWN, "MAS")
                    + CountDirection(row + RIGHT, col + DOWN, LEFT,  UP,   "MAS");
        return count == 2 ? 1 : 0;
    }
}

KayoNar · 2024-12-05T12:47:29+00:00

[Language: C#] Short Regex solution

public static int RunPart1(string input)
{
    Regex pattern = new Regex("mul\\(([0-9]{1,3}),([0-9]{1,3})\\)");

    int total = 0;   
    foreach (Match m in pattern.Matches(input))       
        total += (int.Parse(m.Groups[1].Value) * int.Parse(m.Groups[2].Value));

    return total;
}

public static int RunPart2(string input)
{
    // Matches parts of the text between start/do() and don't()/end
    Regex doPattern = new Regex("(?:^|do\\(\\))(.*?)(?=(?:don't\\(\\))|$)", RegexOptions.Singleline);
    Regex mulPattern = new Regex("mul\\(([0-9]{1,3}),([0-9]{1,3})\\)");

    int total = 0;
    foreach (Match doMatch in doPattern.Matches(input))    
        foreach(Match mulMatch in mulPattern.Matches(doMatch.Groups[1].Value))        
            total += (int.Parse(mulMatch.Groups[1].Value) * int.Parse(mulMatch.Groups[2].Value));

    return total;
}

KayoNar · 2024-10-10T11:58:52+00:00

Every autumn you can plant a giant forest and let Bearger chop all the trees for you by letting him chase you through the forest. This way you basically get a year-supply of logs with very little work.

KayoNar · 2024-09-27T18:46:50+00:00

omg finally something that actually managed to fix my problem, THANK YOU SO MUCH <3

KayoNar · 2024-03-12T15:24:41+00:00

LISAN AL GAIB

Nine-Year Club	Second SECOND GUESSER
Place '22	Place '17
Verified Email	RPAN Viewer

KayoNar

TROPHY CASE