Inlägg

using System.Diagnostics;
using AoCUtils;

Console.WriteLine("Mickur's Advent of Code 2022 - Day 15!");

// Setup
var input = File.ReadAllLines("input.txt");

var sensors = new List<Sensor>();
var beacons = new List<Beacon>();

// Part one variables
var partOneMinX = int.MaxValue;
var partOneMaxX = int.MinValue;

// Parse input
var startTime = Stopwatch.GetTimestamp();
for(var i = 0; i < input.Length; i++)
{
    input[i] = input[i].Replace("Sensor at x=", "");
    input[i] = input[i].Replace(" closest beacon is at x=", "");
    input[i] = input[i].Replace(" y=", "");

    var split = input[i].Split(':');

    var sensor = split[0].Split(',');
    var beacon = split[1].Split(',');
    
    var sensorX = AoCParsing.FastIntParse(sensor[0]);
    var sensorY = AoCParsing.FastIntParse(sensor[1]);
    
    var beaconX = AoCParsing.FastIntParse(beacon[0]);
    var beaconY = AoCParsing.FastIntParse(beacon[1]);

    var range = ManhattanDistance(sensorX, sensorY, beaconX, beaconY);
    
    // Set min and max
    if (sensorX - range < partOneMinX)
        partOneMinX = sensorX - range;
    if (sensorX + range > partOneMaxX)
        partOneMaxX = sensorX + range;

    sensors.Add(new Sensor(sensorX, sensorY, range));
    beacons.Add(new Beacon(beaconX, beaconY));
}
var stopTime = Stopwatch.GetTimestamp();
Console.WriteLine($"Finished parsing in {Stopwatch.GetElapsedTime(startTime, stopTime).TotalMilliseconds} ms");

startTime = Stopwatch.GetTimestamp();
var partOneAnswer = PartOne(2000000);
stopTime = Stopwatch.GetTimestamp();
Console.WriteLine($"Part one answer: {partOneAnswer}");
Console.WriteLine($"Finished part one in {Stopwatch.GetElapsedTime(startTime, stopTime).TotalMilliseconds} ms");

startTime = Stopwatch.GetTimestamp();
var partTwoAnswer = PartTwo(4000000);
stopTime = Stopwatch.GetTimestamp();
Console.WriteLine($"Part two answer: {partTwoAnswer}");
Console.WriteLine($"Finished part two in {Stopwatch.GetElapsedTime(startTime, stopTime).TotalMilliseconds} ms");

int PartOne(int y)
{
    var counter = 0;

    for (var x = partOneMinX; x <= partOneMaxX; x++)
    {
        var isBeacon = false;
        
        foreach (var beacon in beacons)
        {
            if (beacon.X == x && beacon.Y == y)
            {
                isBeacon = true;
                break;
            }
        }

        if (!isBeacon)
        {
            foreach (var sensor in sensors)
            {
                if (sensor.IsInRange(x, y))
                {
                    counter++;
                    break;
                }
            }
        }
    }

    return counter;
}

long PartTwo(int size)
{
    long returnValue = -1;
    
    var cts = new CancellationTokenSource();
    try
    {
        Parallel.For(0, size + 1, new ParallelOptions { CancellationToken = cts.Token }, y =>
        {
            for (var x = 0; x <= size;)
            {
                var inRange = false;
                var xJump = x + 1;

                for (var i = 0; i < sensors.Count; i++)
                {
                    if (sensors[i].IsInRange(x, y))
                    {
                        inRange = true;

                        // Find possible jump
                        if (x < sensors[i].X)
                        {
                            var possibleJump = sensors[i].JumpForward(y);
                            if (possibleJump > xJump)
                            {
                                xJump = possibleJump;
                            }
                        }
                    }
                }

                if (!inRange)
                {
                    returnValue = x * 4000000L + y;
                    cts.Cancel();
                }

                x = xJump;
            }
        });
    }
    catch
    {
        // ignored
    }

    return returnValue;
}

int ManhattanDistance(int firstX, int firstY, int secondX, int secondY)
{
    return Math.Abs(firstX - secondX) + Math.Abs(firstY - secondY);
}

class Sensor
{
    public readonly int X;
    public readonly int Y;

    private readonly int _range;

    public Sensor(int x, int y, int range)
    {
        X = x;
        Y = y;
        _range = range;
    }

    public bool IsInRange(int x, int y)
    {
        return Math.Abs(X - x) + Math.Abs(Y - y) <= _range;
    }

