commit 6f615e3e53c9af2766d9d1fd70119c50e267701f
parent 894d2b1f2c3e4bc12fa95d574a8e695d5bcf05f1
Author: Natasha Kerensikova <natgh@instinctive.eu>
Date: Mon, 23 Dec 2024 17:28:42 +0000
Day 23 reference and solutions
Diffstat:
2 files changed, 128 insertions(+), 0 deletions(-)
diff --git a/2024/day23.nim b/2024/day23.nim
@@ -0,0 +1,96 @@
+# Copyright (c) 2024, Natacha Porté
+#
+# Permission to use, copy, modify, and distribute this software for any
+# purpose with or without fee is hereby granted, provided that the above
+# copyright notice and this permission notice appear in all copies.
+#
+# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+from std/algorithm import sorted
+from std/sequtils import map, mapIt, toSeq
+from std/sets import contains, HashSet, incl, items, len, toHashSet, union
+from std/strutils import join, parseInt, split
+from std/tables import `[]`, `[]=`, getOrDefault, hasKey, pairs, Table
+
+# Read input file
+
+let data = stdin.lines().toSeq().mapIt(it.split("-"))
+
+# Puzzle 1
+
+func image(s: HashSet[string]): string = s.items.to_seq.sorted.join(",")
+
+proc add_edge(edges: var Table[string, HashSet[string]], src, dest: string): void =
+ if edges.has_key(src):
+ edges[src].incl(dest)
+ else:
+ edges[src] = toHashSet(@[dest])
+
+func calc_edges(d: seq[seq[string]]): Table[string, HashSet[string]] =
+ for c in d:
+ assert len(c) == 2
+ add_edge(result, c[0], c[1])
+ add_edge(result, c[1], c[0])
+
+func calc_triangles(cnx: Table[string, HashSet[string]]): HashSet[string] =
+ for src, dest_set in cnx.pairs:
+ assert src notin dest_set
+ for d1 in dest_set.items:
+ for d2 in dest_set.items:
+ if d1 != d2 and d1 in cnx[d2]:
+ result.incl(toHashSet(@[src, d1, d2]).image)
+
+func answer1(cnx: Table[string, HashSet[string]]): int =
+ var acc: HashSet[string]
+ for src, dest_set in cnx.pairs:
+ assert src notin dest_set
+ if src[0] != 't':
+ continue
+ for d1 in dest_set.items:
+ for d2 in dest_set.items:
+ if d1 != d2 and d1 in cnx[d2]:
+ acc.incl(toHashSet(@[src, d1, d2]).image)
+ result = len(acc)
+
+let cnx = calc_edges(data)
+
+echo "Puzzle 1: ", answer1(cnx)
+
+# Puzzle 2
+
+func is_subset(small, big: HashSet[string]): bool =
+ for i in small.items:
+ if i notin big:
+ return false
+ result = true
+
+proc largest_subset(edges: Table[string, HashSet[string]]): string =
+ var
+ subsets = calc_triangles(edges)
+ sz = 3
+ while len(subsets) > 1:
+ echo "Found ", len(subsets), " strongly-connected subsets of size ", sz
+ var next: HashSet[string]
+ for s in subsets.items:
+ let
+ base_seq = s.split(",")
+ base = base_seq.to_hash_set
+ for i1 in base_seq:
+ for i2 in base_seq:
+ assert i1 == i2 or (i1 in edges[i2] and i2 in edges[i1])
+ for n, dest_set in edges.pairs:
+ if n notin base and is_subset(base, dest_set):
+ next.incl(union(base, to_hash_set(@[n])).image)
+ subsets = next
+ sz += 1
+ assert len(subsets) == 1
+ for i in subsets.items:
+ result = i
+
+echo "Puzzle 2: ", largest_subset(cnx)
diff --git a/2024/ref/day23.txt b/2024/ref/day23.txt
@@ -0,0 +1,32 @@
+kh-tc
+qp-kh
+de-cg
+ka-co
+yn-aq
+qp-ub
+cg-tb
+vc-aq
+tb-ka
+wh-tc
+yn-cg
+kh-ub
+ta-co
+de-co
+tc-td
+tb-wq
+wh-td
+ta-ka
+td-qp
+aq-cg
+wq-ub
+ub-vc
+de-ta
+wq-aq
+wq-vc
+wh-yn
+ka-de
+kh-ta
+co-tc
+wh-qp
+tb-vc
+td-yn
