Advent of Code 2023 - Day 23

Mix.install([:memoize])

Sample

sample = """
#.#####################
#.......#########...###
#######.#########.#.###
###.....#.>.>.###.#.###
###v#####.#v#.###.#.###
###.>...#.#.#.....#...#
###v###.#.#.#########.#
###...#.#.#.......#...#
#####.#.#.#######.#.###
#.....#.#.#.......#...#
#.#####.#.#.#########v#
#.#...#...#...###...>.#
#.#.#v#######v###.###v#
#...#.>.#...>.>.#.###.#
#####v#.#.###v#.#.###.#
#.....#...#...#.#.#...#
#.#########.###.#.#.###
#...###...#...#...#.###
###.###.#.###v#####v###
#...#...#.#.>.>.#.>.###
#.###.###.#.###.#.#v###
#.....###...###...#...#
#####################.#
"""

"#.#####################\n#.......#########...###\n#######.#########.#.###\n###.....#.>.>.###.#.###\n###v#####.#v#.###.#.###\n###.>...#.#.#.....#...#\n###v###.#.#.#########.#\n###...#.#.#.......#...#\n#####.#.#.#######.#.###\n#.....#.#.#.......#...#\n#.#####.#.#.#########v#\n#.#...#...#...###...>.#\n#.#.#v#######v###.###v#\n#...#.>.#...>.>.#.###.#\n#####v#.#.###v#.#.###.#\n#.....#...#...#.#.#...#\n#.#########.###.#.#.###\n#...###...#...#...#.###\n###.###.#.###v#####v###\n#...#...#.#.>.>.#.>.###\n#.###.###.#.###.#.#v###\n#.....###...###...#...#\n#####################.#\n"

Input

