AOC-2021/day-10-part2

package main

import (
        "bufio"
        "fmt"
        "os"
        "errors"
)

type Stack struct {
        data       []int
        sp         uint
        size, step uint
}

func NewStack(size, step uint) (stack *Stack, err error) {
        if step == 0 {
                err = errors.New("step can't be 0")
        } else {
                err = nil
                stack = &Stack{
                        data: make([]int, size),
                        size: size,
                        step: step,
                        sp:   0}
        }
        return
}

func grow(s *Stack) {
        tmp := make([]int, s.size)
        copy(tmp, s.data)
        s.size += s.step
        s.data = make([]int, s.size)
        copy(s.data, tmp)
}

func (s *Stack) Push(data int) {
        if s.sp >= s.size {
                grow(s)
        }
        s.data[s.sp] = data
        s.sp++
}

func (s *Stack) Pop() (popped int) {
        s.sp--
        popped = s.data[s.sp]
        return
}

func (s Stack) Peek() int {
        return s.data[s.sp-1]
}

func (s Stack) Dump() {
        for i := uint(0); i < s.sp; i++ {
                fmt.Printf("[%d] %d\n", i, s.data[i])
        }
}


const INITIAL_STACK_SIZE = 5000

const (
        PAREN_OPEN    = iota // 0
        PAREN_CLOSE          // 1
        BRACKET_OPEN         // 2
        BRACKET_CLOSE        // 3
        BRACE_OPEN           // 4
        BRACE_CLOSE          // 5
        AB_OPEN              // AB == angle bracket
        AB_CLOSE             // 7
)

type TokenType int8

func t2s(t TokenType) (str string) {
        switch t {
        case PAREN_OPEN:
                str = "PAREN_OPEN"
        case PAREN_CLOSE:
                str = "PAREN_CLOSE"
        case BRACKET_OPEN:
                str = "BRACKET_OPEN"
        case BRACKET_CLOSE:
                str = "BRACKET_CLOSE"
        case BRACE_OPEN:
                str = "BRACE_OPEN"
        case BRACE_CLOSE:
                str = "BRACE_CLOSE"
        case AB_OPEN:
                str = "AB_OPEN"
        case AB_CLOSE:
                str = "AB_CLOSE"
        default:
                str = "UNKNOWN"
        }
        return
}

func Printfln(format string, a ...interface{}) {
        fmt.Printf(format+"\n", a...)
}

func Printerrfln(format string, a ...interface{}) {
        fmt.Fprintf(os.Stderr, format+"\n", a...)
}

func assert_err(err error) {
        if err != nil {
                panic(err.Error())
        }
}

func scanLine(txt string, linenum int) (l Line) {
        for _, c := range txt {
                switch c {
                case '(':
                        l.types = append(l.types, PAREN_OPEN)
                case ')':
                        l.types = append(l.types, PAREN_CLOSE)
                case '[':
                        l.types = append(l.types, BRACKET_OPEN)
                case ']':
                        l.types = append(l.types, BRACKET_CLOSE)
                case '{':
                        l.types = append(l.types, BRACE_OPEN)
                case '}':
                        l.types = append(l.types, BRACE_CLOSE)
                case '<':
                        l.types = append(l.types, AB_OPEN)
                case '>':
                        l.types = append(l.types, AB_CLOSE)
                default:
                        Printerrfln("ERROR: unknown character '%c' in line %d!", c, linenum)
                        os.Exit(1)
                }
        }
        l.line = linenum
        return
}

func ReadInput(filename string) (lines []Line) {
        f, err := os.Open(filename)
        assert_err(err)
        defer f.Close()

        sc := bufio.NewScanner(f)

        line := 0
        for sc.Scan() {
                txt := sc.Text()
                if txt != "" {
                        lines = append(lines, scanLine(txt, line))
                        line++
                }
        }
        return
}

type Line struct {
        types []TokenType
        line  int
}

func (l Line) Len() int {
        return len(l.types)
}

func (l Line) DumpRaw() {
        Printfln("== line %d ==", l.line)
        for _, t := range l.types {
                fmt.Printf("| %d ", t)
        }
        fmt.Print("|\n")
}

func (l Line) Dump() {
        Printfln("== line %d ==", l.line)
        for _, t := range l.types {
                fmt.Printf("| %s ", t2s(t))
        }
        fmt.Print("|\n")
}

func (l Line) Check() (score int64, ok bool) {
        s, err := NewStack(INITIAL_STACK_SIZE, 2)
        assert_err(err)
        score = 0

        s.Push(-1) // BEGIN
        for _, t := range l.types {
                switch t {
                case PAREN_OPEN:
                        s.Push(PAREN_OPEN)
                case BRACKET_OPEN:
                        s.Push(BRACKET_OPEN)
                case BRACE_OPEN:
                        s.Push(BRACE_OPEN)
                case AB_OPEN:
                        s.Push(AB_OPEN)

                case PAREN_CLOSE:
                        if TokenType(s.Pop()) != PAREN_OPEN {
                                //Printerrfln("ERROR (")
                                ok = false
                                return
                        }
                case BRACKET_CLOSE:
                        if TokenType(s.Pop()) != BRACKET_OPEN {
                                //Printerrfln("ERROR [")
                                ok = false
                                return
                        }
                case BRACE_CLOSE:
                        if TokenType(s.Pop()) != BRACE_OPEN {
                                //Printerrfln("ERROR {")
                                ok = false
                                return
                        }
                case AB_CLOSE:
                        if TokenType(s.Pop()) != AB_OPEN {
                                //Printerrfln("ERROR <")
                                ok = false
                                return
                        }
                }
        }

        t := TokenType(s.Pop())
        for t != -1 {
                //Printfln("pop(): %s", t2s(t))
                score *= 5
                switch t {
                case PAREN_OPEN:
                        score += 1
                case BRACKET_OPEN:
                        score += 2
                case BRACE_OPEN:
                        score += 3
                case AB_OPEN:
                        score += 4
                }
                t = TokenType(s.Pop())
        }

        ok = true
        return
}

func sort(scores []int64) int64 {
        for i := 0; i < len(scores); i++ {
                //fmt.Printf("%ld\n", scores[i]);
                for j := 1; j < len(scores)-i; j++ {
                        if scores[j-1] > scores[j] {
                                tmp := scores[j-1]
                                scores[j-1] = scores[j]
                                scores[j] = tmp
                        }
                }
        }
        for i := 0; i < len(scores); i++ {
                //Printfln("[%d]: %d", i, scores[i])
        }
        return scores[(len(scores)-1)/2]
}

func main() {
        input := ReadInput("input.txt")
        scores := []int64{}

        for i := 0; i < len(input); i++ {
                //input[i].Dump()
                //input[i].DumpRaw()
                if s, ok := input[i].Check(); ok {
                        scores = append(scores, s)
                }
                //fmt.Print("=============\n")
        }
        Printfln("Answer: %d", sort(scores))
}