»Day 6: Chronal Coordinates«

The sixth day lets us build a »Voronoi diagram« under the Manhattan distance, where the seeds are given.

Preprocessing

  seeds = [tuple(map(int, l.split(','))) for l in open('day6.txt').readlines()]

Part 1

To crack the problem, we need to figure out which cells in the diagram will turn out to be infinite. For this, we use two ingredients:

  • The function closest calculates the seed closest to a given point, returning 0 in case of a tie and index of the closest seed (starting at 1) otherwise.
  • Manually hardcoding the size of a “sufficiently large” bounding box of all seeds, the infinite cells will correspond precisely to:

Finally, we need to calculate the size of the largest finite cell.

  from collections import Counter
  closest = lambda x,y: next(map(lambda l: l[0][1]*(l[0][0]!=l[1][0]), [sorted((abs(x-i)+abs(y-j),k) for k,(i,j) in enumerate(seeds,1))]))
  size = 400 # size of the "sufficiently large" bounding box

  c = Counter(closest(x, y) for x in range(size) for y in range(size))
  infinite = set(closest(x, y) for x in range(size) for y in range(size) if {0,size-1}&{x,y})
  print(f'Part 1: {max(c[k] for k in c.keys() if not k in infinite)}')

Part 2

The second part asks us to calculate the number of grid coordinates with a total sum of distances from all of the seeds less than 10000. All needed to do here is to find the size of another, for this problem “sufficiently large”, bounding box. Next, a simple bruteforce iteration suffices.

  MAX = 10000
  all_seeds_dist = lambda x, y: sum(abs(x-i) + abs(y-j) for i, j in seeds)
  bound_size = 1000; assert(all_seeds_dist(bound_size, bound_size) > 10000) # sufficient bound
  print(f'Part 2: {sum(all_seeds_dist(x, y) < MAX for x in range(bound_size) for y in range(bound_size))}')

»Day 7: The sum of its parts«

In the seventh day, we are given a list of instructions/tasks, together with constraints saying that some tasks must be performed before others. We will be interested in “optimal” ways to perform the tasks.

Preprocessing

To simplify sum cumbersome operations with the graph, we will use some functions from the networkx library.

  from networkx import DiGraph

  g = DiGraph()
  for l in open('day7.txt').readlines():
      g.add_edge(l.split()[1], l.split()[-3])

Part 1

Given a graph of dependencies, the first part asks us to find the lexicographically smallest topological ordering of this graph. This is something that networkx already has a function for.

  from networkx.algorithms.dag import lexicographical_topological_sort
  print(f'Part 1: {"".join(lexicographical_topological_sort(g))}')

Part 2

In the second part, we are given additional information: for each task, we now know the amount of time it takes. Our workforces has now been increased to 5 workers and we are interested in knowing the smallest possible time in which our workers can complete all of the task. We opt for greedy approach. At each iteration we either:

  • see that some worker is free, in which case we assign to him the least-time consuming task from all tasks which are available at the moment.
  • see that all workers are busy, in which case we can fast-forward the time until some of the workers finishes his task. We then mark the task as done and free the worker.

We also note that the first part might have been solved by setting nworkers = 1 and printing the tasks as they get assigned to the single worker.

  nworkers, time, workers = 5, 0, {} # workers = {task: remaining time, ...}
  while workers or g:
      ready = set(t for t in g if not g.in_degree(t)) - workers.keys()
      if ready and len(workers) < nworkers:
          workers[min(ready)] = ord(min(ready)) - 4 # minutes required for task min(ready)
      else:
          mtime = min(workers.values())
          workers = dict([(t, r-mtime) for t, r in workers.items() if r > mtime or g.remove_node(t)])
          time += mtime
  print(f'Part 2: {time}')

»Day 8: Memory Maneuver«

In the eight day, we are given tree flattened in a specific recursive way. Given this flattened version, we are supposed to perform some calculations involving leaves of the tree.

Preprocessing

In the recursive functions below, we will be accessing the elements of the list from the back, we thus reverse the list immediately during parsing.

  l = list(map(int, open('day8.txt').read().strip().split()[::-1]))

Part 1

