It’s a cool fact that the minimiser of ∑_i |x_i - m| is the median of the x_i. So that reduces the search space in part 1 to one. I’m embarrassed to tell you my part 2 because, although my solution worked, I can’t prove that it should.
> It’s a cool fact that the minimiser of ∑_i |x_i - m| is the median of the x_i I didn’t know that. I love it! :slightly_smiling_face:
Back to the median… one thing I couldn’t prove to myself last night was whether the solution would always be a member of the dataset (e.g. meaning the median or similar couldn’t work). I always felt like there’d be some set of data where the optimal end position wouldn’t be in the original data. But I couldn’t prove it to myself one way or the other quickly enough.
The median need not be in the dataset. The median of {1, 3} is 2.
But it is an optimal position (in this case the fuel costs for any of 1,2, or 3 are the same). In part2, 2 would be the unique solution I think.
> The median need not be in the dataset. The median of {1, 3} is 2. Heh, I always remembered the median as being the middle of the dataset, but a member of the dataset. But, looking it up again, you’re absolutely right. That does make it more plausible.
<https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day07/day07.rkt|Day 7> - pleased with the aesthetics of this one using for/sum and for/list One thing I enjoy trying to do with Advent of Code is to minimize the differences between parts as much as possible. For today, the only difference is: (define part1-cost identity)
(define (part2-cost n)
(/ (* n (add1 n)) 2))
<https://github.com/otherjoel/advent-of-code/blob/main/2021/day07.rkt|My day 7> — I guessed at using the median for part 1 and that worked fine. Then I guessed I would need the average for part 2, and when it didn’t immediately work I went all round the houses trying to zero in by recursively bifurcating the range. Then I brute forced it and realized the optimal position was one less than my average, which I’d rounded to the nearest integer. So I found that I could pass both the test inputs and the real one by taking the more optimal of (floor average) and (ceiling average).
Finishes part 2 in 116 μs
Nice
Nice work @joel - I took your idea to create <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day07/day07-joeldueck.rkt|a fast version> of part 2 only. My <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day07/day07.rkt|brute force solution> takes 44,000 μs, and the fast version using your idea takes 19 μs. That’s quite a difference! I was going for elegance today.
Nice! I kinda like how you space things out when there are double parens/brackets
Apparently one way to think about is that the travel cost is quadratic, and the way to minimize the sum of squares distances is to find the mean. Not that I get any of that, I’m just paraphrasing what I read when I peeked at peter norvig’s python solutions, hehe
<https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day07/day07-joeldueck-unsafe.rkt|Final tweak> of my port of Joel’s using unsafe arithmetic. Pretty ugly, but it went from 19 μs down to 17 μs :)
@hoshom where did you see Norvig’s code? I’d like to bookmark it.
@berkozkutuk has joined the channel
Yup