advent-of-code-2024/day18/blocked.go

package main

import (
    "os"
    "fmt"
    "strings"
    "strconv"
)


// ----------------------------------------
type Direction uint8

const (
    Up    Direction = iota
    Down  Direction = iota
    Left  Direction = iota
    Right Direction = iota
)


// ----------------------------------------
type Position struct {
    coord  [2]uint
    direc Direction
}

func (p Position) StepUnbound(d Direction) Position {
    switch {
        case d == Down: p.coord[1]++
        case d == Up: p.coord[1]--
        case d == Left: p.coord[0]--
        case d == Right: p.coord[0]++
    }
    p.direc = d

    return p
}


// ----------------------------------------
type Maze struct {
    start [2]uint
    end   [2]uint
    field [][]byte
    blocks_added [][2]uint
}

func NewMaze(byte_positions string, bytes_to_load uint, size [2]uint) *Maze {
    /* size = [2]unit{x,y} */

    var maze Maze

    // create board
    maze.field = make([][]byte, 0, size[1] + 2)
    for i := range size[1] + 2 {
        line := make([]byte, size[0] + 2)
        for j := range line {
            if i == 0 || uint(i) == size[1] + 1 || j == 0 || uint(j) == size[0] + 1 {
                line[j] = '#'
            } else {
                line[j] = '.'
            }
        }
        maze.field = append(maze.field, line)
    }

    // add byte corruptions
    maze.blocks_added = make([][2]uint, 0)
    lines := strings.Split(byte_positions, "\n")
    for i, line := range lines {
        if uint(i) >= bytes_to_load { break }
        x, err := strconv.Atoi(strings.Split(line, ",")[0])
        check(err)
        y, err := strconv.Atoi(strings.Split(line, ",")[1])
        check(err)

        maze.field[y + 1][x + 1] = '#'
        maze.blocks_added = append(maze.blocks_added, [2]uint{uint(x + 1), uint(y + 1)})
    }

    // set start/ end
    maze.start = [2]uint{1,1}
    maze.end = size

    return &maze
}

func (m *Maze) Step(pos Position) []Position {
    out := make([]Position, 0, 4)

    if m.field[pos.coord[1] + 1][pos.coord[0]] == '.' && pos.direc != Up {
        out = append(out, pos.StepUnbound(Down))
    }
    if m.field[pos.coord[1] - 1][pos.coord[0]] == '.' && pos.direc != Down {
        out = append(out, pos.StepUnbound(Up))
    }
    if m.field[pos.coord[1]][pos.coord[0] + 1] == '.' && pos.direc != Left {
        out = append(out, pos.StepUnbound(Right))
    }
    if m.field[pos.coord[1]][pos.coord[0] - 1] == '.' && pos.direc != Right {
        out = append(out, pos.StepUnbound(Left))
    }

    return out
}

func (m *Maze) PopCorruptedBlock() [2]uint {
    block := m.blocks_added[len(m.blocks_added)-1]
    m.blocks_added = m.blocks_added[:len(m.blocks_added)-1]

    m.field[block[1]][block[0]] = '.'
    
    return block
}

func (m *Maze) Start() Position {
    return Position{m.start, Right}
}

func (m *Maze) Finished(pos Position) bool {
    return m.end == pos.coord
}

func (m *Maze) Print() {
    for _, line := range m.field {
        fmt.Println(string(line))
    }
}


// ----------------------------------------
type MazeGraph struct {
    cost     uint
    children []*MazeGraph
}

var new_maze_graph_visited map[Position]uint

func NewMazeGraph(m *Maze, start Position, cost uint) *MazeGraph {
    children := make([]*MazeGraph, 0, 3)

    // finish reached?
    if m.Finished(start) { return &MazeGraph{ cost, children } }

    // check for loop
    value, exists := new_maze_graph_visited[start]
    if exists {
        if value <= cost { return nil } 
    }
    new_maze_graph_visited[start] = cost

    // build subgraphs/ children
    for _, position := range m.Step(start) {
        child := NewMazeGraph(m, position, cost + 1)
        if child != nil { children = append(children, child) }
    }

    // found dead end
    if len(children) == 0 { return nil }

    // collapse if there is only one possible way
    if len(children) == 0 { return children[0] }
    
    return &MazeGraph{ cost: cost, children: children }
}

func (graph *MazeGraph) Leaves() []*MazeGraph {
    out := make([]*MazeGraph, 0)

    if len(graph.children) == 0 {
        out = append(out, graph)
        return out
    }

    for _, g := range graph.children {
        out = append(out, g.Leaves()...)
    }
    return out
}

// ----------------------------------------
func check(err error) { if err != nil { panic(err) } }


func main() {
    dat, err := os.ReadFile("data.txt")
    check(err)

    input := strings.TrimSpace(string(dat))
    maze := NewMaze(input, 10e10, [2]uint{71,71})

    // check if paths exits
    var pos [2]uint
    new_maze_graph_visited = make(map[Position]uint)

    for NewMazeGraph(maze, maze.Start(), 0) == nil {
        pos = maze.PopCorruptedBlock()
        new_maze_graph_visited = make(map[Position]uint)
    }

    fmt.Println(pos[0] - 1, ",", pos[1] - 1)
}