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

  • What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
  • Where do I participate?: https://adventofcode.com/
  • Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
  • cvttsd2si@programming.dev
    ·
    7 months ago

    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
  • hades@lemm.ee
    ·
    6 months ago

    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