186 lines
3.4 KiB
Go
186 lines
3.4 KiB
Go
package main
|
|
|
|
import (
|
|
"bufio"
|
|
"fmt"
|
|
"os"
|
|
"slices"
|
|
"time"
|
|
)
|
|
|
|
const FILE_PATH = "./input.txt"
|
|
|
|
//const FILE_PATH = "./sample.txt"
|
|
|
|
func LoadInput(filename string) ([]string, error) {
|
|
file, err := os.Open(filename)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
defer file.Close()
|
|
|
|
var lines []string
|
|
scanner := bufio.NewScanner(file)
|
|
for scanner.Scan() {
|
|
lines = append(lines, scanner.Text())
|
|
}
|
|
|
|
if err := scanner.Err(); err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
return lines, nil
|
|
}
|
|
|
|
type structuredInput = string
|
|
|
|
func TransformInput(lines []string) structuredInput {
|
|
return lines[0]
|
|
}
|
|
|
|
type Block struct {
|
|
id int
|
|
length int
|
|
free int
|
|
|
|
used int
|
|
freeUsed int
|
|
}
|
|
|
|
func Part1CreateBlocks(input structuredInput) []Block {
|
|
var result = make([]Block, 0)
|
|
var temp Block
|
|
for i := 0; i < len(input); i += 2 {
|
|
temp = Block{id: i / 2, length: int(input[i] - '0')}
|
|
if i+1 < len(input) {
|
|
temp.free = int(input[i+1] - '0')
|
|
}
|
|
result = append(result, temp)
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
func Part1(input structuredInput) int {
|
|
var result = 0
|
|
|
|
var blocks = Part1CreateBlocks(input)
|
|
var j = 0
|
|
|
|
for i := 0; i < len(blocks); i++ {
|
|
for blocks[i].used != blocks[i].length {
|
|
result += j * blocks[i].id
|
|
blocks[i].used += 1
|
|
j++
|
|
}
|
|
|
|
for blocks[i].freeUsed != blocks[i].free {
|
|
for m := len(blocks) - 1; m >= 0; m-- {
|
|
if blocks[m].used != blocks[m].length {
|
|
result += j * blocks[m].id
|
|
blocks[m].used += 1
|
|
break
|
|
}
|
|
}
|
|
|
|
blocks[i].freeUsed += 1
|
|
j++
|
|
}
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
func findBlockWithLE(blocks []Block, size int, self int) int {
|
|
for i := len(blocks) - 1; i >= 0; i-- {
|
|
if blocks[i].id != self && blocks[i].length <= size {
|
|
return i
|
|
}
|
|
}
|
|
|
|
return -1
|
|
}
|
|
|
|
func getIndex(blocks []Block, id int) int {
|
|
for i, block := range blocks {
|
|
if block.id == id {
|
|
return i
|
|
}
|
|
}
|
|
|
|
return -1
|
|
}
|
|
|
|
func printBlocks(blocks []Block) {
|
|
for i := 0; i < len(blocks); i++ {
|
|
for j := 0; j < blocks[i].length; j++ {
|
|
fmt.Print("|", blocks[i].id)
|
|
}
|
|
for j := 0; j < blocks[i].free; j++ {
|
|
fmt.Print("|", ".")
|
|
}
|
|
}
|
|
fmt.Println()
|
|
}
|
|
|
|
func Part2(input structuredInput) int {
|
|
var result = 0
|
|
|
|
var blocks = Part1CreateBlocks(input)
|
|
|
|
var index int
|
|
var freeHost int
|
|
var freeUser int
|
|
var j int
|
|
|
|
for i := len(blocks) - 1; i >= 0; i-- {
|
|
index = getIndex(blocks, i)
|
|
for j := 0; j < index; j++ {
|
|
if blocks[j].free >= blocks[index].length {
|
|
freeHost = blocks[j].free
|
|
freeUser = blocks[index].free
|
|
blocks[j].free = 0
|
|
blocks[index].free = freeHost - blocks[index].length
|
|
blocks = slices.Insert(blocks, j+1, blocks[index])
|
|
blocks[index+1].id = -1
|
|
blocks[index+1].free = freeUser + blocks[index+1].length
|
|
blocks[index+1].length = 0
|
|
break
|
|
}
|
|
}
|
|
}
|
|
|
|
j = 0
|
|
for i := 0; i < len(blocks); i++ {
|
|
for m := 0; m < blocks[i].length; m++ {
|
|
result += j * blocks[i].id
|
|
j++
|
|
}
|
|
j += blocks[i].free
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
func main() {
|
|
var start time.Time
|
|
var elapsed time.Duration = 0
|
|
input, err := LoadInput(FILE_PATH)
|
|
if err != nil {
|
|
fmt.Println("Error loading input:", err)
|
|
return
|
|
}
|
|
|
|
structuredInput := TransformInput(input)
|
|
fmt.Println("Structured Input:", structuredInput)
|
|
|
|
start = time.Now()
|
|
fmt.Println("Solution Part 1: ", Part1(structuredInput))
|
|
elapsed = time.Since(start)
|
|
fmt.Printf("Part 1 took %s\n", elapsed)
|
|
|
|
start = time.Now()
|
|
fmt.Println("Solution Part 2: ", Part2(structuredInput))
|
|
elapsed = time.Since(start)
|
|
fmt.Printf("Part 2 took %s\n", elapsed)
|
|
}
|