day19.nim (1911B)
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/sequtils import foldl, filter, map, toSeq 16 from std/strutils import split, startsWith 17 from std/tables import `[]`, `[]=`, hasKey, initTable 18 19 # Read input file 20 21 func read_input(s: seq[string]): (seq[string], seq[string]) = 22 assert len(s) >= 3 23 assert s[1] == "" 24 result = (s[0].split(", "), s[2 .. ^1]) 25 26 let (patterns, designs) = read_input(stdin.lines().toSeq()) 27 28 # Puzzle 1 29 30 var memo1 = initTable[string, bool]() 31 memo1[""] = true 32 33 proc is_possible(design: string): bool = 34 if memo1.hasKey(design): 35 return memo1[design] 36 37 result = false 38 for p in patterns: 39 assert len(p) > 0 40 if design.startsWith(p) and is_possible(design[len(p) .. ^1]): 41 result = true 42 break 43 memo1[design] = result 44 45 echo "Puzzle 1: ", designs.filter(is_possible).len() 46 47 # Puzzle 2 48 49 var memo2 = initTable[string, int]() 50 memo2[""] = 1 51 52 proc arrangements(design: string): int = 53 if memo2.hasKey(design): 54 return memo2[design] 55 56 result = 0 57 for p in patterns: 58 assert len(p) > 0 59 if design.startsWith(p): 60 result += arrangements(design[len(p) .. ^1]) 61 memo2[design] = result 62 63 echo "Puzzle 2: ", designs.map(arrangements).foldl(a + b)