Nim
Part 3 is a recursive solution with caching (memoization).
proc isValid(name: string, rules: Table[char, set[char]]): bool =
for i in 0 ..< name.high:
if name[i+1] notin rules[name[i]]: return false
true
proc allNames(prefix: string, rules: Table[char, set[char]], range: Slice[int]): int =
var memo {.global.}: Table[(int, char), int]
if prefix.len >= range.b: return
if (prefix.len, prefix[^1]) in memo: return memo[(prefix.len, prefix[^1])]
for ch in rules.getOrDefault(prefix[^1]):
if prefix.len + 1 >= range.a:
inc result
result += allNames(prefix & ch, rules, range)
memo[(prefix.len, prefix[^1])] = result
proc solve_part1*(input: string): Solution =
let (names, rules) = parseInput(input)
for name in names:
if name.isValid(rules):
return Solution(kind: skString, strVal: name)
proc solve_part2*(input: string): Solution =
let (names, rules) = parseInput(input)
for ni, name in names:
if name.isValid(rules):
result.intVal += ni + 1
proc solve_part3*(input: string): Solution =
let (names, rules) = parseInput(input)
var seen: seq[string]
for name in names:
if not name.isValid(rules): continue
if seen.anyIt(name.startsWith it): continue
result.intVal += allNames(name, rules, 7..11)
seen.add name
Full solution at Codeberg: solution.nim