Added solutions for 12th day: caves pathing

6 files changed, 213 insertions, 0 deletions

diff --git a/2021/12/example b/2021/12/example
new file mode 100644
index 0000000..6fd8c41
--- /dev/null
+++ b/2021/12/example
@@ -0,0 +1,7 @@
+start-A
+start-b
+A-c
+A-b
+b-d
+A-end
+b-end
diff --git a/2021/12/example2 b/2021/12/example2
new file mode 100644
index 0000000..62cc714
--- /dev/null
+++ b/2021/12/example2
@@ -0,0 +1,10 @@
+dc-end
+HN-start
+start-kj
+dc-start
+dc-HN
+LN-dc
+HN-end
+kj-sa
+kj-HN
+kj-dc
diff --git a/2021/12/example3 b/2021/12/example3
new file mode 100644
index 0000000..65f3833
--- /dev/null
+++ b/2021/12/example3
@@ -0,0 +1,18 @@
+fs-end
+he-DX
+fs-he
+start-DX
+pj-DX
+end-zg
+zg-sl
+zg-pj
+pj-he
+RW-he
+fs-DX
+pj-RW
+zg-RW
+start-pj
+he-WI
+zg-he
+pj-fs
+start-RW
diff --git a/2021/12/first.go b/2021/12/first.go
new file mode 100644
index 0000000..7b9df44
--- /dev/null
+++ b/2021/12/first.go
@@ -0,0 +1,75 @@
+package main
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+	"strings"
+)
+
+type cave struct {
+	name  string
+	big   bool
+	leafs []int // index in caves array
+}
+
+var (
+	caves = []cave{cave{name: "start"}, cave{name: "end"}}
+	score = 0
+)
+
+const (
+	START = 0
+	END   = 1
+)
+
+func getIdOrAdd(name string) int {
+	for i, v := range caves {
+		if v.name == name {
+			return i
+		}
+	}
+	caves = append(caves, cave{
+		name: name,
+		big:  name[0] >= 'A' && name[0] <= 'Z',
+	})
+	return len(caves) - 1
+}
+
+func contains(id int, passed []int) bool {
+	for _, v := range passed {
+		if v == id {
+			return true
+		}
+	}
+	return false
+}
+
+func parcours(id int, passed []int) {
+	if !caves[id].big {
+		if contains(id, passed) {
+			return
+		}
+		passed = append(passed, id)
+	}
+	for _, v := range caves[id].leafs {
+		if v == END {
+			score++
+			continue
+		}
+		parcours(v, passed)
+	}
+}
+
+func main() {
+	scanner := bufio.NewScanner(os.Stdin)
+	for scanner.Scan() {
+		line := strings.Split(scanner.Text(), "-")
+		a := getIdOrAdd(line[0])
+		b := getIdOrAdd(line[1])
+		caves[a].leafs = append(caves[a].leafs, b)
+		caves[b].leafs = append(caves[b].leafs, a)
+	}
+	parcours(START, nil)
+	fmt.Println(score)
+}
diff --git a/2021/12/input b/2021/12/input
new file mode 100644
index 0000000..a409ba5
--- /dev/null
+++ b/2021/12/input
@@ -0,0 +1,21 @@
+TR-start
+xx-JT
+xx-TR
+hc-dd
+ab-JT
+hc-end
+dd-JT
+ab-dd
+TR-ab
+vh-xx
+hc-JT
+TR-vh
+xx-start
+hc-ME
+vh-dd
+JT-bm
+end-ab
+dd-xx
+end-TR
+hc-TR
+start-vh
diff --git a/2021/12/second.go b/2021/12/second.go
new file mode 100644
index 0000000..5350060
--- /dev/null
+++ b/2021/12/second.go
@@ -0,0 +1,82 @@
+package main
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+	"strings"
+)
+
+type cave struct {
+	name  string
+	big   bool
+	leafs []int // index in caves array
+}
+
+var (
+	caves = []cave{cave{name: "start"}, cave{name: "end"}}
+	score = 0
+)
+
+const (
+	START = 0
+	END   = 1
+)
+
+func getIdOrAdd(name string) int {
+	for i, v := range caves {
+		if v.name == name {
+			return i
+		}
+	}
+	caves = append(caves, cave{
+		name: name,
+		big:  name[0] >= 'A' && name[0] <= 'Z',
+	})
+	return len(caves) - 1
+}
+
+func contains(id int, passed []int) bool {
+	for _, v := range passed {
+		if v == id {
+			return true
+		}
+	}
+	return false
+}
+
+func parcours(id int, passed []int, doublePass bool) {
+	if !caves[id].big {
+		if contains(id, passed) {
+			if doublePass {
+				return
+			} else {
+				doublePass = true
+			}
+		} else {
+			passed = append(passed, id)
+		}
+	}
+	for _, v := range caves[id].leafs {
+		if v == END {
+			score++
+			continue
+		} else if v == START {
+			continue
+		}
+		parcours(v, passed, doublePass)
+	}
+}
+
+func main() {
+	scanner := bufio.NewScanner(os.Stdin)
+	for scanner.Scan() {
+		line := strings.Split(scanner.Text(), "-")
+		a := getIdOrAdd(line[0])
+		b := getIdOrAdd(line[1])
+		caves[a].leafs = append(caves[a].leafs, b)
+		caves[b].leafs = append(caves[b].leafs, a)
+	}
+	parcours(START, nil, false)
+	fmt.Println(score)
+}