commit 5d1f81a28d79bf586f3d77cc74e14cd081701260
parent e45241ffc2509f27bcd841269a3a101305d14927
Author: bsandro <email@bsandro.tech>
Date: Fri, 16 Dec 2022 23:26:47 +0000
Day 16 part 1 rework - sample works, input still does not :(
Diffstat:
| M | day16/main.go | | | 245 | ++++++++++++++++++++++++++++++++++++++++++++++++------------------------------- |
1 file changed, 150 insertions(+), 95 deletions(-)
diff --git a/day16/main.go b/day16/main.go
@@ -1,60 +1,75 @@
package main
import (
- "strings"
"bufio"
"fmt"
"log"
"os"
"sort"
+ "strings"
)
type Valve struct {
- name string
- rate int
- open bool
+ 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, ","))
+ 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
+ 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)
+ 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 := 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"
+ 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) Swap(i, j int) {
+ ps[i], ps[j] = ps[j], ps[i]
}
-func (ps Paths) Find(name string) (*Path) {
+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
@@ -64,71 +79,94 @@ func (ps Paths) Find(name string) (*Path) {
}
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"
+ 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
+ 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 {
+ 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)
- //}
+ visited[cur] = parent
+ for _, s := range vs[cur].connections {
+ if _, exists := visited[s]; !exists {
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!="" {
+ if parent != "" {
path.path = append(path.path, parent)
}
- c:=parent//visited[parent]
- for c!="" {
- c=visited[c]
- if c!="" {
+ c := 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})
+ upcoming = append(upcoming, Step{name: s, parent: cur})
}
- }
+ }
}
}
-
- return path, false
+
+ return path, false
}
-func (vs Valves) GetPaths(start string) Paths {
+
+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 { continue }
- if p,found:=vs.FindPath(start,v.name);found{
+ 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)
+ //log.Fatal("no path:", start, v.name)
}
}
sort.Sort(paths)
@@ -136,9 +174,10 @@ func (vs Valves) GetPaths(start string) Paths {
}
type Strings []string
+
func (ss Strings) Has(s string) bool {
- for _, s1:=range ss {
- if s1==s {
+ for _, s1 := range ss {
+ if s1 == s {
return true
}
}
@@ -166,59 +205,72 @@ func day16(input_file string) {
for scanner.Scan() {
in := scanner.Text()
in1, in2, found := strings.Cut(in, "; ")
- if !found {log.Fatal("parsing error")}
+ 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)}
+ 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}
-
+ valves[vname] = &Valve{name: vname, rate: vrate, connections: conns}
+
}
if err = scanner.Err(); err != nil {
log.Fatal(err)
}
- fmt.Print(valves)
- fmt.Println("--------")
+ //fmt.Print(valves)
- rate:=0
- pressure:=0
- v:=valves["AA"]
- for i:=1;i<=30;{
- paths:=valves.GetPaths(v.name)
- //fmt.Println("~~~>", v.name)
+ 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(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))
+ 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*(len(path.path))
- i+=len(path.path)-1
- v=valves[path.name]
+ pressure += rate * plen
+ i += plen - 1
+ v = valves[path.name]
v.open = true
- rate+=v.rate
+ 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
+ pressure += rate
}
+ i++
//fmt.Println("===============")
}
fmt.Printf("rate:%d, pressure:%d\n", rate, pressure)
@@ -227,3 +279,6 @@ func day16(input_file string) {
//2591 too high
//1634 too low
//2096 too low
+//2128 wrong
+//2342 wrong
+//2297 wrong
