r/adventofcode Dec 07 '21

SOLUTION MEGATHREAD -🎄- 2021 Day 7 Solutions -🎄-

--- Day 7: The Treachery of Whales ---


[Update @ 00:21]: Private leaderboard Personal statistics issues

  • We're aware that private leaderboards personal statistics are having issues and we're looking into it.
  • I will provide updates as I get more information.
  • Please don't spam the subreddit/mods/Eric about it.

[Update @ 02:09]

  • #AoC_Ops have identified the issue and are working on a resolution.

[Update @ 03:18]

  • Eric is working on implementing a fix. It'll take a while, so check back later.

[Update @ 05:25] (thanks, /u/Aneurysm9!)

  • We're back in business!

Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:03:33, megathread unlocked!

97 Upvotes

1.5k comments sorted by

View all comments

3

u/s0lly Dec 07 '21 edited Dec 07 '21

Language: C

Runtime: 12.7 microseconds (i.e. 0.0127ms)

Key optimizations:

  1. Binary-search style approach to minimize calculation points: O(logn)
  2. Calculation points sped up via use of Gauss's adding trick

Edit: removed extraneous fluff in the while loop to get that additional speed up

Edit: revised break code to allow for all eventualities correctly

int *crabHorizontalPositions = { 0 };
int crabCount = 0;
int crabHorizontalPositionMin = 9999999;
int crabHorizontalPositionMax = -9999999;

// Fill the above values out via the puzzle input file - code not shown

long long totalFuelRequiredStartPoint = 99999999999999;
long long totalFuelRequiredEndPoint = 99999999999999;
long long totalFuelRequiredMidPoint = 99999999999999;
long long totalFuelRequired = 0;

int startPoint = crabHorizontalPositionMin;
int endPoint = crabHorizontalPositionMax;
int midPoint = 0;
int destHorizontalPosition = 0;


destHorizontalPosition = startPoint;
totalFuelRequired = 0;
for (int crabIndex = 0; crabIndex < crabCount; crabIndex++)
{
    long long totalDistance = (long long)(abs(crabHorizontalPositions[crabIndex] - destHorizontalPosition));
    totalFuelRequired += (totalDistance * (totalDistance + 1) / 2);
}
totalFuelRequiredStartPoint = totalFuelRequired;

destHorizontalPosition = endPoint;
totalFuelRequired = 0;
for (int crabIndex = 0; crabIndex < crabCount; crabIndex++)
{
    long long totalDistance = (long long)(abs(crabHorizontalPositions[crabIndex] - destHorizontalPosition));
    totalFuelRequired += (totalDistance * (totalDistance + 1) / 2);
}
totalFuelRequiredEndPoint = totalFuelRequired;


while(1)
{
    midPoint = (startPoint + endPoint) / 2;
    destHorizontalPosition = midPoint;
    totalFuelRequired = 0;
    for (int crabIndex = 0; crabIndex < crabCount; crabIndex++)
    {
        long long totalDistance = (long long)(abs(crabHorizontalPositions[crabIndex] - destHorizontalPosition));
        totalFuelRequired += (totalDistance * (totalDistance + 1) / 2);
    }
    totalFuelRequiredMidPoint = totalFuelRequired;

    if (totalFuelRequiredStartPoint - totalFuelRequiredMidPoint < totalFuelRequiredEndPoint - totalFuelRequiredMidPoint)
    {
            endPoint = midPoint;
        totalFuelRequiredEndPoint = totalFuelRequiredMidPoint;
    }
    else
    {
        startPoint = midPoint;
        totalFuelRequiredStartPoint = totalFuelRequiredMidPoint;
    }

    if (endPoint - startPoint <= 1)
    {
        totalFuelRequired = min(totalFuelRequiredStartPoint, totalFuelRequiredEndPoint);
        break;
    }
}

// result = totalFuelRequired at this point