adventofcode/2020/day16.go

package main

import (
	"fmt"
	"log"
	"os"
	"regexp"
	"strings"

	"git.annabunch.es/annabunches/adventofcode/2020/lib/util"
)

const (
	FIELDS = iota
	MY_TICKET
	OTHER_TICKETS
)

type Field struct {
	Name    string
	Min1    int
	Min2    int
	Max1    int
	Max2    int
	Index   int
	Indexes map[int]bool
}

func parseInput(input []string) ([]*Field, []int, [][]int) {
	fields := make([]*Field, 0)
	myTicket := make([]int, 0)
	otherTickets := make([][]int, 0)

	state := FIELDS
	re := regexp.MustCompile("^(.*): ([0-9]+)-([0-9]+) or ([0-9]+)-([0-9]+)$")

	for _, line := range input {
		if line == "your ticket:" {
			state = MY_TICKET
			continue
		} else if line == "nearby tickets:" {
			state = OTHER_TICKETS
			continue
		} else if line == "" {
			continue
		}

		switch state {
		case FIELDS:
			data := re.FindAllStringSubmatch(line, 32)
			field := &Field{
				Name:    data[0][1],
				Min1:    util.MustAtoi(data[0][2]),
				Max1:    util.MustAtoi(data[0][3]),
				Min2:    util.MustAtoi(data[0][4]),
				Max2:    util.MustAtoi(data[0][5]),
				Index:   -1,
				Indexes: make(map[int]bool),
			}
			fields = append(fields, field)
		case MY_TICKET:
			for _, num := range strings.Split(line, ",") {
				myTicket = append(myTicket, util.MustAtoi(num))
			}
		case OTHER_TICKETS:
			ticket := make([]int, 0)
			for _, num := range strings.Split(line, ",") {
				ticket = append(ticket, util.MustAtoi(num))
			}
			otherTickets = append(otherTickets, ticket)
		}
	}

	return fields, myTicket, otherTickets
}

func makeValidValueMap(fields []*Field) map[int]bool {
	valid := make(map[int]bool)
	for _, field := range fields {
		for i := field.Min1; i <= field.Max1; i++ {
			valid[i] = true
		}
		for i := field.Min2; i <= field.Max2; i++ {
			valid[i] = true
		}
	}
	return valid
}

func findInvalidValues(fields []*Field, tickets [][]int) []int {
	answers := make([]int, 0)

	// make a map of all valid values
	valid := makeValidValueMap(fields)

	for _, ticket := range tickets {
		for _, value := range ticket {
			if _, ok := valid[value]; !ok {
				answers = append(answers, value)
			}
		}
	}

	return answers
}

func removeInvalidTickets(fields []*Field, tickets [][]int) [][]int {
	answers := make([][]int, 0)
	valid := makeValidValueMap(fields)

	for _, ticket := range tickets {
		badTicket := false
		for _, value := range ticket {
			if _, ok := valid[value]; !ok {
				badTicket = true
			}
		}
		if !badTicket {
			answers = append(answers, ticket)
		}
	}

	return answers
}

// sets the indexes in place
func findIndexes(fields []*Field, tickets [][]int) {
	for _, field := range fields {
		for i := 0; i < len(fields); i++ {
			field.Indexes[i] = true
		}
	}

	for _, ticket := range tickets {
		for i, num := range ticket {
			for _, f := range fields {
				if f.Indexes[i] && !((num >= f.Min1 && num <= f.Max1) ||
					(num >= f.Min2 && num <= f.Max2)) {
					// this field cannot be in this space
					f.Indexes[i] = false
				}
			}
		}
	}

	unique := false
	for !unique {
		unique = true
		for _, field := range fields {
			if field.Index != -1 {
				continue
			}

			found := make([]int, 0)
			for index, valid := range field.Indexes {
				if valid {
					found = append(found, index)
				}
			}
			if len(found) == 0 {
				log.Panicf("Failed to find any solution for field %s: %v", field.Name, field.Indexes)
			}
			if len(found) == 1 {
				field.Index = found[0]
			}
		}

		// now weed out duplicates
		for _, field := range fields {
			// any field we're certain of we can set to false on all fields
			if field.Index != -1 {
				for _, subField := range fields {
					subField.Indexes[field.Index] = false
				}
			} else {
				// any field we haven't set an Index for means it is still potentially ambiguous
				unique = false
			}
		}
	}
}

func mulDepartureFields(fields []*Field, ticket []int) int {
	product := 1
	for _, field := range fields {
		if strings.Contains(field.Name, "departure") {
			product *= ticket[field.Index]
		}
	}
	return product
}

// 980 too low
func main() {
	step := os.Args[1]
	values := util.InputParserStrings(os.Args[2])

	fields, myTicket, otherTickets := parseInput(values)

	switch step {
	case "1":
		invalidValues := findInvalidValues(fields, otherTickets)
		total := 0
		for _, value := range invalidValues {
			total += value
		}
		fmt.Println(total)

	case "2":
		otherTickets = removeInvalidTickets(fields, otherTickets)
		findIndexes(fields, otherTickets)
		fmt.Println(mulDepartureFields(fields, myTicket))
	}
}