input = """
#.###########################################################################################################################################
#.#...###...#.....#...#.....#.....#.......###...#.....#...................###.....#...###...#.......#...#...#.....###...###...#####.........#
#.#.#.###.#.#.###.#.#.#.###.#.###.#.#####.###.#.#.###.#.#################.###.###.#.#.###.#.#.#####.#.#.#.#.#.###.###.#.###.#.#####.#######.#
#.#.#...#.#.#.#...#.#...#...#...#...#...#...#.#.#.#...#.........#...#...#...#...#.#.#.###.#.#.#.....#.#.#.#.#.#...#...#.#...#...###.#.......#
#.#.###.#.#.#.#.###.#####.#####.#####.#.###.#.#.#.#.###########.#.#.#.#.###.###.#.#.#.###.#.#.#.#####.#.#.#.#.#.###.###.#.#####.###.#.#######
#.#.#...#.#.#.#.###...#...#.>.>.#.....#.....#.#.#.#.###...#...#...#...#...#...#.#.#.#.>.>.#.#.#...###.#.#.#...#...#...#.#.....#...#.#...#...#
#.#.#.###.#.#.#.#####.#.###.#v###.###########.#.#.#.###.#.#.#.###########.###.#.#.#.###v###.#.###.###.#.#.#######.###.#.#####.###.#.###.#.#.#
#.#.#.....#.#.#...#...#.....#...#.#.....#.....#...#...#.#.#.#.#...........###...#...###...#.#.#...#...#.#...#...#.###.#.#...#.#...#.#...#.#.#
#.#.#######.#.###.#.###########.#.#.###.#.###########.#.#.#.#.#.#########################.#.#.#.###.###.###.#.#.#.###.#.#.#.#.#.###.#.###.#.#
#.#.......#...#...#.........#...#...#...#.#.....#.....#.#.#.#.#...........#.....#.........#...#...#...#.###...#.#.#...#.#.#.#.#.....#.#...#.#
#.#######.#####.###########.#.#######.###.#.###.#.#####.#.#.#.###########.#.###.#.###############.###.#.#######.#.#.###.#.#.#.#######.#.###.#
#.#.......#.....#####...#...#.......#...#.#...#...#...#.#...#.#.....#...#...#...#...............#...#.#.>.>.#...#.#...#.#.#...#.....#...#...#
#.#.#######.#########.#.#.#########.###.#.###.#####.#.#.#####.#.###.#.#.#####.#################.###.#.###v#.#.###.###.#.#.#####.###.#####.###
#.#.......#.......#...#.#.....#.....#...#...#...###.#...#.....#...#.#.#.#.....#...#...#.........#...#.#...#.#...#.#...#...#.....###.....#...#
#.#######.#######.#.###.#####.#.#####.#####.###.###.#####.#######.#.#.#.#.#####.#.#.#.#.#########.###.#.###.###.#.#.#######.###########.###.#
#...#...#.#.......#...#...#...#...###.....#...#...#.....#.#.......#...#.#...#...#...#...#.......#.....#...#.#...#...#...###...........#.#...#
###.#.#.#.#.#########.###.#.#####.#######.###.###.#####.#.#.###########.###.#.###########.#####.#########.#.#.#######.#.#############.#.#.###
#...#.#...#.........#...#.#...###...#...#.....###...###.#.#...........#.#...#...#...#...#...#...#.......#.#...#.......#.......#...#...#.#...#
#.###.#############v###.#.###.#####.#.#.###########.###.#.###########.#.#.#####.#.#.#.#.###.#.###.#####.#.#####.#############.#.#.#.###.###.#
#.....###...#.....#.>.#.#.#...#...#...#.......#####...#.#...>.>...#...#.#.###...#.#...#...#.#...#.....#.#...###.#...#.......#.#.#...#...#...#
#########.#.#.###.#v#.#.#.#.###.#.###########.#######.#.#####v###.#.###.#.###.###.#######.#.###.#####.#.###.###.#.#.#.#####.#.#.#####.###.###
#.........#.#...#.#.#...#...#...#.............#.......#.#.....###...###.#...#...#.#...#...#...#.......#...#...#...#...#.....#...#...#...#...#
#.#########.###.#.#.#########.#################.#######.#.#############.###.###.#.#.#.#.#####.###########.###.#########.#########.#.###.###.#
#.........#.....#.#.....#...#...............###.........#.............#.#...###...#.#.#.....#...#.....###.....###...#...#.........#...#.#...#
#########.#######.#####.#.#.###############.#########################.#.#.#########.#.#####.###.#.###.###########.#.#.###.###########.#.#.###
#.........#...###.......#.#.#...............#...#...#.................#...###.......#.......###...#...#...#####...#...#...#...#.......#.#...#
#.#########.#.###########.#.#.###############.#.#.#.#.#######################.#####################.###.#.#####.#######.###.#.#.#######.###.#
#.....#.....#...###...#...#.#...............#.#.#.#.#...........#.....#.....#.....#.............#...#...#.....#...#.....#...#.#.......#...#.#
#####.#.#######.###.#.#.###.###############.#.#.#.#.###########.#.###.#.###.#####.#.###########.#.###.#######.###.#.#####.###.#######.###.#.#
#...#...#.......#...#.#.#...#...#...#.......#.#.#.#.#...........#...#...#...#...#...#...........#.....#.......###...#...#...#.........#...#.#
#.#.#####.#######.###.#.#.###.#.#.#.#v#######.#.#.#.#.#############.#####.###.#.#####.#################.#############.#.###.###########.###.#
#.#...###.......#...#...#...#.#.#.#.>.>.......#...#.#.......###...#.#.....#...#.#...#.......#.....#...#.....#.........#...#...........#...#.#
#.###.#########.###.#######.#.#.#.###v#############.#######.###.#.#.#.#####.###.#.#.#######.#.###.#.#.#####.#.###########.###########.###.#.#
#...#...........###.......#.#.#...###...#.........#.#...###.#...#.#.#.#...#...#.#.#.###.....#...#.#.#.#.....#...........#.............###.#.#
###.#####################.#.#.#########.#.#######.#.#.#.###.#.###.#.#.#.#.###.#.#.#.###v#######.#.#.#.#.###############.#################.#.#
#...#.....#.....###...#...#.#.#...###...#...#...#...#.#.....#...#...#...#.....#...#...>.>.#...#.#.#.#...###...#.....###.................#...#
#.###.###.#.###.###.#.#.###.#.#.#.###.#####.#.#.#####.#########.#######################v#.#.#.#.#.#v#######.#.#.###.###################.#####
#.....###...#...#...#.#...#...#.#.#...#.....#.#.....#.........#...#.......#.............#.#.#.#.#.>.>.#...#.#.#...#...#.................#...#
#############v###.###.###.#####.#.#.###.#####.#####.#########.###.#.#####.#.#############.#.#.#.###v#.#.#.#.#.###.###.#.#################.#.#
#...........#.>...###.....#.....#...###...#...###...###...#...###...#.....#...#.....#...#.#.#...#...#.#.#...#...#.#...#.................#.#.#
#.#########.#v#############.#############.#.#####.#####.#.#v#########.#######.#.###.#.#.#.#.#####.###.#.#######.#.#.###################.#.#.#
#.......#...#.###...###...#.........#...#...#.....#...#.#.>.>.......#...###...#.###...#.#.#.#...#...#.#.....#...#.#.###...#.............#.#.#
#######.#.###.###.#.###.#.#########.#.#.#####.#####.#.#.###v#######.###.###.###.#######.#.#.#.#.###.#.#####.#.###.#.###.#.#v#############.#.#
###...#.#.#...#...#...#.#...........#.#.....#.......#.#...#...#...#...#...#.....#.......#...#.#.....#.....#.#...#.#.#...#.>.#.....#.....#.#.#
###.#.#.#.#.###.#####.#.#############.#####.#########.###.###.#.#.###.###.#######.###########.###########.#.###.#.#.#.#####v#.###.#.###.#.#.#
#...#...#.#...#.#.....#...............#.....#.......#.#...#...#.#...#...#.#.....#.....###...#.#.........#...###.#.#.#...#...#.#...#.#...#.#.#
#.#######.###.#.#.#####################.#####.#####.#.#.###.###.###.###.#.#.###.#####.###.#.#.#.#######.#######.#.#.###.#.###.#.###.#.###.#.#
#.......#.....#.#...........#.........#.....#...#...#...#...#...#...###...#...#.......#...#.#.#.#.......#...###.#.#...#.#...#.#...#.#.....#.#
#######.#######.###########.#.#######.#####.###.#.#######.###.###.###########.#########.###.#.#.#.#######.#.###.#.###.#.###.#.###.#.#######.#
#...###.........#...#.......#.......#.......###.#.#.....#...#.###.....###.....#...###...#...#...#...#.....#...#...###...#...#.###...#.......#
#.#.#############.#.#.#############.###########.#.#.###.###.#.#######.###.#####.#.###.###.#########.#.#######.###########.###.#######.#######
#.#...............#...#.....###...#.###.....#...#...#...#...#...#.....#...#...#.#.....#...#...#####...#...###...###.....#.....#.......#...###
#.#####################.###.###.#.#v###.###.#.#######.###.#####.#.#####.###.#.#.#######.###.#.#########.#.#####v###.###.#######.#######.#.###
#.#.......#...........#...#.....#.>.>...#...#.#.......###.......#.....#.#...#...#.....#.###.#...#...#...#.#...>.>.#...#.#...#...#.....#.#.###
#.#.#####.#.#########.###.#########v#####.###.#.#####################.#.#.#######.###.#.###.###.#.#.#.###.#.###v#.###.#.#.#.#.###.###.#.#.###
#.#.#.....#.#.........###.......###.....#...#.#...###...#...#...#.....#...#.......###...#...#...#.#.#.###...###.#.#...#.#.#.#.....#...#.#.###
#.#.#.#####.#.#################.#######.###.#.###.###.#.#.#.#.#.#.#########.#############.###.###.#.#.#########.#.#.###.#.#.#######v###.#.###
#.#.#.#...#.#.#...###...#...#...#.....#...#.#...#...#.#.#.#.#.#.#.....#...#.........#...#...#.#...#.#.....#.....#...###.#.#.#...#.>.###.#...#
#.#.#.#.#.#.#.#.#.###.#.#.#.#.###.###.###.#.###.###.#.#.#.#.#.#.#####.#.#.#########.#.#.###.#.#.###.#####.#.###########.#.#.#.#.#.#v###.###.#
#...#...#...#...#.....#.#.#...###...#.....#...#.###...#.#.#.#.#.#.....#.#.#...#.....#.#.#...#.#.###.#.....#...........#.#.#.#.#...#...#.#...#
#######################.#.#########.#########.#.#######.#.#.#.#.#v#####.#.#.#.#.#####.#.#.###.#.###.#.###############.#.#.#.#.#######.#.#.###
###...#...#.............#.....#.....#.......#.#.#.......#.#.#.#.>.>.###.#.#.#.#...#...#.#...#.#...#.#...#.....#.......#.#.#.#.#.......#.#.###
###.#.#.#.#.#################.#.#####.#####.#.#.#.#######.#.#.###v#.###.#.#.#.###v#.###.###.#.###.#.###.#.###.#.#######.#.#.#.#.#######.#.###
#...#.#.#.#...#...###...#.....#.......#...#.#...#...#...#.#.#.#...#...#.#.#.#...>.>.###.#...#.#...#.#...#...#...#...###.#.#.#.#...#.....#...#
#.###.#.#.###.#.#v###.#.#.#############.#.#.#######.#.#.#.#.#.#.#####.#.#.#.#####v#####.#.###.#.###.#.#####.#####.#.###.#.#.#.###.#.#######.#
#...#.#.#.###...#.>.#.#.#...#...........#...#.......#.#.#.#.#.#.#...#.#.#.#...#...#...#...###...###...#...#.......#...#.#.#...#...#.###.....#
###.#.#.#.#######v#.#.#.###.#.###############.#######.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#################.#.###########.#.#.#####.###.###.#####
#...#.#.#...###...#.#.#.#...#.#.....#...#...#.......#.#.#.#...#...#.#.#.#.#...#...#.#.#.....#.....#.....#.........#...#.#.#...#...#...#.....#
#.###.#.###.###.###.#.#.#.###.#.###.#.#.#.#.#######.#.#.#.#########.#.#.#.#.#####.#.#.#.###.#.###.#.#############.#.###.#.#.#.###.###.#####.#
#...#.#...#...#...#.#.#...###...###...#...#...#...#...#.#.#...#...#.#.#.#...#.....#.#.#...#.#.#...#.......#...###...###.#.#.#.....#...#.....#
###.#.###.###.###.#.#.#######################.#.#.#####.#.#.#.#.#.#.#.#.#####.#####.#.###.#.#.#.#########.#.#.#########.#.#.#######.###.#####
###.#.###...#.....#.#.#.......#.............#.#.#.....#...#.#...#...#...#...#.......#...#.#...#.#...#...#...#.....#...#...#.........###.....#
###.#.#####.#######.#.#.#####.#.###########.#.#.#####.#####.#############.#.###########.#.#####.#.#.#.#.#########.#.#.#####################.#
#...#.#.....#.....#...#...#...#...........#...#.#.....#...#.#...#...#...#.#.............#.....#.#.#.#.#.#...#.....#.#.#...###...#...#...#...#
#.###.#.#####.###.#######.#.#############.#####.#.#####.#.#.#.#.#.#.#.#.#.###################.#.#.#.#.#.#.#.#.#####.#.#.#.###.#.#.#.#.#.#.###
#...#.#.....#.#...#...#...#...#####.......#...#.#...###.#.#...#...#...#.#.......###...#...#...#.#.#.#.#...#...#...#.#.#.#.#...#.#.#.#.#.#...#
###.#.#####.#.#.###.#.#.#####.#####.#######.#.#.###.###.#.#############.#######.###.#.#.#.#.###.#.#.#.#########.#.#.#.#.#.#.###.#.#.#.#.###.#
#...#.....#.#.#...#.#.#.....#.#.....#...###.#.#.#...#...#.###...#.......###.....#...#.#.#.#...#.#.#.#.....#...#.#.#.#.#.#.#...#.#.#.#.#.#...#
#.#######.#.#.###.#.#.#####.#.#.#####.#.###.#.#.#.###.###.###.#.#.#########.#####.###.#.#.###.#.#.#.#####v#.#.#.#.#.#.#.#.###.#.#.#.#.#.#v###
#.#.....#.#.#.#...#.#.#...#.#.#.....#.#.#...#.#.#.###...#.....#.#.........#.....#...#.#.#.....#.#.#...#.>.>.#.#.#.#.#.#.#.#...#.#.#.#.#.>.###
#.#.###.#.#.#.#.###.#.#.#.#.#.#####v#.#.#.###.#.#.#####.#######.#########.#####.###.#.#.#######.#.###.#.#v###.#.#.#.#.#.#.#.###.#.#.#.###v###
#.#.#...#...#.#.#...#.#.#.#.#.#...>.>.#...#...#.#.#...#...#.....###.......###...###.#...#...###...###...#...#.#.#...#.#.#.#.#...#.#...#...###
#.#.#.#######.#.#.###.#.#.#.#.#.###v#######.###.#.#.#.###.#.#######v#########.#####.#####.#.###############.#.#.#####.#.#.#.#.###.#####.#####
#...#.#...#...#.#.###.#.#.#.#.#.###.....#...#...#.#.#...#.#.#.....>.>.###...#...#...#...#.#...#.........#...#.#.###...#.#...#.#...#.....#####
#####.#.#.#.###.#.###.#.#.#.#.#.#######.#.###.###.#.###.#.#.#.#####v#.###.#.###.#.###.#.#.###.#.#######.#.###.#.###.###.#####.#.###.#########
#.....#.#.#...#.#...#.#.#...#...#.....#.#...#.###.#.###.#.#...#.....#...#.#.###.#.....#...#...#.......#.#...#.#...#...#.###...#.###.........#
#.#####.#.###.#.###.#.#.#########.###.#.###.#.###.#.###.#.#####.#######.#.#.###v###########.#########.#.###.#.###.###.#.###.###.###########.#
#.#...#.#.#...#.#...#.#.#.........#...#...#.#.#...#...#...#...#.......#...#.#.>.>.......#...###.......#.#...#.#...###.#.#...#...#...###.....#
#.#.#v#.#.#.###.#.###.#.#.#########.#####.#.#.#.#####.#####.#.#######.#####.#.#v#######.#.#####.#######.#.###.#.#####.#.#.###.###.#.###.#####
#.#.#.>.#...###.#...#.#.#.........#.....#.#.#.#...#...#.....#.....#...#.....#.#.#...###...#.....#.....#...###...#####...#.#...#...#.....#...#
#.#.#v#########.###.#.#.#########.#####.#.#.#.###.#.###.#########.#.###.#####.#.#.#.#######.#####.###.###################.#.###.#########.#.#
#...#.........#.....#...###...###.....#...#...#...#.###.........#.#...#.......#.#.#...#...#.......###.............#...###...###...........#.#
#############.#############.#.#######.#########.###.###########.#.###.#########.#.###.#.#.#######################.#.#.#####################.#
#.............###...#.......#.#.......#.....###...#.#...........#.....###.......#...#...#.......#.................#.#.###.....#.............#
#.###############.#.#.#######.#.#######.###.#####.#.#.###################.#########.###########.#.#################.#.###.###.#.#############
#.#...#.........#.#.#.......#.#.........#...#...#...#...#.........#...#...#...#.....###...#.....#.#.....#...###...#.#.#...#...#.............#
#.#.#.#.#######.#.#.#######.#.###########.###.#.#######.#.#######.#.#.#.###.#.#.#######.#.#.#####.#.###.#.#.###.#.#.#.#.###.###############.#
#.#.#.#.#.......#.#.###.....#...........#.###.#.#...###...###.....#.#.#.....#...#.......#...#...#...###...#...#.#.#.#.#...#.###...#...#...#.#
#.#.#.#.#.#######.#.###.###############.#.###.#.#.#.#########.#####.#.###########.###########.#.#############.#.#.#.#.###.#.###.#.#.#.#v#.#.#
#...#...#.....#...#...#.......#.....###...#...#.#.#.#...#.....#...#.#.#...#...###.......#...#.#.#...#.........#.#.#.#...#.#.#...#.#.#.>.#...#
#############.#.#####.#######.#.###.#######.###.#.#.#.#.#.#####.#.#.#.#.#.#.#.#########.#.#.#.#.#.#.#.#########.#.#.###.#.#.#.###.#.###v#####
#...#.........#.#.....###...#...#...#...###...#.#.#.#.#.#.....#.#...#...#...#.#...#####...#.#.#.#.#.#.......#...#.#...#.#.#.#...#...###.....#
#.#.#.#########.#.#######.#.#####.###.#.#####.#.#.#.#.#.#####v#.#############.#.#.#########.#.#.#.#.#######.#.###.###.#.#.#.###.###########.#
#.#...#...###...#.#...#...#.#.....#...#.#...#.#.#.#.#.#.....>.>.#.....#...#...#.#...........#.#.#.#.###...#.#.#...#...#.#.#...#...#...#.....#
#.#####.#v###.###.#.#.#.###.#.#####.###.#.#.#.#.#.#.#.#######v###.###.#.#.#.###.#############.#.#.#.###.#.#v#.#.###.###.#.###.###.#.#.#.#####
#.......#.>...#...#.#.#...#.#.#...#...#.#.#.#.#.#.#.#.#.....#...#...#...#...###...........#...#.#.#...#.#.>.>.#...#...#...#...#...#.#...#####
#########v#####.###.#.###.#.#.#.#.###.#.#.#.#.#.#.#.#.#.###.###.###.#####################.#.###.#.###.#.###v#####.###.#####.###.###.#########
#.........#.....###.#.###.#.#...#.#...#.#.#...#...#...#...#.#...###.#...###...#...#...#...#...#.#.#...#...#...###...#...#...#...###.........#
#.#########.#######.#.###.#.#####v#.###.#.###############.#.#.#####.#.#.###.#.#.#.#.#.#v#####.#.#.#.#####.###.#####.###.#.###.#############.#
#.........#.....#...#.#...#...#.>.>.###.#.......#.........#...#.....#.#.#...#.#.#.#.#.>.>.#...#.#.#...#...###.#...#.....#...#...#...........#
#########.#####.#.###.#.#####.#.#v#####.#######.#.#############.#####.#.#.###.#.#.#.###v#.#.###.#.###.#.#####.#.#.#########.###.#.###########
#.........#...#.#...#.#.....#...#.....#.#.......#.............#.....#.#.#.#...#.#...#...#...###...#...#.#...#...#.........#.....#...........#
#.#########.#.#.###.#.#####.#########.#.#.###################.#####.#.#.#.#.###.#####.#############.###.#.#.#############.#################.#
#...#.....#.#.#.....#.....#.#.........#.#...#.................###...#.#...#...#.#...#...........#...#...#.#...............#...........#.....#
###.#.###.#.#.###########.#.#.#########.###.#.###################.###.#######.#.#.#.###########.#.###.###.#################.#########.#.#####
###...###...#.....#...###...#.........#.....#...................#...#.......#...#.#.......#.....#...#.###...#...........###.........#.#.....#
#################.#.#.###############.#########################.###.#######.#####.#######.#.#######.#.#####.#.#########.###########.#.#####.#
#...............#.#.#...#...........#.......###...#.............###.#...#...#...#.......#.#.......#.#.#.....#.#.........#...#.......#.#.....#
#.#############.#.#.###.#.#########.#######.###.#.#.###############.#.#.#.###.#.#######.#.#######.#.#.#.#####.#.#########.#.#.#######.#.#####
#.#...#...#...#...#.#...#.#.......#.....#...#...#.#.#.............#.#.#...#...#.........#.#...#...#...#.......#.........#.#.#.......#...#...#
#.#.#.#.#.#.#.#####.#.###.#.#####.#####.#.###.###.#.#.###########.#.#.#####.#############.#.#.#.#######################.#.#.#######.#####.#.#
#...#...#...#.......#...#...#####.....#...###...#.#...#...........#...#.....#...........#...#...#...#...#...#...........#.#.....###.......#.#
#######################.#############.#########.#.#####.###############.#####.#########.#########.#.#.#.#.#.#.###########.#####.###########.#
#.................#.....#.....#.......###...#...#.......#...###...#...#.......#.........#.......#.#...#...#.#.#.......###...#...#...........#
#.###############.#.#####.###.#.#########.#.#.###########.#.###.#.#.#.#########.#########.#####.#.#########.#.#.#####.#####.#.###.###########
#.#.............#.#.#...#...#.#.......#...#.#.............#...#.#.#.#.......#...#.....#...#.....#.......#...#.#.#.....#...#.#...#...........#
#.#.###########.#.#.#.#.###.#.#######.#.###.#################.#.#.#.#######.#.###.###.#.###.###########.#.###.#.#.#####.#.#.###.###########.#
#...#...........#...#.#...#.#.......#...#...###...#...........#.#.#.....#...#.....#...#...#.#.......#...#...#...#.....#.#.#.#...#...#.......#
#####.###############.###.#.#######.#####.#####.#.#.###########.#.#####.#.#########.#####.#.#.#####.#.#####.#########.#.#.#.#.###.#.#.#######
#...#.....#.......###.#...#...#...#.......#...#.#.#.....###...#.#...#...#...#...#...#...#.#.#.#.....#...#...#...#.....#.#...#...#.#.#.......#
#.#.#####.#.#####.###.#.#####.#.#.#########.#.#.#.#####v###.#.#.###.#.#####.#.#.#.###.#.#.#.#.#.#######.#.###.#.#v#####.#######.#.#.#######.#
#.#.......#...#...#...#...###...#...#.....#.#.#.#.#...>.>.#.#.#.#...#.#.....#.#.#...#.#.#.#.#.#.#...#...#.#...#.>.>.###...#.....#.#.###.....#
#.###########.#.###.#####.#########.#.###.#.#.#.#.#.#####.#.#.#.#.###.#.#####.#.###v#.#.#.#.#.#.#.#.#.###.#.#######.#####.#.#####.#.###v#####
#...#.........#...#.#.....#...#.....#...#.#.#.#.#.#...###.#.#...#.#...#.#...#.#.#.>.>.#.#.#...#.#.#.#.#...#.......#...#...#.#...#.#.#.>.#...#
###.#.###########.#.#.#####.#.#.#######.#.#.#.#.#.###.###.#.#####.#.###.#.#.#.#.#.#####.#.#####.#.#.#.#.#########.###.#.###.#.#.#.#.#.#v#.#.#
#...#.#...........#.#.#...#.#.#...#...#.#.#.#.#.#...#...#.#...#...#...#...#...#.#.###...#.....#.#.#...#...#...#...#...#...#...#...#.#.#.#.#.#
#.###.#.###########.#.#.#.#.#.###v#.#.#.#.#.#.#.###.###.#.###.#.#####.#########.#.###.#######.#.#.#######.#.#.#.###.#####.#########.#.#.#.#.#
#...#.#.....#.....#.#.#.#.#.#.#.>.>.#.#.#.#.#.#.#...#...#.#...#.#...#.....#.....#...#.#...#...#.#.#.......#.#.#.#...#.....#.........#.#.#.#.#
###.#.#####.#.###.#.#.#.#.#.#.#.#####.#.#.#.#.#.#.###.###.#.###.#.#.#####.#.#######.#.#.#.#.###.#.#.#######.#.#.#.###.#####.#########.#.#.#.#
###...#####...###...#...#...#...#####...#...#...#.....###...###...#.......#.........#...#...###...#.........#...#.....#####...........#...#.#
###########################################################################################################################################.#
"""

