adventofcode/2022/day13/main.go

package main

import (
	"fmt"
	"math"
	"sort"
	"strings"

	h "git.bullercodeworks.com/brian/adventofcode/helpers"
)

func main() {
	inp := h.StdinToStringSlice()
	part1(inp)
	fmt.Println()
	part2(inp)
}

func part1(inp []string) {
	commCount := 1
	var result int
	for i := 0; i < len(inp); i++ {
		if inp[i] == "" {
			commCount++
			continue
		}
		pck1 := NewPacket(inp[i])
		i++
		pck2 := NewPacket(inp[i])
		if !pck1.GreaterThan(pck2) {
			result += commCount
		}
	}
	fmt.Println("# Part 1")
	fmt.Println("Sum:", result)
}

func part2(inp []string) {
	var packets []*Packet
	for i := 0; i < len(inp); i++ {
		if inp[i] == "" {
			continue
		}
		packets = append(packets, NewPacket(inp[i]))
	}
	div1, div2 := "[[2]]", "[[6]]"
	var div1Idx, div2Idx int
	packets = append(packets, NewPacket(div1))
	packets = append(packets, NewPacket(div2))
	sort.Slice(packets, func(i, j int) bool {
		return packets[j].GreaterThan(packets[i])
	})
	for i := range packets {
		if packets[i].raw == div1 {
			div1Idx = i + 1
		} else if packets[i].raw == div2 {
			div2Idx = i + 1
		}
	}

	fmt.Println("# Part 2")
	fmt.Println("Decoder Key:", (div1Idx * div2Idx))
}

var outIndent int
var debug bool

func out(o string) {
	if debug {
		fmt.Printf("%s%s\n", strings.Repeat(" ", outIndent), o)
	}
}

type Value struct {
	raw  string
	Val  int
	List *ValueList
}

func NewValue() *Value {
	return &Value{
		Val: math.MinInt,
	}
}
func (v *Value) Equals(v2 *Value) bool {
	if v.IsInt() && v2.IsInt() {
		return v.Val == v2.Val
	} else if !v.IsInt() && !v2.IsInt() {
		return v.List.Equals(v2.List)
	} else {
		// One is a list and the other is not
		if v.IsInt() {
			wrkV := NewValue()
			wrkV.List = NewValueListFrom(v)
			return wrkV.Equals(v2)
		} else {
			wrkV := NewValue()
			wrkV.List = NewValueListFrom(v2)
			return v.Equals(wrkV)
		}
	}
}
func (v *Value) GreaterThan(v2 *Value) bool {
	outIndent++
	if v.IsInt() && v2.IsInt() {
		// Both are ints, which is greater?
		out(fmt.Sprintf("Comparing: %v >? %v", v.Val, v2.Val))
		outIndent--
		return v.Val > v2.Val
	} else if !v.IsInt() && !v2.IsInt() {
		// Both are lists, check values in order
		out(fmt.Sprintf("Comparing Lists: %v >? %v", v.List, v2.List))
		tst := v.List.GreaterThan(v2.List)
		outIndent--
		return tst
	} else {
		// One is a list and the other is not
		out(fmt.Sprintf("Comparing Different Types: %v >? %v", v, v2))
		if v.IsInt() {
			wrkV := NewValue()
			wrkV.List = NewValueListFrom(v)
			tst := wrkV.GreaterThan(v2)
			outIndent--
			return tst
		} else {
			wrkV := NewValue()
			wrkV.List = NewValueListFrom(v2)
			tst := v.GreaterThan(wrkV)
			outIndent--
			return tst
		}
	}
}
func (v *Value) IsInt() bool { return v.Val != math.MinInt }
func (v Value) String() string {
	if v.Val != math.MinInt {
		return fmt.Sprintf("{%d}", v.Val)
	} else {
		ret := "{["
		for i := range *v.List {
			ret = fmt.Sprintf("%s%s,", ret, (*v.List)[i].String())
		}
		ret = strings.TrimSuffix(ret, ",")
		return fmt.Sprintf("%s]}", ret)
	}
}

type ValueList []*Value

func NewValueListFrom(vals ...*Value) *ValueList {
	ret := ValueList{}
	for i := range vals {
		ret.Add(vals[i])
	}
	return &ret
}
func (vl *ValueList) Add(v *Value) {
	*vl = append(*vl, v)
}
func (vl *ValueList) Equals(vl2 *ValueList) bool {
	wrk1, wrk2 := []*Value(*vl), []*Value(*vl2)
	if len(wrk1) != len(wrk2) {
		return false
	}
	for i := range wrk1 {
		v1, v2 := wrk1[i], wrk2[i]
		if !v1.Equals(v2) {
			return false
		}
	}
	return true
}
func (vl *ValueList) GreaterThan(vl2 *ValueList) bool {
	wrk1, wrk2 := []*Value(*vl), []*Value(*vl2)
	out(fmt.Sprintf("Comparing Lists: %v >? %v", wrk1, wrk2))
	for i := range wrk1 {
		var v1, v2 *Value
		v1 = wrk1[i]
		if len(wrk2) > i {
			v2 = wrk2[i]
		} else {
			// vl is greater (has more items)
			return true
		}
		if v1.GreaterThan(v2) {
			out("v1 is greater than v2")
			return true
		} else if v2.GreaterThan(v1) {
			return false
		}
	}
	if len(wrk2) < len(wrk1) {
		return true
	}
	return false
}

type Packet struct {
	raw string
	Val *Value
}

func (p *Packet) GreaterThan(p2 *Packet) bool {
	return p.Val.GreaterThan(p2.Val)
}
func (p Packet) String() string {
	return fmt.Sprintf("[%v]", p.Val)
}
func NewPacket(inp string) *Packet {
	p := Packet{
		raw: inp,
		Val: NewValue(),
	}
	p.Val.List = ParsePacketList(inp)
	return &p
}

func ParsePacketList(inp string) *ValueList {
	if inp[0] != '[' {
		return &ValueList{}
	}
	// parse all string tokens (at depth 1) through to the closing ']'
	var tokens []string
	tokenStart := 1
	var depth int
	for i := 0; i < len(inp); i++ {
		if inp[i] == ',' && depth == 1 {
			// Token break
			tokens = append(tokens, inp[tokenStart:i])
			tokenStart = i + 1
		}
		if inp[i] == '[' {
			depth++
		}
		if inp[i] == ']' {
			depth--
		}
		if depth == 0 {
			if len(inp[tokenStart:i]) > 0 {
				tokens = append(tokens, inp[tokenStart:i])
				tokenStart = i + 1
			}
			break
		}
	}
	// Now parse all tokens and add to the list
	ret := NewValueListFrom()
	for i := range tokens {
		ret.Add(ParsePacketValue(tokens[i]))
	}
	return ret
}

// Parse a value out of the given string
func ParsePacketValue(inp string) *Value {
	var rem string
	v := NewValue()
	if inp[0] == '[' {
		// It's a list
		list := ParsePacketList(inp)
		v.raw = strings.TrimSuffix(inp, rem)
		v.List = list
	} else {
		// It's an integer
		sep := strings.IndexAny(inp, ",]")
		var wrk string
		if sep >= 0 {
			wrk = inp[:sep]
			rem = inp[sep+1:]
		} else {
			wrk = inp
			rem = ""
		}
		v.Val = h.Atoi(wrk)
	}
	return v
}