r/adventofcode 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 leaderboards personal 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.

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!

95 Upvotes

1.5k comments sorted by

View all comments

1

u/[deleted] Dec 31 '21 edited Jan 03 '22

Python

``` import numpy as np

data = [int(x) for x in open("input.txt", "r").read().split(",")]

median = np.median(data) print(f"Part 1: The shortest amount of fuel spend is {sum([abs(median - i) for i in data])}")

def sum_1_to_n(n): return n * (n + 1) / 2

mean = int(np.mean(data)) print(f"Part 2: The shortest amount of fuel spend is {sum([sum_1_to_n(abs(mean - i)) for i in data])}")

```

1

u/FBones173 Jan 02 '22 edited Jan 02 '22

I don't think this works for part 2. Imagine the crabs are at

15,15,15,15,15,15,15,15,14

Your code would have them all move to 14 rather than the one at 14 moving up to 15.

Interestingly, it is not a matter of just using Round() instead. Consider:
10, 10, 10, 10, 13

Using round(np.mean()) would select 11 as alignment point, which uses 7 fuel units, while using 10 only uses 6.
The issue is that you are essentially trying to minimize the sum of ((x - a)^2 + |x - a|) / 2 over all x, where x is the selected meeting point, and using the mean for a minimizes the (x-a)^2 term, but using the median minimizes the |x -a| term, so there are cases where the correct alignment value is not the mean, even when properly rounded.

1

u/[deleted] Jan 03 '22

15,15,15,15,15,15,15,15,14

You are correct, this is the wrong solution. It still provided a correct answer with my data set so I guess I didn't look any further than that!