Skip Navigation

👣 - 2023 DAY 23 SOLUTIONS -👣

Day 22: A Long Walk

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

5
5 comments
  • Scala3

    val allowed: Map[Char, List[Dir]] = Map('>'->List(Right), '<'->List(Left), '^'->List(Up), 'v'->List(Down), '.'->Dir.all)
    
    def toGraph(g: Grid[Char], start: Pos, goal: Pos) =
        def nb(p: Pos) = allowed(g(p)).map(walk(p, _)).filter(g.inBounds).filter(g(_) != '#')
    
        @tailrec def go(q: List[Pos], seen: Set[Pos], acc: List[WDiEdge[Pos]]): List[WDiEdge[Pos]] =
            q match
                case h :: t =>
                    @tailrec def findNext(prev: Pos, n: Pos, d: Int): Option[(Pos, Int)] =
                        val fwd = nb(n).filter(_ != prev)
                        if fwd.size == 1 then findNext(n, fwd.head, d + 1) else Option.when(fwd.size > 1 || n == goal)((n, d))
    
                    val next = nb(h).flatMap(findNext(h, _, 1))
                    go(next.map(_._1).filter(!seen.contains(_)) ++ t, seen ++ next.map(_._1), next.map((n, d) => WDiEdge(h, n, d)) ++ acc)
                case _ => acc
        
        Graph() ++ go(List(start), Set(start), List()) 
    
    def parseGraph(a: List[String]) =
        val (start, goal) = (Pos(1, 0), Pos(a(0).size - 2, a.size - 1))
        (toGraph(Grid(a.map(_.toList)), start, goal), start, goal)
    
    def task1(a: List[String]): Long = 
        val (g, start, goal) = parseGraph(a)
        val topo = g.topologicalSort.fold(failure => List(), order => order.toList.reverse)
        topo.tail.foldLeft(Map(topo.head -> 0.0))((m, n) => m + (n -> n.outgoing.map(e => e.weight + m(e.targets.head)).max))(g.get(start)).toLong
    
    def task2(a: List[String]): Long = 
        val (g, start, goal) = parseGraph(a)
    
        // this problem is np hard (reduction from hamilton path)
        // on general graphs, and I can't see any special case
        // in the input.
        // => throw bruteforce at it
        def go(n: g.NodeT, seen: Set[g.NodeT], w: Double): Double =
            val m1 = n.outgoing.filter(e => !seen.contains(e.targets.head)).map(e => go(e.targets.head, seen + e.targets.head, w + e.weight)).maxOption
            val m2 = n.incoming.filter(e => !seen.contains(e.sources.head)).map(e => go(e.sources.head, seen + e.sources.head, w + e.weight)).maxOption
            List(m1, m2).flatMap(a => a).maxOption.getOrElse(if n.outer == goal then w else -1)
        
        val init = g.get(start)
        go(init, Set(init), 0).toLong
    
  • Rust Solution

    For Part One I used a depth-first search which took too long for part two. Part Two I created an adjacency list of the junction points while keeping track of the distance to the adjacent nodes at the same time. Then depth-first search through the adjacency list.

  • Nim

    Part 1 was just a simple search. Part 2 looked like it just needed a trivial modification, but with the removal of the one-way tiles, the result I was getting was getting for the example was too large. I switched to a different method of determining the path length, but didn't yet figure out what what I had been doing wrong. Since the search space was now significantly larger, my part 2 code took almost an hour to come up with the answer.

    I rewrote part 2 to simplify the maze into a graph with a node for each intersection and for the start and goal tiles, with edge costs equal to the path length between each. This resulted in significantly faster iteration (17 seconds instead of 52 minutes), but didn't actually reduce the search space. I'm assuming there's some clever optimization that can be done here, but I'm not sure what it is.

    The rewrite was still getting the wrong answer, though. I eventually figured out that it was including paths that didn't actually reach the goal, as long as they didn't revisit any nodes. I changed my recursive search function to return a large negative result at dead ends, which fixed the issue.

  • Python

    from .solver import Solver
    
    
    def _directions_from(char: str) -> list[tuple[int, int]]:
      if char == '.':
        return [(0, 1), (0, -1), (1, 0), (-1, 0)]
      if char == 'v':
        return [(1, 0)]
      if char == '^':
        return [(-1, 0)]
      if char == '<':
        return [(0, -1)]
      if char == '>':
        return [(0, 1)]
      raise ValueError(f'unknown char: {char}')
    
    class Day23(Solver):
      lines: list[str]
    
      def __init__(self):
        super().__init__(23)
    
      def presolve(self, input: str):
        self.lines = input.splitlines()
    
      def _find_longest(self, current: tuple[int, int], visited: set[tuple[int, int]]) -> int|None:
        i, j = current
        if i == len(self.lines) - 1:
          return 0
        visited.add(current)
        options = []
        for di, dj in _directions_from(self.lines[i][j]):
          ni, nj = i + di, j + dj
          if ni < 0 or ni >= len(self.lines) or nj < 0 or nj >= len(self.lines[0]):
            continue
          if self.lines[ni][nj] == '#':
            continue
          if (ni, nj) in visited:
            continue
          result = self._find_longest((ni, nj), visited)
          if result is not None:
            options.append(result)
        visited.remove(current)
        if options:
          return max(options) + 1
        return None
    
      def solve_first_star(self) -> int:
        start_i = 0
        start_j = self.lines[0].find('.')
        result = self._find_longest((start_i, start_j), set())
        assert result
        return result
    
      def _find_longest_2(self, current: tuple[int, int],
                          connections: dict[tuple[int, int], list[tuple[int, int, int]]],
                          visited: set[tuple[int, int]]) -> int|None:
        i, j = current
        if i == len(self.lines) - 1:
          return 0
        visited.add(current)
        options = []
        for ni, nj, length in connections[(i, j)]:
          if (ni, nj) in visited:
            continue
          result = self._find_longest_2((ni, nj), connections, visited)
          if result is not None:
            options.append(result + length)
        visited.remove(current)
        if options:
          return max(options)
        return None
    
      def solve_second_star(self) -> int:
        start_i = 0
        start_j = self.lines[0].find('.')
    
        stack = [(start_i, start_j)]
        connections = {}
        visited = set()
        while stack:
          edge_i, edge_j = stack.pop()
          i, j = edge_i, edge_j
          path_length = 0
          options = []
          connections[(edge_i, edge_j)] = []
          while True:
            options = []
            path_length += 1
            visited.add((i, j))
            for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
              ni, nj = i + di, j + dj
              if ni < 0 or ni >= len(self.lines) or nj < 0 or nj >= len(self.lines[0]):
                continue
              if self.lines[ni][nj] == '#':
                continue
              if (ni, nj) in visited:
                continue
              options.append((ni, nj))
            if len(options) == 1:
              i, j = options[0]
            else:
              connections[(edge_i, edge_j)].append((i, j, path_length - 1))
              break
          connections[(i, j)] = [(ni, nj, 1) for ni, nj in options]
          stack.extend(options)
    
        connections_pairs = list(connections.items())
        for (i, j), connected_nodes in connections_pairs:
          for (ni, nj, d) in connected_nodes:
            if (ni, nj) not in connections:
              connections[(ni, nj)] = [(i, j, d)]
            elif (i, j, d) not in connections[(ni, nj)]:
              connections[(ni, nj)].append((i, j, d))
    
        result = self._find_longest_2((start_i, start_j), connections, set())
        assert result
        return result