# Advent of Code 2021 Day 7: The Treachery of Whales

By **Andreas Røssland**

https://adventofcode.com/2021/day/7 https://github.com/roessland/advent-of-code

The task this time was to find the position which minimizes the total distance from that position to each crabs starting position, using two different distance measures:

$$ \begin{aligned}dist(x, y) &= |x-y| \quad &\textrm{(Euclidean)} \\ dist2(x,y) &= \frac{|x-y| \cdot (|x-y| + 1)}{2} \quad &\textrm{(Almost Euclidean squared)} \end{aligned} $$

After finding the closed form sum for `dist2`

I just bruteforced it by trying the whole range of possible positions.

I also tried gradient descent and Nelder-Mead but the code was much more complicated than the bruteforce solution, and barely faster. Gradient descent was tricky since the function is not differentiable, so I had to approximate the gradient using a difference method.

```
package main
import (
"fmt"
"github.com/roessland/gopkg/mathutil"
"io/ioutil"
"math"
"strconv"
"strings"
)
func Dist(crabs []int, n int) (sumDist int) {
for _, crab := range crabs {
sumDist += mathutil.AbsInt(crab - n)
}
return sumDist
}
func Dist2(crabs []int, n int) (sumDist2 int) {
for _, crab := range crabs {
dist1 := mathutil.AbsInt(crab - n)
sumDist2 += dist1 * (dist1 + 1) / 2
}
return sumDist2
}
func MinMax(crabs []int) (int, int) {
min := math.MaxInt32
max := math.MinInt32
for _, crab := range crabs {
min = mathutil.MinInt(min, crab)
max = mathutil.MaxInt(max, crab)
}
return min, max
}
func main() {
crabs := ReadInput()
minDist, minDist2 := math.MaxInt32, math.MaxInt32
min, max := MinMax(crabs)
for pos := min; pos <= max; pos++ {
dist := Dist(crabs, pos)
if dist < minDist {
minDist = dist
}
dist2 := Dist2(crabs, pos)
if dist2 < minDist2 {
minDist2 = dist2
}
}
fmt.Println("Part 1:", minDist)
fmt.Println("Part 2:", minDist2)
}
func ReadInput() []int {
buf, err := ioutil.ReadFile("input.txt")
if err != nil {
panic(err)
}
var crabs []int
for _, str := range strings.Split(string(buf), ",") {
n, err := strconv.Atoi(str)
if err != nil {
panic(err)
}
crabs = append(crabs, n)
}
return crabs
}
```