aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJulien Dessaux2021-12-12 17:34:37 +0100
committerJulien Dessaux2021-12-12 17:34:37 +0100
commit86a723beebcd2710d648c355d52bd96a5344f041 (patch)
treed8ee2e50f18b6e1a584b5b381c9e40afccece21a
parentAdded solutions for 11th day: octopus flashes (diff)
downloadadvent-of-code-86a723beebcd2710d648c355d52bd96a5344f041.tar.gz
advent-of-code-86a723beebcd2710d648c355d52bd96a5344f041.tar.bz2
advent-of-code-86a723beebcd2710d648c355d52bd96a5344f041.zip
Added solutions for 12th day: caves pathing
Diffstat (limited to '')
-rw-r--r--2021/12/example7
-rw-r--r--2021/12/example210
-rw-r--r--2021/12/example318
-rw-r--r--2021/12/first.go75
-rw-r--r--2021/12/input21
-rw-r--r--2021/12/second.go82
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)
+}