Day 7: The Treachery of Whales

exec(f'p={input()}')
print(sum(abs(x-sorted(p)[len(p)//2])for x in p))

exec(f'p={input()}')
n=sum(p)//len(p)
c=lambda d:d*(d+1)//2
print(sum(c(abs(x-n+n%2-1))for x in p))

def compute_p1(input)
  numbers = input.split(',').map(&:to_i)
  best_fuel_use = 9999999999999
  numbers.max.times do |tgt|
    total = numbers
              .map { |v| (v-tgt).abs }
              .sum

    best_fuel_use = total if total < best_fuel_use
  end

  return best_fuel_use
end

The only change from the first version is that instead of just taking the abs/distance for each crab-ship to the prospective target, we have to find that distance and take the sum of all digits up to that value. I forget the name for it, but that always takes the form n * (n+1) / 2 so it's just as easy to compute, no extra loops or conditions.

I did have to increase my initial best_fuel_use value from 999999 to 9999999999999 :p (Ruby will automatically promote its basic integer type Fixnum if a value gets too large, so there's not a convenient i64::MAX or equivalent lying around.)

def compute_p2(input)
  numbers = input.split(',').map(&:to_i)

  best_fuel_use = 9999999999999
  numbers.max.times do |tgt|
    total = numbers
              .map { |v| diff = (v-tgt).abs; diff * (diff+1) / 2 }
              .sum

    best_fuel_use = total if total < best_fuel_use
  end

  best_fuel_use
end

This could be made more efficient by splitting up the search space, starting at the mean value and then working up and down from there in a gradient-descent fashion, but that wasn't necessary for the provided input.

More or less the exact same approach, just less readable :P
I did switch to using 1/0.0 which evaluates to a floating point +Infinity value which works just as well as 9999999999999 in rather fewer characters, as well as replacing the plain loop with a reduce over the range so that I can return directly from there without the extra variable.

  n=input.split(',').map(&:to_i)
  (0..n.max).reduce(1/0.0){|b,t|f=n.map{|v|d=(v-t).abs;d*(d+1)/2}.sum;f<b ? f : b}

#!/usr/bin/awk -f
{ split($0, input, ",") }

END {
	for (i in input)
		if (input[i] > max)
			max = input[i]

	for (i = 0; i <= max; ++i) {
		total = 0

		for (j in input)
			total += (input[j] > i) ? input[j] - i : i - input[j]

		if (total < min || ! min)
			min = total
	}

	print min
}

#!/usr/bin/awk -f
{ split($0, input, ",") }

END {
	for (i in input)
		if (input[i] > max)
			max = input[i]

	for (i = 0; i <= max; ++i) {
		total = 0

		for (j in input) {
			steps = (input[j] > i) ? input[j] - i : i - input[j]
			total += (steps * (steps + 1)) / 2
		}

		if (total < min || ! min)
			min = total
	}

	print min
}

I had done a similar problem in the past, so I knew that the optimal position would just be the median of the given positions. To compute this, I just sorted the numbers and took the item in the middle. From there, it was just a matter of computing the fuel costs. The main thing that tripped me up was that JavaScript sorts everything alphabetically... even an array of numbers... unless you specify a custom comparison function. Pretty terrible.

let crabs      = IO.readline(line => line.split(',').map(n => parseInt(n, 10)));
let sorted     = crabs.sort((a, b) => a - b);
let optimal    = sorted[crabs.length / 2];
let movements  = crabs.map(crab => Math.abs(optimal - crab));
let fuel_costs = movements.reduce((a, b) => a + b, 0);

IO.print(`Part A: ${fuel_costs}`);

For the second part, I couldn't think of anything clever, so I just brute-forced it (ie. try every possible position and see which one yielded the minimum fuel cost). My distance function initially used a while loop to compute the sum from 1 to d, but then I remembered there was a formula for this (and looked it up online).

With this, I learned about JavaScripts Math.max and Math.min functions, along with the Math.SAFE_MAX_INTEGER constant. It has its quirks, but JavaScript is growing on me.

function distance(d) {
    return d * (d + 1) / 2;
}

let crabs = IO.readline(line => line.split(',').map(n => parseInt(n, 10)));
let min_position   = Math.min(...crabs);
let max_position   = Math.max(...crabs);
let min_fuel_costs = Number.MAX_SAFE_INTEGER;

for (let position = min_position; position < max_position; position++) {
    let movements  = crabs.map(crab => distance(Math.abs(position - crab)));
    let fuel_costs = movements.reduce((a, b) => a + b, 0);
    min_fuel_costs = Math.min(min_fuel_costs, fuel_costs);
}

IO.print(`Part B: ${min_fuel_costs}`);

use std::env;
use std::io::{self};

fn part1(input: &Vec<isize>) -> isize {
    let min = input.iter().min().unwrap();
    let max = input.iter().max().unwrap();
    let mut min_fuel = isize::MAX;
    for pos in *min..=*max {
        let mut fuel = 0;
        for crab in input {
            fuel += (pos - crab).abs();
        }
        min_fuel = std::cmp::min(min_fuel, fuel);
    }
    min_fuel
}

fn part2(input: &Vec<isize>) -> isize {
    let min = input.iter().min().unwrap();
    let max = input.iter().max().unwrap();
    let mut min_fuel = isize::MAX;
    for pos in *min..=*max {
        let mut fuel = 0;
        for crab in input {
            let x = (pos - crab).abs();
            fuel += (x.pow(2) + x) / 2;
        }
        min_fuel = std::cmp::min(min_fuel, fuel);
    }
    min_fuel
}

fn day07(input: &str) -> io::Result<()> {
    // Input
    let input = std::fs::read_to_string(input)
        .unwrap()
        .trim()
        .split(",")
        .map(|x| x.parse::<isize>().unwrap())
        .collect();

    // Answers
    println!("Part 1: {}", part1(&input)); // 349812
    println!("Part 2: {}", part2(&input)); // 99763899

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    day07(&filename).unwrap();
}

I can't really describe how I knew it, but I just sort of intuited that the median value was what I was looking for in this one. So I tried that and it worked.

#data = test_data
data = real_data
data = data.split(',')
data = [int(i) for i in data]

data.sort()

n = len(data)
  
if n % 2 == 0:
    median1 = data[n//2]
    median2 = data[n//2 - 1]
    median = (median1 + median2)/2
else:
    median = data[n//2]
    
target = median
fuel_used = 0
for distance in data:
    fuel_used = fuel_used + abs(target - distance)
print("Median is: " + str(median))
print(fuel_used)

I'm sure there's a general equation for this, but I didn't want to deal with that nonsense, so I made a lookup table and then used that to do a very simple gradient decent starting at the median value. While true feels super dirty, but I think that's as close as python gets to do while.

#data = test_data
data = real_data
data = data.split(',')
data = [int(i) for i in data]

data.sort()

n = len(data)

fuel_lookup = [0]*2500

fuel_count = 0
for x in range(0,2500):
    fuel_count = fuel_count + x
    fuel_lookup[x] = fuel_count

def calc_fuel(target, data):
    fuel_used = 0
    for location in data:
        distance = abs(target - location)
        fuel_used = fuel_used + fuel_lookup[distance]
    return fuel_used
  
if n % 2 == 0:
    median1 = data[n//2]
    median2 = data[n//2 - 1]
    median = (median1 + median2)/2
else:
    median = data[n//2]
    
target = int(median)
target_fuel = calc_fuel(target, data)

look_direction = -1
if calc_fuel(target + 1, data) < target_fuel:
    look_direction = 1
    
while True:
    target = target + look_direction
    new_target_fuel = calc_fuel(target, data)
    if new_target_fuel < target_fuel:
        target_fuel = new_target_fuel
    else:
        break
        
print(target_fuel)

• I think this one is small enough that it can be brute forced? But there are definitely some shortcuts if you think about the underlying math

• I'm pretty sure in both parts A and B there is only 1 local minima, which is also the global minima, which is also your target

defmodule AdventOfCode.Solution.Year2021.Day07 do
  def part1(input) do
    input
    |> parse_input()
    |> find_min_fuel_consumption(&fuel_consumption_a/2)
  end

  def part2(input) do
    input
    |> parse_input()
    |> find_min_fuel_consumption(&fuel_consumption_b/2)
  end

  defp find_min_fuel_consumption(locs, consumption_fn) do
    Enum.min(locs)..Enum.max(locs)
    |> Enum.map(&consumption_fn.(locs, &1))
    |> Enum.min()
  end

  defp parse_input(input) do
    input
    |> String.trim()
    |> String.split(",", trim: true)
    |> Enum.map(&String.to_integer/1)
  end

  defp fuel_consumption_a(locs, position) do
    locs
    |> Enum.map(&abs(&1 - position))
    |> Enum.sum()
  end

  defp fuel_consumption_b(locs, position) do
    locs
    |> Enum.map(fn loc ->
      n = abs(loc - position)

      # Math!! 1 + 2 + ... + n == n(n+1)/2
      div(n * (n + 1), 2)
    end)
    |> Enum.sum()
  end
end

(define (part-01 input)
  (apply min
         (for/list ([move (in-inclusive-range 1 (apply max input))])
           (min-fuel (fixed-cost move) input))))

(define (min-fuel cost crabs)
  (for/sum ([c crabs]) (cost c)))

(define ((fixed-cost move) i)
  (abs (- i move)))

(define (part-02 input)
  (apply min
    (for/list ([move (in-inclusive-range 1 (apply max input))])
      (min-fuel (increasing-cost move) input))))

(define ((increasing-cost move) i)
  (define n (abs (- i move)))
  (* 1/2 n (add1 n)))

One thing I'm jealous of is in haskell all functions have 1 argument but the magic of syntax sugar lets you define and call them as if they had multiple arguments.

There is some syntax sugar in Racket to define your own curried procedures though which I used today.

(define ((fixed-cost move) i)
  (abs (- i move)))

The de-sugared version is

(define (fixed-cost move)
  (lambda (i)
    (abs (- i move))))

.. or fully de-sugared

(define fixed-cost
  (lambda (move)
    (lambda (i)
      (abs (- i move)))))

A couple of drawbacks in Racket compared to e.g. haskell.

• Function application isn't as nice ((fixed-cost 2) 7).
• Unless built-in or library procedures are define that way you have to use curry/curryr which I actually use quite often for AoC because I often want to map/fold using multi-argument procedures with only one argument varying.

=ARRAYFORMULA(
  SUM(
   IF(ISBLANK(A2:A),,
    ABS(A2:A-MEDIAN(SORT(A2:A))))))

    =ARRAYFORMULA(
      SUM(
       IF(ISBLANK(A2:A),,
        (ABS(A2:A-(INT(AVERAGE(A2:A)))))*
        (((ABS(A2:A-(INT(AVERAGE(A2:A))))))+1)/2)))

data = list(map(int, open("input.txt").read().split(",")))
one = list()
two = list()

for t in data:
    one.append(0)
    two.append(0)
    for f in data:
        one[-1] += abs(f - t)
        two[-1] += sum(range(1, abs(f - t) + 1))

print("Part One:", min(one))
print("Part Two:", min(two))

import std/[strformat, sequtils, strutils, math]

proc parseFile(fileName: string): seq[int] =
  var input: seq[string] = split(readLines(fileName, 1)[0], ",")
  return mapIt(input, parseInt(it))

func totalDist(positions: seq[int], destination: int): int =
  return sum(mapIt(positions, abs(it - destination)))

proc main(inputFile: string) =
  var crabs: seq[int] = parseFile(inputFile)

  var minDistance: int = 999_999_999
  var minDistancePos: int

  for pos in min(crabs) .. max(crabs):
    var currDist: int = totalDist(crabs, pos)
    if currDist < minDistance:
      minDistance = currDist
      minDistancePos = pos

  echo &"The minimum fuel needed is {minDistance}"

when is_main_module:
  # main("test.txt")
  main("input.txt")

func fuelBurn(distance: int): int = 
  return sum(toSeq(1 .. distance))

func totalDist2(positions: seq[int], destination: int): int =
  return sum(mapIt(positions, fuelBurn(abs(it - destination))))

# added to main

  minDistance = 999_999_999
  minDistancePos = 0

  for pos in min(crabs) .. max(crabs):
    var currDist: int = totalDist2(crabs, pos)
    if currDist < minDistance:
      minDistance = currDist
      minDistancePos = pos

  echo &"The minimum fuel needed is {minDistance}"

const fs = require('fs');
const readline = require('readline');

let inputArr = [];

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		try {
			inputArr.push(line);
		} catch(e) {
			console.error(e);
		}
	}
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let currentFuel = 0;
	let bestFuel = 99999999;
	let bestIndex = 0;
	let crabPositionArr = inputArr[0].split(',');
	let maxIndex = crabPositionArr.reduce((a,b) => { return Math.max(a,b) });
	for (let i = 0; i<maxIndex; i++) {
		currentFuel = 0;
		// try aligning all the crabs to this index
		for (crab of crabPositionArr) {
			currentFuel += Math.abs(crab - i);
		}
		// if this uses less fuel than bestFuel, save this index to bestIndex
		if (currentFuel < bestFuel) {
			bestFuel = currentFuel;
			bestIndex = i;
		}
	}
	console.log("Answer found! Index " + bestIndex + " uses the least fuel at " + bestFuel);
})();

const fs = require('fs');
const readline = require('readline');

let inputArr = [];

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		try {
			inputArr.push(line);
		} catch(e) {
			console.error(e);
		}
	}
}

function crabFuel(spaces) {
	let totalFuel = 0;
	for (let i = spaces; i > 0; i--) {
		totalFuel += i;
	}
	return totalFuel;
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let currentFuel = 0;
	let bestFuel = 99999999;
	let bestIndex = 0;
	let crabPositionArr = inputArr[0].split(',');
	let maxIndex = crabPositionArr.reduce((a,b) => { return Math.max(a,b) });
	for (let i = 0; i<maxIndex; i++) {
		currentFuel = 0;
		// try aligning all the crabs to this index
		for (crab of crabPositionArr) {
			currentFuel += crabFuel(Math.abs(crab - i));
		}
		// if this uses less fuel than bestFuel, save this index to bestIndex
		if (currentFuel < bestFuel) {
			bestFuel = currentFuel;
			bestIndex = i;
		}
	}
	console.log("Answer found! Index " + bestIndex + " uses the least fuel at " + bestFuel);
})();

Parsing

Parsing is simple today: the input is a single line with comma-separated numbers.

fn parse(input: &str) -> Vec<isize> {
    input
        .trim()
        .split(',')
        .map(|n| n.parse::<isize>().unwrap())
        .collect()
}

Part I

Fuel consumption

Let's first assume that we know the target. Then the fuel consumption calculation is trivial:

fn fuel_consumption(positions: &Vec<isize>, center: isize) -> isize {
    let mut fuel_used = 0;

    for &pos in positions {
        fuel_used += (pos - center).abs();
    }

    fuel_used
}

The target is the point that has the overall least distance to each submarine. If we assume that the positions are sorted, that point is the middle of the list (i.e. the median).

fn median(positions: &mut Vec<isize>) -> isize {
    // TODO: Make this O(n)
    positions.sort_unstable();

    positions[positions.len() / 2]
}

Edit: Of course that doesn't work in the general case... 🤦 but this was a nice opportunity to try out property-based testing with QuickCheck.

After reworking it a bit I came up with:

fn median(positions: &mut Vec<isize>) -> isize {
    positions.sort_unstable();

    let mid = positions.len() / 2;
    let m1 = positions[mid];
    let m2 = positions[mid - 1];

    if fuel_consumption(&positions, m1) < fuel_consumption(&positions, m2) {
        m1
    } else {
        m2
    }
}

QuickCheck has so far been unable to disprove it, though it does assume that the list has at least two elements.

Edit 2: Or I could just have used the proper definition of a median instead of going from memory. 🤦

If anyone is still reading this, I apologize. Tomorrow I'll spend a while polishing everything before jumping into the thread with half-baked code...

Part II

Now we need to change how fuel consumption is calculated. Since more fuel is spent with every step, we have cost series of 1 + 2 + 3 ... which of course has Gauss's famous sum formula: n * (n + 1) / 2.

fn fuel_consumption2(positions: &Vec<isize>, center: isize) -> isize {
    let mut fuel_used = 0;

    for &pos in positions {
        let dist = (pos - center).abs();
        let cost = (dist * (dist + 1)) / 2;
        fuel_used += cost;
    }

    fuel_used
}

Unfortunately, I can't really think of a better method than brute force for part 2, though I think you can bisect the list instead of iterating over every entry.

fn find_best_spot(positions: &Vec<isize>) -> isize {
    let &min = positions.iter().min().unwrap();
    let &max = positions.iter().max().unwrap();

    let mut best_consumption = isize::MAX;
    let mut best_position = 0;

    for pos in min..max {
        let cost = fuel_consumption2(&positions, pos);
        if cost < best_consumption {
            best_consumption = cost;
            best_position = pos;
        }
    }

    best_position
}

Main

fn main() {
    let input = include_str!("../../input-07.txt");
    let mut positions = parse(input);

    println!(
        "Part I:  {}",
        fuel_consumption(&positions.clone(), median(&mut positions))
    );

    println!(
        "Part II: {}",
        fuel_consumption2(&positions, find_best_spot(&positions))
    );
}

func main() {
	var positions []int = ReadData()

	P := Min(positions...)
	max := Max(positions...)
	cost := CalcCost(positions, P)
	for i := P + 1; i <= max; i++ {
		current := CalcCost(positions, i)
		if current < cost {
			cost = current
			P = i
		}
	}

	fmt.Println(P, "-", cost)
}

func CalcCost(a []int, t int) int {
	cost := 0

	for _, p := range a {
		cost += Abs(t - p)
	}

	return cost
}

func CalcCost(a []int, t int) int {
	cost := 0

	for _, p := range a {
		d := Abs(t - p)
		for i := 0; i < d; i++ {
			cost += 1 + i
		}
	}

	return cost
}

fn parse_input(input: &str){
    let crabs: Vec<_> = input.split(",").map(|x| x.parse::<isize>().unwrap()).collect();
    let max = &crabs.iter().max().expect("No isize found.");
    let min = &crabs.iter().min().expect("No isize found.");
    println!("Part 1: {:?}",part1(&crabs,**min,**max));
    println!("Part 2: {:?}",part2(&crabs,**min,**max));
}
fn main() {
    parse_input(&std::fs::read_to_string("input.txt").unwrap().trim().to_string());
}

fn part1(crabs: &Vec<isize>, min: isize, max: isize) -> isize{
    let mut distance = isize::MAX;
    let mut cheapest = isize::MAX;
    for x in min..max {
        let mut fuel = 0;
        for crab in crabs {
            fuel += (crab - x).abs();

        }
        if fuel < distance {
            distance = fuel;
            cheapest = x;
        }
    }

    distance
}

fn part2(crabs: &Vec<isize>, min: isize, max: isize) -> isize{
    let mut distance = isize::MAX;
    let mut cheapest = isize::MAX;
    for x in min..max {
        let mut fuel = 0;
        for crab in crabs {
            let n = (crab - x).abs();
            fuel += n * (n+1) / 2;

        }
        if fuel < distance {
            distance = fuel;
            cheapest = x;
        }
    }
    distance

}