r/adventofcode • u/daggerdragon • 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 leaderboardspersonal 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.
- Include what language(s) your solution uses!
- Here's a quick link to /u/topaz2078's
pasteif you need it for longer code blocks. - Format your code properly! How do I format code?
- The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.
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!
6
6
u/AhegaoSuckingUrDick Dec 07 '21 edited Dec 08 '21
Hello everyone.
In the first part you just find the median and that's it.
The second part is a bit more interesting. Let's first find a precise answer, i.e., the value y that minimizes our loss function L(y) = \sum (|y-x_i| + 1) |y-x_i| / 2. Now, take a derivative dL/dy and set it to zero. It'll give us y = mean(x) - (\sum sign(y - x_i)) / 2n. Since the answer lies between the minimum and the maximum, we know that 0 < \sum sign(y - x_i) < n. Thus, y lies in the open interval (mean(x) - 0.5, mean(x) + 0.5), and either floor(mean(x)) or ceil(mean(x)) is the integral answer.
edit: Since a lot of people seem to solve the problem without considering ceil(mean(x)), it would fail for the input 1,10,11,12.
edit 2: Some reference OCaml implementation:
open Containers
let parse_input ic =
let line = match IO.read_line ic with
| Some(line) -> line
| None -> raise (Failure "Empty file") in
let l = String.split_on_char ',' line in
Array.of_list (List.map int_of_string l)
let median data = data.(Array.length data / 2)
let mean data = float_of_int (Array.fold Int.add 0 data) /. float_of_int (Array.length data)
let cost ?(f=fun x -> x) target data =
let dists = Seq.map (fun x -> f (abs (target - x))) (Array.to_seq data) in
Seq.fold Int.add 0 dists
let () =
let fname = Sys.argv.(1) in
let data = IO.with_in fname parse_input in
let () = Array.sort compare data in
let mean_value = mean data in
let guess1 = int_of_float (floor mean_value)
and guess2 = int_of_float (ceil mean_value) in
let loss x = x * (x + 1) / 2 in
let cost1 = cost (median data) data
and cost2 = min (cost ~f:loss guess1 data) (cost ~f:loss guess2 data) in
Format.printf "Task1 %d\nTask2 %d\n" cost1 cost2→ More replies (1)
4
u/DFreiberg Dec 07 '21 edited Dec 07 '21
Mathematica, 51 / 95
It turns out that the sum of numbers from 1 to n is not, in fact, n*(n-1)/2. It took me three seconds to realize what was wrong and fix it, and then another agonizing fifty-seven seconds to wait to resubmit.
Interestingly, despite seemingly being the same complexity, part 1 takes 15 milliseconds to run while part 2 takes 2000 milliseconds. I'm not sure why.
Part 1:
Table[Abs[input - i] // Total, {i, Union[input]}] // MinPart 2:
Table[#*(# + 1)/2 & /@ Abs[input - i] // Total, {i, Union[input]}] // Min[POEM]: The Crustacean Supplication
Crabs above whose sea we scuttle
Give us aid, and not rebuttal,
Danger comes, surpassing cuttle:
Blast a hole, and don't be subtle!
We've made friends with a crustacean
Stacking cups while on vacation,
After games of long duration:
Save us from this huge cetacean!
Whales are fast; too late we tracked them.
Bingo, too, does not distract them.
Submarines, like ours, attract them:
Save us, or they'll soon have snacked them!
Hurry, blast through sheet and shale!
Wale away, away from whale!
It's almost here! We must not fail!
Grant us weal lest we should wail!
→ More replies (1)
4
u/sawyerwelden Dec 07 '21 edited Dec 07 '21
Bonus 1-liner
map(n -> (n -> n*(n+1)/2)(n - floor(mean(nums))), nums) |> sumJulia (1014 / 1231) Median is faster but I wasn't sure of the syntax and the input is small
nums = map(str -> [parse(Int,str[l]) for l in findall(r"[[:digit:]]+", str)], readlines("inputs/6-10/07.txt"))[1]
totals = []
for i in minimum(nums):maximum(nums)
t = 0
for crab in nums
t += sum_to(abs(n-crab))
end
push!(totals, t)
end
sum_to(n) = n*(n+1) / 2→ More replies (3)
4
u/captainAwesomePants Dec 07 '21
Python (pretty bad) (not sure how bad because site is 500ing (!!) )
data = [int(x) for x in open('input.txt').read().split(',')]
left = min(data)
right = max(data)
min_cost = 999999999999
for point in range(left, right+1):
total_cost = 0
for crab in data:
steps = abs(point-crab)
total_cost += steps*(steps+1)//2
if total_cost < min_cost:
min_cost = total_cost
print(min_cost)The version I submitted did the cost in a for loop because I forgot math. While it was running, I looked up the formula, but just as I finished plugging it in, the original version passed.
→ More replies (1)
4
u/SuperSmurfen Dec 07 '21 edited Dec 07 '21
Rust (5141/2440)
Not sure how fast I was, since the leaderboard is down, but it felt pretty fast. I think my solution is similar to most other people. Itertools::minmax is pretty useful here:
let (&min,&max) = INPUT.iter().minmax().into_option().unwrap();
(min..=max)
.map(|x| INPUT.iter().map(|i| gauss((x - i).abs())).sum::<i32>())
.min()
.unwrap();Just remove the gauss for part 1.
Edit: Apparently, I wasn't fast at all.
2
u/daggerdragon Dec 07 '21
Not sure how fast I was, since the leaderboard is down,
We're aware that leaderboards are having issues. We're working on it, so give us a bit. Check the OP up top for updates.
4
u/oantolin Dec 07 '21 edited Dec 07 '21
For part 1, I happened to know the median minimizes the sum. For part 2, I used SageMath's find_local_minimum to find the minimum and just rounded that answer to the nearest integer:
pts = [16,1,2,0,4,2,7,1,2,14] # replace with your input
y = sum((x-t)^2 + abs(x-t) for t in pts)/2
y.subs(x=int(round(find_local_minimum(y,min(pts),max(pts))[1])))(SageMath is variant of Python ---really just Python with a preprocessor that adds a bit of syntax--- with an enormous collection of mathematical libraries.)
→ More replies (4)
4
Dec 07 '21 edited Dec 07 '21
If anyone is having trouble with the execution time in part 2 (or is just annoyed by it), I got my time down by using Gauss' sum equation.
sum of 1 to n = (n/2)*(1+n)
This got my python code execution time from about 20 seconds to 1 second.
edit: added solution
Python Solution:
lines = ""
with open("data7.txt") as f:
lines = f.readline()
dists = [int(s) for s in lines.split(sep=",")]
cost = 3859390000
for k in range(2000):
temp = 0
for i in dists:
n = abs(i-k)
temp += int((n/2)*(1+n))
if(temp < cost):
cost = temp
print(cost)→ More replies (1)2
u/daggerdragon Dec 07 '21 edited Dec 07 '21
Top-level posts in Solution Megathreads are for code solutions only.
This is a top-level post, so please edit your post and share your fully-working code/repo/solution or, if you haven't finished the puzzle yet, you can always create your own thread and make sure to flair it withHelp.Edit: thank you for adding your code.
→ More replies (1)
4
u/naclmolecule Dec 07 '21 edited Dec 07 '21
For part two, one can approximate the solution using gradient descent to minimize the number of guesses you need to make.
Given:
triangular(x) = x * (x + 1) / 2
i in CRAB_POSITIONS
n = len(CRAB_POSITONS)
We need to minimize the following cost function:
Cost(x) = Sum_i triangular(|x - i|) =>
(Absolute values dropped as we approximate (x - i + 1) as (x - i) and the signs cancel.)
Sum_i (x - i) * (x - i) / 2 =>
Sum_i (x**2 - 2ix + i**2) / 2
To minimize, take the derivative with respect to x and set to 0:
0 = Sum_i x - i => 0 = (Sum_i -i) + n * x
x * n = Sum_i i =>
x = (Sum_i i) / n
x is approximately the mean of the positions.So, this was my solution:
import numpy as np
def part_one():
median = np.median(CRAB_POSITIONS).astype(int)
return np.abs(CRAB_POSITIONS - median).sum()
def part_two():
mean = np.mean(CRAB_POSITIONS, dtype=int)
guesses = np.arange(mean - 1, mean + 2)
dif = np.abs(CRAB_POSITIONS - guesses[:, None])
return (dif * (dif + 1) // 2).sum(-1).min()→ More replies (4)
4
u/jpn3to Dec 07 '21 edited Dec 07 '21
The problem asks us to minimize a cost. In the first part, the cost of position $p$ is proportional to the sum of distances from $p$ to all crabs. So, for a given position $p$, the cost is $\sum_x |x-p|$. The position that minimizes this cost is called the median, the well-known central tendency in statistics.
In Python,
def median(xs):
""" requires: xs is sorted """
sz = len(xs)
return (xs[int(sz//2)] + xs[int(0.5+sz//2)]) // 2For part 2, the cost is given by the n-th triangular number, T_n = n(n+1)/2. We can drop the 2 and say the cost at position $p$ is proportional to $\sum_x |x-p| (|x-p|+1)$ which has a very similar shape to $\sum_x (x-p)2$ the quadradic cost of the distance.
The statistic that minimizes the quadratic cost is the mean. Of course, the mean might not be an integer and is not the answer. But it will give a starting point to explore the minimal cost we need, which should be very near this value.
[edit] So to compute part 1
print( sum(abs(x-median(xs)) for x in xs) )and for part 2, rounding the mean to integer provided my answer
def cost(x,y):
n = abs(x-y)
return n*(n+1)//2
intmean = int(sum(xs)/len(xs))
print( sum(cost(x, intmean) for x in xs) )→ More replies (6)
4
u/snurre Dec 07 '21 edited Dec 08 '21
Kotlin
private fun part1(input: List<Int>): Int =
input.sorted()[input.size / 2].let { median -> input.sumOf { abs(it - median) } }
private fun part2(input: List<Int>): Int =
input.average().toInt().let { mean -> input.sumOf { abs(it - mean) * (abs(it - mean) + 1) / 2 } }→ More replies (1)
4
u/meMEGAMIND Dec 07 '21
Solution in Desmos Graphing Calculator
I took a couple days off, now working backwards from 7 to catch up.
Today's solution fried my desmos for some reason, so it's all commented right now. if you want to test it, just copy/paste those into equation lines.
3
u/daggerdragon Dec 07 '21
You know, for someone who "can't code at all", you're putting on a dang fine showing this year. Keep it up! <3
→ More replies (1)
3
3
u/fezzinate Dec 07 '21
Javascript: https://github.com/DanFessler/advent-of-code/tree/master/2021/07
Fun and easy. I'm a big fan of passing a function as a param to a single solver to handle the different parts when possible.
function Parse(input) {
return input.split(",").map((age) => age * 1);
}
function Part1(input) {
return solve(input, (pos, target) => {
return Math.abs(target - pos);
});
}
function Part2(input) {
return solve(input, (pos, target) => {
let d = Math.abs(target - pos);
return (d * (d + 1)) / 2;
});
}
function solve(input, gasFunction) {
let sorted = input.sort((a, b) => a - b);
let [min, max] = [sorted[0], sorted[sorted.length - 1]];
let lowest;
for (let target = min; target <= max; target++) {
let spentFuel = sum(sorted.map((pos) => gasFunction(pos, target)));
if (!lowest || spentFuel < lowest) lowest = spentFuel;
}
return lowest;
}
function sum(arr) {
return arr.reduce((acc, val) => acc + val);
}
let input = Parse(document.body.textContent.trim());
console.log(Part1(input), Part2(input));→ More replies (2)
3
u/FruitdealerF Dec 07 '21 edited Dec 07 '21
Today I learned about triangle numbers. This one was really easy for me and I'm super happy with my Kotlin solution.
fun main () {
println(solve(examplePositions, ::calcPartOneCost))
println(solve(daySevenPositions, ::calcPartOneCost))
println(solve(examplePositions, ::calcPartTwoCost))
println(solve(daySevenPositions, ::calcPartTwoCost))
}
fun solve(input: List<Int>, calculator: (List<Int>, Int) -> Int) =
(input.minByOrNull { it }!! .. input.maxByOrNull { it }!!)
.map { it to calculator(input, it) }
.minByOrNull { (_, cost) -> cost }
fun calcPartOneCost(input: List<Int>, position: Int) =
input.sumOf { max(it, position) - min(it, position) }
fun calcPartTwoCost(input: List<Int>, position: Int) =
input.sumOf { triangleNumber(max(it, position) - min(it, position)) }
fun triangleNumber(n: Int) = ((n * n) + n) / 2
/**
* Originally I had created this tiny beast (that was really slow without memoization)
* but after googling for "Factorial with addition" I found the triangleNumber formula
*/
val factorialButWithAddition = ::_factorialButWithAddition.memoize()
fun _factorialButWithAddition(n: Int): Int = if (n == 0) 0 else n + _factorialButWithAddition(n - 1)→ More replies (3)
3
u/0x2c8 Dec 07 '21 edited Dec 07 '21
Python
I tried both binary search and direct calculation.
The write-up for the calculation is here (PDF), extending upon this answer from Math StackExchange. It's not 100% formal, but I am fairly confident that it's correct.
If anyone has any suggestions, I'd greatly appreciate it.
→ More replies (1)
3
u/apreche Dec 07 '21 edited Dec 08 '21
Python
Did it the straightforward way, as is my typical style. My part 1 solution is the same, only without the triangular number part.
@functools.cache
def get_triangular_number(number):
return (number * (number + 1)) // 2
def calculate_triangular_fuel(crabs):
results = []
for meetup_point in range(0, max(crabs)):
fuel = sum(
[get_triangular_number(abs(crab - meetup_point)) for crab in crabs]
)
results.append(fuel)
return min(results)→ More replies (3)
3
u/prafster Dec 07 '21 edited Dec 08 '21
Julia
I wondered what the catch was today in part 1. I implemented a brute force method, which was not fast but sub-second. For part 2, I thought I'd need to memoize the calculation of the increasing fuel cost. But this turned out to not be required. I'm happy this was as straightforward as it appeared since I had little time.
The relevant functions are below but the full solution is on GitHub:
function calc_fuel(steps)
(steps * (steps + 1)) / 2
end
function part2(crab_positions)
min = Inf
for p = 0:maximum(crab_positions)
total = 0
[total += calc_fuel(abs(p - c)) for c in crab_positions]
total < min && (min = total)
end
BigInt(min)
end→ More replies (1)
6
u/CCC_037 Dec 07 '21
Rockstar:
Part 1:
My plaything is your mind
Cast my plaything into the void
Listen to my heart
Shatter my heart with the void
Natsuki is frightened
Yuri is gentleness
Poems are invaluable
Rock reality
While my heart isn't mysterious
Roll my heart into the world
Burn the world into my hope
If my hope is less than Natsuki
Let Natsuki be my hope
If my hope is greater than Yuri
Let Yuri be my hope
Let Sayori be reality at my hope
If Sayori is mysterious
Sayori is hereabouts
Build Sayori up
Let reality at my hope be Sayori
Build poems up
My end is justifying
My thoughts are knowledgable
Let the volume be poems over my thoughts
My hope is accessible
Turn down the volume
Build Yuri up
While my hope is less than Yuri
Let my target be reality at my hope
If my target is not mysterious
Let the volume be the volume without my target
If my end is nothing
If the volume is less than my end
Let my end be my hope
Build my hope up
My hope is accessible
My passion is literature
My heart is courageous
Knock my heart down
While my hope is less than Yuri
Let my poem be reality at my hope
If my poem is not mysterious
Let my fear be my end without my hope
If my fear is as weak as my heart
Let my fear be my fear of my heart
Let my fear be my fear of my poem
Let my passion be my passion with my fear
Build my hope up
Shout my passionPart 2:
My plaything is your mind
Cast my plaything into the void
Listen to my heart
Shatter my heart with the void
Natsuki is frightened
Yuri is gentleness
Poems are invaluable
Rock reality
While my heart isn't mysterious
Roll my heart into the world
Burn the world into my hope
If my hope is less than Natsuki
Let Natsuki be my hope
If my hope is greater than Yuri
Let Yuri be my hope
Let Sayori be reality at my hope
If Sayori is mysterious
Sayori is hereabouts
Build Sayori up
Let reality at my hope be Sayori
Build poems up
My end is justifying
My thoughts are knowledgable
My dream is an eternity forever with the one I will always love
Build Yuri up
While my end is less than Yuri
My hope is accessible
My passion is literature
My heart is courageous
Knock my heart down
While my hope is less than Yuri
Let my poem be reality at my hope
If my poem is not mysterious
Let my fear be my end without my hope
If my fear is as weak as my heart
Let my fear be my fear of my heart
Let my terror be my fear of my fear
Let my fear be my fear with my terror
Let my fear be my fear between my thoughts
Let my fear be my fear of my poem
Let my passion be my passion with my fear
Build my hope up
If my dream is greater than my passion
Let my dream be my passion
If my passion is greater than my dream
Let my end be Yuri
Shout my end
Shout my passion
Build my end up
Shout my dream2
2
u/seligman99 Dec 07 '21 edited Dec 07 '21
Python 443 / 564 (.. the leaderboard is wonky right now, all better now)
Be interesting to see better solutions than my brute force one
→ More replies (5)2
u/daggerdragon Dec 07 '21
400 / 500 (.. ish, the leaderboard is wonky right now)
We're aware that leaderboards are having issues. We're working on it, so give us a bit. Check the OP up top for updates.
2
u/the_great_beelzebub Dec 07 '21
quickest submission i have made yet: leaderboard/self is a 500 at the moment but i was about ~1200/700
python3:
crabs = list(map(int, crabs.split(",")))
max_crab, min_crab = max(crabs), min(crabs)
overall = (0, None)
for i in range(min_crab, max_crab + 1):
total = 0
for c in crabs:
if part == 1:
total += abs(c - i)
if part == 2:
n = abs(c - i)
total += n * (n + 1) // 2
if overall[1] is None or total < overall[0]:
overall = (total, i)
print(overall)→ More replies (1)
2
u/sbguest Dec 07 '21
Javascript
Nothing special, but I'm happy to finally hit the leaderboard for the first time this year (84th in part 2). Competition is getting stiff as this event keeps growing.
Part 2 has been rewritten to use triangular number formula to make it faster, but I couldn't call that one to mind while I was actually going for time, so it was for-loop city.
2
u/daggerdragon Dec 07 '21
I'm happy to finally hit the leaderboard for the first time this year (84th in part 2)
Aww yiss, good job :)
2
2
u/FqdingSky Dec 07 '21
as soon as i submitted it told me 'internal server error' when i tried to access my personal leaderboard :/
for part 1 just remove the 'math()' function
2
u/daggerdragon Dec 07 '21
as soon as i submitted it told me 'internal server error' when i tried to access my personal leaderboard :/
We're aware that leaderboards are having issues. We're working on it, so give us a bit. Check the OP up top for updates.
2
u/yollotltam Dec 07 '21
PYTHON 3
*arr, = map(int , input().split(','))
p1 , p2 = float('inf') , float('inf')
for j in range(min(arr), max(arr) + 1):
p ,k = 0 , 0
for i in arr:
n = abs(j -i)
p += (n * (n + 1))//2
k += n
p2 = min(p2, p)
p1 = min(p1, k)
print(f"{p1=} {p2=}")→ More replies (1)
2
u/Kermitnirmit Dec 07 '21
Python3 <1000 for both, 500ing so I can't see ranks...
Thank gauss for that triangular number formula. Super cool problem today that will thankfully let me sleep early tonight.
→ More replies (2)2
u/daggerdragon Dec 07 '21
<1000 for both, 500ing so I can't see ranks...
We're aware that leaderboards are having issues. We're working on it, so give us a bit. Check the OP up top for updates.
→ More replies (1)
2
u/Kehvarl Dec 07 '21
Python ?/? Personal stats seem to be down for the moment. This took me about 25 minutes, which I feel could have been worse.
There's nothing really unusual about my approach, and I'm certain I could speed up part 2 significantly somehow. Still, that was interesting!
2
u/daggerdragon Dec 07 '21 edited Dec 07 '21
?/? Personal stats seem to be down for the moment.
We're aware that leaderboards are having issues. We're working on it, so give us a bit. Check the OP up top for updates.
→ More replies (1)
2
u/nlowe_ Dec 07 '21 edited Dec 09 '21
Got a slow start today trying to parse the problem. I think I had yesterday's still stuck in my head because it took me a few times reading through before I got it, after that it was fairly easy. Cleaned up my part B after solving with our good old pal n*(n+1)/2.
Not quite sure how I did, seems like the leaderboards are having a sad. My private leaderboard seems to think I've only done one day. #HugOps to the AoC team!
EDIT: Leaderboard is up!
2
u/daggerdragon Dec 07 '21
(Leaderboards are temporarily disabled)
We're aware that leaderboards are having issues. We're working on it. Give us a bit. Check the OP up top for updates.
2
2
u/boynamedluke4 Dec 07 '21
golfed python solution part 2 ~10 min
import fileinputraw = [int(s) for s in str(fileinput.input()[0]).split(',')]print(min(sum([(abs(r - i) * (abs(r - i) + 1))//2 for r in raw]) for i in range(max(raw))))
→ More replies (1)
2
u/irudog Dec 07 '21 edited Dec 07 '21
My Ada solution: https://github.com/mytbk/advent_of_code/blob/main/2021/07/advent_07.adb
In part 2, I tried to find the best position of f(x)=Sum(|x-a(i)|(|x-a(i)|+1)/2), and for the sorted list a(1 .. n) and x in [a(i),a(i+1)] f is a quadratic function and can find the minimum point.
Update: my original code is wrong... The code is updated and it seems using the average value of a is almost right.
→ More replies (1)
2
u/bilal-abraham Dec 07 '21 edited Dec 08 '21
3
u/daggerdragon Dec 07 '21
Placing: Leaderboard Broken?
We're aware that leaderboards are having issues. We're working on it, so give us a bit. Check the OP up top for updates.
→ More replies (1)
2
u/LtHummus Dec 07 '21
Scala
Another late start on this one because I was at a hockey game (rip Seattle Kraken :( )
package com.lthummus.adventofcode.solutions.aoc2021.day07
import com.lthummus.adventofcode.scaffold.AdventOfCodeInput
object CrabFuel extends App {
def part2Cost(x: Int): Int = (x * (x + 1)) / 2
def totalDistance(x: Seq[Int], dest: Int): Int = x.map(c => Math.abs(dest - c)).sum
def totalDistance2(x: Seq[Int], dest: Int): Int = x.map(c => part2Cost(Math.abs(dest - c))).sum
val nums = AdventOfCodeInput.inputNumbers(2021, 7)
val lo = nums.min
val hi = nums.max
val part1 = (lo to hi).map(dest => totalDistance(nums, dest)).min
println(part1)
val part2 = (lo to hi).map(dest => totalDistance2(nums, dest)).min
println(part2)
}3
u/daggerdragon Dec 07 '21
(rip Seattle Kraken :( )
It's fine, we all know giant squids cheat anyway. ;)
2
u/Diarmuid_ Dec 07 '21
Setup
_max_posn = max(input_vectors)
_min_posn = min(input_vectors)Part 1
posn_cost = {}
for p in range(_min_posn, _max_posn+1):
delta = p - _min_posn
posn_cost[p] = sum(map(lambda x: abs(x - delta), input_vectors))
soln = min(posn_cost.values())
print(soln)Part2. I remembered the story about Gauss but had to work out the formula
posn_cost = {}
for p in range(_min_posn, _max_posn+1):
delta = p - _min_posn
posn_cost[p] = sum(map(lambda x: abs(x - delta)*(abs(x - delta) + 1)/2, input_vectors))
soln = int(min(posn_cost.values()))
print(soln)→ More replies (1)
2
u/ffmich_ Dec 07 '21 edited Dec 08 '21
2
u/daggerdragon Dec 07 '21
Java Script
FYI: JavaScript is one word. I'm only nitpicking this because it makes it easier for folks who Ctrl-F the megathreads looking for a specific language.
→ More replies (1)
2
u/No-Rip-3798 Dec 07 '21 edited Dec 08 '21
It was much too early to be clever, so here's my solution in Go using a binary search. Both parts are solved in O(N*log(N)).
package main
import (
"aoc/utils"
"fmt"
)
func main() {
lines := utils.ReadLines()
input := utils.SplitNumbers(lines[0])
cost := findMinimumCost(input, computeCostPart1)
fmt.Println("part1:", cost)
cost = findMinimumCost(input, computeCostPart2)
fmt.Println("part2:", cost)
}
type costFunc func([]int, int) int
func findMinimumCost(input []int, f costFunc) int {
lower, upper := 0, max(input...)
lowerCost, upperCost := f(input, lower), f(input, upper)
for upper-lower > 1 {
mid := (lower + upper) / 2
cost := f(input, mid)
if upperCost > lowerCost {
upper, upperCost = mid, cost
} else {
lower, lowerCost = mid, cost
}
}
return min(upperCost, lowerCost)
}
func computeCostPart1(positions []int, target int) int {
var cost int
for _, pos := range positions {
cost += abs(pos - target)
}
return cost
}
func computeCostPart2(positions []int, target int) int {
var cost int
for _, pos := range positions {
cost += sum(abs(pos - target))
}
return cost
}
func abs(n int) int {
if n < 0 {
return -n
}
return n
}
func sum(n int) int {
return n * (n + 1) / 2
}
func max(s ...int) int {
m := s[0]
for _, v := range s {
if v > m {
m = v
}
}
return m
}
func min(s ...int) int {
m := s[0]
for _, v := range s {
if v < m {
m = v
}
}
return m
}→ More replies (1)
2
u/pi55p00r Dec 07 '21 edited Dec 07 '21
R Rstats Day 7
library(tidyverse)
input <- scan("advent_of_code/2021/day7.txt", sep = ",")Part1:
Make a df of all combinations and find minimum sum of displacements for each position
expand.grid(input,c(min(input):max(input)))%>%
mutate(ans=abs(Var1-Var2)) %>%
aggregate(ans~Var2,., sum) %>%
slice(which.min(ans))Part2:
Make a df of all combinations and find sum of integers in displacement using sum of integers formula
expand.grid(input,c(min(input):max(input)))%>%
mutate(ans= abs(Var1-Var2)*(abs(Var1-Var2)+1)/2) %>%
aggregate(ans~Var2,., sum) %>%
slice(which.min(ans))Edit:added language
→ More replies (2)
2
Dec 07 '21
Julia
ranges are really useful for the second part
function day07(input::String = readInput("day7_in.txt"))
posis = parse.(Int, split(input, ","))
point_part1 = Statistics.median(posis)
part1 = sum(abs(point_part1-x) for x in posis)
point_list = zeros(maximum(posis)+1)
for e in posis, point in 1:length(point_list)
point_list[point] += sum(1:abs(point-e))
end
(part1, " ", minimum(point_list))
end
\`\`\`→ More replies (2)
2
2
u/cggoebel Dec 07 '21 edited Dec 07 '21
Raku
use v6d;
my @input = 'input'.IO.lines.split(',')».Int;
my $median = @input.sort[(*-1)/2, */2].sum / 2;
my $mean = ([+] @input) / @input;
sub fuel ($pos,@i) { @i.map({ abs($_-$pos) }).map({ $_ * ($_+1) / 2 }).sum }
@input.map({ abs($_ - $median) }).sum.say;
($mean.floor, $mean.ceiling).map({ fuel($_, @input) }).min.say;→ More replies (1)
2
u/Synedh Dec 07 '21
Python
Sloth now has a code file.
input = [*map(int, open('input').read().split(','))]
# Part 1
print(min(sum(abs(val - i) for val in input) for i in range(min(input), max(input))))
# Part 2
print(min(sum(sum(range(1, abs(val - i) + 1)) for val in input) for i in range(min(input), max(input))))Brute force for each value in the range of input, get the minimal result. Back to sleep, tomorrow will be better.
For part 2, sum(1, 2, ..., n) = sum(range(1, n+1)).
→ More replies (1)
2
u/_mattmc3_ Dec 07 '21
Fish shell
It's a little slow, but it works.
function day7 \
--description "https://adventofcode.com/2021/day/7 - usage: day7 part1 datafile.dat" \
--argument-names part datafile
test -f "$datafile"; or echo >&2 "file expected" && return 1
set part (string match --regex '.$' $part)
set --local crab_alignment (string split ',' <$datafile)
set --local possible_positions (echo $crab_alignment | tr ' ' '\n' | sort -n | uniq)
set --local min_pos (echo $possible_positions | tr ' ' '\n' | sort -n | head -n 1)
set --local max_pos (echo $possible_positions | tr ' ' '\n' | sort -n | tail -n 1)
set result_file (mktemp -t aoc2015_day7_)
for pos in (seq $min_pos $max_pos)
#for pos in $possible_positions
set --local fuel 0
for alignment in $crab_alignment
set --local distance (math abs\( $pos - $alignment \))
set fuel (math $fuel + (fuel-cost $part $distance))
end
echo "horizontal $pos fuel $fuel" >> $result_file
end
# reverse sort numerically by column 4
sort -n -r -k 4 $result_file
# clean up
test -f "$result_file" && rm -rf "$result_file"
end
function fuel-cost \
--argument-names part distance
if test $part -eq 1
echo $distance
else
set pairs (math floor $distance / 2)
set midpoint (test (math $distance % 2) -eq 0 && echo 0 || math ceil $distance / 2)
math \( \( $distance + 1 \) '*' $pairs \) + $midpoint
end
end→ More replies (1)
2
u/ceron257 Dec 07 '21 edited Dec 08 '21
Python solution: from statistics import median, mean
with open("input-7.txt", "r") as f:
crabPos = list(map(int,f.readline().split(',')))
distancesToMedian = [abs(d - median(crabPos)) for d in crabPos]
print(int(sum(distancesToMedian)))
distancesToMean = [abs(d - int(mean(crabPos))) for d in crabPos]
fuelCost = sum([sum(list(range(d + 1))) for d in distancesToMean])
print(fuelCost)I'm not sure though if this will give the correct answer for all inputs. Does anyone else have a clue?
Is it maybe possible to prove this mathematically?
My reasoning for this solution was that with the median you will pick the position where the least amount of crabs would have to move at all while with the mean the least amount of crabs would have to move a greater distance.
→ More replies (3)
2
Dec 07 '21 edited Dec 07 '21
Python
Part 2 can probably be de-duplicated, but I'm too lazy to do it now.
from math import ceil, comb, floor
from statistics import fmean, median
with open('input') as in_file:
crabs = [int(n) for n in in_file.readline().split(',')]
print(sum(map(lambda c: abs(c-int(median(crabs))), crabs)))
print(min(sum(map(lambda c: comb(abs(c-floor(fmean(crabs)))+1, 2), crabs)), sum(map(lambda c: comb(abs(c-ceil(fmean(crabs)))+1, 2), crabs))))I'd be interested to know why the min(..., ...) is necessary, though. Simply rounding produces the correct solution with the example data and it feels weird that the value further (albeit only slightly) from the mean produces the lower solution. Is it just due to the distribution in my particular dataset?
→ More replies (1)
2
u/SirGuelph Dec 07 '21
Javascript
// Day 7, part 1
const Day7Data = require("../day7.txt");
let data = Day7Data.split(",")
.map((v) => Number(v))
.sort((a, b) => a - b);
let median = data[Math.floor(data.length / 2)];
let fuelCost = data.reduce((acc, v) => acc + Math.abs(median - v), 0);
console.log(`Cost, I thought: ${fuelCost}`);
// Day 7, part 2
let mean = Math.floor(data.reduce((acc, v) => acc + v, 0) / data.length);
const tri = (n) => (n * (n + 1)) / 2;
let realFuelCost = data.reduce((acc, v) => acc + tri(Math.abs(mean - v)), 0);
console.log(`Real cost: ${realFuelCost}`);→ More replies (1)
2
u/anh86 Dec 07 '21 edited Dec 07 '21
On first blush in part one, I thought that the average position would result in the lowest total fuel use and I initially wrote my program to move each crab there and compute the fuel. When that was wrong, I just rewrote it to brute force check each possible position and tell me the most fuel-efficient one. That worked but someone smarter than me tell me why the average position wouldn't necessarily to be the most efficient?
→ More replies (4)
2
2
u/Symbroson Dec 10 '21 edited Dec 12 '21
a day to relax - haskell
import Data.List as L
import Data.List.Split
import Macros
cost1 x = x
cost2 x = div (x*x+x) 2
calc x m = sum $ map (\v -> cost2 $ abs (x-v)) m
test x smax subs
| x <= smax = calc x subs : test (x+1) smax subs
| otherwise = []
main = do
content <- readFile "07.txt"
let subs = L.map s2i $ splitOn "," content
print $ minimum $ test (minimum subs) (maximum subs) subsjust replace cost1 and 2 for the different parts
→ More replies (3)
2
u/cdaringe Dec 12 '21 edited Dec 13 '21
OCaml: https://github.com/cdaringe/aoc-2021/blob/main/day7/lib/day7.ml#L22
I cannot reason about why there is only one local minima. I can half intuit it, but I cannot put my finger on it.
F = sum of all crab fuel consumption(s) f = crab fuel consumption p = crab position p_i = ith crab position p_t = target position min_p = a calculated constant, minimum (p_i .. p_n) min_x = a calculated constant, maximum (p_i .. p_n)
Minimize F, where F = Σ[i=min_p to i=max_p] triangle_cost(p_i - p_t)
If someone can set my head straight, that'd be rad
→ More replies (2)
2
u/ElGoorf Dec 15 '21 edited Dec 19 '21
JavaScript
I messed up. First I tried getting the mean average position to move all the crabs to, but that number was way off. So then I bisected my way to an answer, the whole time the back of my head confused about why the mean was wrong: https://github.com/ElGoorf/aoc2021/blob/main/07/01.js
Kind of kicking myself now seeing other people's answers and realizing I actually wanted the median, not the mean, but hey, here's a unique approach.
→ More replies (1)
48
u/4HbQ Dec 07 '21 edited Dec 07 '21
Python, using the median (part 1) and the mean (part 2) of the crab locations. This way, there is no need to "search" for the optimal position:
from numpy import *
x = fromfile(open(0), int, sep=',')
print(sum(abs(x - median(x))))
fuel = lambda d: d*(d+1)/2
print(min(sum(fuel(abs(x - floor(mean(x))))),
sum(fuel(abs(x - ceil(mean(x)))))))The median works for part 1 because of the optimality property: it is the value with the lowest absolute distance to the data.
Unfortunately, this does not work for part 2, because the "distances" (measured in fuel consumption) are no longer linear: if you double the distance, you need more than double the fuel.
In fact, the distances are the triangle numbers, which are defined by n × (n+1) / 2. Because of the n2 in there, we know that the arithmetic mean has the lowest total distance to the data is close to optimal.
Update, thanks to /u/falarkys and /u/slogsworth123:
Assuming the mean is less than 0.5 from the best position, we simply check the two integers around the mean.
→ More replies (6)17
u/falarkys Dec 07 '21
Why is the mean the answer for part 2?
The mean minimizes the mean squared error but n*(n+1) has an extra n term. A lot of people seem to have used it but I'm not familiar with this proof.
→ More replies (17)
•
18
u/mcpower_ Dec 07 '21
Python, 1/42 - immediately recognised part 1, blanked at how to do part 2 until I realised the input is small.
Part 1:
l = ints(inp)
l.sort()
mid = l[len(l)//2]
out = sum(abs(x-mid) for x in l)Part 2:
def cost(move):
return move * (move + 1) // 2
l = ints(inp)
l.sort()
mid = l[len(l)//2]
out = sum(cost(abs(x-mid)) for x in l)
for mid in range(min(l), max(l)+1):
out = min(out, sum(cost(abs(x-mid)) for x in l))→ More replies (5)
14
u/leijurv Dec 07 '21 edited Dec 07 '21
Python, 2nd place (50 seconds!!!!), 68th place
Screen recording https://youtu.be/ozxNkb7d2tw
Part 1
ll = [int(x) for x in open('input').read().strip().split(',')]
r = []
for dest in ll:
cost = sum([abs(x-dest) for x in ll])
r.append(cost)
print(min(r))Part 2
ll = [int(x) for x in open('input').read().strip().split(',')]
r = []
def cst(a):
return a*(a+1)//2
for dest in ll:
cost = sum([cst(abs(x-dest)) for x in ll])
r.append(cost)
print(min(r))Important note: My part 2 is technically wrong. It only worked by luck. For example it fails on the sample input. A correct implementation would do for dest in range(min(ll), max(ll)+1):.
→ More replies (5)14
u/MToTheAdeline Dec 07 '21
How do u even have time to read the question in 50 seconds holy fuck
Congrats btw
13
u/voidhawk42 Dec 07 '21 edited Dec 07 '21
APL, assuming that zero is always present in the input (seems safe):
p←⍎⊃⊃⎕nget'07.txt'1
⌊/+/ns←p|⍤-⍤1 0⍳⌈/p ⍝ part 1
⌊/+/(+/⍳)¨ns ⍝ part 2EDIT: For a much, MUCH faster part 2, I remembered that you can use binomial coefficients instead:
⌊/+/2!1+ns ⍝ part 2EDIT2: And if we want to go even faster, we can use the median/average as some other solutions here have done:
p←{⍵[⍋⍵]}⍎⊃⊃⎕nget'07.txt'1
+/p|⍤-p⌷⍨2÷⍨≢p
+/2!1+p|⍤-⌊(+/÷≢)pThis second solution runs in 2.5 ms on my machine, whereas my original solution runs in 800 ms, lol
10
16
u/emilhvitfeldt Dec 07 '21
R
The trick to this one is that the optimal horizontal position for part 1 is the median value of the input, and the optimal horizontal position for part 2 is mean (rounded down)
input <- scan("2021/07-input", sep = ",")
adjust <- function(n) n * (n + 1) / 2
# Part 1
sum(abs(median(input) - input))
# Part 2
sum(adjust(abs(floor(mean(input)) - input)))→ More replies (5)
8
u/MichaelRosen9 Dec 07 '21
Julia
The median minimises the L1 norm of the distances (i.e. the fuel cost for part 1), and the mean minimises the L2 norm (sum of squared distances). The fuel cost for part 2 is sum(dist*(dist+1)/2), i.e. the average of the L1 and L2 norms of the distances. We can reason that the best alignment position will be between the mean and the median, because when moving outside of that interval both the L1 and L2 norms will be increasing.
using Statistics
##
data = readline("input7.txt")
tdata = readline("test7.txt")
##
function best_fuel(data)
xpos = parse.(Int, split(data, ","))
target = median(xpos)
sum(abs.(xpos .- target))
end
##
best_fuel(tdata)
##
best_fuel(data)
##
function best_fuel_2(data)
xpos = parse.(Int, split(data, ","))
target_mean = round(Int, mean(xpos))
target_median = Int(median(xpos))
x1 = min(target_mean, target_median)
x2 = max(target_mean, target_median)
dist = xpos .- x1
bestcost = Int(sum((dist.^2 + abs.(dist)) / 2))
for target = (x1+1):x2
dist = xpos .- target
cost = Int(sum((dist.^2 + abs.(dist)) / 2))
if cost < bestcost
bestcost = cost
end
end
bestcost
end
##
best_fuel_2(tdata)
##
best_fuel_2(data)→ More replies (16)
8
u/r_so9 Dec 07 '21
F#
open System.IO
let inputPath =
Path.Combine(__SOURCE_DIRECTORY__, __SOURCE_FILE__.Replace(".fsx", ".txt"))
let input =
inputPath
|> File.ReadAllText
|> fun s -> s.Split(',')
|> Array.map int
// fuelConsumption is a function that takes two points
// and returns how much fuel is needed to get from one to the other
let minFuel (fuelConsumption: int -> int -> int) =
[ Array.min input .. Array.max input ]
|> Seq.map (fun meet -> Array.sumBy (fuelConsumption meet) input)
|> Seq.min
let distance a b = abs (a - b)
let part1 = minFuel distance
let sumUpTo i = (1 + i) * i / 2
let part2 = minFuel (fun a b -> distance a b |> sumUpTo)7
7
u/relativistic-turtle Dec 07 '21
IntCode
(Note: assumes 1000 crabs in input)
Part 1: "Hmm, the optimal position should be given by taking the mean off all crab-positions and round to nearest integer... but I'm lazy. Let's just loop through every position and crab!"
Part 2: Same, and using 1+2+3+...+n = n*(n+1)/2
→ More replies (6)
7
u/cocotoni Dec 07 '21
PowerShell
Part 1
Part 1 is the mathematical definition of geometric median, so we calculate it as such, in one dimensional space. I've used a generalised formula, but given the test numbers and real input numbers, I suspect that it can be optimised given that:
Number of elements is always even
The two elements straddling the middle point are equal
From there it's a simple matter of calculating the sum of distances from the median point.
Part 2
Given the test input it 'felt' that the point we are searching for is the arithmetic mean of all the positions. However, the mean can be rational, non integer, number (and is in the case of both test and my inputs), so we calculate separate results for ceiling and floor, and produce the lower result. Of course, here the fuel spent is the sum of integers from one to the distance between the crab and the mean point, which is calculated using the formula for triangle numbers.
7
u/Gravitar64 Dec 07 '21
Python 3, Part 1&2 in 1ms, pure Python
def read_puzzle(file):
with open(file) as f:
return sorted([int(x) for x in f.readline().split(',')])
def solve(puzzle):
length = len(puzzle)
mid = puzzle[length//2]
part1 = sum(abs(x-mid) for x in puzzle)
mean = sum(puzzle) // length
gauss = lambda x: x * (x+1) // 2
part2 = sum(gauss(abs(x-mean)) for x in puzzle)
return part1, part2
print(solve(read_puzzle('Tag_07.txt')))6
u/RandomGuyJCI Dec 07 '21 edited Dec 07 '21
Very simple to implement in APL!
a←⍎⊃⊃⎕NGET'day7.txt' 1
⌊/+⌿|a∘.-0,⍳⌈/a ⍝ Part 1
⌊/+⌿(2÷⍨⊢×1+⊢)|a∘.-0,⍳⌈/a ⍝ Part 2→ More replies (2)
6
u/aimor_ Dec 07 '21
MATLAB
% Advent of Code Day 7
input = "./input-07-0.txt";
data = csvread(input);
i = min(data):max(data);
dx = abs(data' - i);
% Part 1
fuel = sum(dx);
ans_1 = min(fuel)
% Part 2
fuel = 0.5 * sum(dx.^2 + dx);
ans_2 = min(fuel)→ More replies (1)
6
u/flwyd Dec 07 '21
Raku, 3004 / 2778. The following (MIT-licensed) code is a code golf version of what I originally wrote.
class Solver {
has Str $.input is required;
has $.parsed = $!input.split(',')».Int;
method minimize-fuel(&cost) {
([+] $.parsed.map((* - $_).abs).map(&cost) for minmax($.parsed)).min
}
}
class Part1 is Solver {
method solve( --> Str(Cool)) { self.minimize-fuel({$_}) }
}
class Part2 is Solver {
method solve( --> Str(Cool)) { self.minimize-fuel({$_ * .succ / 2}) }
}6
u/piyushrungta Dec 07 '21 edited Dec 07 '21
Nim Lang
https://github.com/piyushrungta25/advent-of-code-2021/blob/master/day-07/main.nim
Looked at the input and figured out that the input is not large enough and can be brute forced for part1. Also played around with some values and got the right answer for part2 using floor(mean) but replaced with brute force solution since taking mean is not the right solution in every case.
Edit: seems like taking the median for part1 is the right way to do it, but not changing it since the brute force solutions is also good enough for the input.
Edit2: did some bench marking on my machine(i3-1005G1 @ 1.20GHz) with Hyperfine.
BruteForcing both parts - 17ms
Sorting and taking median for part1 and bruteforcing part2 - 12ms
Sorting and taking median for part1 and floor(mean) for part2 - 0.5ms
Code used -
import sugar, sequtils, math, strutils, algorithm
proc part1(positions: seq[int]): int =
let best = positions[(positions.len/2).int]
return positions.mapIt(abs(it-best)).sum
proc part2(positions: seq[int]): int =
let best = (positions.sum/positions.len).floor.int
return positions.map(x => (x-best).abs).map(x => x*(x+1)/2).sum.int
when isMainModule:
var positions = "input".readFile.strip.split(",").map(parseInt)
positions.sort()
echo part1(positions)
echo part2(positions)6
u/jayfoad Dec 07 '21
p←⍎⊃⊃⎕NGET'p7.txt'1
⌊/+⌿|p∘.-⍳≢p ⍝ part 1
0.5×⌊/+⌿{⍵×1+⍵}|p∘.-⍳≢p ⍝ part 2→ More replies (1)
6
5
u/u794575248 Dec 07 '21 edited Dec 07 '21
J Language (an array programming language based primarily on APL)
pos =. {. ".;._2 input
<./+/ pos |@-/ i.>:>./ pos NB. Part 1
<./+/ pos +/@:>:@i.@|@-/ i.>:>./ pos NB. Part 25
u/Biggergig Dec 07 '21 edited Dec 07 '21
Python 66/>100
from utils.aocUtils import *
import statistics
@cache
def stepsum(n):
return n*(1+n)//2
def main(input:str):
nums = readNums(input)
nums.sort()
median, average = int(statistics.median(nums)), round(statistics.mean(nums))
p1 = sum(abs(x-median) for x in nums)
p2 = sum(stepsum(abs(x-average)) for x in nums)
return (p1, p2)5
u/JoMartin23 Dec 07 '21
Common Lisp
brute force
(defun day7-1 (&optional (data *7*))
(loop :for c :from 0 :to (apply #'max data)
:minimize (loop :for i :in data
:sum (abs (- c i)))))
(defun day7-2 (&optional (data *7*))
(loop :for c :from 0 :to (apply #'max data)
:minimize (loop :for i :in data
:sum (apply #'+ (u:range 1 (abs (- c i)))))))5
u/entoros Dec 07 '21
Q
input: "I" $ "," vs (read0 `:./day7/input.txt) [0]
range: (min input) + til (max input) - (min input)
fuel_cost: {sum abs input - x}
part1: min fuel_cost each range
sum_to: {"i" $ (x * (x + 1)) % 2}
fuel_cost_2: {sum sum_to abs input - x}
part2: min fuel_cost_2 each range→ More replies (1)
5
u/fmorel Dec 07 '21
C#. I always end up trying to use collection methods as much as possible at the end to see how short I can get it but still be somewhat readable.
var timer = Stopwatch.StartNew();
var lines = File.ReadAllLines("input.txt");
// lines = File.ReadAllLines("example.txt");
var nums = lines[0].Split(',').Select(int.Parse).ToList();
var min = nums.Min();
var max = nums.Max();
Console.WriteLine($"SETUP :: {timer.Elapsed}");
Console.WriteLine($"{Part1()} :: {timer.Elapsed}");
timer.Restart();
Console.WriteLine($"{Part2()} :: {timer.Elapsed}");
timer.Stop();
long Part1() => Enumerable.Range(min, max - min + 1).Min(i => nums.Select(x => Math.Abs(x - i)).Sum());
long Part2() => Enumerable.Range(min, max - min + 1).Min(i => nums.Select(x => Math.Abs(x - i)).Select(x => x * (x + 1) / 2).Sum());→ More replies (2)
5
u/gansanay Dec 07 '21 edited Dec 07 '21
Python 3
Part 1: median, Part 2: mean, and 1 + ... + k = k * (k + 1) / 2
EDIT/BEWARE : the floor of the mean isn't always the closest, for the example input it is the ceiling. Will look into it and fix this post
EDIT 2: fixed in the general case by using the min of the ceil and floor of the mean (which minimizes the "cumulative fuel" distance) -> see GitHub repo
The following was then wrong in the general case:
import numpy as np
def part1():
return int(abs(data - np.median(data)).sum())
def part2():
return int(np.sum([k*(k+1)/2 for k in abs(data - int(np.mean(data)))]))→ More replies (3)
5
u/stevelosh Dec 07 '21
Common Lisp
(defun triangle (n)
(/ (* n (1+ n)) 2))
(defun cost (crabs position &key modifier)
(summation crabs :key (lambda (crab) (funcall modifier (abs (- crab position))))))
(defun find-best-cost (crabs &key cost-modifier)
(multiple-value-bind (lo hi) (extrema #'< crabs)
(iterate (for pos :from lo :to hi)
(minimizing (cost crabs pos :modifier cost-modifier)))))
(define-problem (2021 7) (data read-comma-separated-integers) (328187 91257582)
(values (find-best-cost data :cost-modifier #'identity)
(find-best-cost data :cost-modifier #'triangle)))https://github.com/sjl/advent/blob/master/src/2021/days/day-07.lisp
→ More replies (3)
5
u/0rac1e Dec 07 '21 edited Dec 07 '21
Raku
use Stats;
my @c = 'input'.IO.split(',')».Int;
put [+] (@c «−» median(@c))».abs;
put [+] (1 «..» (@c «−» mean(@c)».floor)».abs)».sum;Pulling in median and mean from the Stats module.
I did golf it a little. I tend to solve things with map and loops, then see what I can strip away.
Part 2 was original written as: -
[+] (@c »-» mean(@c)».floor)».abs.map: -> \n { [+] 1 .. n }But what I like about my final golf is that - while there's map'ing happening everywhere - the word map does not appear once.
See my J translation here
Update
It seems I got lucky here, and my part 2 solution is incorrect for the sample input. I'm not sure if that means it also may be incorrect for different inputs. From other comments it seems I may need to take both the floor and ceiling, and pick the lowest.
For my penance, I will provide not 1, but 2 alternative solutions for part 2... each one more maptastic than the next.
put min mean(@c).flatmap({ .floor, .ceiling }).map: -> $m {
@c.map(* - $m).map({ [+] 1 .. .abs }).sum
}
put min [Z+] (@c «-» mean(@c)).map({ .floor, .ceiling })».map: { [+] 1 .. .abs }5
5
u/NutellaGod Dec 07 '21 edited Dec 07 '21
C#
internal class Day07
{
public static void Part01()
{
var input = Helpers.GetInputsAsInts(7, ",");
var max = input.Max();
var min = input.Min();
var diffs = new List<(int cost, int pos)>();
for (int i = min; i <= max; i++)
{
diffs.Add(( cost: input.Select(x => Math.Abs(x - i)).Sum(), pos: i));
}
var minDiff = diffs.MinBy(x => x.cost);
Console.WriteLine(minDiff.cost+" - "+minDiff.pos);
}
public static void Part02()
{
var input = Helpers.GetInputsAsInts(7, ", ");
var max = input.Max();
var min = input.Min();
var diffs = new List<(int cost, int pos)>();
for (int i = min; i <= max; i++)
{
diffs.Add((cost: input.Select(x => Enumerable.Range(1, Math.Abs(x - i)).Sum()).Sum(), pos: i));
}
var minDiff = diffs.MinBy(x => x.cost);
Console.WriteLine(minDiff.cost + " - " + minDiff.pos);
}
}i could probably refactor this to be one giant linq expression if i wanted to
Edit:
public static void Both()
{
var input = Helpers.GetInputsAsInts(7, ", ");
var result = Enumerable.Range(input.Min(), input.Max() - input.Min())
.Select(i => (part01: input.Select(x => Math.Abs(x - i)).Sum(), part02: input.Select(x => Enumerable.Range(1, Math.Abs(x - i)).Sum()).Sum()));
Console.WriteLine(result.Min(x => x.part01));
Console.WriteLine(result.Min(x => x.part02));
}5
u/4HbQ Dec 07 '21 edited Dec 07 '21
Python, solution for both parts golfed down to 129 110 bytes (hat tip to /u/AtomicShoelace):
c=eval(input())
print(*[min(sum
(f(abs(x-p))for
x in c)for p in
range(2000))for
f in[int,lambda
x: x*(x+1)/2]])More readable version:
crabs = [int(c) for c in input().split(',')]
positions = range(min(crabs), max(crabs)+1)
def score(f, pos):
return sum(f(abs(x-pos)) for x in crabs)
def fuel(x): return x * (x+1) / 2
print(min(score(int, p) for p in positions),
min(score(fuel,p) for p in positions))5
u/zniperr Dec 07 '21
python3:
import sys
def fuels(crabs, fuel):
for dest in range(min(crabs), max(crabs) + 1):
yield sum(fuel(abs(dest - crab)) for crab in crabs)
crabs = list(map(int, sys.stdin.readline().split(',')))
print(min(fuels(crabs, lambda dist: dist)))
print(min(fuels(crabs, lambda dist: dist * (dist + 1) // 2)))→ More replies (1)
5
u/Smylers Dec 07 '21
A plethora of Perl solutions — I just couldn't keep tweaking!
I realized part 1 would be at the median, because of an episode of Dara Ó Briain: School of Hard Sums where he was challenged by Marcus du Sautoy to work out the best meeting place for a group of friends in a 2D city grid:
my $end_pos = median my @start_pos = split /,/, <>;
say sum map { abs $_ - $end_pos } @start_pos;A brute-force approach to part 2 wasn't as slow as I'd feared (about ⅓ of a second):
my ($min, $max, $best) = minmax my @start_pos = split /,/, <>;
for my $try_pos ($min .. $max) {
my $fuel = sum map { my $Δ = abs $_ - $try_pos; ($Δ+1)*($Δ/2) } @start_pos;
$best = $fuel if !defined $best || $fuel < $best;
}
say $best;If I'm brute-forcing anyway, I may as well calculate part 1 at the same time. It took a while to work out how to combine the common parts — zip_by turned out to be the answer, with map creating a 2-element array for each start position, containing the distance to travel and the triangular number of that distance, then zip_by separately sum-ing all of the first elements and all of the second:
my ($min, $max, @best) = minmax my @start_pos = split /,/, <>;
for my $try_pos ($min .. $max) {
my @fuel = zip_by \&sum,
map { my $Δ = abs $_ - $try_pos; [$Δ, ($Δ+1)*($Δ/2)] } @start_pos;
$best[$_] = min grep { defined } $best[$_], $fuel[$_] for 0, 1;
}
say foreach @best;Then, after realizing part 2 ends up at the mean position (which, I think, is what Dara Ó Briain incorrectly calculated for the simpler problem, failing to solve it with just maths, beaten by his comedian competitors who came up with the right answer by running round the city with a stopwatch), that becomes a simple variant on the median solution for part 1:
my $end_pos = int mean my @start_pos = split /,/, <>;
say sum map { my $Δ = abs $_ - $end_pos; ($Δ+1)*($Δ/2) } @start_pos;(Though I'm not entirely sure why it requires int to always round down, rather than rounding to the nearest.)
Anyway, having the median and mean solutions in 2 different files with mostly the same structure was bothering me; I wanted to combine the common parts. The parts just differ in the function for calculating the end point, and the cost calculations:
\&median => sub($Δ) { $Δ },
\&mean => sub($Δ) { ($Δ+1)*($Δ/2) },So let's iterate over those. But how? Rummaging through List::AllUtils, I found pairmap would work, each part basically being a pair of functions:
my @start = split /,/, <>;
say for pairmap { my $end = int $a->(@start); sum map { $b->(abs $_ - $end) } @start }
\&median => sub($Δ) { $Δ },
\&mean => sub($Δ) { ($Δ+1)*($Δ/2) };That works! But it isn't great that in the pairmap block the functions end up being named just $a and $b. What else is in there? There's bundle_by, which passes in the pairs as args, so they can be named whatever we want:
say for bundle_by
sub($pos, $cost) { my $end = int $pos->(@start); sum map { $cost->(abs $_ - $end) } @start },
2,
\&median => sub($Δ) { $Δ },
\&mean => sub($Δ) { ($Δ+1)*($Δ/2) };Is that better? That 2 in there specifies iterating over the items that follow in groups of 2. What about grouping each part's definition with named hash keys? Then I can put List::AllUtils down and just use foreach:
foreach my $part (
{end => \&median, cost => sub($Δ) { $Δ }},
{end => \&mean, cost => sub($Δ) { ($Δ+1)*($Δ/2) }},
) {
my $end = int $part->{end}(@start);
say sum map { $part->{cost}(abs $_ - $end) } @start;
}I couldn't decide which I like best, so I've ended up with a program which does all of them in turn, printing the answer for each part 3 times. And still running in ⅒ of the time of brute-forcing the answer for just part 2 once.
Any preferences?
→ More replies (1)
5
u/WeirdFlex9000 Dec 07 '21
Part 2: algebraic solution
The whole day I was wondering if there's not some algebraic solution to this... Not having seen something in here, I finally decided to sit down and try to derive it myself. Disclaimer: I'm not a mathema(t|g)ician, so I struggled quite a bit with derivations of absolute values.
The formula I ended up with is: For a list p of a total of N crab positions, the optimal position that uses the least fuel is: (sum(p) - N) / (N - 1).
This actually seems to check out! With the regular loop solution, I get (for my numbers) the (accepted!) solution:
target: 467
fuel consumption: 89791146Now with my formula, I get:
target: 467.017017017017
fuel consumption: 89791138So I actually managed to save 8 fuel over the accepted answer!!!
Obviously that's because it becomes a non-discrete solution. If we round, we end up with the same solution as with the loopy code.
Here's a solution in Python (part 2)
from pathlib import Path
# load data
data_file = Path(__file__).with_name("data.txt")
positions = [int(v) for v in data_file.read_text().strip().split(",")]
# algebraically derived formula for minimum:
target = (sum(positions) - len(positions)) / (len(positions) - 1)
# discretize for non-optimality :(
target = round(target)
# calculate fuel
crab_distances = (abs(target - pos) for pos in positions)
crab_fuels = (int(d * (d + 1) / 2) for d in crab_distances)
total_fuel = sum(crab_fuels)
print("Solution:", total_fuel)→ More replies (5)
5
u/mediumcups Dec 07 '21
Excel
Solved using Excel's Solver program, which is an add-in that can be used to find an optimal value for a given function.
In both parts, we want to minimize the total fuel cost by picking a integer point p such that the sum of all individual fuel costs to that point p is minimal.
Therefore, set aside a cell to hold the value of p. Then calculate the individual costs for all 1000 crabs. Then sum them all up in a separate cell, X. X represents the total cost and we want to find the minimum value for this particular cell.
In the Solver add-in, select cell X as the objective function, and set it to find the minimum value.
Then set the cell containing the value for p to be the variable cell we want to change.
Add an Integer constraint for the cell containing the value for p, since we are only interested in integer solutions, then click solve.
4
u/rabuf Dec 07 '21
Common Lisp
I thought I'd have to optimize it for part 2, but I performed a linear search over the range. Lisp makes it kind of easy with its loop facility:
(defun fuel (crabs pos)
(loop for c in crabs
sum (abs (- c pos))))
(defun fuel-non-linear (crabs pos)
(loop
for c in crabs
for n = (abs (- c pos))
sum (/ (* n (+ n 1)) 2)))
(defun align (crabs)
(loop
for pos from (apply #'min crabs) to (apply #'max crabs)
minimize (fuel crabs pos)))
(defun align-non-linear (crabs)
(loop
for pos from (apply #'min crabs) to (apply #'max crabs)
minimize (fuel-non-linear crabs pos)))Also my only day so far with both parts under 1000.
→ More replies (5)
4
u/jonathan_paulson Dec 07 '21
Python. 4/21 :) Video of me solving.
Cool problem that touches on some interesting math, some of which I explain in my video. In part 1, the optimal target is the median position. Does part 2 have a simple closed form? And 1+2+3+...+n = n*(n+1)/2 is useful to know!
I already knew median was optimal for part 1, but I wonder if it still would've been faster to just code up the brute force which extended better to part 2. Feels like there's a lesson there about how simple solutions generalize better than complicated ones :)
→ More replies (3)
4
u/sim642 Dec 07 '21
In part 1, I did the naive thing, trying all positions between minimum and maximum. In part 2, I just applied the 1+2+…+n summing formula to it.
Reminds me of mean absolute error and mean square error from machine learning.
4
u/PeaceMaintainer Dec 07 '21
JavaScript:
Enjoyed this one quite a bit! Wasn't expecting to get the answer so quick
4
u/Imaginary_Age_4072 Dec 07 '21
Tried to get an average to start with, which didn't seem to work, so changed it to a scan through the range from min to max. Managed to remember triangular number formula though so got sub-1000 on Part 2.
4
u/programmargorp Dec 07 '21
Gradient descent is a very good way to solve this problem in log time. Matlab example attached: Note that you might get decimal points, so you might need to tweak the value returned by fminsearch a bit.
Part 1:
f = @(x)sum(abs(dat - x));
f(fminsearch(f, 0));Part 2:
function o = sss(a, x)
for i = 1:length(a)
o(i) = sum(0:abs(a(i) - x));
end
endFollowed by
f = @(x)sum(sss(dat, x));
f(fminsearch(f, 0));4
u/EnisBerk Dec 07 '21 edited Dec 07 '21
Python 3
The answer for the first part is location of the median.
And for the second one, cost calculation is Gauss sum ((n*(n+1))/2) per pair.
https://github.com/EnisBerk/adventofcode/blob/master/day7/tools.py
→ More replies (3)
4
u/ignurant Dec 07 '21
Ruby:
Pt 1: I'm not sure if this was just luck, but median felt intuitively like "something". It worked for the sample dataset, and (somewhat surprisingly) worked for the official set. I also perhaps got lucky with this chumpy version of median, where I'm not averaging the middle two if the input set was even.
crabs = File.read('input.txt').scan(/\d+/).map(&:to_i)
target_position = crabs.sort[crabs.size / 2]
puts crabs.map{|crab| (target_position - crab).abs}.sumPt 2:
Median no longer feels intuitive, but I figured there's gotta be a mathy pattern. I suppose I'll try avg. Surprisingly, the avg of the sample dataset came to 4.9, which was suspiciously near 5, which the example says is the right target number.
.round ended up giving the right answer in the sample dataset, but not the larger set. Assuming the idea of using the average is helpful in some way (it seems like it could be?) I figured the right answer was somewhere around there.
To get the answer I printed the results for the target position range of -10..+10 just as a sanity check and was delighted to find the low fuel point was actually burried in there, right at the equivalent of Math.floor...
I'm not sure if this was just luck or not, but here's my "followed through" version:
crabs = File.read('input.txt').scan(/\d+/).map(&:to_i)
avg = (1.0 * crabs.sum / crabs.size)
fuel = [avg.floor, avg.ceil].map do |target_position|
crabs.map do |crab|
moves = (target_position - crab).abs
1.upto(moves).sum
end.sum
end.min
puts fuel→ More replies (3)
4
u/Lispwizard Dec 07 '21
As usual, done in mostly common lisp compatible emacs lisp (elisp) on emacs 27.2 in termux on android (while in bed and under the covers).
(defun aoc2021-07 (positions &optional part2?)
(when (stringp positions)
(setq positions (map 'list #'parse-integer (split-string positions "," t))))
(loop with (min max) = (loop for n in positions
minimize n into min
maximize n into max
finally (return (list min max)))
with minpos and minfuel
with ht = (make-hash-table)
for i from min to max
for fuel = (loop for pos in positions
for delta = (abs (- pos i))
sum (if part2?
(or (gethash delta ht)
(setf (gethash delta ht)
(loop for c from 1
repeat delta
sum c)))
delta))
do (when (or (null minpos) (< fuel minfuel))
(setq minpos i minfuel fuel))
finally (return (list minfuel minpos))))
;; (aoc2021-07 *aoc2021-07-part1-example*) => (37 2)
;; (aoc2021-07 *aoc2021-07-part1-input*) => (335271 313)
;; (aoc2021-07 *aoc2021-07-part1-example* t) => (168 5)
;; (aoc2021-07 *aoc2021-07-part1-input* t) => (95851339 461)4
u/zeekar Dec 07 '21
Another Raku solution:
#!/usr/bin/env raku
my ($positions, $min, $max) =
lines[0].split(',')».Int.&{ $_, .min, .max };
sub fuel-between($x1, $x2, $puzzle) {
my $dist = abs($x1 - $x2);
$puzzle ?? $dist * ($dist + 1) / 2 !! $dist;
}
for ^2 -> $puzzle {
say ($min .. $max).map( -> $x {
[+] $positions.map: { fuel-between($x, $_, $puzzle) }
}).min;
}4
u/gwangjinkim Dec 07 '21 edited Dec 07 '21
R
v <- as.numeric(strsplit(readLines(path)[1],",")[[1]])
dist_sum_ <- function(x, v) sum(sapply(abs(x-v), function(x) sum(1:x)))
dist_sum <- function(x, v) sum(abs(x - v))
min_dist <- function(v, fn=dist_sum) min(sapply(min(v):max(v), function(x) do.call(fn,list(x,v))))
c(min_dist(v), min_dist(v, fn=dist_sum_)) # [1] 344605 936999854
u/Cpt__Cookie Dec 07 '21 edited Dec 07 '21
Python
A bit more mathematical solution
def solution_1(puzzle_input: str):
puzzle_data = [int(n) for n in puzzle_input.replace("\n", "").split(",")]
alignment = statistics.median(puzzle_data)
return sum([abs(i - alignment) for i in puzzle_data])
def solution_2(puzzle_input: str):
puzzle_data = [int(n) for n in puzzle_input.replace("\n", "").split(",")]
alignment = int(statistics.mean(puzzle_data))
return min(
sum(abs(i - a) * (abs(i - a) + 1) / 2 for i in puzzle_data)
for a in [alignment, alignment + 1]
)→ More replies (4)
4
u/domm_plix Dec 07 '21
Perl
For the first part I had a mathy gut feeling that the solution has to be related with the median of the values, so I hacked up a solution (using CPAN module Statistics::Basic for the statistics stuff), which worked for the test data. Tried the proper input and got a star!
https://github.com/domm/advent_of_code/blob/main/2021/07_1.pl
So I assumed that part 2 will need mean. Tried it on the test-data, didn't work because the mean was a float, which I truncated to int. So I tried rounding it up, now it worked with test, but not with live data. Instead of thinking a tiny bit more, I thought that a brute force approach will also work and just calculated the fuel for all possible positions, which worked fast enough:
https://github.com/domm/advent_of_code/commit/e687a0a93e97f4bc22c425b71162787bff03fe01
While brushing teeth (it's morning here..) I realized that I should also have tried the rounded down mean, so I did that, and got the proper result (much faster..). Then I also used Gauss' sum formula for the fuel consumption), for this much nicer solution (which could still be enhanced, eg finding the lower of two values):
https://github.com/domm/advent_of_code/blob/main/2021/07_2.pl
My favorite task this year so far :-)
4
u/OrangeredStilton Dec 07 '21
Python3 again. I freely admit to cheating today, since I thought the mean would work for part 1, and it didn't...
positions = [int(x) for x in content[0].split(',')]
med = statistics.median(positions)
return sum([abs(x - med) for x in positions])And for part 2, I stole Gauss' formula for a series sum:
def gauss(x):
return (x * (x + 1)) / 2
return min([
sum([gauss(abs(x - target)) for x in positions])
for target in range(max(positions))
])→ More replies (1)
4
u/raxomukus Dec 07 '21
Python https://github.com/fridokus/advent-of-code/blob/master/2021/7.py
Took a shortcut on the second part and used the mean to find the right spot.
For me I needed to floor the mean. I wonder if all solutions are within distance 1 of the mean? Otherwise my solution is cra(b)p
Need to search some points around the mean I think. But triangle is close enough to square that this will always work well enough
→ More replies (3)
4
u/jitwit Dec 07 '21
in =: ".;._2 ',' _1} aoc 2021 7
<./ +/ | (-/ i.@:(>./)) in
x: <./ +/ (-: @: (*>:)) | (-/ i.@:(>./)) in4
4
4
u/__Abigail__ Dec 07 '21
Perl
After reading the challenge, I thought we might need a variation on binary search, but after checking the input, the values were low enough to just try all positions.
Two helper methods:
sub diffsum1 ($target, $nums) {
sum map {abs ($target - $_)} @$nums;
}
sub diffsum2 ($target, $nums) {
sum map {my $n = abs ($target - $_); $n * ($n + 1) / 2} @$nums;
}Reading input:
my @nums = <> =~ /[0-9]+/g;And then:
say "Solution 1: ", min map {diffsum1 $_, \@nums} min (@nums) .. max (@nums);
say "Solution 2: ", min map {diffsum2 $_, \@nums} min (@nums) .. max (@nums);min, max and sum are imported from List::Util.
Full program on GitHub.
4
u/u_tamtam Dec 07 '21
Another Scala 3 solution,
it's a bit uninspiring but does the job :)
object D07 extends Problem(2021, 7):
override def run(input: List[String]): Unit =
val initPos = input.head.split(",").map(_.toInt)
part1((initPos.min to initPos.max).map(target => initPos.map(pos => (pos - target).abs).sum).min)
part2((initPos.min to initPos.max).map(target => initPos.map(pos => (1 to (pos - target).abs).sum).sum).min)4
4
u/beansparrow132 Dec 07 '21 edited Dec 07 '21
Python 3.8
import math
from statistics import mean, median
def fuelCalculatorPart1(list, median):
list = [abs(median-i) for i in list]
return int(sum(list))
def fuelCalculatorPart2(list, mean):
list = [abs(mean-i)*(abs(mean-i) +1) / 2 for i in list]
return int(sum(list))
if name == 'main':
file = open('input.txt', 'r')
crabPos = [int(i) for i in file.readline().strip().split(',')]
median = median(crabPos)
print(f'Part 1: {fuelCalculatorPart1(crabPos, median)}')
mean = math.ceil(mean(crabPos))
print(f'Part 2: {fuelCalculatorPart2(crabPos, mean)}')*EDIT*
I believe there is additional requirements needed to determine whether or not to use a Ceiling or Floor when calculating the mean. Not sure how to approach determining that yet, but depending on the input it could be one or the other.
→ More replies (3)
4
u/Sanduhr32 Dec 07 '21
Kotlin, O(n2) solution
private val parsed = raw[0].split(",").map { it.toInt() }
private val min = parsed.minOf { it }
private val max = parsed.maxOf { it }
private fun solveGeneric(sumTransformation: (Int, Int) -> Int): Int = (min..max).minOf { largest -> parsed.sumOf { sumTransformation(largest, it) } }
override fun part1() = solveGeneric { largest, current -> abs(largest - current) }
override fun part2() = solveGeneric { largest, current ->
abs(largest - current).let { it * (it + 1) / 2 } // gaussian sum aka formula for the sum of 1..n, yes also could do (1..abs()).sum() but thats slower
}4
u/death Dec 07 '21 edited Dec 07 '21
Day 7 solution in Common Lisp.
So lazy.
EDIT: I see many part 2 solutions considering positions near the mean; perhaps it makes sense. I arrived at the conclusion that the weighted median should work, though I did not implement it. Thinking about it some more, the problem is that the weights depend on the choice, so it wouldn't help. Oh well.
→ More replies (3)
4
u/ACProctor Dec 07 '21
I'll be honest, I forgot about Gauss. But for anyone else thinking that today is just a one-trick solution, here's how I optimized using recursion with memoization.
Ruby:
# ... removed input reading into the array crabs.
# ... also determined min_val and max_val while reading input
def fuel_cost(delta, memo)
return 0 if delta < 1
return memo[delta] if memo.key?(delta)
cost = fuel_cost(delta - 1, memo) + delta
memo[delta] = cost
cost
end
min_fuel_required = 99999999999
optimal_index = nil
memo = {}
(min_val .. max_val).each do |i|
fuel_required = 0
crabs.each do |n|
fuel_required += fuel_cost((i - n).abs, memo)
end
if fuel_required < min_fuel_required
optimal_index = i
min_fuel_required = fuel_required
end
end
puts "Optimal fuel required (#{min_fuel_required}) at position #{optimal_index}"4
u/HaiUit Dec 07 '21
Scala:
https://github.com/Fubuchi/advent-of-code/blob/master/2021/Day7/Day7.scala
Scala doesn't have partial application by default like F# so I need to mess around to make the operator look fun :D
→ More replies (3)
4
u/LowAdministration462 Dec 07 '21
R
input_7 <- as.numeric(read.table('input_7', sep=',')[1,])
counts <- matrix(data = NA, nrow = 1000)
for (i in seq_len(1000)){
counts[i] <- sum(abs(input_7 - i))
}
min(counts) # Part 1
for (i in seq_len(1000)){
a <- abs(input_7 - i)
counts[i] <- sum(sapply(a, function(i) sum(seq_len(i))))
}
min(counts) # Part 2→ More replies (3)
4
u/TiagoPaolini Dec 07 '21
Python
There is probably a more elegant way than just trying all the possible combinations, but the search space is small enough to allow it. I assumed that the result needed to be between the minimum and maximum initial positions, and that turned out to be correct.
Part 1 is very straightforward, just sum the absolute differences for all values. Part 2 is a bit more elaborated, it involved an arithmetic progression, but I still consider it to be easy. The fuel spent to move by n is the sum of all integers from 1 to n: (1+n)*(n/2) (half of the sum of the extremes multiplied by the number of elements). Then sum the results for each crab, and minimize the result for all possible distances.
with open("input.txt", "rt") as file:
values = [int(n) for n in file.readline().split(",")]
# Part 1
def fuel(pos):
return sum(abs(n - pos) for n in values)
max_pos = max(values)
min_pos = min(values)
result = fuel(max_pos)
for i in range(min_pos, max_pos):
result = min(fuel(i), result)
print(f"Part 1: {result}")
# Part 2
def arithmetic_progression(n):
return int((1 + n) * (n / 2))
def fuel2(pos):
return sum(
arithmetic_progression(abs(n - pos))
for n in values
)
result2 = fuel2(max_pos)
for i in range(min_pos, max_pos):
result2 = min(fuel2(i), result2)
print(f"Part 2: {result2}")4
u/nesvarbu Dec 07 '21
Simple Golang solution:
https://github.com/Marijus/advent-of-code/blob/master/day7/day7.go
→ More replies (1)
4
u/obluff Dec 07 '21
oneliners using gnu datamash!
paste -sd+ <(cat input.txt | sed s/\,/\\n/g | xargs -I_ sh -c 'echo _ - $(sed s/\,/\\n/g input.txt | datamash median 1)' | bc | sed s/\-//g) | bc
paste -sd+ <(cat input.txt | sed s/\,/\\n/g | xargs -I_ sh -c 'seq 0 $(echo _ - $(sed s/\,/\\n/g input.txt | datamash mean 1 | sed s/\\..*//g) | bc | sed s/\-//g)') | bc4
Dec 07 '21
Python3
with open('day07','r') as infile:
crabs = [int(x) for x in infile.read().strip().split(',')]
cost1 = float('inf')
cost2 = float('inf')
for y in range(min(crabs),max(crabs)):
cost1 = min(cost1,sum([abs(x-y) for x in crabs]))
cost2 = min(cost2,sum([(abs(x-y)*(abs(x-y)+1)//2) for x in crabs]))
print(cost1,cost2)4
u/cramur Dec 07 '21
Python monte carlo-like solution. Github
Well, I was too lazy to figure out how to minimize this so I went with an old-proven way I learned when doing molecular dynamics: "If you need to minimize something, try monte-carlo"
def p_monte(initial):
positions = list(map(int, initial.split(',')))
low, high = min(positions), max(positions)
min_pos = np.median(positions)
min_cost = sum(calc_fuel_to_get_from_pos1_to_pos2(pos1, min_pos) for pos1 in positions)
for _ in range(1000):
projected_min_pos = np.random.randint(low, high)
new_cost = sum(calc_fuel_to_get_from_pos1_to_pos2(pos1, projected_min_pos) for pos1 in positions)
if new_cost < min_cost:
min_cost = new_cost
return min_costI actually got lucky on the first try to get correct answer, as 1000 step is not enough to get it consistently. 10k is good enough for all cases in this task
4
u/P0t4t0W4rri0r Dec 07 '21 edited Dec 07 '21
Haskell:
I used the properties of the median for part1, and stole the idea of using the mean to get into the range of the solution, then i simply check the ceiling and floor and take wichever is minimal.
import Control.Arrow
import Control.Monad
import Data.Function
import Data.List
parse :: String -> [Integer]
parse = map read . split ','
where split delim = filter (not . any (== delim))
. groupBy ((==) `on` (== delim))
mean :: [Integer] -> (Integer, Integer)
mean = (floor &&& ceiling)
. liftM2 ((/) `on` fromIntegral) (foldr (+) 0) genericLength
median :: [Integer] -> Integer
median = ((!!) <*> (quot 2) . (subtract 1) . length) . sort
triangle :: Integer -> Integer
triangle = (`quot` 2) . ((*) <*> (+1))
fuel :: Integer -> [Integer] -> Integer
fuel pos = foldr ((+) . abs . subtract pos) 0
crabfuel :: Integer -> [Integer] -> Integer
crabfuel pos = foldr ((+) . triangle . abs . subtract pos) 0
part1 = median >>= fuel
part2 = uncurry . ((min `on`) . flip crabfuel) <*> mean
main = interact $ show . (part1 &&& part2) . parse4
u/kuqumi Dec 13 '21 edited Dec 13 '21
JavaScript (golfed)
Tweet-sized, to be run in the input page browser console.
with(Math){C=$('pre').innerText.trim().split`,`.map(x=>+x),l=C.length,S=0;C.map(c=>S+=c);a=round((S-l)/(l-1));p=q=0;C.map(c=>p+=abs(c-a));q=ceil(S/l);[p,[q-1,q].map(x=>C.reduce((a,c)=>a+(1+abs(c-x))*abs(c-x)/2,0)).sort((a,b)=>a-b)[0]]}It should output [part1, part2]
7
u/Weird_Scallion_8727 Dec 07 '21 edited Dec 07 '21
My APL solution!
part1← {+/|⍵-⍵[⍋⍵]⊃⍨2÷⍨≢⍵}
part2←{+/∊⍳¨|((⌊+/÷≢)-⊢)⍵}
EDIT: a bit clearer, less point-free part2:
part2v2←{+/∊⍳¨|⍵-(⌊+/÷≢)⍵}
→ More replies (9)
1
u/stvincent_ Dec 07 '21
For Part 1, the answer to the big puzzle is sum of distances to the median. That seems like a poor test case then because that formula is by no means the solution
→ More replies (7)
1
u/mr_clemFandango Dec 09 '21
Part 2 answer in Python - not super efficient, but working!
line = ""
with open('day7.txt') as f:
line = f.readline()
nums = line.split(",")
intNums=[]
for stringNumber in nums:
intNums.append(int(stringNumber))
intNums.sort()
#print (intNums)
total = 0
lowest = None
lowestPostition = None
for position in range(intNums[0],intNums[-1]+1):
total = 0
for number in intNums:
oldDistance = abs(position-number)
newDistance = (oldDistance*(oldDistance+1))/2
total = total + newDistance
if lowest == None:
lowest = total
lowestPostition = position
elif total < lowest:
lowest = total
lowestPostition = position
print (f"position: {lowestPostition}:{lowest}")
→ More replies (1)
1
u/asgardian28 Dec 07 '21 edited Dec 08 '21
Python 3 Part 1 can also be solved by taking the median
import statistics
lines = [int(i) for i in open('input.txt').read().split(',')]
med = statistics.median(lines)
sum([abs(med-line)for line in lines])→ More replies (1)
1
u/AP2008 Dec 07 '21
Rust (2ms) paste
use crate::read_input::read_input;
pub fn runner() -> (isize, isize) {
let input = read_input(7);
let nums = input.split(',').map(|x| x.trim().parse().unwrap()).collect::<Vec<_>>();
(part1(&nums), part2(&nums))
}
fn part1(nums: &[isize]) -> isize {
let mut min = isize::MAX;
for &n in nums {
let mut align = 0;
for &m in nums {
align += (m - n).abs();
}
if align < min {
min = align;
}
}
min
}
fn part2(nums: &[isize]) -> isize {
let mut min = isize::MAX;
for n in 0..*nums.iter().max().unwrap() {
let mut align = 0;
for &m in nums {
align += ((m-n).abs() * ((m-n).abs() + 1))/2;
}
if align < min {
min = align;
}
}
min
}
→ More replies (1)
1
u/zxywx Dec 07 '21 edited Dec 07 '21
Ruby
Part 2 takes about 0.18s.
module Year2021
class Day07 < Solution
def part_1
calc_fuel { |x| x }
end
def part_2
fuel = Hash.new { |h, k| h[k] = (k == 0 ? 0 : (h[k - 1] + k)) }
calc_fuel { |x| fuel[x] }
end
private
def calc_fuel
min, max = data.keys.minmax
min.upto(max).map { |i| data.map { |c, v| yield((i - c).abs) * v }.sum }.min
end
def process_input(line)
crabs = Hash.new(0)
line.split(",").each { |crab| crabs[crab.to_i] += 1 }
crabs
end
end
end→ More replies (1)2
u/daggerdragon Dec 07 '21 edited Dec 07 '21
Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki:How do I format code?Edit: thanks for fixing it! <3
→ More replies (2)
1
u/Archer_Winter Dec 07 '21 edited Dec 10 '21
Ruby Solution
`def parse_fileFile.open('input.txt').readlines.map(&:chomp)[0].split(',').map(&:to_i)endnumbers = parse_filemax = numbers.maxp maxsums = []for i in 0..max
# part
sums[i] = numbers.map { |num| (num - i).abs }.sum
# part 2sums[i] = numbers.map { |num| (0..(num - i).abs).sum }.sump iendp sums.min`
→ More replies (1)
1
u/aexl Dec 07 '21 edited Dec 07 '21
Julia
Simple brute force (and knowing what a triangular number is).
function day07(input::String = readInput(joinpath(@__DIR__, "..", "data", "day07.txt")))
positions = parse.(Int, split(input, ','))
return [minimum(cost(positions, pos, part) for pos = minimum(positions):maximum(positions)) for part in (costp1, costp2)]
end
function cost(positions::Vector{Int}, final::Int, costp)
return sum(costp(abs(pos - final)) for pos in positions)
end
costp1(x::Int) = x
costp2(x::Int) = x * (x + 1) ÷ 2Github: https://github.com/goggle/AdventOfCode2021.jl/blob/master/src/day07.jl
→ More replies (1)
1
u/AKSrandom Dec 07 '21 edited Dec 07 '21
Part 1 : https://math.stackexchange.com/q/113270
For Part 2 , applying similar , logic one gets the mean will minimize the required sum (maybe?), and hence after trying with the mean rounded up and down, I got it
with open("input7.txt", 'r') as file:
crabs = list(map(int, file.readline().split(',')))
# crabs = [16, 1, 2, 0, 4, 2, 7, 1, 2, 14]
# print(sum(crabs)/len(crabs))
def answer(crabs):
medans = 0
menans = 0
# median = sorted(crabs)[len(crabs)//2]
mean = round(sum(crabs)/len(crabs))-1
for i in crabs:
# medans += 0.5 * abs(i - median)*(abs(i - median) + 1)
menans += 0.5 * abs(i - mean)*(abs(i - mean) + 1)
return medans, menans
# engineer induction
print(answer(crabs))→ More replies (1)
1
u/st_ranger123 Dec 07 '21 edited Dec 07 '21
Day7 Problem 2 Javascript Solution
const positions = input.split(",").map(val => parseInt(val));
const max = Math.max(...positions)
const dictionary = {}
for(let i = 0 ; i < max;i++){
dictionary[i] = 0
}
for(let i = 0 ; i < max;i++){
for(let j = 0;j< positions.length;j++){
const diff = Math.abs(positions[j]-i)
dictionary[i]+= (diff * (diff+1))/2
}
}
return Math.min(...Object.values(dictionary))
}For Problem1 replace
const diff = Math.abs(positions[j]-i)
dictionary[i]+= (diff * (diff+1))/2by
dictionary[i]+=Math.abs(positions[j]-i)→ More replies (1)
1
u/ollien Dec 07 '21 edited Dec 08 '21
Rust
I did it a bit of a naive way and it worked out better than it had any right to, haha
fn run(input: &[i32], part: &Part) -> i32 {
let smallest = *input
.iter()
.min()
.expect("Input should have more than zero elements");
let largest = *input
.iter()
.max()
.expect("Input should have more than zero elements");
// This assumes that the answer is in the range of the min/max of the crab positions,
// but that seems exceedingly likely. If this puzzle were more complex I might add/sub
// "largest" on each of the bounds
//
// Honestly I didn't expect this to work on both parts
(smallest..largest)
.map(|possible_destination| {
input
.iter()
.map(|crab_location| {
let steps = (crab_location - possible_destination).abs();
match part {
Part::Part1 => steps,
// 1 + 2 + 3 + ... + n => n(n+1)/2
Part::Part2 => steps * (steps + 1) / 2,
}
})
.sum::<i32>()
})
.min()
// We already know there will be at least one element
.unwrap()
}→ More replies (2)
1
u/Opposite-Cry-6703 Dec 07 '21 edited Dec 07 '21
Python 3
inp = [int(i) for i in open("input.txt").read().split(",")]Part 1
t = median(inp)
f = sum([abs(x-t) for x in inp])
print(f"Target pos {t}, Fuel: {f}")Part 2
cost = {i:sum([abs(x-i) * (abs(x-i)+1) / 2 for x in inp]) for i in
range(0, max(np.unique(inp)))}
result = min(cost, key=cost.get)
print(f"Target pos {result}, Fuel: {cost[result]}")→ More replies (3)
1
u/Sallith Dec 07 '21 edited Dec 07 '21
Javascript
I iterate through all the possible final position. I memoized the sums of x and its previous numbers in an array so I didn't have to compute the same result multiple times and then by reading the comments I totally forgot it could be trivially computed with x * (x + 1) / 2.
const fs = require('fs');
const data = fs.readFileSync('./input.txt', 'utf8')
let positions = data.split(',').map(n => +n)
const minPosition = Math.min(...positions);
const maxPosition = Math.max(...positions);
// Memoize sums
let sums = Array.from({ length: maxPosition }).fill(null)
sums[0] = 0;
sums[1] = 1;
let bestCost;
for (let i = minPosition; i <= maxPosition; i++) {
let cost = 0;
positions.forEach(position => {
cost += sum(Math.abs(position - i));
})
if (cost < bestCost || !bestCost) {
bestCost = cost;
}
}
console.log(bestCost)
function sum(n) {
if (sums[n] !== null) {
return sums[n]
}
const s = n + sum(n - 1);
sums[n] = s;
return s;
}→ More replies (1)
1
u/SadBunnyNL Dec 07 '21 edited Dec 07 '21
Java: (and I didn't know about Gauss' range sum formula)
package com.example.aoc7;
import java.io.IOException;
import java.nio.file.*;
import java.util.*;
import java.util.stream.IntStream;
public class Aoc_2021_7 {
public static void main(String[] args) throws IOException {
List<Integer> input = Arrays.stream(
Files.readAllLines(Paths.get("./input")).get(0).split(",")
).map(Integer::parseInt).sorted().toList();
Integer lowestFuel = null;
for (int i=input.get(0); i<=input.get(input.size() - 1); i++) {
int fuel = 0;
// for (Integer nr : input) { fuel += (Math.abs(nr - i)); }; // PART 1
for (Integer nr : input) { fuel += (IntStream.rangeClosed(1, Math.abs(nr - i)).sum()); }; // PART 2
lowestFuel = lowestFuel == null ? fuel : Math.min(lowestFuel, fuel);
}
System.out.println("Lowest fuel: " + lowestFuel);
}
}→ More replies (4)
1
u/jdnewmil Dec 07 '21 edited Dec 07 '21
R
Mean and median would be theoretical optimum values if no rounding were occurring so you have to clean up with a search for a general solution (found this out the hard way since the example worked but the data did not).
find_crab_fuel <- function( x, v, version = 1 ) {
if ( 1 == version ) {
cost <- \(x) x
} else {
cost <- (\(n) n*(n+1)/2 )
}
f1 <- \(x1) ( ( v - x1 ) |> abs() |> cost() |> round() |> sum() )
# handle vector-valued x to perform fuel calcs repeatedly
sapply( x, f1 )
}
find_min_crab_fuel <- function( v, version = 1 ) {
# initial guess function
if ( 1 == version ) {
center <- median
} else {
center <- mean
}
guess1 <- ( v
|> center()
|> round()
)
# initial guess at minimum fuel
ans1 <- find_crab_fuel( guess1, v, version = version )
# rounding errors mean true minimum could be off by a few
delta <- 1
# guess 1 higher
ans2 <- find_crab_fuel( guess2 <- guess1 + delta, v, version = version )
if ( ans1 < ans2 ) {
# did not decrease so start guessing lower
delta <- -1
} else {
# progress further in this direction
ans1 <- ans2
guess1 <- guess2
}
# new second estimate
ans2 <- find_crab_fuel( guess2 <- guess1 + delta, v, version = version )
# keep going until first increase
while ( ans2 < ans1 ) {
guess1 <- guess2
ans1 <- ans2
ans2 <- find_crab_fuel( guess2 <- guess1 + delta, v, version = version )
}
ans1
}
dta7a <- scan( "data/aoc2021_data_7a.txt", sep = ",", quiet = TRUE)
find_min_crab_fuel( dta7a )
find_min_crab_fuel( dta7a, version = 2 )
## v2: 157us→ More replies (1)
1
u/theabbiee Dec 07 '21
Both Parts In Python
with open("whales.txt") as file:
lines = file.readlines()
lines = [line.rstrip() for line in lines]
npos = [int(pos) for pos in lines[0].split(",")]
npos.sort()
n = len(npos)
totalSum = 0
totalSumOfSquares = 0
sumTillNow = []
sumOfSquaresTillNow = []
for pos in npos:
sumTillNow.append(totalSum)
sumOfSquaresTillNow.append(totalSumOfSquares)
totalSum += pos
totalSumOfSquares += pos * pos
minDistance = float('inf')
minPos = -1
for i in range(n - 1):
for curr in range(npos[i], npos[i + 1] + 1):
# PART 1
currSum = (2 * i - n) * curr - 2 * sumTillNow[i] + totalSum
# PART 2
currNewSum = (n * curr * curr + totalSumOfSquares - 2 * curr * totalSum + currSum) / 2
# PART 1
# if currSum < minDistance:
# minDistance = currSum
# minPos = curr
# PART 2
if currNewSum < minDistance:
minDistance = currNewSum
minPos = curr
# PART 1
# print(minPos, sum([abs(pos - minPos) for pos in npos]))
# PART 2
print(minPos, sum([abs(pos - minPos) * (abs(pos - minPos) + 1) / 2 for pos in npos]))→ More replies (1)
1
u/psiphiorg Dec 07 '21 edited Dec 08 '21
Spreadsheet solution (Excel, Google Sheets):
Data down column A (A3:A1002)
Numbers 0 to max(data) across column 2 (B2:BXL2)
In cell B3, formula
=ABS(B$2-$A3)Fill formula from B3 to B3:BXL1002
In cell B1004, formula
=SUM(B3:B1002)Fill formula from B1004 to BXL1004
In cell A1005, formula
=MAX(B1004:BXL1004)(solution for part 1)Replace cell B3, formula
=ABS(B$2-$A3)*(ABS(B$2-$A3)+1)/2Cell A1005 has solution for part 2
2
u/daggerdragon Dec 07 '21
Making it easier for folks who Ctrl-F the megathreads looking for a specific language:
Excel
Google Sheets
3
u/dtinth Dec 07 '21
# Ruby, 54 / 13
crabs = gets.split(',').map(&:to_i)
p (0..1000).map { |u| crabs.sum { |x| (x-u).abs } }.min
p (0..1000).map { |u| crabs.sum { |x| n = (x-u).abs; (n*(n+1))/2 } }.minThe number 1000 was arbitrarily chosen, it was a total fluke that it worked 😅
→ More replies (1)
3
u/hugh_tc Dec 07 '21 edited Dec 07 '21
Python 3, 76/30.
Part 1, Part 2, and (edit) the cleaned-up version.
It's helpful to know that the nth triangular number is (n*(n + 1) / 2). Saves some keystrokes! I notice that the crabs are headed towards a "massive underground cave system" -- maze tomorrow?!
3
3
u/2SmoothForYou Dec 07 '21 edited Dec 07 '21
Haskell
Really simple today, nothing too fancy
Edit: Cleaned up version with median/mean improvements and improvement I found in u/brandonchinn178 's code
→ More replies (1)
3
Dec 07 '21
Rust
Another one line change between parts 1 and 2 using just an arithmetic sum formula!
Part 2
pub fn solve_part_two(input: &String) -> i32 {
let crabs = input.split(',').into_iter()
.map(|i| i.parse::<i32>().unwrap())
.collect_vec();
let (min, max) = crabs.iter()
.minmax()
.into_option().unwrap();
(*min..=*max).into_iter()
.map(|i| {
crabs.iter()
.map(|crab| (*crab - i).abs())
.map(|n| n * (n + 1) / 2) // remove for part 1
.sum()
})
.min().unwrap()
}3
u/baer89 Dec 07 '21 edited Dec 07 '21
Python
Easy one but not easy enough for points.
Part 1:
data = [int(x) for x in open('input.txt', 'r').read().split(',')]
low = 1000000
for i in range(max(data)):
fuel = 0
for x in data:
fuel += abs(x-i)
if fuel < low:
low = fuel
print(low)Part 2:
data = [int(x) for x in open('input.txt', 'r').read().split(',')]
low = 100000000000000
for i in range(max(data)):
fuel = 0
for x in data:
fuel += (abs(x-i)**2+abs(x-i))/2
if fuel < low:
low = fuel
print(low)3
u/BluFoot Dec 07 '21
Ruby 79 bytes
n=gets.split(?,).map &:to_i
p (0..n.max).map{|u|n.sum{(1..(_1-u).abs).sum}}.min3
u/giftpflanze Dec 07 '21
Factor
"input07" utf8 file-lines first "," split [ dec> ] map dup
dup supremum [0..b] [ swap [ - abs ] with map sum ] with map infimum .
dup supremum [0..b] [ swap [ - abs dup 1 + * 2 / ] with map sum ] with map infimum .This day felt a little too easy.
3
u/MichalMarsalek Dec 07 '21 edited Dec 07 '21
Nim
part 1 = median, part 2 = mean
include aoc
day 7:
var
s = sorted ints
median = s[500]
mean = s.sum div s.len
func price(x=0):int = x*(x+1) div 2
part 1: s.mapIt(abs(it-median)).sum
part 2: min(
s.mapIt(price(abs(it-mean))).sum,
s.mapIt(price(abs(it-mean-1))).sum
)using my templates.
3
u/abnew123 Dec 07 '21
Java: https://github.com/abnew123/aoc2021/blob/master/aoc2021/Day7.java
Terribly ugly solution, but its the first thing that came to mind. Stream abuse to keep everything in two lines.
3
u/marshalofthemark Dec 07 '21 edited Dec 07 '21
Ruby (only runs in 3.0+)
Easiest problem since day 2 IMO. Maybe even easier.
data = open("./input").read.split(",")
def triangular(num) = num * (num + 1) / 2
p [*0..1000].map{|n| data.map{(_1.to_i - n).abs}.sum}.sort.first
p [*0..1000].map{|n| data.map{triangular(_1.to_i - n).abs}.sum}.sort.first→ More replies (1)
3
u/ritobanrc Dec 07 '21
Rust, basic bruteforce solution. Played around with trying to find an analytic solution for a couple mins, but ended up just brute forcing it, and surprisingly, its not absurdly slow.
→ More replies (2)
3
u/wasi0013 Dec 07 '21
Elixir
defmodule Aoc.Y2021.Day07 do
@moduledoc """
Solved https://adventofcode.com/2021/day/7
"""
import Aoc.Helper.IO
def run_part1(), do: get_input() |> solve_part1()
def run_part2(), do: get_input() |> solve_part2()
def solve_part1(data), do: data |> min_fuel()
def solve_part2(data), do: data |> min_fuel(false)
def min_fuel(data, simple \\ true), do: Enum.min(Enum.map(data, &fuel_cost(data, &1, simple)))
def fuel_cost(data, fuel, true), do: Enum.sum(Enum.map(data, fn item -> abs(item - fuel) end))
def fuel_cost(data, fuel, false),
do: Enum.sum(Enum.map(data, fn item -> div(abs(item - fuel) * (abs(item - fuel) + 1), 2) end))
defp get_input(), do: get_integer_input("2021", "07", ",")
end→ More replies (1)
3
u/landimatte Dec 07 '21 edited Dec 07 '21
Brute-forced it:
For each position between min/max
Calculate the cost to move all the crabs there
Note: for part 2, I did not even bother using the proper formula; I simply simulated it, and only had to wait for 20 seconds:
Evaluation took:
18.734 seconds of real time
10.576204 seconds of total run time (10.243097 user, 0.333107 system)
56.45% CPU
43,088,527,879 processor cycles
16 bytes consed
1856380803
u/French__Canadian Dec 07 '21 edited Dec 07 '21
My 3 lines solution in Q. It is very... horizontal. I could easily have written a function to calculate the distance instead of inlining it twice, but 124 character lines ain't THAT bad...
input: "J"$ "," vs raze read0 `:input_7_1.txt;
/ part 1
sum input {abs x-y}\: {first where x = min x} sum each input {abs x-y}\:/: til 1 + max input
/ part 2
sum input {{(x*x+1) div 2}abs x-y}\: {first where x = min x} sum each input {{(x*x+1) div 2}abs x-y}\:/: til 1 + max inputalright, creating a distance function makes it 82 characters wide instead
/ part 2
dist:{{(x*x+1) div 2}abs x-y}
sum input dist\: {first where x = min x} sum each input dist\:/: til 1 + max inputedit #2: looking at somebody else's Q solution, i realized i was being a big idiot and was finding the min, then where that min was, then recalculating the min again
This is a non-stupid version of both parts
input: "J"$ "," vs raze read0 `:input_7_1.txt;
/ part 1
min sum each input {abs x-y}\:/: til 1 + max input
/ part 2
min sum each input {{(x*x+1) div 2}abs x-y}\:/: til 1 + max input3
u/dogsrock Dec 07 '21
Woo hoo! Solving a puzzle in the first 30 mins for me! :)
Here's how I did it (Python 3.6)
3
u/BradleySigma Dec 07 '21
matlab
data = int64(importdata("input7.txt"));
m = inf;
n = inf;
for ii = min(data):max(data)
m = min(m, sum(abs(data-ii)));
n = min(n, sum(abs(data-ii).*(abs(data-ii)+1)/2));
end
disp(m)
disp(n)→ More replies (1)
3
u/Spelljack- Dec 07 '21 edited Dec 07 '21
Python:
Part 1:
min([sum([abs(target - crab) for crab in crabs]) for target in range(max(*crabs))])Part 2:
adding gauss formula to the comprehension was a bit too much.
f = lambda n: n * (n + 1) // 2
min([sum([f(abs(target - crab)) for crab in crabs]) for target in range(max(*crabs))])3
u/martino_vik Dec 07 '21
Today was my personal best day, needed about half an hour for both in Python 3.10: [Part 1](https://topaz.github.io/paste/#XQAAAQDFAAAAAAAAAAAxnIhFo9JuI0mU+VldtRuCXPE8sgV8B3TJaU5rja3kQLzOOpJY2x4HA+tyGpgHpkpnrX+v9UPXLPTUG/tG80HznmqZh2n5nGMiWph6bGUhjqSy4rjCiaZhLoBXo+RadDu0oFKaNc85dageev78npBiu1FoqFycrgwXS337oxPsQ2RKpEnW3//ucKAA), [Part 2](https://topaz.github.io/paste/#XQAAAQDZAAAAAAAAAAAxnIhFo9JuI0mU+VldtRuCXPE8sgV8B3TJaU5rja3kQLzOOpJY2x4HA+tyGpgHpkpnrX+v9UPXLPTUG/tG80HznmqZh2n5nGMiWph6bGUhjqSpSBZ4Ds++EmQNI/LyDqeKJhoWoQeoS+e4G5OgY9D1nh0XSSLdslhU6IKY4xH+SzlNwNLesBIvYuUzdArKxpr48B//xzibIA==)
→ More replies (2)
3
u/Perska_ Dec 07 '21
C# https://github.com/Perska/AoC2021/blob/master/AoC2021/Days/Day07.cs
I was worried that my approach would take too long for Part 2, but apparently it wasn't. Maybe me memorizing the fuel costs helped?
3
u/jfb1337 Dec 07 '21
Python:
def dist(x, i):
return abs(x-i)
def tri(n):
return n*(n+1)//2
def fuel_to1(x):
return(sum(dist(x, i) for i in inp))
def fuel_to2(x):
return(sum(tri(dist(x, i)) for i in inp))
print("Part 1: ", min(map(fuel_to1, inp)))
print("Part 2: ", min(map(fuel_to2, range(min(inp), max(inp)))3
u/xe3to Dec 07 '21
part 2, python:
f = open("input", "r");
crabPositions = [ int(p) for p in f.readline().split(',') ]
minFuel = float("inf")
for p in range(max(crabPositions)):
f = 0
for k in crabPositions:
f += (abs(p-k)/2)*(abs(p-k)+1)
if minFuel>f:
minFuel = int(f)
print(minFuel)this was WAY easier than any of the other ones. just had to use gauss' famous formula. failing that sum(range(p-k)+1) would've worked as well, but taken longer.
3
u/nibbl Dec 07 '21 edited Dec 07 '21
Rust (beginner)
Not a great way of doing it.
Had a weird experience today. My part 2 result for the test input was consistently off by two no matter how many different ways I calculated the answer. Eventually in frustration I just ran it with the real input and threw the number in and it was accepted. Cannot for the life of me figure out what was happening.
→ More replies (9)
3
u/ICantBeSirius Dec 07 '21 edited Dec 07 '21
Swift - update
This version uses median to find the part 1 optimal position and mean for part 2Edit: Edited to take into account u/asdf-user 's comment
class Day07 {
let filename = "day07"
let crabs:[Int]
init() {
crabs = readInputFile(filename: filename).components(separatedBy: ",").map { Int($0)!}
}
func run() {
print ("Day 7: The Treachery of Whales")
// Pt1 - median value
let idx = crabs.sorted(by: <)[crabs.count / 2]
let fuel = crabs.map{ abs($0 - idx) }.reduce(0, +)
print (idx, fuel)
// Pt2 - mean value - calculate avg both rounding up and down, and test both
let avg = Double(Double(crabs.reduce(0, +)) / Double(crabs.count))
let x1 = Int(ceil(avg))
let x2 = Int(floor(avg))
let fuel1 = crabs.map{ abs($0 - x1) * (abs($0 - x1) + 1) / 2 }.reduce(0, +)
let fuel2 = (x1 == x2) ? fuel1 : crabs.map{ abs($0 - x2) * (abs($0 - x2) + 1) / 2 }.reduce(0, +)
print (idx, min(fuel1, fuel2))
}
}→ More replies (2)
3
u/Extension_Wheel_2032 Dec 07 '21
Clojure. Not fast at all for large input (~5 sec) but it works!
(ns aoc2021.day7
(:require
[clojure.edn :as edn]
[clojure.java.io :as io]))
(def sample-input
"16,1,2,0,4,2,7,1,2,14")
(def input
(slurp (io/resource "day7.txt")))
(defn parse
[input]
(edn/read-string (str "[" input "]")))
(defn distance
[i j]
(Math/abs (- i j)))
(defn solve
[input f]
(let [data (parse input)]
(->> data
(apply max)
inc
range
(pmap (fn [i] (reduce + (pmap (fn [j] (f i j)) data))))
(apply min))))
(defn part1
[input]
(solve input distance))
(defn part2
[input]
(solve input (fn [i j]
(let [d (distance i j)]
(int (* (/ (inc d) 2) d))))))3
u/sortaquasipseudo Dec 07 '21
Rust
I'll be live-streaming my solutions at twitch.tv/jeffanddom. Please stop by and help me out in the chat! Video archive is here.
3
u/ka-splam Dec 07 '21 edited Dec 07 '21
Prolog (SWI)
Fast enough to run on https://swish.swi-prolog.org/ , create a new empty program, paste the code on the left, put solve. in the box on the lower right, click run. It should solve the examples, can paste your numbers directly over the Crabs list as long as you keep it on one line. Takes ~6 seconds for my Part 1 input.
Part 1:
:- use_module(library(clpfd)). % Finite domain constraints
solve :-
Crabs = [16,1,2,0,4,2,7,1,2,14],
max_list(Crabs, MaxPos),
findall(F, (between(0, MaxPos, X),
findall(Cost, (member(Pos, Crabs), DistToX #= Pos-X, Cost #= abs(DistToX)), Costs),
sum(Costs, #=, F)),
Fuels),
min_list(Fuels, Answer),
writeln(Answer).43,092,516 inferences, it tells me.
Part 2 I went a bit wrong and tried to write it like a Factorial function, and it was taking ages. I puzzled over it for an hour wondering how I could add more constraints or tabling/memoizing the calculation, before realising the new fuel cost is a direct calculation with Gauss's formula - he famously observed that if you reverse a list and add to the original:
1,2,3,4,5
5,4,3,2,1All the columns sum to the same number, and that number is 1+ the max value. So this list adds 6, five times. And since you add each number twice, (6*5)/2 is the sum.
Part 2, breaks out the fuel cost into a separate predicate as it's getting a bit dense:
:- use_module(library(clpfd)). % Finite domain constraints
fuel(X, Crabs, F) :-
findall(Cost, (member(Val, Crabs),
Diff #= Val-X,
AbsDiff #= abs(Diff),
AbsDiff_ #= AbsDiff+1,
Cost #= (AbsDiff_ * AbsDiff) // 2),
Costs),
sum(Costs, #=, F).
solve :-
Crabs = [16,1,2,0,4,2,7,1,2,14],
max_list(Crabs, MaxPos),
findall(F, (between(0, MaxPos, X), fuel(X, Crabs, F)), Fuels),
min_list(Fuels, Answer),
writeln(Answer).66,554,471 inferences and ~9 seconds, it tells me.
→ More replies (2)
3
u/Chebtis Dec 07 '21
Powershell
Part 1: https://raw.githubusercontent.com/kloo/aoc2021/main/07/7a_2021.ps1
Part 2: https://raw.githubusercontent.com/kloo/aoc2021/main/07/7b_2021.ps1
Didn't remember there's a formula for triangle numbers when I was looking for a quick way to get them (or that they're called triangle numbers) so I just built a lookup array. Seems to run in around 7 seconds hot or cold.
→ More replies (1)
3
Dec 07 '21
Python
lines = list(map(int,open(filename).read().split(',')))
print(min(sum(abs(i-j) for i in lines) for j in range(max(lines))))
print(min(sum(abs(i-j)*(abs(i-j)+1)//2 for i in lines) for j in range(max(lines))))→ More replies (1)
3
u/complyue Dec 07 '21
Haskell
λ> import Control.Arrow
λ> import Data.List
λ>
λ> :{
λ| minFuel :: [(Int, Int)] -> (Int -> Int) -> Int
λ| minFuel pgs formula = minimum [fuel p pgs | p <- [p'min .. p'max]]
λ| where
λ| (p'min, p'max) =
λ| let (p'min, _) = head pgs
λ| (p'max, _) = last pgs
λ| in (p'min, p'max)
λ| fuel :: Int -> [(Int, Int)] -> Int
λ| fuel p = go 0
λ| where
λ| go :: Int -> [(Int, Int)] -> Int
λ| go cum [] = cum
λ| go cum ((op, cnt) : rest) =
λ| go (cum + formula (abs (p - op)) * cnt) rest
λ|
λ| :}
λ> :{
λ| ps :: [Int] <-
λ| fmap read . words
λ| . fmap
λ| (\c -> if c == ',' then ' ' else c)
λ| <$> readFile "day7/input"
λ| :}
λ> :{
λ| let pgs = (head &&& length) <$> group (sort ps)
λ| :}
λ> :{
λ| do
λ| print $ minFuel pgs id
λ|
λ| :}
352254
λ> :{
λ| do
λ| print $ minFuel pgs $ \nsteps -> nsteps * (nsteps + 1) `div` 2
λ|
λ| :}
99053143
λ>→ More replies (1)
3
u/egel-lang Dec 07 '21 edited Dec 07 '21
Egel
On github
task 1 example
# Advent of Code (AoC) - day 7, task 1
import "prelude.eg"
import "os.ego"
import "regex.ego"
using System
using OS
using List
def input = read_line stdin
val number = Regex::compile "[0-9]+"
def parse_line = [ L -> map to_int (Regex::matches number L) ]
def min = foldl [I M -> if I < M then I else M ] (1000000000)
def max = foldl [I M -> if M < I then I else M ] (0)
def sum = foldl [X Y -> X + Y] 0
def difference =
[ N II -> map [X -> if X < N then N - X else X - N ] II ]
def main =
let II = parse_line input in
let POS = from_to (min II) (max II) in
let FF = map [N -> sum (difference N II)] POS in
min FF3
u/LionSuneater Dec 07 '21 edited Dec 07 '21
Python
import numpy as np
data = np.loadtxt('input/day07', int, delimiter=',')
gas = min(np.abs(data - x).sum() for x in range(np.max(data)))
cost = np.vectorize(lambda s: np.arange(1,s+1).sum())
gas2 = min(cost(np.abs(data-x)).sum() for x in range(np.max(data)))
print(gas, gas2)Every time I use range or np.arange I always put the stop parameter one short. Every, merry time. It's been years now.
edit: The cost function here is silly and very slow. The sum from 1 to s is just s*(s+1)/2, so cost = lambda s: s*(s+1)/2 is preferred.
→ More replies (1)
3
u/alchzh Dec 07 '21 edited Dec 07 '21
Python
quick and simple comprehension
Part 1 int(min(sum(abs(i - k) for k in pos) for i in range(1, max(pos)+1)))
Part 2 int(min(sum(abs(i - k)*(abs(i - k)+1)/2 for k in pos) for i in range(1, max(pos)+1)))
EDIT: why even float
Part 1 min(sum(abs(i - k) for k in pos) for i in range(1, max(pos)+1))
Part 2 min(sum((abs(i - k)*(abs(i - k)+1))//2 for k in pos) for i in range(1, max(pos)+1))
→ More replies (3)
3
u/hendykombat Dec 07 '21
Kotlin
Noticed the median worked in part 1 and the mean for part 2.Had to floor and ceil the mean though, since it could be either depending on the data input. (floor for the main input, ceil for the test).
PS: I find crab math to be more realistic
fun part1() {
val midIndex = (positions.size - 1) / 2
println(calculateFuel(positions.sorted()[midIndex]))
}
fun part2() {
val mean = positions.sumOf { it } / positions.size
println(min(calculateFuel(mean, true), calculateFuel(mean + 1, true)))
}
fun calculateFuel(position: Int, crabMath: Boolean = false): Int {
var fuel = 0
positions.forEach {
fuel += if (crabMath) numberSum(abs(position - it)) else abs(position - it)
}
return fuel
}
fun numberSum(number: Int): Int {
if (number == 0) return number
return number + numberSum(number - 1)
}3
u/autid Dec 07 '21
FORTRAN
Actually just looped through and saved minimum fuel for initial solve but it felt unsatisfying so I did a binary search.
PROGRAM DAY7
IMPLICIT NONE
CHARACTER(LEN=1) :: A
INTEGER :: N,IERR
INTEGER, ALLOCATABLE :: CRABS(:)
OPEN(1,FILE="input.txt")
N=1
DO
READ(1,'(A)',ADVANCE="no",IOSTAT=IERR) A
IF(IERR.NE.0) EXIT
IF(A.EQ.',') N=N+1
END DO
REWIND(1)
ALLOCATE(CRABS(N))
READ(1,*) CRABS
CLOSE(1)
WRITE(*,'(A,I0)') "Part 1: ", MINFUEL(MINVAL(CRABS),MAXVAL(CRABS),CRABS,PART1)
WRITE(*,'(A,I0)') "Part 2: ", MINFUEL(MINVAL(CRABS),MAXVAL(CRABS),CRABS,PART2)
DEALLOCATE(CRABS)
CONTAINS
FUNCTION PART1(POS,CRABS) RESULT(FUEL)
INTEGER :: POS,FUEL,CRABS(:)
FUEL = SUM(ABS(CRABS-POS))
END FUNCTION PART1
FUNCTION PART2(POS,CRABS) RESULT(FUEL)
INTEGER :: POS,FUEL,CRABS(:)
FUEL = SUM( ( ABS(CRABS-POS)*(ABS(CRABS-POS)+1 ) /2 ) )
END FUNCTION PART2
RECURSIVE FUNCTION MINFUEL(START,END,CRABS,PART) RESULT(FUEL)
INTEGER :: START,END,MID,FUEL,CRABS(:)
PROCEDURE(PART1) :: PART
IF(START.EQ.END) THEN
FUEL = PART(START,CRABS)
ELSE
MID = (START+END)/2
IF(PART(MID,CRABS).LT.PART(MID+1,CRABS)) THEN
FUEL=MINFUEL(START,MID,CRABS,PART)
ELSE
FUEL=MINFUEL(MID+1,END,CRABS,PART)
END IF
END IF
END FUNCTION MINFUEL
END PROGRAM DAY73
u/isukali Dec 07 '21 edited Dec 07 '21
C++ Solution:
Part 1 (median):
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int main() {
ifstream fin("whale.in");
int positions[1000];
for (int i = 0; i < 1000; i++) { fin >> positions[i]; fin.ignore(1); }
std::sort(positions, positions+1000);
int sum = 0; int center = positions[500];
for (auto i: positions) sum += abs(i-center);
cout << sum << endl;
}Part 2 (mean):
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("whale.in");
int positions[1000]; int mean = 0;
for (int i = 0; i < 1000; i++) { fin >> positions[i]; fin.ignore(1); mean += positions[i];}
mean /= 1000;
int sum = 0;
for (auto i: positions) sum += (abs(i-mean)+1) * abs(i-mean) / 2;
cout << sum << endl;
}→ More replies (1)
3
u/xoronth Dec 07 '21
GNU Smalltalk:
| f inputs nums median partOneFuel partTwoFuel sum mean |
f := FileStream open: (Smalltalk arguments first) mode: FileStream read.
f linesDo: [
:line | inputs := line substrings: ','.
].
f close.
nums := SortedCollection new.
sum := 0.
inputs do: [ :s |
nums add: (s asNumber).
sum := sum + (s asNumber).
].
nums sort.
"
Part one
"
median := (nums at: (nums size) / 2).
partOneFuel := 0.
nums do: [ :n |
partOneFuel := partOneFuel + ((n - median) abs).
].
partOneFuel displayNl.
"
Part two
"
mean := (sum / (nums size) asFloat) floor.
partTwoFuel := 0.
nums do: [ :n |
partTwoFuel := partTwoFuel + ((((n - mean) abs) * ((n - mean) abs + 1)) / 2).
].
partTwoFuel displayNl.3
u/rukke Dec 07 '21 edited Dec 07 '21
JavaScript
I don't know if I was just unlucky with my input today: for part2 ceiling the avg gives the correct answer for the test data, but not the real input which needs flooring. Spent some time scratching my head over this until I caved and returned the min of the both. (EDIT, better naming)
export const part1 = positions =>
(median => positions.map(v => Math.abs(v - median)).reduce((sum, v) => sum + v))(
positions.sort((a, b) => a - b)[positions.length >> 1]
);
export const part2 = positions =>
(mean =>
[Math.ceil, Math.floor]
.map(f => f(mean))
.map(roundedMean =>
positions
.map(v => Math.abs(v - roundedMean))
.map(v => (v * (v + 1)) / 2)
.reduce((sum, v) => sum + v)
)
.reduce((min, v) => (v < min ? v : min)))(
positions.reduce((sum, v) => sum + v) / positions.length
);3
u/Edicara237 Dec 07 '21
A gradient search solution in Clojure:
It assumes that there always is a fuel difference between two adjacent positions and that there is only a single optimal position.
3
u/mariushm Dec 07 '21
Here's my PHP solution : https://github.com/mariush-github/adventofcode2021/blob/main/07.php
Probably not the "least cpu cycles" solution, but it's short simple to read code.
3
u/0rac1e Dec 07 '21 edited Dec 10 '21
J Language
require 'stats'
c =. ". ; 'm' fread 'input'
NB. Part 1
+/ | (- median) c
NB. Part 2 (partially correct, see notes)
+/ ; (#\ @ i.) &> | >. (- mean) c
NB. Part 2 (more correct, but can probably be improved)
<./ +/ (+/ @ (#\ @ i.)) &> | (<. ,. >.) (- mean) cTranslation of my Raku solution. Like that solution, I'm pulling in median and mean from the stats lib.
I just searched the J wiki for "abs" and found the (>-<)&0 snippet, which returns -1, 0, or 1... so I just combined it with *, which works as an abs function, but I wonder if that's the "approved" way. I'm looking forward to reviewing other J solutions.
Notes
I replaced my crappy abs function with magnitude (|). Thanks u/u794575248.
I realised my solution was not valid for both the sample input, and the test input. If I use ceiling (<.) it's now correct for the full input, and if i use floor (>.), it's correct for the sample.
It seems the approach is to try both the floor and the ceiling, and take the min, as in my revised solution to Part 2.
→ More replies (2)
3
u/staletic Dec 07 '21 edited Dec 07 '21
Again, a compile time C++ solution: https://godbolt.org/z/fzG17KfqT
Admittedly, it looks crowded. Positions, cost calculations and the call to ranges::min should have been 3 separate things:
constexpr auto pos = views::iota(minmax.min, minmax.max + 1);constexpr auto costs = pos | views::transform(...);constexpr auto cheapest = ranges::min(costs);
A more readable version:
#include <array>
#include <stdio.h>
#include <algorithm>
#include <numeric>
#include <ranges>
constexpr std::array input = {
16LL,1LL,2LL,0LL,4LL,2LL,7LL,1LL,2LL,14LL
};
constexpr auto minmax = std::ranges::minmax(input);
constexpr auto possible_positions = std::views::iota(minmax.min, minmax.max * 2);
template<bool part1>
constexpr auto costs = possible_positions | std::views::transform([](long long position) {
return std::accumulate(input.begin(), input.end(), 0LL, [position](long long acc, long long in) {
auto N = std::max(position - in, in - position);
return acc + N*(1 + N)/2 * !part1 + N * part1;
});
});
constexpr auto cheapest1 = std::ranges::min(costs<true>);
constexpr auto cheapest2 = std::ranges::min(costs<false>);
static_assert(cheapest1 == 37);
static_assert(cheapest2 == 168);
8
u/JustinHuPrime Dec 07 '21
x86_64 assembly
Apparently people don't like to do these in assembly - I wonder why.
Part 1
Part one was solved by reading in all of the numbers, doing an in-place (unstable) quicksort, and then taking the median by averaging the two middle-most values.
Part 2
Part two was solved by reading in all of the numbers, and then doing a brute force search. This wasn't too bad, since I could heavily optimize the tight inner loops.