https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2021 day 7> :thread:
# advent-of-code
a
d
Nobody will believe this but I was just talking to @rossman earlier today about Gauss and the formula for the sum of the first n integers. Crazy coincidence!
s
Haha nice David, I used that too
m
🙌 4
j
(0..x).sum() == (x+1)*x/2
:)
m
I will argue the intent of the 
sum()
version is more readable. 😄 But yours is definitely faster.
j
also part1 can be done in O(n log n) just by sorting and taking median, but part2? I’m still fighting with that one to be better than naive O(n^2)
⭐ 3
m
j
and part 2 in O(nlogn): (local minimum around average) edit: no need to sort for part 2. O(n) it is then
d
p
All right, made it more efficient 🙂
e
part 2 is always close to the arithmetic mean. it's a bit off due to an extra linear term, but it's never off by more than 1/2 (if my math is right), and we only care about integers, so…
I went into a little more detail at https://old.reddit.com/r/adventofcode/comments/rar7ty/2021_day_7_solutions/hnkga9w/ but haven't done a real write-up
m
its the monday puzzle blues
Copy code
val parsed = input.split(",").map(String::toInt).sorted()
private val rangeToCheck = parsed.first()..parsed.last()

override fun part1() = solve { it }
override fun part2() = solve { it * (it + 1) / 2 }

private fun solve(mapping: (Int) -> Int) = rangeToCheck.minOf { candidate ->
    parsed.map { abs(it - candidate) }.sumOf(mapping)
}
n
I see many solutions are using 
minOf
and calculating the distance for each element. It got me thinking: since the distance is a convex function, is there a concise way to stop the traversal when you hit the minimum? My solution is not very concise (takeWhile and a local variable)
p
Besides the ones taking the mean values another approach could also do these range lookups. Sort the values and then change where you are looking at
I think I'm trying to describe binary search 😛
r
you can also do part 1 in average O(n) since it's median, you can find it via quick selecting (size/2)-th smallest element in the array
n
Right, that’s the best solution. My question was just a mental exercise. Good point @Paul Woitaschek that a binary search is better.
g
e
there's inputs that will be one off of that on part 2
Also, AOC admins ask that you do not redistribute the site's text
g
That's what I thought, too ...
For some (good) reason, it worked with the example and with my "real input" as well. Chances are 50%, I think 🙂
The AOC admins don't want you to show your result (which I removed), according to their FAQ.
r
I've seen somewhere on reddit from AoC admins that you can have your own input in repo
e
the text in the kdoc is what I'm talking about - they've asked other people to take that down
g
Ok, I remove it then ...
t
Started late today and have had meetings all morning. Bah. • Blog • Code
k
@ephemient could you please provide your calculation on why it should be near mean? I still cannot figure a way why
r
there is a great thread on reddit explaining it with heavy math
e
yes, that post is exactly the same argument
6 Views
Open in Slack
PreviousNext
Powered by