Inlägg

internal class Day17 : Puzzle
{
    public override object PartOne() =>
        GetTarget()
            .Pipe(Solve)
            .MaxHeight;

    public override object PartTwo() =>
        GetTarget()
            .Pipe(Solve)
            .Count;
    
    private static (int Count, int MaxHeight) Solve(Area target)
    {
        var count = 0;
        var maxVerticalVelocity = 0;
        var minHorizontalVelocity = CalculateMinHorizontalVelocity(target.X1);

        for (var vY = target.Y1; vY <= -target.Y1 - 1; vY++) 
        for (var vX = minHorizontalVelocity; vX <= target.X2; vX++)
        for (var t = 0; t < int.MaxValue; t++)
        {
            var verticalPosition = CalculatePosition(vY, t);
            var horizontalPosition = CalculateHorizontalPosition(vX, t);

            if (verticalPosition.IsBetween(target.Y1, target.Y2) && horizontalPosition.IsBetween(target.X1, target.X2))
            {
                maxVerticalVelocity = vY;
                count += 1;
                break;
            }

            if (verticalPosition < target.Y1)
                break;
        }

        return (count, CalculateMaxPosition(maxVerticalVelocity));
    }

    private static int CalculateMaxPosition(int v) => v * (v + 1) / 2;
    private static int CalculatePosition(int v, int t) => (t + 1) * (2 * v - t) / 2;
    private static int CalculateHorizontalPosition(int v, int t) => t >= v ? CalculateMaxPosition(v) : CalculatePosition(v, t);
    private static int CalculateMinHorizontalVelocity(int pos) => (int)Math.Ceiling((Math.Sqrt(8 * pos + 1) - 1) / 2);

    private Area GetTarget()
    {
        var values = Utilities.GetInput(GetType())
            .Pipe(x => Regex.Matches(x, @-?\d+)
                .Select(y => int.Parse(y.Value))).ToArray();

        return new Area(values[0], values[1], values[2], values[3]);
    }

    private record Area(int X1, int X2, int Y1, int Y2);
}

internal class Day12 : Puzzle
{
    public override object PartOne() => GetPathCount(new HashSet<Node>(), GetStartNode(), false);

    public override object PartTwo() => GetPathCount(new HashSet<Node>(), GetStartNode(), true);

    private static int GetPathCount(HashSet<Node> visitedLimitedNodes, Node node, bool allowVisitOneLimitedNodeTwice)
    {
        if (node.IsEnd) return 1;

        if (allowVisitOneLimitedNodeTwice && node.LimitedVisits && visitedLimitedNodes.Contains(node))
            allowVisitOneLimitedNodeTwice = false;

        if (node.LimitedVisits)
            visitedLimitedNodes = new HashSet<Node>(visitedLimitedNodes, visitedLimitedNodes.Comparer) { node };

        return node.ConnectedNodes
            .Where(x => !x.IsStart && 
                        (!x.LimitedVisits || allowVisitOneLimitedNodeTwice || !visitedLimitedNodes.Contains(x)))
            .Sum(x => GetPathCount(visitedLimitedNodes, x, allowVisitOneLimitedNodeTwice));
    }

    private Node GetStartNode()
    {
        var paths = Utilities.GetInput(GetType())
            .Split(Environment.NewLine)
            .Select(x => x.Split("-").ToArray())
            .Select(x => (Start: x[0], Destination: x[1]));

        var nodesDict = new Dictionary<string, Node>();

        foreach (var (start, destination) in paths)
        {
            nodesDict.TryAdd(start, new Node(start));
            nodesDict.TryAdd(destination, new Node(destination));

            var (startNode, destinationNode) = (nodesDict[start], nodesDict[destination]);

            startNode.ConnectedNodes.Add(destinationNode);
            destinationNode.ConnectedNodes.Add(startNode);
        }

        return nodesDict["start"];
    }

    private class Node
    {
        public readonly bool IsStart;
        public readonly bool IsEnd;
        public readonly bool LimitedVisits;

        public Node(string name)
        {
            ConnectedNodes = new List<Node>();
            IsStart = name == "start";
            IsEnd = name == "end";
            LimitedVisits = name == name.ToLower();
        }

