2024-12-13 10:02:48 +00:00
|
|
|
package two
|
|
|
|
|
|
|
|
import (
|
|
|
|
"bytes"
|
|
|
|
|
|
|
|
log "github.com/sirupsen/logrus"
|
|
|
|
)
|
|
|
|
|
|
|
|
func Solve(buf []byte) (int, error) {
|
|
|
|
r := bytes.NewReader(buf)
|
|
|
|
graph, err := parseLines(r)
|
|
|
|
if err != nil {
|
|
|
|
return 0, err
|
|
|
|
}
|
|
|
|
|
|
|
|
var totalCost int
|
|
|
|
totalAreaVisited := make(map[point]struct{})
|
2025-01-08 05:42:35 +00:00
|
|
|
for y := range graph.data {
|
|
|
|
for x := range graph.data[y] {
|
|
|
|
start := newPoint(x, y)
|
2024-12-13 10:02:48 +00:00
|
|
|
if graph.isOutOfBounds(start) {
|
|
|
|
continue
|
|
|
|
}
|
|
|
|
|
|
|
|
_, ok := totalAreaVisited[start]
|
|
|
|
if ok {
|
|
|
|
continue
|
|
|
|
}
|
|
|
|
totalAreaVisited[start] = struct{}{}
|
|
|
|
|
|
|
|
path := exploreAreaSequentially(start, graph)
|
2025-01-07 17:24:23 +00:00
|
|
|
numSides := analyzeSides(graph.valueAt(firstPointFromMap(path.visited)), path, graph)
|
2024-12-13 10:02:48 +00:00
|
|
|
|
|
|
|
totalCost += len(path.visited) * numSides
|
|
|
|
for point := range path.visited {
|
|
|
|
totalAreaVisited[point] = struct{}{}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
return totalCost, nil
|
|
|
|
}
|
|
|
|
|
2024-12-13 23:40:43 +00:00
|
|
|
const (
|
|
|
|
first = iota
|
|
|
|
second
|
|
|
|
diagonal
|
|
|
|
)
|
|
|
|
|
2025-01-07 17:24:23 +00:00
|
|
|
func analyzeSides(kind rune, path path, g *graph) int {
|
|
|
|
log.Debugf("graph for values %s\n%s\n", string(kind), g.debug(path.visited))
|
2024-12-13 10:02:48 +00:00
|
|
|
|
|
|
|
var corners int
|
|
|
|
for current := range path.visited {
|
|
|
|
ns := neighbours(current)
|
|
|
|
|
2024-12-13 23:40:43 +00:00
|
|
|
for _, points := range [][]point{
|
|
|
|
{ns[N], ns[E], point{current.x + 1, current.y - 1}},
|
|
|
|
{ns[N], ns[W], point{current.x - 1, current.y - 1}},
|
|
|
|
{ns[S], ns[E], point{current.x + 1, current.y + 1}},
|
|
|
|
{ns[S], ns[W], point{current.x - 1, current.y + 1}},
|
|
|
|
} {
|
2025-01-07 17:24:23 +00:00
|
|
|
if isCorner(current, points[first], points[second], g) {
|
2024-12-13 23:40:43 +00:00
|
|
|
corners++
|
|
|
|
}
|
2024-12-13 10:02:48 +00:00
|
|
|
|
2025-01-07 17:24:23 +00:00
|
|
|
if isInnerCorner(current, points[first], points[second], points[diagonal], g) {
|
2024-12-13 23:40:43 +00:00
|
|
|
corners++
|
|
|
|
}
|
2024-12-13 10:02:48 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
log.Debugf("this path has %d corners", corners)
|
|
|
|
|
|
|
|
return corners
|
|
|
|
}
|
|
|
|
|
2025-01-07 17:24:23 +00:00
|
|
|
func isCorner(current, p, q point, g *graph) bool {
|
|
|
|
if g.isOutOfBounds(p) && g.isOutOfBounds(q) {
|
2024-12-13 10:02:48 +00:00
|
|
|
return true
|
|
|
|
}
|
|
|
|
|
2025-01-07 17:24:23 +00:00
|
|
|
if !g.isOutOfBounds(p) {
|
|
|
|
if g.isOutOfBounds(q) && !g.sameKind(p, current) {
|
2024-12-13 10:02:48 +00:00
|
|
|
return true
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2025-01-07 17:24:23 +00:00
|
|
|
if !g.isOutOfBounds(q) {
|
|
|
|
if g.isOutOfBounds(p) && !g.sameKind(q, current) {
|
2024-12-13 10:02:48 +00:00
|
|
|
return true
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2025-01-07 17:24:23 +00:00
|
|
|
if !g.isOutOfBounds(p) && !g.isOutOfBounds(q) {
|
|
|
|
if !g.sameKind(p, current) && !g.sameKind(q, current) {
|
2024-12-13 10:02:48 +00:00
|
|
|
return true
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
return false
|
|
|
|
}
|
|
|
|
|
2025-01-07 17:24:23 +00:00
|
|
|
func isInnerCorner(current, p, q, diagonal point, g *graph) bool {
|
|
|
|
if !g.isOutOfBounds(p) && !g.isOutOfBounds(q) {
|
|
|
|
if g.sameKind(p, current) && g.sameKind(q, current) &&
|
|
|
|
!g.sameKind(diagonal, current) {
|
2024-12-13 23:24:05 +00:00
|
|
|
return true
|
|
|
|
}
|
|
|
|
}
|
|
|
|
return false
|
|
|
|
}
|