    public int JumpForward(int y)
    {
        var yDiff = Math.Abs(Y - y);
        return X + _range - yDiff + 1;
    }
}

class Beacon
{
    public readonly int X;
    public readonly int Y;

    public Beacon(int x, int y)
    {
        X = x;
        Y = y;
    }
}

using System.Diagnostics;
using AoCUtils;

Console.WriteLine("Mickur's Advent of Code 2022 - Day 13!");

// Setup
var input = File.ReadAllLines("input.txt");
var ParsedInput = new List<object>();
var PartOneAnswer = 0;
var PartTwoAnswer = 0;

var sw = new Stopwatch();
sw.Start();

// Parsing
foreach (var line in input)
{
    if(!string.IsNullOrWhiteSpace(line))
        ParsedInput.Add(ParseArray(line));
}

sw.Stop();
Console.WriteLine($"Finished parsing in {sw.ElapsedMilliseconds} ms ({sw.ElapsedTicks} ticks)");
sw.Restart();

// Part One
var rightIndicies = new List<int>();

for (var i = 0; i < ParsedInput.Count; i += 2)
{
    var leftObjects = ParsedInput[i];
    var rightObjects = ParsedInput[i + 1];

    var result = CompareArrays((List<object>) leftObjects, (List<object>) rightObjects);
    
    if (result == -1)
    {
        rightIndicies.Add((i / 2) + 1);
    }
}

PartOneAnswer = rightIndicies.Sum();

sw.Stop();
Console.WriteLine($"Finished part one in {sw.ElapsedMilliseconds} ms ({sw.ElapsedTicks} ticks)");
sw.Restart();

// Part Two
/*var newStuff = new List<object>();
foreach (var line in input)
{
    if(!string.IsNullOrWhiteSpace(line))
        newStuff.Add(ParseArray(line));
}*/

var div1 = ParseArray("[[2]]");
var div2 = ParseArray("[[6]]");

//newStuff.Add(div1);
//newStuff.Add(div2);

ParsedInput.Add(div1);
ParsedInput.Add(div2);

ParsedInput.Sort(delegate(object arr1, object arr2)
{
    return CompareArrays((List<object>) arr1, (List<object>) arr2);
});

var div1Index = 0;
var div2Index = 0;

for (int i = 0; i < ParsedInput.Count; i++)
{
    if (ParsedInput[i] == div1)
    {
        div1Index = i + 1;
    }
    
    if (ParsedInput[i] == div2)
    {
        div2Index = i + 1;
    }
}

PartTwoAnswer = div1Index * div2Index;

sw.Stop();
Console.WriteLine($"Finished part two in {sw.ElapsedMilliseconds} ms ({sw.ElapsedTicks} ticks)");

Console.WriteLine($"Part One answer: {PartOneAnswer}");
Console.WriteLine($"Part Two answer: {PartTwoAnswer}");

List<object> ParseArray(ReadOnlySpan<char> span)
{
    var depth = 0;
    var objects = new List<object>();

    var tempstring = "";

    for (var i = 0; i < span.Length; i++)
    {
        char currChar = span[i];
        
        // int is complete, parse it and save it!
        if (currChar == ',' || currChar == ']')
        {
            if (tempstring != "")
            {
                var value = AoCParsing.FastIntParse(tempstring);
                objects.Add(value);
                tempstring = "";
            }
        }
        
        if (currChar == '[') // This is our array!
        {
            // If we find a new array on our level, parse it!
            if (depth == 1)
            {
                var toAdd = ParseArray(span.Slice(i));
                objects.Add(toAdd);
            }
            
            depth++;
        }
        
        if (currChar == ']') // This is our array!
        {
            if (depth == 1)
                return objects;
            
            depth--;
        }
        
        if (char.IsDigit(currChar) && depth == 1)
        {
            tempstring += currChar;
        }
    }

    return objects;
}

int CompareArrays(List<object> array1, List<object> array2)
{
    var maxLength = Math.Max(array1.Count, array2.Count);
    
    for (var i = 0; i < maxLength; i++)
    {
        // Left is empty, right order!
        if (i >= array1.Count)
            return -1;

        // Right is empty, wrong order!
        if (i >= array2.Count)
            return 1;
        
        // Both are Ints
        if (array1[i] is int && array2[i] is int)
        {
            var a = (int)array1[i];
            var b = (int)array2[i];
            
            if (a < b)
            {
                return -1;
            }
            
            if (a > b)
            {
                return 1;
            }
        }
        // Make sure both are lists
        else
        {
            var a = array1[i] is List<object> ? (List<object>)array1[i] : new List<object> { (int)array1[i] };
            var b = array2[i] is List<object> ? (List<object>)array2[i] : new List<object> { (int)array2[i] };

            var result = CompareArrays(a, b);
            if (result != 0)
                return result;
        }
    }

    return 0;
}

