day23.nim (3178B)
1 # Copyright (c) 2024, Natacha Porté 2 # 3 # Permission to use, copy, modify, and distribute this software for any 4 # purpose with or without fee is hereby granted, provided that the above 5 # copyright notice and this permission notice appear in all copies. 6 # 7 # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8 # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 10 # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 12 # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 13 # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 14 15 from std/algorithm import sorted 16 from std/sequtils import map, mapIt, toSeq 17 from std/sets import contains, HashSet, incl, items, len, toHashSet, union 18 from std/strutils import join, parseInt, split 19 from std/tables import `[]`, `[]=`, getOrDefault, hasKey, pairs, Table 20 21 # Read input file 22 23 let data = stdin.lines().toSeq().mapIt(it.split("-")) 24 25 # Puzzle 1 26 27 func image(s: HashSet[string]): string = s.items.to_seq.sorted.join(",") 28 29 proc add_edge(edges: var Table[string, HashSet[string]], src, dest: string): void = 30 if edges.has_key(src): 31 edges[src].incl(dest) 32 else: 33 edges[src] = toHashSet(@[dest]) 34 35 func calc_edges(d: seq[seq[string]]): Table[string, HashSet[string]] = 36 for c in d: 37 assert len(c) == 2 38 add_edge(result, c[0], c[1]) 39 add_edge(result, c[1], c[0]) 40 41 func calc_triangles(cnx: Table[string, HashSet[string]]): HashSet[string] = 42 for src, dest_set in cnx.pairs: 43 assert src notin dest_set 44 for d1 in dest_set.items: 45 for d2 in dest_set.items: 46 if d1 != d2 and d1 in cnx[d2]: 47 result.incl(toHashSet(@[src, d1, d2]).image) 48 49 func answer1(cnx: Table[string, HashSet[string]]): int = 50 var acc: HashSet[string] 51 for src, dest_set in cnx.pairs: 52 assert src notin dest_set 53 if src[0] != 't': 54 continue 55 for d1 in dest_set.items: 56 for d2 in dest_set.items: 57 if d1 != d2 and d1 in cnx[d2]: 58 acc.incl(toHashSet(@[src, d1, d2]).image) 59 result = len(acc) 60 61 let cnx = calc_edges(data) 62 63 echo "Puzzle 1: ", answer1(cnx) 64 65 # Puzzle 2 66 67 func is_subset(small, big: HashSet[string]): bool = 68 for i in small.items: 69 if i notin big: 70 return false 71 result = true 72 73 proc largest_subset(edges: Table[string, HashSet[string]]): string = 74 var 75 subsets = calc_triangles(edges) 76 sz = 3 77 while len(subsets) > 1: 78 echo "Found ", len(subsets), " strongly-connected subsets of size ", sz 79 var next: HashSet[string] 80 for s in subsets.items: 81 let 82 base_seq = s.split(",") 83 base = base_seq.to_hash_set 84 for i1 in base_seq: 85 for i2 in base_seq: 86 assert i1 == i2 or (i1 in edges[i2] and i2 in edges[i1]) 87 for n, dest_set in edges.pairs: 88 if n notin base and is_subset(base, dest_set): 89 next.incl(union(base, to_hash_set(@[n])).image) 90 subsets = next 91 sz += 1 92 assert len(subsets) == 1 93 for i in subsets.items: 94 result = i 95 96 echo "Puzzle 2: ", largest_subset(cnx)