"#.###########################################################################################################################################\n#.#...###...#.....#...#.....#.....#.......###...#.....#...................###.....#...###...#.......#...#...#.....###...###...#####.........#\n#.#.#.###.#.#.###.#.#.#.###.#.###.#.#####.###.#.#.###.#.#################.###.###.#.#.###.#.#.#####.#.#.#.#.#.###.###.#.###.#.#####.#######.#\n#.#.#...#.#.#.#...#.#...#...#...#...#...#...#.#.#.#...#.........#...#...#...#...#.#.#.###.#.#.#.....#.#.#.#.#.#...#...#.#...#...###.#.......#\n#.#.###.#.#.#.#.###.#####.#####.#####.#.###.#.#.#.#.###########.#.#.#.#.###.###.#.#.#.###.#.#.#.#####.#.#.#.#.#.###.###.#.#####.###.#.#######\n#.#.#...#.#.#.#.###...#...#.>.>.#.....#.....#.#.#.#.###...#...#...#...#...#...#.#.#.#.>.>.#.#.#...###.#.#.#...#...#...#.#.....#...#.#...#...#\n#.#.#.###.#.#.#.#####.#.###.#v###.###########.#.#.#.###.#.#.#.###########.###.#.#.#.###v###.#.###.###.#.#.#######.###.#.#####.###.#.###.#.#.#\n#.#.#.....#.#.#...#...#.....#...#.#.....#.....#...#...#.#.#.#.#...........###...#...###...#.#.#...#...#.#...#...#.###.#.#...#.#...#.#...#.#.#\n#.#.#######.#.###.#.###########.#.#.###.#.###########.#.#.#.#.#.#########################.#.#.#.###.###.###.#.#.#.###.#.#.#.#.#.###.#.###.#.#\n#.#.......#...#...#.........#...#...#...#.#.....#.....#.#.#.#.#...........#.....#.........#...#...#...#.###...#.#.#...#.#.#.#.#.....#.#...#.#\n#.#######.#####.###########.#.#######.###.#.###.#.#####.#.#.#.###########.#.###.#.###############.###.#.#######.#.#.###.#.#.#.#######.#.###.#\n#.#.......#.....#####...#...#.......#...#.#...#...#...#.#...#.#.....#...#...#...#...............#...#.#.>.>.#...#.#...#.#.#...#.....#...#...#\n#.#.#######.#########.#.#.#########.###.#.###.#####.#.#.#####.#.###.#.#.#####.#################.###.#.###v#.#.###.###.#.#.#####.###.#####.###\n#.#.......#.......#...#.#.....#.....#...#...#...###.#...#.....#...#.#.#.#.....#...#...#.........#...#.#...#.#...#.#...#...#.....###.....#...#\n#.#######.#######.#.###.#####.#.#####.#####.###.###.#####.#######.#.#.#.#.#####.#.#.#.#.#########.###.#.###.###.#.#.#######.###########.###.#\n#...#...#.#.......#...#...#...#...###.....#...#...#.....#.#.......#...#.#...#...#...#...#.......#.....#...#.#...#...#...###...........#.#...#\n###.#.#.#.#.#########.###.#.#####.#######.###.###.#####.#.#.###########.###.#.###########.#####.#########.#.#.#######.#.#############.#.#.###\n#...#.#...#.........#...#.#...###...#...#.....###...###.#.#...........#.#...#...#...#...#...#...#.......#.#...#.......#.......#...#...#.#...#\n#.###.#############v###.#.###.#####.#.#.###########.###.#.###########.#.#.#####.#.#.#.#.###.#.###.#####.#.#####.#############.#.#.#.###.###.#\n#.....###...#.....#.>.#.#.#...#...#...#.......#####...#.#...>.>...#...#.#.###...#.#...#...#.#...#.....#.#...###.#...#.......#.#.#...#...#...#\n#########.#.#.###.#v#.#.#.#.###.#.###########.#######.#.#####v###.#.###.#.###.###.#######.#.###.#####.#.###.###.#.#.#.#####.#.#.#####.###.###\n#.........#.#...#.#.#...#...#...#.............#.......#.#.....###...###.#...#...#.#...#...#...#.......#...#...#...#...#.....#...#...#...#...#\n#.#########.###.#.#.#########.#################.#######.#.#############.###.###.#.#.#.#.#####.###########.###.#########.#########.#.###.###.#\n#.........#.....#.#.....#...#...............###.........#.............#.#...###...#.#.#.....#...#.....###.....###...#...#.........#...#.#...#\n#########.#######.#####.#.#.###############.#########################.#.#.#########.#.#####.###.#.###.###########.#.#.###.###########.#.#.###\n#.........#...###.......#.#.#...............#...#...#.................#...###.......#.......###...#...#...#####...#...#...#...#.......#.#...#\n#.#########.#.###########.#.#.###############.#.#.#.#.#######################.#####################.###.#.#####.#######.###.#.#.#######.###.#\n#.....#.....#...###...#...#.#...............#.#.#.#.#...........#.....#.....#.....#.............#...#...#.....#...#.....#...#.#.......#...#.#\n#####.#.#######.###.#.#.###.###############.#.#.#.#.###########.#.###.#.###.#####.#.###########.#.###.#######.###.#.####" <> ...

