advent2022

main.go (5994B)

---

 package main
 
 import (
 	"bufio"
 	"fmt"
 	"log"
 	"os"
 	"sort"
 	"strings"
 )
 
 type Valve struct {
 	name        string
 	rate        int
 	open        bool
 	connections []string
 }
 
 func (v Valve) String() string {
 	return fmt.Sprintf("%s,%d,[%s]", v.name, v.rate,
 		strings.Join(v.connections, ","))
 }
 
 type Step struct {
 	name, parent string
 }
 type Path struct {
 	name    string
 	valve   *Valve
 	path    Strings
 	nested  Paths
 	sumRate int // valve.rate + max(nested rates)
 }
 
 func (p Path) Score() int {
 	return (10 + p.valve.rate) / len(p.path)
 }
 func (p Path) String() string {
 	s := fmt.Sprintf("(%s:%d:%d:%d sum:%d){", p.name,
 		p.valve.rate, len(p.path), p.Score(), p.sumRate)
 	s += strings.Join(p.path, "->")
 	s += "}"
 	if len(p.nested) > 0 {
 		for _, n := range p.nested {
 			s += "~>"
 			s += n.String()
 		}
 	}
 	return s
 }
 
 type Paths []Path
 
 func (ps Paths) String() string {
 	var s string
 	for _, p := range ps {
 		s += p.String() +
 			"\n"
 	}
 	return s
 }
 func (ps Paths) Len() int { return len(ps) }
 func (ps Paths) Swap(i, j int) {
 	ps[i], ps[j] = ps[j], ps[i]
 }
 func (ps Paths) Less(i, j int) bool {
 	//return ps[i].valve.rate > ps[j].valve.rate
 	/*if ps[i].sumRate == ps[j].sumRate { return len(ps[i].path) < len(ps[j].path)
 	}*/
 	return ps[i].sumRate > ps[j].sumRate
 }
 func (ps Paths) Find(name string) *Path {
 	for _, p := range ps {
 		if p.name == name {
 			return &p
 		}
 	}
 	return nil
 }
 
 type Valves map[string]*Valve
 
 func (vs Valves) SumRates(names Strings) int {
 	sum := 0
 	for _, n := range names {
 		sum += vs[n].rate
 	}
 	return sum
 }
 func (vs Valves) String() string {
 	var out string
 	for k, v := range vs {
 		out += "[" + k + "]:" + v.String() + "\n"
 	}
 	return out
 }
 
 func (vs Valves) FindRoutes(start string, steps int, visited Strings) Paths {
 	steps--
 	// opening the valve costs 1
 	if steps <= 1 {
 		//fmt.Println("route exhausted")
 		return Paths{}
 	}
 	visited = append(visited, start)
 	paths := vs.GetPaths(start, visited, steps+1)
 	//fmt.Println("FindRoutes", steps, start) fmt.Println(paths)
 	for i, p := range paths {
 		paths[i].sumRate = paths[i].valve.rate * steps
 		paths[i].nested = vs.FindRoutes(p.name, steps-len(p.path), visited)
 		if len(paths[i].nested) > 0 {
 			sort.Sort(paths[i].nested)
 			paths[i].sumRate += paths[i].nested[0].sumRate
 		}
 	}
 
 	return paths
 }
 func (vs Valves) FindPath(start, end string) (Path, bool) {
 	var path Path
 	path.valve = vs[end]
 	path.name = end
 	var upcoming []Step
 	visited := make(map[string]string) // name:parent
 
 	upcoming = append(upcoming, Step{name: start, parent: ""})
 	for len(upcoming) > 0 {
 		cur := upcoming[0].name
 		parent := upcoming[0].parent
 		upcoming = upcoming[1:]
 		if _, exists := visited[cur]; exists {
 			continue
 		}
 		visited[cur] = parent
 		for _, s := range vs[cur].connections {
 			if _, exists := visited[s]; !exists {
 				if s == end {
 					path.path = append(path.path, s, cur)
 					if parent != "" {
 						path.path = append(path.path, parent)
 					}
 					c := parent
 					for c != "" {
 						c = visited[c]
 						if c != "" {
 							path.path = append(path.path, c)
 						}
 					}
 					return path, true
 				} else {
 					upcoming = append(upcoming, Step{name: s, parent: cur})
 				}
 			}
 		}
 	}
 
 	return path, false
 }
 
 func (vs Valves) GetPaths(start string, excluded Strings, limit int) Paths {
 	var paths Paths
 	for _, v := range vs {
 		if v.name == start || v.open || v.rate == 0 || excluded.Has(v.name) {
 			continue
 		}
 		if p, found := vs.FindPath(start, v.name); found && (len(p.path) <= limit) {
 			paths = append(paths, p)
 		} else {
 			//log.Fatal("no path:", start, v.name)
 		}
 	}
 	sort.Sort(paths)
 	return paths
 }
 
 type Strings []string
 
 func (ss Strings) Has(s string) bool {
 	for _, s1 := range ss {
 		if s1 == s {
 			return true
 		}
 	}
 	return false
 }
 func main() {
 	if len(os.Args) > 1 {
 		day16(os.Args[1])
 	} else if len(os.Args) == 1 {
 		fmt.Printf("usage: %s inputfile.txt\n", os.Args[0])
 	} else {
 		fmt.Println("No input data")
 	}
 }
 
 func day16(input_file string) {
 	fmt.Printf("day 16 input filename: %s\n", input_file)
 	input, err := os.Open(input_file)
 	if err != nil {
 		log.Fatal(err)
 	}
 	defer input.Close()
 	valves := make(Valves)
 	scanner := bufio.NewScanner(input)
 	for scanner.Scan() {
 		in := scanner.Text()
 		in1, in2, found := strings.Cut(in, "; ")
 		if !found {
 			log.Fatal("parsing error")
 		}
 		var vname string
 		var vrate int
 		cnt, err := fmt.Sscanf(in1, "Valve %s has flow rate=%d", &vname, &vrate)
 		if cnt != 2 || err != nil {
 			log.Fatal("parsing error:", err)
 		}
 		in2s := strings.SplitN(in2, " ", 5)
 		conns_s := in2s[4]
 		conns := strings.Split(conns_s, ", ")
 
 		valves[vname] = &Valve{name: vname, rate: vrate, connections: conns}
 
 	}
 	if err = scanner.Err(); err != nil {
 		log.Fatal(err)
 	}
 
 	//fmt.Print(valves)
 
 	paths := valves.FindRoutes("AA", 29, Strings{})
 	//fmt.Println("FindRoutes path:", paths)
 	var pathway Strings
 	sort.Sort(paths)
 	/*for _, p:=range paths{
 		fmt.Println(p.sumRate)
 	}*/
 	p := &paths[0]
 	for {
 		pathway = append(pathway, p.name)
 		//fmt.Println(p.sumRate)
 		if len(p.nested) > 0 {
 			sort.Sort(p.nested)
 			p = &p.nested[0]
 		} else {
 			break
 		}
 	}
 	fmt.Println(pathway)
 
 	rate := 0
 	pressure := 0
 	v := valves["AA"]
 	for i := 1; i <= 30; {
 		//paths := valves.GetPaths(v.name, Strings{}) fmt.Println("~~~>", v.name)
 		//fmt.Println(paths)
 		if len(pathway) > 0 {
 			//left := 30 - i
 			path, _ := valves.FindPath(v.name, pathway[0])
 			plen := len(path.path)
 			pathway = pathway[1:]
 			fmt.Printf("%s -> %s (%d)\n", v.name, path.name, plen)
 			//fmt.Println(path)
 			pressure += rate * plen
 			i += plen - 1
 			v = valves[path.name]
 			v.open = true
 			rate += v.rate
 			fmt.Printf("[%d] rate:%d, pressure:%d\n", i, rate, pressure)
 		} else {
 			//fmt.Printf("[%d] no more paths\n", i)
 			pressure += rate
 		}
 		i++
 		//fmt.Println("===============")
 	}
 	fmt.Printf("rate:%d, pressure:%d\n", rate, pressure)
 }
 
 //2591 too high
 //1634 too low
 //2096 too low
 //2128 wrong
 //2342 wrong
 //2297 wrong