155 lines
3.4 KiB
Go
155 lines
3.4 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"strconv"
|
|
"strings"
|
|
)
|
|
|
|
type Inode struct {
|
|
fileId int // inode with id -1 are empty
|
|
length int
|
|
}
|
|
|
|
func (inode *Inode) String() string {
|
|
v := ""
|
|
if inode.fileId < 0 {
|
|
v = "."
|
|
} else {
|
|
v = strconv.Itoa(inode.fileId)
|
|
}
|
|
return strings.Repeat(v, inode.length)
|
|
}
|
|
|
|
func (inode *Inode) IsFreeSpace() bool {
|
|
return inode.fileId < 0
|
|
}
|
|
|
|
func (inode *Inode) Copy() *Inode {
|
|
return &Inode{inode.fileId, inode.length}
|
|
}
|
|
|
|
type FileSystem struct {
|
|
inodes *DoubleLinkedList[*Inode]
|
|
}
|
|
|
|
func (fs *FileSystem) String() string {
|
|
ret := ""
|
|
for inode := range fs.inodes.Iter() {
|
|
ret += inode.String()
|
|
}
|
|
return ret
|
|
|
|
}
|
|
|
|
func (fs *FileSystem) CheckSum() int {
|
|
ret, idx := 0, 0
|
|
for inode := range fs.inodes.Iter() {
|
|
if inode.IsFreeSpace() {
|
|
idx += inode.length
|
|
continue
|
|
}
|
|
for j := 0; j < inode.length; j++ {
|
|
ret = ret + idx*inode.fileId
|
|
idx++
|
|
}
|
|
}
|
|
return ret
|
|
}
|
|
|
|
func parseString(s string) *FileSystem {
|
|
dll := NewDLL[*Inode]()
|
|
inode := &Inode{-1, 0}
|
|
for _, c := range s {
|
|
fileId := -1
|
|
|
|
if c != '.' {
|
|
fileId, _ = strconv.Atoi(string(c))
|
|
}
|
|
if inode.fileId == fileId {
|
|
inode.length += 1
|
|
} else {
|
|
dll.InsertLast(inode)
|
|
inode = &Inode{fileId, 1}
|
|
}
|
|
}
|
|
dll.InsertLast(inode)
|
|
if inode, ok := dll.Last(); !ok || !inode.IsFreeSpace() {
|
|
dll.InsertLast(&Inode{-1, 0})
|
|
}
|
|
return &FileSystem{dll}
|
|
}
|
|
|
|
func parseInput(input string) *FileSystem {
|
|
dll := NewDLL[*Inode]()
|
|
id := 0
|
|
for i, c := range input {
|
|
var inode *Inode
|
|
length, _ := strconv.Atoi(string(c))
|
|
if isFreeSpace := i%2 == 1; isFreeSpace {
|
|
inode = &Inode{-1, length}
|
|
} else {
|
|
inode = &Inode{id, length}
|
|
id++
|
|
}
|
|
dll.InsertLast(inode)
|
|
}
|
|
if inode, ok := dll.Last(); !ok || !inode.IsFreeSpace() {
|
|
dll.InsertLast(&Inode{-1, 0})
|
|
}
|
|
return &FileSystem{dll}
|
|
}
|
|
|
|
func (fs *FileSystem) takeFilesFromTheEnd(id DllId) *Inode {
|
|
for node, ok := fs.inodes.nodes[fs.inodes.LastNode]; ok; node, ok = fs.inodes.nodes[node.PreviousId] {
|
|
if node.Id == id {
|
|
break
|
|
}
|
|
if inode, _ := fs.inodes.GetById(node.Id); !inode.IsFreeSpace() && inode.length > 0 {
|
|
return inode
|
|
}
|
|
}
|
|
return nil
|
|
}
|
|
|
|
func (fs *FileSystem) OptimizeDiskFragmentation() {
|
|
emptySpaceAtTheEndId, _ := fs.inodes.LastId()
|
|
emptySpaceAtTheEnd, _ := fs.inodes.Last()
|
|
for discId, ok := fs.inodes.FirstId(); ok; discId, ok = fs.inodes.NextId(discId) {
|
|
freeSpaceInode, _ := fs.inodes.GetById(discId)
|
|
if !freeSpaceInode.IsFreeSpace() || discId == emptySpaceAtTheEndId {
|
|
continue
|
|
}
|
|
fileInodeAtTheEnd := fs.takeFilesFromTheEnd(discId)
|
|
if fileInodeAtTheEnd == nil {
|
|
break
|
|
}
|
|
|
|
if freeSpaceInode.length <= fileInodeAtTheEnd.length {
|
|
newInode := &Inode{fileInodeAtTheEnd.fileId, freeSpaceInode.length}
|
|
fs.inodes.InsertBefore(discId, newInode)
|
|
emptySpaceAtTheEnd.length += freeSpaceInode.length
|
|
fileInodeAtTheEnd.length -= freeSpaceInode.length
|
|
freeSpaceInode.length = 0
|
|
} else {
|
|
newFreeSpaceInode := &Inode{-1, freeSpaceInode.length - fileInodeAtTheEnd.length}
|
|
fs.inodes.InsertAfter(discId, newFreeSpaceInode)
|
|
fs.inodes.InsertBefore(discId, fileInodeAtTheEnd.Copy())
|
|
emptySpaceAtTheEnd.length += fileInodeAtTheEnd.length
|
|
fileInodeAtTheEnd.length = 0
|
|
freeSpaceInode.length = 0
|
|
}
|
|
}
|
|
}
|
|
|
|
func Question9A(input string) int {
|
|
fs := parseInput(input)
|
|
fs.OptimizeDiskFragmentation()
|
|
return fs.CheckSum()
|
|
}
|
|
|
|
func main() {
|
|
fmt.Println("The answer to question 9A is: ", Question9A(realInput))
|
|
|
|
}
|