        public IList<Node> ConnectedNodes { get; }
    }
}

internal class Day09 : Puzzle
{
    private static int _xMax;
    private static int _yMax;

    public override object PartOne()
    {
        var map = GetLocations().ToDictionary(p => (p.X, p.Y));
        
        return map.Where(p => GetAdjacentLocations(map, p.Key.X, p.Key.Y).All(a => a.Height > p.Value.Height))
            .Sum(p => p.Value.Height + 1);
    }

    public override object PartTwo()
    {
        var map = GetLocations().ToDictionary(p => (p.X, p.Y));
        
        return map.Where(p => GetAdjacentLocations(map, p.Key.X, p.Key.Y).All(a => a.Height > p.Value.Height))
            .Select(x => GetBasinSize(map, x.Key.X, x.Key.Y))
            .OrderByDescending(x => x)
            .Take(3)
            .Aggregate(1, (current, basin) => current * basin);
    }

    private static IEnumerable<Location> GetAdjacentLocations(IDictionary<(int, int), Location> map, int x, int y)
    {
        return new (int X, int Y)[] { (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1) }
            .Where(a => a.X.IsBetween(0, _xMax) && a.Y.IsBetween(0, _yMax))
            .Select(a => map[(a.X, a.Y)]);
    }

    private static int GetBasinSize(IDictionary<(int, int), Location> map, int x, int y) => GetBasin(map, x, y).Distinct().Count() + 1;

    private static IEnumerable<Location> GetBasin(IDictionary<(int, int), Location> map, int x, int y)
    {
        var higherAdjacentLocations = GetAdjacentLocations(map, x, y)
            .Where(a => a.Height != 9 && a.Height > map[(x, y)].Height)
            .ToArray();

        return higherAdjacentLocations.Concat(higherAdjacentLocations.SelectMany(a => GetBasin(map, a.X, a.Y)));
    }

    private IEnumerable<Location> GetLocations()
    {
        var rows = Utilities.GetInput(GetType())
            .Split(Environment.NewLine);

        _yMax = rows.Length - 1;
        _xMax = rows[0].Length - 1;

        for (var y = 0; y < rows.Length; y++)
        for (var x = 0; x < rows[y].Length; x++)
            yield return new Location(x, y, (int)char.GetNumericValue(rows[y][x]));
    }

    private record Location(int X, int Y, int Height);
}

internal class Day10 : Puzzle
{
    public override object PartOne()
    {
        return GetChunks()
            .Select(x => ValidateChunk(x, new Stack<char>()))
            .Where(x => x.Status == ChunkStatusEnum.Corrupted)
            .Sum(x => GetChunkOperator(x.FirstInvalidCharacter).FirstScore);
    }

    public override object PartTwo()
    {
        var scores = GetChunks()
            .Select(x => ValidateChunk(x, new Stack<char>()))
            .Where(x => x.Status == ChunkStatusEnum.Incomplete)
            .Select(x => CalculateScore(x.RemainingCharacters))
            .OrderBy(x => x)
            .ToArray();

        return scores[(scores.Length - 1) / 2];
    }

    private static (ChunkStatusEnum Status, char? FirstInvalidCharacter, Stack<char> RemainingCharacters) ValidateChunk(Queue<char> chunk, Stack<char> openings)
    {
        if (chunk.Count == 0)
            return openings.Count == 0 ? (ChunkStatusEnum.Valid, null, openings) : (ChunkStatusEnum.Incomplete, null, openings);

        var currentChar = chunk.Dequeue();

        if (IsClosingCharacter(currentChar))
            return openings.Pop() == GetChunkOperator(currentChar).Opening ? ValidateChunk(chunk, openings) : (ChunkStatusEnum.Corrupted, currentChar, openings);

        openings.Push(currentChar);
        return ValidateChunk(chunk, openings);
    }

    private static long CalculateScore(IEnumerable<char> characters) => characters.Aggregate<char, long>(0, (sum, c) => sum * 5 + GetChunkOperator(c).SecondScore);
    private static ChunkOperator GetChunkOperator(char? op) => ChunkOperators.Single(x => x.Opening == op || x.Closing == op);
    private static bool IsClosingCharacter(char op) => ChunkOperators.Any(x => x.Closing == op);

