The Treachery of Whales - Advent of Code 2021 Day 7

An old Soviet submarine that was on visit

Maritime Museum of San Diego

Today's problem involves finding the minimum amount of fuel required to move all crab submarines into a horizontal position. 

A full description of the problem can be found here - https://adventofcode.com/2021/day/7

Understanding the problem

The given input file contains the horizontal positions of all crab submarines. In the first part of the problem each move consumes 1 unit of fuel. In the second part of the problem the first move costs 1 unit and each single move costs 1 more unit than the previous move.

First Part

While studying the solution of the first part of the problem, it becomes evident that we need to figure out the median of all crab submarines. This may seem counterintuitive but it makes sense because we need to make as few moves as possible. There are two factors here 

• Distance
• Minimizing the number of subs moved

Second Part

The answer of the second part gives away the solution. We need to figure out the average. This makes sense as we need to move all subs equidistantly towards a horizontal line. 

One caveat is that the average is usually a floating number that can be rounded either up or down. We need to explore both alternatives, solve for fuel consumed and then pick the best one - in this case the minimum fuel used.

To illustrate further, in the following example for the 4 crab subs 10,10,10,1 it is possible to have two different averages 6 and 5 and both will produce different results. We need to pick the best one.

Code

I decided to use numpy in this implementation as I had never used it before

import math
from numpy import array, abs, sum, median, mean

with open('input.txt') as f:
    lines = f.readlines()

crabSubs = array([ int(i) for i in  lines[0].split(',') ])

print(crabSubs)

# fuel consumption at 1 

medianSub = round(median(crabSubs))

print("Median" , medianSub)
print("Part 1 " , sum([ abs(medianSub - i) for i in crabSubs ]))

# fuel consumption incremental by 1 every 1 move

meanSub = mean(crabSubs)
meanSubFloor =  math.floor(meanSub)
meanSubCeil = math.ceil(meanSub)

print("Mean Floor",meanSubFloor)
print("Mean Ceil", meanSubCeil)

def calculateFuel(r):
    return sum([ i for i in range(1,r+1)])

meanSubFuelFloor  = sum([ calculateFuel(i) for i in  abs(array(crabSubs) - meanSubFloor) ])
meanSubFuelCeil  = sum([ calculateFuel(i) for i in  abs(array(crabSubs) - meanSubCeil)  ])

print("Part 2 " , min(meanSubFuelFloor,meanSubFuelCeil))