On Day 7 we're being attacked by a giant whale. Luckily, there are a bunch of carbs in tiny submarines there to help us. The crabs do need some help in getting organized though, and that's our task.

The crabs needs to line up in the same horizontal position, to be able to blow a hole in the ocean floor so that we can escape from the whale down in to the underwater cave system.

Our input for this challenge looks like this:

16,1,2,0,4,2,7,1,2,14

Each number is a crab, and the number represents its horizontal position. Since the crabs have a limited amount of fuel, they can't just move to any arbitrary position. We need to make sure they all move to the position that costs the least amount of fuel. 1 horizontal step = 1 fuel unit. For Part 1 we need to find the position that will be the cheapest position for all crabs to align, and sum up all the fuel consumed to get there.

To figure this out, we find the median position of all the crab positions. Then we just calculate the amount of fuel needed for each crab to get there, and add that up.

public static void Part1(int[] crabs)
{
    var median = GetMedian(crabs);
    var fuelConsumedPart1 = crabs.Sum(crab => Math.Abs(crab - median));

    Console.WriteLine($"Part1: {fuelConsumedPart1}");
}

The GetMedian() implementation is just something I googled and found, it looks like this:

public static int GetMedian(int[] array)
{
    int medianValue;

    int[] tempArray = array;
    int count = tempArray.Length;

    Array.Sort(tempArray);

    if (count % 2 == 0)
    {
        // count is even, need to get the middle two elements, add them together, then divide by 2
        int middleElement1 = tempArray[(count / 2) - 1];
        int middleElement2 = tempArray[(count / 2)];
        medianValue = (middleElement1 + middleElement2) / 2;
    }
    else
    {
        // count is odd, simply get the middle element.
        medianValue = tempArray[(count / 2)];
    }

    return medianValue;
}

In Part 2 it turns out that the fuel consumption is a little bit more complicated than we thought. It actually costs 1 fuel more for each step the crab has to move. So step 1 costs 1 fuel, step 2 costs 2 fuel etc. So the median step from Part 1 might not be the most efficient step anymore. I'm sure there's a clever algorithm for this aswell, but I don't know it.

What I did instead was start going through each possible position, starting with position 0 and moving on up. I keep track of the cheapest position, which is going to be the last position up until a certain point. Once the current position is more expensive than the last, we know we've found our spot and can break the loop.

public static void Part2(int[] crabs)
{
    int? fuelConsumedPart2 = null;
    var max = crabs.Max();

    for (var i = 0; i <= max; i++)
    {
        var positionCost = crabs.SelectMany(crab => Enumerable.Range(1, Math.Abs(crab - i))).Sum();

        if (!fuelConsumedPart2.HasValue || positionCost < fuelConsumedPart2)
        {
            fuelConsumedPart2 = positionCost;
        }
        else if (positionCost > fuelConsumedPart2)
        {
            break;
        }
    }

    Console.WriteLine($"Part2: {fuelConsumedPart2}");
}

There it is, Day 7 done!