commit e45241ffc2509f27bcd841269a3a101305d14927
parent 768cb5c7831dda700d425cf2cef81dfa88cd7c32
Author: bsandro <email@bsandro.tech>
Date: Fri, 16 Dec 2022 16:56:04 +0000
Day 16 part 1 - working sample, non-working input
Diffstat:
3 files changed, 296 insertions(+), 0 deletions(-)
diff --git a/day16/input.txt b/day16/input.txt
@@ -0,0 +1,57 @@
+Valve ED has flow rate=0; tunnels lead to valves PS, AW
+Valve SI has flow rate=0; tunnels lead to valves AA, HX
+Valve LX has flow rate=22; tunnels lead to valves DY, YH
+Valve CR has flow rate=0; tunnels lead to valves BE, HX
+Valve BI has flow rate=0; tunnels lead to valves GC, AY
+Valve PB has flow rate=4; tunnels lead to valves IX, YG, RI, KR, BV
+Valve YY has flow rate=0; tunnels lead to valves PH, GJ
+Valve PH has flow rate=11; tunnels lead to valves YY, VE, ZG, MM
+Valve DY has flow rate=0; tunnels lead to valves LX, AW
+Valve SD has flow rate=0; tunnels lead to valves AY, EC
+Valve SV has flow rate=24; tunnels lead to valves CC, GF
+Valve RL has flow rate=0; tunnels lead to valves OW, IN
+Valve GF has flow rate=0; tunnels lead to valves RQ, SV
+Valve BE has flow rate=5; tunnels lead to valves CR, JC, MF, IT
+Valve PR has flow rate=0; tunnels lead to valves BV, GJ
+Valve AW has flow rate=21; tunnels lead to valves VE, DY, TR, ED
+Valve FY has flow rate=17; tunnels lead to valves GG, KJ
+Valve GC has flow rate=0; tunnels lead to valves BI, GJ
+Valve RI has flow rate=0; tunnels lead to valves PB, AY
+Valve RQ has flow rate=0; tunnels lead to valves HH, GF
+Valve IT has flow rate=0; tunnels lead to valves MZ, BE
+Valve XG has flow rate=0; tunnels lead to valves BL, AA
+Valve MK has flow rate=0; tunnels lead to valves HX, DV
+Valve IX has flow rate=0; tunnels lead to valves PB, JC
+Valve BV has flow rate=0; tunnels lead to valves PR, PB
+Valve TR has flow rate=0; tunnels lead to valves CD, AW
+Valve PS has flow rate=0; tunnels lead to valves ED, AY
+Valve HH has flow rate=12; tunnels lead to valves RQ, NL, ZQ
+Valve AA has flow rate=0; tunnels lead to valves KR, SI, XG, EC, ZG
+Valve FT has flow rate=0; tunnels lead to valves IN, YH
+Valve YG has flow rate=0; tunnels lead to valves PB, HX
+Valve HX has flow rate=14; tunnels lead to valves MK, ZQ, YG, SI, CR
+Valve DV has flow rate=0; tunnels lead to valves MK, QR
+Valve GJ has flow rate=3; tunnels lead to valves PR, CD, YY, GC, BL
+Valve BL has flow rate=0; tunnels lead to valves GJ, XG
+Valve CD has flow rate=0; tunnels lead to valves TR, GJ
+Valve GG has flow rate=0; tunnels lead to valves FY, NL
+Valve JC has flow rate=0; tunnels lead to valves IX, BE
+Valve JN has flow rate=0; tunnels lead to valves OW, QR
+Valve RM has flow rate=18; tunnel leads to valve KJ
+Valve NL has flow rate=0; tunnels lead to valves GG, HH
+Valve QR has flow rate=20; tunnels lead to valves CC, DV, PN, JN
+Valve ZG has flow rate=0; tunnels lead to valves AA, PH
+Valve AY has flow rate=6; tunnels lead to valves RI, PS, SD, BI, MM
+Valve VE has flow rate=0; tunnels lead to valves PH, AW
+Valve OW has flow rate=25; tunnels lead to valves MZ, RL, JN
+Valve MM has flow rate=0; tunnels lead to valves AY, PH
+Valve KJ has flow rate=0; tunnels lead to valves RM, FY
+Valve MF has flow rate=0; tunnels lead to valves BE, PN
+Valve YH has flow rate=0; tunnels lead to valves LX, FT
+Valve ZQ has flow rate=0; tunnels lead to valves HX, HH
+Valve KR has flow rate=0; tunnels lead to valves AA, PB
+Valve PN has flow rate=0; tunnels lead to valves MF, QR
+Valve CC has flow rate=0; tunnels lead to valves SV, QR
+Valve MZ has flow rate=0; tunnels lead to valves OW, IT
+Valve EC has flow rate=0; tunnels lead to valves SD, AA
+Valve IN has flow rate=16; tunnels lead to valves RL, FT
diff --git a/day16/main.go b/day16/main.go
@@ -0,0 +1,229 @@
+package main
+
+import (
+ "strings"
+ "bufio"
+ "fmt"
+ "log"
+ "os"
+ "sort"
+)
+
+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 []string
+}
+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){", p.name, p.valve.rate, len(p.path),p.Score())
+ s += strings.Join(p.path, "->")
+ s += "}"
+ 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 {
+ if ps[i].Score() == ps[j].Score() {
+ return len(ps[i].path) < len(ps[j].path)
+ } else {
+ return ps[i].Score() > ps[j].Score()
+ }
+}
+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) String() string {
+ var out string
+ for k,v := range vs {
+ out += "["+k+"]:"+v.String()+"\n"
+ }
+ return out
+}
+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 start=="BB"&& end=="JJ"{
+ // fmt.Printf("(bb->jj) cur %s, trying nested %s\n", cur,s)
+ //}
+ if s == end {
+ //fmt.Println("start,end,s,cur,parent:", start,end,s,cur,parent)
+ //fmt.Println("visited:",visited)
+ // unwind
+ // parent <- cur < s
+ path.path = append(path.path, s, cur)
+ if parent!="" {
+ path.path = append(path.path, parent)
+ }
+ c:=parent//visited[parent]
+ for c!="" {
+ c=visited[c]
+ if c!="" {
+ path.path = append(path.path, c)
+ }
+ }
+ //if start=="BB"&& end=="JJ"{
+ //fmt.Println("path:", start, end, path.path)
+ //}
+ return path, true
+ } else {
+ upcoming = append(upcoming, Step{name:s,parent:cur})
+ }
+ }
+ }
+ }
+
+ return path, false
+}
+func (vs Valves) GetPaths(start string) Paths {
+ var paths Paths
+ for _,v:= range vs {
+ if v.name==start || v.open || v.rate == 0 { continue }
+ if p,found:=vs.FindPath(start,v.name);found{
+ 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)
+ fmt.Println("--------")
+
+ rate:=0
+ pressure:=0
+ v:=valves["AA"]
+ for i:=1;i<=30;{
+ paths:=valves.GetPaths(v.name)
+ //fmt.Println("~~~>", v.name)
+ //fmt.Println(paths)
+ if len(paths) > 0 {
+ left:=30-i
+ var path *Path
+ for j, p := range paths {
+ if len(p.path) <= left {
+ path = &paths[j]
+ break
+ }
+ }
+ if path == nil {
+ break
+ }
+ //path:=paths[0]
+ fmt.Printf("%s -> %s (%d)\n", v.name, path.name, len(path.path))
+ //fmt.Println(path)
+ pressure+=rate*(len(path.path))
+ i+=len(path.path)-1
+ v=valves[path.name]
+ v.open = true
+ rate+=v.rate
+ fmt.Printf("[%d] rate:%d, pressure:%d\n", i, rate, pressure)
+ i++
+ } else {
+ //fmt.Printf("[%d] no more paths\n", i)
+ i++
+ pressure+=rate
+ }
+ //fmt.Println("===============")
+ }
+ fmt.Printf("rate:%d, pressure:%d\n", rate, pressure)
+}
+
+//2591 too high
+//1634 too low
+//2096 too low
diff --git a/day16/sample.txt b/day16/sample.txt
@@ -0,0 +1,10 @@
+Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
+Valve BB has flow rate=13; tunnels lead to valves CC, AA
+Valve CC has flow rate=2; tunnels lead to valves DD, BB
+Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
+Valve EE has flow rate=3; tunnels lead to valves FF, DD
+Valve FF has flow rate=0; tunnels lead to valves EE, GG
+Valve GG has flow rate=0; tunnels lead to valves FF, HH
+Valve HH has flow rate=22; tunnel leads to valve GG
+Valve II has flow rate=0; tunnels lead to valves AA, JJ
+Valve JJ has flow rate=21; tunnel leads to valve II
