package main
import (
"bufio"
"log"
"os"
"strings"
)
type routes map[string][]string
type seen map[string]int
func main() {
if err := myMain(); err != nil {
log.Println(err)
}
}
func myMain() error {
r, err := parseInput("input.txt")
if err != nil {
return err
}
log.Println(solveFirst(r))
log.Println(solveSecond(r))
return nil
}
type condFn func(seen, string) bool
func solveFirst(r routes) int {
s := seen{}
return r.genRoutes(s, "start", isSeen)
}
func solveSecond(r routes) int {
s := seen{}
return r.genRoutes(s, "start", seenTooMuch)
}
func seenTooMuch(s seen, root string) bool {
if s[root] >= 2 {
return true
}
if s[root] == 0 {
return false
}
if s[root] == 1 {
for k, v := range s {
if k == root {
continue
}
if v > 1 {
return true
}
}
}
return false
}
func isSeen(s seen, root string) bool {
if s[root] > 0 {
return true
}
return false
}
func (r routes) genRoutes(s seen, root string, fn condFn) int {
var sum int
if root == "end" {
sum++
return sum
}
if fn(s, root) {
return 0
}
if strings.ToLower(root) == root && root != "end" {
// lowercase, only visit once
s[root]++
}
for _, item := range r[root] {
sum += r.genRoutes(s, item, fn)
}
s[root]--
return sum
}
func parseInput(fileName string) (routes, error) {
var ret = routes{}
fd, err := os.Open(fileName)
if err != nil {
return ret, err
}
defer fd.Close()
buf := bufio.NewScanner(fd)
for buf.Scan() {
tmp := strings.Split(buf.Text(), "-")
if tmp[1] != "start" && tmp[0] != "end" {
ret[tmp[0]] = append(ret[tmp[0]], tmp[1])
}
if tmp[0] != "start" && tmp[1] != "end" {
ret[tmp[1]] = append(ret[tmp[1]], tmp[0])
}
}
return ret, nil
}