advent2022/solutions/day13/day13.go

package day13

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strings"
)

type Element struct {
	isNumber bool
	number   int
	sublist  []Element
}

func parseElement(line string) (retval Element, remainder string, err error) {
	line = strings.TrimSpace(line)
	//fmt.Printf("Working on line: '%s'\n", line)
	if line[0] == '[' {
		sublist := []Element{}

		if line[1] == ']' {
			retval = Element{false, 0, sublist}
			remainder = line[2:]
			return
		}

		work := line[1:]
		for {
			element, rest, suberr := parseElement(work)
			//fmt.Println("Back from subcall with element", element, "rest", rest, "suberr", suberr)
			if suberr != nil {
				err = fmt.Errorf("suberror: %s", suberr)
				return
			}
			sublist = append(sublist, element)
			if rest[0] == ',' {
				work = rest[1:]
			} else if rest[0] == ']' {
				work = rest[1:]
				break
			} else {
				err = fmt.Errorf("don't know how to deal with list that ends with '%s'", rest)
				return
			}
		}

		retval = Element{false, 0, sublist}
		remainder = work
		return
	} else if line[0] >= '0' && line[0] <= '9' {
		var computed int

		for computed = 0; line[0] >= '0' && line[0] <= '9'; line = line[1:] {
			computed = (computed * 10) + int(line[0]-'0')
		}

		retval = Element{true, computed, nil}
		remainder = line
		return
	} else {
		err = fmt.Errorf("panic: Don't know how to parse line element '%s'", line)
		return
	}
}

func renderElement(element Element) string {
	if element.isNumber {
		return fmt.Sprintf("%d", element.number)
	} else {
		retval := "["

		if len(element.sublist) > 0 {
			retval += renderElement(element.sublist[0])
		}

		for i := 1; i < len(element.sublist); i++ {
			retval += fmt.Sprintf(",%s", renderElement(element.sublist[i]))
		}

		retval += "]"
		return retval
	}
}

type OrderResult int

const (
	ProperlyOrdered OrderResult = iota
	ImproperlyOrdered
	Unknown
)

func compareElements(a Element, b Element) OrderResult {
	if a.isNumber && b.isNumber {
		return compareNumbers(a.number, b.number)
	} else if a.isNumber && !b.isNumber {
		return compareLists([]Element{{true, a.number, nil}}, b.sublist)
	} else if !a.isNumber && b.isNumber {
		return compareLists(a.sublist, []Element{{true, b.number, nil}})
	} else {
		return compareLists(a.sublist, b.sublist)
	}
}

func compareNumbers(a int, b int) OrderResult {
	if a < b {
		return ProperlyOrdered
	}

	if a > b {
		return ImproperlyOrdered
	}

	return Unknown
}

func compareLists(a []Element, b []Element) OrderResult {
	if len(a) > 0 && len(b) > 0 {
		headResult := compareElements(a[0], b[0])

		if headResult != Unknown {
			return headResult
		}

		return compareLists(a[1:], b[1:])
	}

	if len(a) == 0 && len(b) == 0 {
		return Unknown
	}

	if len(a) == 0 {
		return ProperlyOrdered
	}

	return ImproperlyOrdered
}

func Run(filename string) {
	file, err := os.Open(filename)

	if err != nil {
		fmt.Println("Error opening file:", err)
		return
	}

	scanner := bufio.NewScanner(file)
	scanner.Split(bufio.ScanLines)
	elements := []Element{}

	for scanner.Scan() {
		line := scanner.Text()
		if len(line) == 0 {
			continue
		}
		element, remainder, err := parseElement(line)
		if err != nil {
			fmt.Println(err)
			return
		}
		if len(remainder) > 0 {
			fmt.Printf("Unexpected remainder in line: '%s'\n", remainder)
			return
		}
		fmt.Println("Parsed element", renderElement(element))
		elements = append(elements, element)
	}

	total := 0
	for i := 0; i < len(elements); i += 2 {
		index := i/2 + 1
		switch compareElements(elements[i], elements[i+1]) {
		case ProperlyOrdered:
			fmt.Printf("Pair #%d is properly ordered\n", index)
			total += index
		case ImproperlyOrdered:
			fmt.Printf("Pair #%d is NOT properly ordered\n", index)
		case Unknown:
			fmt.Printf("Pair #%d is UNKNOWN\n", index)
		default:
			fmt.Printf("PANIC PANIC PANIC: Unknown ordering?!\n")
		}
	}
	fmt.Println("\nTotal proper index value is", total)

	divider2, _, _ := parseElement("[[2]]")
	divider6, _, _ := parseElement("[[6]]")
	elements = append(elements, divider2, divider6)

	sort.SliceStable(elements, func(i, j int) bool {
		return compareElements(elements[i], elements[j]) == ProperlyOrdered
	})

	fmt.Println()
	fmt.Println("Sorted order:")
	decoderKey := 1
	for i := 0; i < len(elements); i++ {
		fmt.Println(renderElement(elements[i]))
		if compareElements(elements[i], divider2) == Unknown || compareElements(elements[i], divider6) == Unknown {
			decoderKey *= i + 1
		}
	}
	fmt.Println("Decoder key is", decoderKey)

	file.Close()
}