Advent of Code 2021 - Day 7

I got 4th on part 1; 21st on part 2.

Unclear if knowing that the median was the answer for part 1 helped or hurt me :) Probably helped for part 1 and hurt for part 2?

Anyone know the closed form answer for part 2?

[umairgillani]

It's an absolute pleasure to see you code. Its amazing how quickly your parse the statement and understand what's being asked in the problem. Please share why you solve only Advent problems in Python?? Big Fan from Pakistan

[rastislavsvoboda]

nice and quick! congrats

def cost1(h1, h2):
dist = abs(h1-h2)
return dist

def cost2(h1, h2):
dist = abs(h1-h2)
return (dist * (dist + 1)) // 2

def solve(nums, minN, maxN, cost_fun):
F = {}
for h in range(minN, maxN+1):
F[h] = sum(cost_fun(x, h) for x in nums)
return min(F.values())

// rest is obvious ;-)

[nelonelo]

Which Keyboard do you use? It sounds so satisfying 😂

[Benbb]

I also saw very quickly that answer for part 1 was the median, . Then for part 2, it seemed to me it was the average number. I just tried few numbers around it to be sure 😄

[karltillstrom]

Awesome solution, really liked the reasoning in the explanation

[sanderalewijnse]

So for the second part I used that the fuel(x) ( = total cost for all crabs to get to x) is a piece-wise quadratic function.

It is the sum of fuel(x, p) (=total cost for crab starting at p to get to x), which = abs(p-x) * (abs(p-x) + 1)) / 2, which is quadratic from -infinity to p, and p to infinity.

You can go over each piece of that function in linear time (after sorting the input points) and compute the analytical minimum for each piece in constant time. Making the total algo time near-linear in the number of input points, and independent of the numerical range of the input (assuming the analytics don't blow up, which they didn't for me).

[tomcrsee]

reasoning on part 2, if it makes sense, feel free to improve them or point out any mistakes
def:

sumN(n) = (n * (n+1)) / 2

For a target T, the score is sum(sumN(|x - T|) for x in positions))
So if the target is to be moved by +1, the score changes by (sumN(m) - sumN(n)), where n = (|x - T|) and m = (|x - T| + 1) = (n + 1) (essentially for the new T)


# Move T to left
oldT = T
T = T-1
for x in positions:
if x < oldT: # for all x < oldT
cost -= (oldT - x)
else: # for all x >= oldT
cost += (x - oldT)

It's the exact opposite for T+1

The cost decreases by (T - x) for x < T and increases by (x - T) for x >= T.
So the delta is: |sum(x - T) for x in positions if x < T| ~== |sum(x - T) for x in positions if x >= T|
So what can T be? We can choose T as the mean of all the numbers.
chossing T = min(positions) would be an advantage for all starting postions
chossing T = max(positions) would be an advantage for all ending postions
chossing T = median of positions would be okay if it's a normal distribution, but that's not the case here and a number can occur any number of times.

Let's see an example:
Consider the following positions 1, 1, 1, 2, 5, 8
Let's say that you choose T to be the median, which is 2, then the cost = 30
Now, let's take T to be equal to the mean, which is 2, then the cost = 28
the positions are distributed more towards the left, so it's always best to take the mean. (same if postitions are distributed more towards the right)

[xlustx]

Did you know that the input also runs in the intcode program? :)

[ujjawalsinha]

For the second part, mean is a good measure for target. Not sure why though, I think because the cost function for second part is quadratic in the absoulte distance

[LucFouin]

is it me or you got lucky on ex1? with an even number of crabs, and individual crab distance around the centered position of the sorted array, you could have guessed wrong as the median would have been the mean between the two numbers closest to the middle of the sorted array, no?

[phyzix_phyzix]

Are you the guy that writes really messy code at my job? Don't forget KROs are due next week. Also, I'm not doing your code review.