Part 1

defmodule Part1 do
  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.with_index()
    |> Enum.reduce(%{}, fn {row, y}, acc ->
      row
      |> String.graphemes()
      |> Enum.with_index()
      |> Enum.reduce(acc, fn {cell, x}, acc ->
        Map.put(acc, {x, y}, cell)
      end)
    end)
  end

  def start(map) do
    map
    |> Stream.filter(fn {{_, y}, cell} ->
      y == 0 && cell == "."
    end)
    |> Enum.at(0)
    |> elem(0)
  end

  def goal(map) do
    map
    |> Stream.filter(fn {{_, _}, cell} -> cell == "." end)
    |> Enum.max_by(fn {{_, y}, _} -> y end)
    |> elem(0)
  end

  def paths(map) do
    paths(map, start(map), goal(map))
  end

  def paths(map, start, goal) do
    paths(map, start, goal, MapSet.new([start]))
  end

  def paths(_map, start, goal, visited) when start == goal do
    [visited]
  end

  def paths(map, start, goal, visited) do
    {x, y} = start

    case map[start] do
      "." -> [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}]
      ">" -> [{x + 1, y}]
      "<" -> [{x - 1, y}]
      "^" -> [{x, y - 1}]
      "v" -> [{x, y + 1}]
    end
    |> Enum.filter(fn {_, y} -> y >= 0 end)
    |> Enum.filter(fn n -> map[n] != "#" end)
    |> Enum.filter(fn n -> !MapSet.member?(visited, n) end)
    |> Enum.flat_map(fn n ->
      paths(map, n, goal, MapSet.put(visited, n))
    end)
  end