    private static ChunkOperator[] ChunkOperators => new[]
    {
        new ChunkOperator('(', ')', 3, 1), 
        new ChunkOperator('[', ']', 57, 2), 
        new ChunkOperator('{', '}', 1197, 3), 
        new ChunkOperator('<', '>', 25137, 4)
    };

    private IEnumerable<Queue<char>> GetChunks()
    {
        return Utilities.GetInput(GetType())
            .Split(Environment.NewLine)
            .Select(x => new Queue<char>(x.ToCharArray()));
    }

    private record ChunkOperator(char Opening, char Closing, int FirstScore, int SecondScore);

    private enum ChunkStatusEnum
    {
        Valid,
        Incomplete,
        Corrupted
    }
}

using System;
using System.Linq;

namespace Aoc2021.Puzzles
{
    internal class Day07 : Puzzle
    {
        public override object PartOne() => CalculateMinFuelCost(d => d);

        public override object PartTwo() => CalculateMinFuelCost(d => (d * d + d) / 2);

        private int CalculateMinFuelCost(Func<int, int> fuelCostFunc)
        {
            var positions = Utilities.GetInput(GetType())
                .Split(",")
                .Select(int.Parse)
                .ToArray();

            var (start, count) = (positions.Min(), positions.Max() - positions.Min() + 1);
            
            return Enumerable.Range(start, count)
                .AsParallel()
                .Min(position => CalculateFuelCostAtPosition(positions, position, fuelCostFunc));
        }

        private static int CalculateFuelCostAtPosition(int[] positions, int position, Func<int, int> fuelCostFunc)
        {
            return positions
                .Select(p => Math.Abs(position - p))
                .Sum(fuelCostFunc);
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Aoc2021.Puzzles
{
    internal class Day08 : Puzzle
    {
        public override object PartOne()
        {
            return ReadInput()
                .SelectMany(x => x.Output)
                .Count(x => new[] { 2, 3, 4, 7 }.Contains(x.Length));
        }

        public override object PartTwo()
        {
            return ReadInput()
                .Select(x => (x.Output, Map: DecipherSignalPatterns(x.Input)))
                .Sum(x => ConvertOutputSignalsToValue(x.Output, x.Map));
        }

        private static int ConvertOutputSignalsToValue(string[] output, IDictionary<int, string> map)
        {
            return output.Select(p => GetOutputDigit(map, p))
                .Select((x, i) => x * (int)Math.Pow(10, 3 - i))
                .Sum();
        }

        private static int GetOutputDigit(IDictionary<int, string> map, string pattern)
        {
            return map.Single(m => m.Value.ElementsEqual(pattern)).Key;
        }

        private static IDictionary<int, string> DecipherSignalPatterns(string[] patterns)
        {
            var map = new Dictionary<int, string>
            {
                { 1, patterns.Single(p => p.Length == 2) },
                { 4, patterns.Single(p => p.Length == 4) },
                { 7, patterns.Single(p => p.Length == 3) },
                { 8, patterns.Single(p => p.Length == 7) }
            };

            map.Add(3, patterns.Single(p => p.Length == 5 && map[7].All(p.Contains)));
            map.Add(9, patterns.Single(p => p.Length == 6 && map[3].All(p.Contains)));
            map.Add(0, patterns.Single(p => p.Length == 6 && map[7].All(p.Contains) && map.None(x => x.Value == p)));
            map.Add(6, patterns.Single(p => p.Length == 6 && map.None(x => x.Value == p)));
            map.Add(5, patterns.Single(p => p.Length == 5 && p.All(x => map[6].Contains(x))));
            map.Add(2, patterns.Single(p => map.None(x => x.Value == p)));

            return map;
        }

        private (string[] Input, string[] Output)[] ReadInput()
        {
            return Utilities.GetInput(GetType())
                .Split(Environment.NewLine)
                .Select(row => Regex.Matches(row, @\w{1,7}\b).Select(x => x.Value).ToArray())
                .Select(x => (x.Take(10).ToArray(), x.TakeLast(4).ToArray()))
                .ToArray();
        }
    }
}