advent_of_code_2024/day_09/solution.go

package day_09

const Empty = -1

type State int

type Chunk struct {
	start, length int
}

const (
	ReadingValue = iota
	ReadingSpace = iota
)

// task:https://adventofcode.com/2024/day/9
func SolveBasic(input string) int {
	diagram := loadDiagram(input)

	diagram = compress(diagram)

	return hashSum(diagram)
}

// task:https://adventofcode.com/2024/day/9#part2
func SolveComplex(input string) int {
	diagram := loadDiagram(input)

	diagram = safeCompress(diagram)

	return hashSum(diagram)
}

func hashSum(diagram []int) int {
	sum := 0
	for i, val := range diagram {
		if val != Empty {
			sum += i * val
		}
	}
	return sum
}

func compress(diagram []int) []int {
	startingCursor := 0
	endingCursor := len(diagram) - 1

	for {
		for diagram[startingCursor] != Empty && startingCursor < endingCursor {
			startingCursor++
		}
		for diagram[endingCursor] == Empty && startingCursor < endingCursor {
			endingCursor--
		}
		if startingCursor >= endingCursor {
			break
		}
		diagram[startingCursor] = diagram[endingCursor]
		diagram[endingCursor] = Empty
	}
	return diagram
}

func safeCompress(diagram []int) []int {
	value := diagram[len(diagram)-1]

	for value >= 0 {
		file := locateFile(diagram, value)
		if hole, found := findHole(diagram, file.start, file.length); found {
			copyFile(diagram, file, value, hole)
		}
		value--
	}

	return diagram
}

func copyFile(diagram []int, file Chunk, value int, hole Chunk) {
	for i := 0; i < file.length; i++ {
		diagram[hole.start+i] = value
		diagram[file.start+i] = Empty
	}
}

func findHole(diagram []int, end int, length int) (Chunk, bool) {
	for i := 0; i < end; i++ {
		if diagram[i] == Empty {
			size := 0
			for i+size < end && diagram[i+size] == Empty {
				size++
			}
			if size >= length {
				return Chunk{i, size}, true
			}
		}
	}
	return Chunk{}, false
}

func locateFile(diagram []int, value int) Chunk {
	length := 0
	for i := 0; i < len(diagram); i++ {
		if diagram[i] == value {
			start := i
			for i+length < len(diagram) && diagram[i+length] == value {
				length++
			}
			return Chunk{start, length}
		}
	}
	panic("couldn't find the value")
}

func loadDiagram(input string) []int {
	diagram := make([]int, 0, len(input)*5) // we reserve about the average we need
	state := ReadingValue
	currentValue := 0

	for _, r := range input {
		lenght := int(r - '0')
		if state == ReadingValue {
			for i := 0; i < lenght; i++ {
				diagram = append(diagram, currentValue)
			}
			currentValue++
		} else {
			for i := 0; i < lenght; i++ {
				diagram = append(diagram, Empty)
			}
		}
		state = (state + 1) % 2
	}

	return diagram
}