end

(input |> Part1.parse() |> Part1.paths() |> Enum.map(&amp;MapSet.size/1) |> Enum.max()) - 1

2106

Part 2

defmodule Part2 do
  use Memoize

  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.with_index()
    |> Enum.reduce(%{}, fn {row, y}, acc ->
      row
      |> String.graphemes()
      |> Enum.with_index()
      |> Enum.reduce(acc, fn {cell, x}, acc ->
        Map.put(acc, {x, y}, cell)
      end)
    end)
  end

  defp start(map) do
    map
    |> Stream.filter(fn {{_, y}, cell} ->
      y == 0 && cell == "."
    end)
    |> Enum.at(0)
    |> elem(0)
  end

  defp goal(map) do
    map
    |> Stream.filter(fn {{_, _}, cell} -> cell == "." end)
    |> Enum.max_by(fn {{_, y}, _} -> y end)
    |> elem(0)
  end

  defp forks(map) do
    map
    |> Enum.filter(fn {{x, y}, c} ->
      c != "#" &&
        [{x + 1, y}, {x - 1, y}, {x, y - 1}, {x, y + 1}]
        |> Enum.filter(fn n ->
          cell = map[n]
          cell != nil && cell != "#"
        end)
        |> length > 2
    end)
    |> Enum.map(&elem(&1, 0))
    |> MapSet.new()
  end

  defp bfs(map, q, others, dists) do
    if q == [] do
      dists
    else
      [head | tail] = q

      if MapSet.member?(others, head) do
        bfs(map, tail, others, dists)
      else
        {x, y} = head

        neighbors =
          [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}]
          |> Enum.filter(fn n ->
            cell = map[n]
            cell != nil && cell != "#" && !Map.has_key?(dists, n)
          end)

        d = Map.get(dists, head, 0) + 1

        dists = Enum.reduce(neighbors, dists, fn n, acc -> Map.put(acc, n, d) end)

        bfs(map, tail ++ neighbors, others, dists)
      end
    end
  end

  defp graph(map, nodes) do
    nodes
    |> Enum.sort()
    |> Enum.map(fn n ->
      {
        n,
        bfs(map, [n], MapSet.delete(nodes, n), %{n => 0})
        |> Enum.filter(fn {k, _} -> MapSet.member?(nodes, k) && k != n end)
        |> Map.new()
      }
    end)
    |> Map.new()
  end

  defp paths(graph, start, goal, path \\ [])

  defp paths(_, start, goal, path) when start == goal do
    [[goal | path]]
  end

  defp paths(graph, start, goal, path) do
    graph[start]
    |> Enum.filter(fn {n, _cost} ->
      !Enum.any?(path, fn p -> p == n end)
    end)
    |> Enum.flat_map(fn {n, _cost} ->
      paths(graph, n, goal, [start | path])
    end)
  end

  defp cost(_graph, [_]), do: 0

  defp cost(graph, path) do
    [head | tail] = path
    next = List.first(tail)

    graph[head][next] + cost(graph, tail)
  end

  def solve(map) do
    start = start(map)
    goal = goal(map)
    forks = forks(map)

    nodes = MapSet.union(MapSet.new([start, goal]), forks)
    graph = graph(map, nodes)

    paths(graph, start, goal)
    |> Enum.map(&cost(graph, &1))
    |> Enum.max()
  end
end

Part2.parse(input)
|> Part2.solve()

6350