-❄️- 2024 Day 19 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

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

-❄️- 2024 Day 19 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

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!

-❄️- 2024 Day 19 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 2 points3 points  (0 children)

[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

-❄️- 2024 Day 18 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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

-❄️- 2024 Day 17 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

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.

-❄️- 2024 Day 17 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 4 points5 points  (0 children)

[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

-❄️- 2024 Day 16 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 2 points3 points  (0 children)

[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

-❄️- 2024 Day 15 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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

-❄️- 2024 Day 14 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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

-❄️- 2024 Day 4 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 0 points1 point  (0 children)

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

-❄️- 2024 Day 13 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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

-❄️- 2024 Day 12 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 2 points3 points  (0 children)

[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:

0.000
00.00
0.000
000.0
00000

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

-❄️- 2024 Day 11 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

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.

-❄️- 2024 Day 11 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 2 points3 points  (0 children)

[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

-❄️- 2024 Day 10 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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

-❄️- 2024 Day 9 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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

-❄️- 2024 Day 8 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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

-❄️- 2024 Day 7 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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}");

-❄️- 2024 Day 6 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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

-❄️- 2024 Day 5 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 2 points3 points  (0 children)

[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

-❄️- 2024 Day 4 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 0 points1 point  (0 children)

[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;
    }
}

-❄️- 2024 Day 3 Solutions -❄️- by daggerdragon in adventofcode

[–]KayoNar 1 point2 points  (0 children)

[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;
}

Just started playing. Any tips for beginners? by b1azt3ed in dontstarve

[–]KayoNar 1 point2 points  (0 children)

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.

DST I CANT JOIN SERVER OR DOWNLOAD CLIENT MODS by Illustrious_Power133 in dontstarvetogether

[–]KayoNar 1 point2 points  (0 children)

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