In the first part, we need to sum up the values attached at each leave. This is quite easy to do just by mimicking the flattening process recursively. Note that we, very conveniently, use the pop() function of Python lists, which allows us to consecutively, and recursively, iterate over the whole list.

  def consume():
      ch, m = l.pop(), l.pop()
      return sum(consume() for _ in range(ch)) + sum(l.pop() for _ in range(m))
  print(f'Part 1: {consume()}')

Part 2

In the second part, rather than summing up the values attached at the leaves, we will need to sum up scores calculated at each node. The calculation of the score gets more involved, but can be still done just by mimicking the flattening process recursively.

  l = list(map(int, open('day8.txt').read().strip().split()[::-1]))

  def consume2():
      ch, m = l.pop(), l.pop()
      scores = [consume2() for _ in range(ch)] + [0]
      return sum(l.pop() for _ in range(m)) if ch == 0 else sum(scores[min(l.pop()-1, ch)] for _ in range(m))
  print(f'Part 2: {consume2()}')

»Day 9: Marble Mania«

In the ninth day, we are given a circular list of marbles, into which we will be inserting new marbles in a specific way, placed by players taking turns.

Preprocessing

  import re
  players, marbles = map(int, re.findall(r'-?\d+', open('day9.txt').read()))

The first part asks us to simulate the game. Since any new marble will be placed within small distance 7 from the last one, we can simmulate the whole game via rotation of the circular array. This can be done very efficiently using the Python’s deque, which offers precisely the operation of rotation (both clockwise and anticlockwise). We then blindly implement the rules of the game as given by the problem statement.

Part 1

  from collections import deque, defaultdict

  def game(marbles, players):
      q, scores = deque([0]), defaultdict(int)
      for i in range(1, marbles + 1):
          if i % 23 == 0:
              q.rotate(7); scores[i%players] += q.pop() + i; q.rotate(-1)
          else:
              q.rotate(-1); q.append(i)
      return max(scores.values())

  print(f'Part 1: {game(marbles, players)}')

Part 2

In the second part, we are required to do nothing else than to play the game with a bigger amount of marbles. Since the implementation with deque is sufficiently fast, there is nothing else to do.

  print(f'Part 2: {game(marbles*100, players)}')

»Day 10: The Stars Align«

In the tenth day, we are given a collection of particles in a grid, together with their corresponding velocities. We are told that the particles will align to form a sentence at a particular nonnegative time.

Preprocessing

Apart from parsing of the input, we prepare for the first time a utility function that will be needed: The »ternary search«, which can minimize a convex function in a logarithmic time.

  import re
  particles = [tuple(map(int, re.findall(r'-?\d+', l))) for l in open('day10.txt').readlines()]

  def ternarySearch(f, l, r, prec=1e-2):
      while abs(r - l) > prec:
          lt, rt = l + (r - l)/3, r - (r - l)/3
          l, r = (lt, r) if f(lt) > f(rt) else (l, rt)
      return (l + r)/2

Part 1

In the first part, we are supposed to find the sentence formed when the particles align. For this, we will use the following heuristic (which is not guaranteed to work in general; if we however assume the given velocities to be somehow random, this heuristics will do well): we will try to minimize the diameter of the set of particles, where the diameter is defined as:

Since this function is first decreasing and, after reaching its minimum, increasing, we may use ternary search to find the minimum. After calculating the optimal time for the diameter to be minimal, we simply print the positions of the particles.

  diameter = lambda t: sum(max(p[i]+t*p[i+2] for p in particles) - min(p[i]+t*p[i+2] for p in particles) for i in [0,1])
  T = round(ternarySearch(diameter, 0, 1e8)) # optimal time for minimizing diameter

  xs, ys = [p[0]+T*p[2] for p in particles], [p[1]+T*p[3] for p in particles]
  final = set(zip(xs, ys))

  print('Part 1:')
  for i in range(min(ys), max(ys)+1):
      print(''.join('#' if (j, i) in final else '.' for j in range(min(xs), max(xs)+1)))

Part 2

The second part only asks us for the time when the particles align. This has been already calculated.

  print(f'Part 2: {T}')