Advent of Code 2021 - Day 7

Day 7: The Treachery of Whales

Useful Links

‹›

• 2021 Main Page
• My solution code

Concepts and Packages Demonstrated

NumPySciPyTriangle numbersArithmetic progressionlamdba

Problem Intro

Here I’ve documented two different solutions to this problem:

• Solution #1 - With cost functions
• Solution #2 - Optimising with SciPy

Phew, a nice easy one today.

We’re told that a giant whale is attacking our sub. A swarm of crabs, each in their own tiny sub, has come to rescue us. They’re going to blast a hole in the ocean floor that we can escape through. In order to blast, all the crabs need to align in a single vertical column. They are currently at various horizontal positions, so we need all the crabs to move to a single horizontal position, in order to form the vertical column.

The crab subs can only move horizontally, and moving costs fuel. We need to align them to a single column, with the lowest cost.

Our input data is the horizontal positions of all the crabs:

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

Part 1

Given the current crab positions, and with each 1 unit horizontal move by a crab costing 1 fuel, move all the crabs to the horizontal position that costs the least fuel. What is the total fuel cost?

Solution #1

We start by reading the input data, splitting the data at the commas, and converting each input value to an int. (Nothing new here.)

input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
    data = [int(x) for x in f.read().split(",")]
    
logger.info("Part 1 min cost: %s", get_min_cost(data))

Then we pass our list of int values into our get_min_cost() function.

def get_min_cost(data, cost_func=lambda x: x) -> tuple:
    """ Function that determines the minimum total cost to arrange our crabs

    Args:
        data (array): The initial crab positions
        cost_func (func, optional): Determines the cost for a given distance.
                                    Defaults to a cost of 1 per unit distance.

    Returns:
        tuple: Alignment position, cost
    """
    max_horizontal = max(data)
    
    costs = {}
    for i in range(max_horizontal+1):
        individual_costs = []
        for posn in data:
            individual_costs.append(cost_func(abs(posn - i)))
        
        costs[i] = sum(individual_costs)    # sun of all the costs to reach this position

    min_cost = min(costs.items(), key=lambda x: x[1])
    return min_cost   

This function starts by determining the first crab that is furthest out. Clearly, there will be no point forming a column further out than this. Then we iterate through all possible horizontal positions between 0 and furthest out, and for each horizontal position, we determine the cost to get there, for each crab. We add up all the crab costs, and store that against cost[i], where i is the horizontal position.

Finally, we return a tuple of the position [i] that has the lowest cost of all the positions, cost[i].

And that’s all there is to Part 1!

Note the use of this lambda function as a parameter:

cost_func=lambda x: x

This is equivalent to:

def some_anonymous_function(x):
    return x

So, this function simply takes an input distance - i.e. the distance between where the crab is now, and where it needs to get to - and then returns that same value as the cost.

You may be asking: “If we’re just returning the number we pass in, then what’s the point?” That brings us to Part 2…

Part 2

Now we’re told that the cost per unit of horizontal crab movement increases with distance. So, moving 1 unit costs 1, moving a second unit costs 2, moving a third unit costs 3.

Thus:

Step	Step Cost	Cumulative Cost
1	1	1
2	2	3
3	3	6
4	4	10

So the cumulative costs are the triangle numbers!

All we need to do is update this line to use a new cost function, i.e. one that returns the triangle number, rather than simply itself.

logger.info("Part 1 min cost: %s", get_min_cost(data))

The simplest way to do it would be to simply do a sum of the range of the number of steps taken. I.e. if a crab moves 3 places, we would do a sum of 1, 2, 3. This works, but it’s a little slow, since we have to compute all the step values and add them up.

It’s much easier to use a bit of basic math. Specifically, the formula that returns the sum of an arithmetic sequence. An arithmetic sequence is one where the difference between one term and the next is constant. The sum of first n terms in an arithmetic series is given by:

\[S_{n} = \frac{n}{2} (2a + (n-1)d)\]

where Sn gives us the sub for n terms, a is the value of the first term, and d is the difference between the terms.

For our problem, the cost for the first move is always 1, so a=1. And the increment in cost with each step is 1, so d=1. Thus, the equation simplifies to:

\[S_{n} = \frac{n}{2}(n+1)\]

How do we update our function call to do this? Easy… just pass in the new lambda function as a parameter to the function.

logger.info("Part 2 min cost: %s", get_min_cost(data, lambda n: n*(n+1)/2)) 

And the output looks like this:

2022-01-12 13:57:56.124:INFO:__main__:  Part 1 min cost: (350, 345035)
2022-01-12 13:57:56.461:INFO:__main__:  Part 2 min cost: (478, 97038163)
2022-01-12 13:57:56.461:INFO:__main__:  Execution time: 0.5585 seconds

Not too bad.

We could optimise a bit by only caring about unique starting positions. (Much like the lanternfish solution.) But it probably wouldn’t make much difference.

Solution #2

Here we’re going to use both NumPy and SciPy. This makes for much shorter code!

The advantage of using NumPy is that we can read the input csv data, and convert it into an np array all in one line. Furthermore, in our cost function, we can pass in any given position, and then use the numpy sum function to return the aggregate distance of that position from all elements in the array, all in one line.

Finally, we use the optimize.minimize_scalar() function from SciPy, in order to quickly determine which input value produces the minimum result, given a cost function. This saves us trawling through all positions, and then evaluating which position had the smallest cost.

import logging
import os
import time
import numpy as np
from scipy import optimize

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"
# INPUT_FILE = "input/sample_input.txt"

logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s", 
                    datefmt='%H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(level=logging.DEBUG)

input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
data: np.ndarray = np.loadtxt(input_file, delimiter=",", dtype=np.int32)

# minimize_scaler expects the function as first param, and args are any additional params the func requires
cost_part_1 = optimize.minimize_scalar(cost, args=(data))
logger.info("Part 1 min cost: %s", round(cost_part_1.fun))

cost_part_2 = optimize.minimize_scalar(cost, args=(data, lambda n: n*(n+1)/2))
logger.info("Part 2 min cost: %s", round(cost_part_2.fun)) 

def cost(posn: int, data: np.ndarray, cost_func=lambda n: n) -> int:
    """ Return the sum of applying the cost_func to get to position n, for every item in the array. """
    return cost_func(np.abs(posn-data)).sum()

Output:

2022-01-12 19:48:56.137:INFO:__main__:  Part 1 min cost: 345035
2022-01-12 19:48:56.137:INFO:__main__:  Part 2 min cost: 97038064
2022-01-12 19:48:56.137:INFO:__main__:  Execution time: 0.0033 seconds

Same answer, but over 100x faster!

‹›