68 lines
934 B
Go
68 lines
934 B
Go
|
package main
|
||
|
|
|
||
|
|
import (
|
||
|
|
"bufio"
|
||
|
|
"fmt"
|
||
|
|
"math"
|
||
|
|
"os"
|
||
|
|
"strconv"
|
||
|
|
"strings"
|
||
|
|
)
|
||
|
|
|
||
|
|
func main() {
|
||
|
|
// too lazy for fancy algorithms
|
||
|
|
var crabs []int
|
||
|
|
topCrab := 0
|
||
|
|
|
||
|
|
s := bufio.NewScanner(os.Stdin)
|
||
|
|
s.Scan()
|
||
|
|
for _, crabStr := range strings.Split(s.Text(), ",") {
|
||
|
|
crab, _ := strconv.Atoi(crabStr)
|
||
|
|
crabs = append(crabs, crab)
|
||
|
|
if crab > topCrab {
|
||
|
|
topCrab = crab
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// part 1
|
||
|
|
bestFuel := math.MaxInt64
|
||
|
|
|
||
|
|
for x := 0; x <= topCrab; x++ {
|
||
|
|
fuel := 0
|
||
|
|
for _, crab := range crabs {
|
||
|
|
fuel += abs(crab - x)
|
||
|
|
}
|
||
|
|
|
||
|
|
if fuel < bestFuel {
|
||
|
|
bestFuel = fuel
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
fmt.Println(bestFuel)
|
||
|
|
|
||
|
|
// part 2
|
||
|
|
bestFuel2 := math.MaxInt64
|
||
|
|
|
||
|
|
for x := 0; x <= topCrab; x++ {
|
||
|
|
fuel := 0
|
||
|
|
for _, crab := range crabs {
|
||
|
|
diff := abs(crab - x)
|
||
|
|
// triangular number
|
||
|
|
fuel += (diff * (diff + 1)) / 2
|
||
|
|
}
|
||
|
|
|
||
|
|
if fuel < bestFuel2 {
|
||
|
|
bestFuel2 = fuel
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
fmt.Println(bestFuel2)
|
||
|
|
}
|
||
|
|
|
||
|
|
func abs(i int) int {
|
||
|
|
if i < 0 {
|
||
|
|
return -i
|
||
|
|
}
|
||
|
|
return i
|
||
|
|
}
|