3 ms·

Day 6 and 7 are fantastic for that. It's a learning moment, where you can get the benefit of thinking about the problem for a few minutes instead of bruteforcin

Day 6 and 7 are fantastic for that. It's a learning moment, where you can get the benefit of thinking about the problem for a few minutes instead of bruteforcing gives you a dramatic speed up. When I read the Day 7, I saw bruteforcing would lead to bad perfs. Then I remembered that in high school, I learned a formula to calculate the nth term of a sequence without having to process the entire sequence. I couldn't remember the formula, nor the name of the concept, so I google around until I found some tutorials, and relearned what I was taught as a child: arithmetic sums. The consumption for a crab can then be calculated in constant time: def crab_consumption(crab, target): n = abs(target - crab) - 1 return (n**2 + 3*n + 2) / 2 And the Python solution finishes instantly. Bottom line, I could keep using Python for all problems and benefit from the amazing productivity of it. I've been using python since 2.4 now, and it's not always fast enough. But it very, very often, is.

mroche 5y ago
Interesting, I'll have to look at that. Actual algorithms are a big weak point for me, I'm not a developer by day, so I don't spend a lot of time learning code practices or computer science/math topics. This was my solution to Day 7 Part 2 (positions = sorted int list of input data): def calculate_fuel(positions): fuel = None low_fuel_value = None calculated = dict() for value in range(positions[0], positions[-1]+1): consumed = 0 for position in positions: diff = abs(value - position) try: consumed += calculated[diff] except KeyError: if position != value: consumption = sum([x for x in range(1,diff+1)]) calculated[diff] = consumption consumed += consumption if fuel: if consumed < fuel: fuel = consumed low_fuel_value = value else: fuel = consumed low_fuel_value = value print(f"Aligning to: {low_fuel_value}") return fuel And Day 6 I fell for the bruteforce bait and had the thought "It can't be as easy as changing 80 to 256, right?". Then I realized the pain I had created for myself. BUT! My 6p2 code ran faster than my 6p1 by a good margin, which I was happy about.
matsemann 5y ago
Can even calculate the target without bruteforcing. . n^2+n is approximated by n^2 when n is large. Can take the mean of all the distances and use that (or perhaps +/- 1). val crabs = lines.first().split(",").map { it.toInt() } val avg = crabs.sum() / crabs.size return crabs.sumOf { abs(it - avg).let {dst -> (dst * (dst + 1)) / 2} } And similarly for part1 take the median. Why it kinda works: Part1: The median I felt made sense intuitively, as in my head I thought about an example ala 1,1,3,100. Never makes sense to use x>3, because even though the crab at x=100 then can walk shorter, there are 3 others then having to walk longer. And x=1,2or3 doesn't matter, just symmetrically changes which side has to walk one step less or one step more. And for part2 I thought similar, except the cost is exponential and therefore I want to minimize the avg move and not the total moves, thus taking the average.

mroche 5y ago

Interesting, I'll have to look at that. Actual algorithms are a big weak point for me, I'm not a developer by day, so I don't spend a lot of time learning code practices or computer science/math topics. This was my solution to Day 7 Part 2 (positions = sorted int list of input data): def calculate_fuel(positions): fuel = None low_fuel_value = None calculated = dict() for value in range(positions[0], positions[-1]+1): consumed = 0 for position in positions: diff = abs(value - position) try: consumed += calculated[diff] except KeyError: if position != value: consumption = sum([x for x in range(1,diff+1)]) calculated[diff] = consumption consumed += consumption if fuel: if consumed < fuel: fuel = consumed low_fuel_value = value else: fuel = consumed low_fuel_value = value print(f"Aligning to: {low_fuel_value}") return fuel And Day 6 I fell for the bruteforce bait and had the thought "It can't be as easy as changing 80 to 256, right?". Then I realized the pain I had created for myself. BUT! My 6p2 code ran faster than my 6p1 by a good margin, which I was happy about.

matsemann 5y ago

Can even calculate the target without bruteforcing. . n^2+n is approximated by n^2 when n is large. Can take the mean of all the distances and use that (or perhaps +/- 1). val crabs = lines.first().split(",").map { it.toInt() } val avg = crabs.sum() / crabs.size return crabs.sumOf { abs(it - avg).let {dst -> (dst * (dst + 1)) / 2} } And similarly for part1 take the median. Why it kinda works: Part1: The median I felt made sense intuitively, as in my head I thought about an example ala 1,1,3,100. Never makes sense to use x>3, because even though the crab at x=100 then can walk shorter, there are 3 others then having to walk longer. And x=1,2or3 doesn't matter, just symmetrically changes which side has to walk one step less or one step more. And for part2 I thought similar, except the cost is exponential and therefore I want to minimize the avg move and not the total moves, thus taking the average.