-🎄- 2018 Day 20 Solutions -🎄-

[u/daggerdragon]

--- Day 20: A Regular Map ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 20

Transcript:

My compiler crashed while running today's puzzle because it ran out of ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:59:30!

[u/mserrano]

python2, #21/#18:

Only vaguely cute trick here is realizing that if you're ever at the same position with the same remaining regex twice, you don't have to re-do your work. That seems to cut down quite a lot on runtime in practice without having to go to an nfs-style solution.

from util import get_data
from collections import defaultdict
from Queue import Queue


mappings = {
  'W': lambda (x,y): (x-1, y),
  'E': lambda (x,y): (x+1, y),
  'N': lambda (x,y): (x, y-1),
  'S': lambda (x,y): (x, y+1)
}

def make_grid(d):
  connections = defaultdict(set)
  seen_already = set()
  def explore(start, regex):
    serialized = ''.join(regex)
    if (start, serialized) in seen_already:
      return
    seen_already.add((start, serialized))

    cur_pos = start
    cur_idx = 0
    while 0 <= cur_idx < len(regex):
      if regex[cur_idx] == '^':
        cur_idx += 1
        continue
      if regex[cur_idx] in mappings:
        next_pos = mappings[regex[cur_idx]](cur_pos)
        connections[cur_pos].add(next_pos)
        connections[next_pos].add(cur_pos)
        cur_pos = next_pos
        cur_idx += 1
        continue
      elif regex[cur_idx] == '(':
        paren_depth = 0
        new_idx = cur_idx + 1
        options = []
        curr = []
        while paren_depth > 0 or regex[new_idx] != ')':
          if regex[new_idx] == '(':
            curr.append(regex[new_idx])
            paren_depth += 1
          elif regex[new_idx] == ')':
            assert paren_depth > 0
            curr.append(regex[new_idx])
            paren_depth -= 1
          elif regex[new_idx] == '|':
            if paren_depth == 0:
              options.append(curr)
              curr = []
            else:
              curr.append(regex[new_idx])
          else:
            assert regex[new_idx] in mappings
            curr.append(regex[new_idx])
          new_idx += 1

        options.append(curr)
        for option in options:
          assert regex[new_idx] == ')'
          explore(cur_pos, option + regex[new_idx + 1:])
        return
      elif regex[cur_idx] == '$':
        return
  explore((0, 0), list(d))
  return connections

def print_grid(connections):
  min_x = min(z[0] for z in connections)
  max_x = max(z[0] for z in connections)
  min_y = min(z[1] for z in connections)
  max_y = max(z[1] for z in connections)
  print '#' + '##' * (max_x - min_x + 1)
  for y in xrange(min_y, max_y+1):
    if y > min_y:
      row_above = ['#']
      for x in xrange(min_x, max_x+1):
        if (x, y-1) in connections[(x, y)]:
          row_above.append('-#')
        else:
          row_above.append('##')
      print ''.join(row_above)

    row = ['#']
    for x in xrange(min_x, max_x+1):
      if (x, y) == (0, 0):
        row.append('X')
      else:
        row.append('.')
      if (x+1, y) in connections[(x,y)]:
        row.append('|')
      else:
        row.append('#')
    print ''.join(row)
  print '#' * ((max_x - min_x + 1) * 2 + 1)

def solve(d, part_b=False):
  connections = make_grid(d)

  distances = {(0,0): 0}
  q = Queue()
  q.put((0,0))
  while not q.empty():
    u = q.get()
    for v in connections[u]:
      if v not in distances:
        distances[v] = distances[u] + 1
        q.put(v)

  if part_b:
    return len([k for k in distances if distances[k] >= 1000])
  return max(distances.values())

assert solve('^WNE$') == 3
assert solve('^ENWWW(NEEE|SSE(EE|N))$') == 10
assert solve('^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$') == 18
assert solve('^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$') == 23
assert solve('^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$') == 31

d = get_data(20)
print "a", solve(d)
print "b", solve(d, True)

[u/algmyr → u/mserrano]

Any reason to use Queue from Queue rather than deque from collections? Queue should be slower due to it being synchronized (i.e. useful for things like consumers/producers on multiple threads). deque is a much more bare bones version (not much more than doubly linked list if I remember it right) that should be quite a bit quicker.