using System.Diagnostics;

Console.WriteLine("Mickur's Advent of Code 2022 - Day 12!");

// Setup
var input = File.ReadAllLines("input.txt");

var sw = new Stopwatch();
sw.Start();

var hill = new Hill(input);

sw.Stop();
Console.WriteLine($"Finished creating the grid in {sw.ElapsedMilliseconds} ms ({sw.ElapsedTicks} ticks)");
sw.Restart();

var partOneAnswer = hill.PartOne();

sw.Stop();
Console.WriteLine($"Finished part one in {sw.ElapsedMilliseconds} ms ({sw.ElapsedTicks} ticks)");
sw.Restart();

var partTwoAnswer = hill.PartTwo();

sw.Stop();
Console.WriteLine($"Finished part two in {sw.ElapsedMilliseconds} ms ({sw.ElapsedTicks} ticks)");

Console.WriteLine($"Part One Answer: {partOneAnswer} steps");
Console.WriteLine($"Part Two Answer: {partTwoAnswer} steps");

public class Hill
{
    private readonly int[,] _hillGrid;
    private readonly int _width;
    private readonly int _height;

    private readonly int _startX;
    private readonly int _startY;

    private readonly int _endX;
    private readonly int _endY;

    private readonly List<(int, int)> _possibleStartingLocations = new List<(int, int)>();

    public Hill(string[] input)
    {
        _width = input[0].Length;
        _height = input.Length;

        _hillGrid = new int[_width, _height];

        for (var y = 0; y < _height; y++)
        {
            for (var x = 0; x < _width; x++)
            {
                if(input[y][x] == 'a' || input[y][x] == 'S')
                    _possibleStartingLocations.Add((x, y));
                
                if (input[y][x] == 'S')
                {
                    _startX = x;
                    _startY = y;
                    _hillGrid[x, y] = 96;
                }

                else if (input[y][x] == 'E')
                {
                    _endX = x;
                    _endY = y;
                    _hillGrid[x, y] = 123;
                }

                else
                {
                    _hillGrid[x, y] = input[y][x];
                }
            }
        }
    }

    public int PartOne()
    {
        return SolveFromLocation(_startX, _startY);
    }
    
    public int PartTwo()
    {
        var shortest = int.MaxValue;

        foreach (var startingPoint in _possibleStartingLocations)
        {
            var steps = SolveFromLocation(startingPoint.Item1, startingPoint.Item2);

            if (steps >= 0 && steps < shortest)
                shortest = steps;
        }

        return shortest;
    }

    public int SolveFromLocation(int x, int y, bool isPartTwo = false)
    {
        var positionVisited = new HashSet<(int, int)>();
        var queue = new Queue<((int, int), int)>(); // Coordinates and steps

        queue.Enqueue(((x, y), 0));

        while (queue.Count > 0)
        {
            var positionAndCount = queue.Dequeue();
            var posX = positionAndCount.Item1.Item1;
            var posY = positionAndCount.Item1.Item2;
            var count = positionAndCount.Item2;
            var currLocationValue = _hillGrid[posX, posY];

            // In Part Two, starting value is always 97.
            if (isPartTwo && currLocationValue == 96)
                currLocationValue = 97;
            
            if (posX == _endX && posY == _endY)
            {
                return count;
            }

            if (!positionVisited.Contains((posX, posY)))
            {
                positionVisited.Add((posX, posY));

                // Move up possible?
                if (posY > 0 && currLocationValue >= _hillGrid[posX, posY - 1] - 1)
                    queue.Enqueue(((posX, posY - 1), count + 1));

                // Move down possible?
                if (posY < _height - 1 && currLocationValue >= _hillGrid[posX, posY + 1] - 1)
                    queue.Enqueue(((posX, posY + 1), count + 1));

                // Move left possible?
                if (posX > 0 && currLocationValue >= _hillGrid[posX - 1, posY] - 1)
                    queue.Enqueue(((posX - 1, posY), count + 1));

                // Move right possible?
                if (posX < _width - 1 && currLocationValue >= _hillGrid[posX + 1, posY] - 1)
                    queue.Enqueue(((posX + 1, posY), count + 1));
            }
        }

        return -1;
    }
}

using AoCUtils;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;

namespace BenchmarkSandbox
{
    public class Program
    {
        public static void Main(string[] args)
        {
            BenchmarkRunner.Run<Benchmarker>();
        }
    }

    [MemoryDiagnoser]
    [SimpleJob(RuntimeMoniker.Net70)]
    public class Benchmarker
    {
        private string[] input;

        [GlobalSetup]
        public void Setup()
        {
            input = File.ReadAllLines("inputs/2022-Day11.txt");
        }
        
        [Benchmark]
        public List<Monkey> Parse()
        {
            return ParseMonkeys(input);
        }
        
        [Benchmark]
        public ulong SolvePartOne()
        {
            var monkeys = ParseMonkeys(input);
            RunRounds(monkeys, 20, false);
            SortMonkeys(monkeys);
            return monkeys[0].Activity * monkeys[1].Activity;
        }

        [Benchmark]
        public ulong SolvePartTwo()
        {
            var monkeys = ParseMonkeys(input);
            RunRounds(monkeys, 10000, true);
            SortMonkeys(monkeys);
            return monkeys[0].Activity * monkeys[1].Activity;
        }

        public List<Monkey> ParseMonkeys(IReadOnlyList<string> input)
        {
            var monkeyList = new List<Monkey>(10);

            for (var i = 0; i < input.Count; i++)
            {
                var monkey = new Monkey();

                // Parse items
                var itemsString = input[i + 1].AsSpan(18).ToString();
                var items = itemsString.Split(", ");
                for (var j = 0; j < items.Length; j++) monkey.Items.Enqueue(AoCParsing.FastULongParse(items[j]));

                // Parse operation
                var operation = input[i + 2][23];
                var operationValue =
                    input[i + 2][25] == 'o'
                        ? 0
                        : AoCParsing.FastULongParse(input[i + 2].AsSpan(25)); // Set to 0 if "old", otherwise parse it
                monkey.Operation = (operation, operationValue);

                // Parse test
                monkey.TestDivision = AoCParsing.FastULongParse(input[i + 3].AsSpan(21));
                monkey.TestTargets = (AoCParsing.FastIntParse(input[i + 4].AsSpan(29)),
                    AoCParsing.FastIntParse(input[i + 5].AsSpan(30)));

                monkeyList.Add(monkey);

                i += 6;
            }

            return monkeyList;
        }

        public void RunRounds(IReadOnlyList<Monkey> monkeys, int rounds, bool isPartTwo)
        {
            ulong divideBy = 3;

            if (isPartTwo)
            {
                divideBy = 1;
                for (var k = 0; k < monkeys.Count; k++) divideBy *= monkeys[k].TestDivision;
            }

            for (var i = 0; i < rounds; i++)
                // Monkeys
            for (var j = 0; j < monkeys.Count; j++)
                // Items
                while (monkeys[j].Items.Count != 0)
                {
                    var item = monkeys[j].Inspect(isPartTwo, divideBy);
                    monkeys[item.Item2].Items.Enqueue(item.Item1);
                }
        }

        public void SortMonkeys(List<Monkey> monkeys)
        {
            monkeys.Sort(delegate(Monkey m1, Monkey m2)
            {
                if (m1.Activity < m2.Activity)
                    return 1;

                if (m1.Activity > m2.Activity)
                    return -1;

                return 0;
            });
        }
    }
}

public class Monkey
{
    public readonly Queue<ulong> Items = new(10);
    public ulong Activity;
    public (char, ulong) Operation;
    public ulong TestDivision;
    public (int, int) TestTargets;

    public (ulong, int) Inspect(bool isPartTwo, ulong divideBy)
    {
        Activity++;

        var item = Items.Dequeue();

        switch (Operation.Item1)
        {
            case '+':
                item += Operation.Item2 == 0 ? item : Operation.Item2;
                break;

            case '*':
                item *= Operation.Item2 == 0 ? item : Operation.Item2;
                break;
        }

        if (isPartTwo)
            item %= divideBy;
        else
            item /= divideBy;

        return item % TestDivision == 0 ? (item, TestTargets.Item1) : (item, TestTargets.Item2);
    }
}