»Day 11: Chronal Charge«

The eleventh day presents us with a grid where each square is associated with its “power” (a function of its coordinates). We are supposed to find square windows in the grid with the largest sum of powers.

The input is a single integer serial. We prepare a function to calculate the power of a square at coordinates .

Preprocessing

n, serial = 300, 8141
power = lambda x, y: (((x+10)*y+serial)*(x+10)//100)%10-5

In the first part, we are supposed to find a window with the largest power sum. In order to avoid needless calls to power when iterating over windows, we will use a standard trick and construct a grid gcs of “up-left” cummulative sums in the grid. More specifically,

To construct gcd, we use the recursive relationship

At this point, we can calculate the sum of powers in the window with the upper-left corner at position in constant time, as

Finally, we prepare a function max_window which, given an integer , returns a triple with being the maximal possible sum of powers over windows, and is the upper-left corner of such a window. To solve the first part, we only need a single call max_window(3).

Part 1

  gcs = [[power(x, y) for y in range(1, n+1)] for x in range(1, n+1)]
  for x in range(1, n):
      for y in range(1, n):
          gcs[x][y] = power(x+1, y+1) + gcs[x-1][y] + gcs[x][y-1] - gcs[x-1][y-1]

  max_window = lambda k: max((gcs[x+k][y+k] + gcs[x][y] - gcs[x+k][y] - gcs[x][y+k], x+2, y+2) for x in range(n-k) for y in range(n-k))
  print('Part 1: {1},{2}'.format(*max_window(3)))

Part 2

In the second part, we are after maximal sum of powers over windows of arbitrary size. For this it suffices to use the function max_window from before, iterating over all possible windows sizes.

  print('Part 2: {1},{2},{3}'.format(*max((*max_window(k), k) for k in range(1, n))))

»Day 12: Subterranean Sustainability«

In the day 12, we are presented with a toy version of the »Conway’s Game of Life«, that is an (infinite) population of alive (#) and dead (.) cells, represented as a sequence. Each consecutive generation of the population is determined according to given rules: we take a look at a particular cell’s neighbourhood (2 cells to the left and 2 to the right), look up which rule applies to it, based on which we decide whether the cell will be alive or not in the next generation.

Preprocessing

The key idea will be that we will be only retaining the portion of the cell population which contains some alive cells, keeping track of the index of this portion in the sequence (for this purpose the variable shift will be used).

To apply rules at both ends of the portion correctly, we also make sure that we include at least 5 dead cells at either end, in each generation. This will be the job of the function pad. The function update will update the population to the next generation.

We will also need the evaluate function. The “evaluation” of a generation will be the sum of indices of all cells that are alive.

Finally, we parse the initial population and the rules/instructions.

  def pad(s):
      global shift
      while not s.startswith('.'*5):
          s = '.' + s
          shift -= 1
      while not s.endswith('.'*5):
          s = s + '.'
      return s

  def update(s):
      global shift
      shift += 2
      return pad(''.join(instructions.get(s[i-2:i+3], '.') for i in range(2, len(s)-2)))

  evaluate = lambda s: sum(i for i, x in enumerate(s, shift) if x == "#")

  shift = 0
  lines = open('day12.txt').readlines()
  s = pad(lines[0].split()[-1])
  instructions = dict([tuple(x.strip().split(' => ')) for x in lines[2:]])

Part 1

In the first part, we are supposed to find the “evaluation” of the 20-th generation.

  for i in range(20):
      s = update(s)
  print(f'Part 1: {evaluate(s)}')

Part 2

In the second part, we are supposed to find the “evaluation” of the 50000000000-th generation. As this is a large number, we will need to be more clever here.

By observing how the generations evolve, one will notice that from some point onwards, each generation will be of the same pattern, only shifted by a constant (presumably, the problem input was designed to have this property). Assume that is the smallest integer such that the -th generation has the same pattern as the -th generation, only shifted.

The key observation is that for any , the “evaluation” of the -th generation is a simple linear function:

  cnt, shift = 0, 0
  s = pad(lines[0].split()[-1])
  while 1:
      lasts, s, cnt = s, update(s), cnt + 1
      if s == lasts:
          curr_val, next_val = evaluate(s), evaluate(update(s))
          print(f'Part 2: {curr_val + (50000000000 - cnt)*(next_val - curr_val)}')
          break

»Day 13: Mine Cart Madness«

The input for the thirteenth day is hiding an ASCII “art” representing a system of tracks, in which a few carts are buzzing around. At intersections, the carts are turning according to a specific rule. Our task will be to simulate the whole system and examine the crashes of the carts. A toy example of such a system is depicted below.

/->-\
|   |  /----\
| /-+--+-\  |
| | |  | v  |
\-+-/  \-+--/
  \------/

Preprocessing

The problem is a very nice object-oriented programming task and we hence prepare a class Cart representing the carts in the system. For each cart, we need to remember:

  • Position. For a more compact solution, we will use the standard trick where the whole grid is represented as integer points in the complex plane. A position of the cart will in this representation be just a single complex number .
  • Direction. We will need to know whether the cart is facing north, west, south or east. These four directions are in our representations the 4 complex units .
  • Whether a cart has crashed. For this we only need a boolean variable active.
  • The number of times the cart has crossed an intersection. This is needed to determine where the cart is turning at intersections, as specified by the problem’s intersection rule, and will be stored as an integer cnter.

The cart will also have the three following methods:

  • turn, which will take a look at the type of track currently below the cart, and change its direction accordingly. Note that turning left and right can be nicely represented as multiplication by the complex numbers .
  • move, which will move the cart to the next position.
  • crash, which will “crash” the cart.

Finally, we read the ASCII grid and create a Cart object for each cart encountered.

  class Cart:
      def __init__(self, *args):
          self.pos, self.dir = args
          self.active = True
          self.cnter = 0

      def turn(self, track):
          if track == '\\': # regular turning track
              cart.dir *= 1j if int(self.dir.real) else -1j
          if track == '/': # regular turning track
              cart.dir *= -1j if int(self.dir.real) else 1j
          if track == '+': # intersections
              cart.dir *= -1j * pow(1j, self.cnter % 3)
              self.cnter += 1

      def move(self, grid):
          self.turn(grid[int(self.pos.imag)][int(self.pos.real)])
          self.pos += self.dir

      def crash(self):
          self.active = False

  grid, carts = open('day13.txt').readlines(), []
  for y, row in enumerate(grid):
      for x, track in enumerate(row):
          if track in '><v^':
              carts.append(Cart(x + y*1j, {'>':1, '<':-1, 'v':1j, '^':-1j }[track]))
          grid[y] = row.replace('>','-').replace('<','-').replace('^','|').replace('v','|')

Part 1

In the first part, we need to find out where the first crash in the system occurs. For simplicity, we simply print the first crash while solving the second part.

Part 2

In the second part, we are supposed to find the position of the only remaining cart after all of the other carts have crashed (yes, the input contains an odd number of carts). For this, we simply keep moving the carts, iterating in the manner specified by the problem (top-bottom and left-right), and crashing any two carts whose positions coincide.

  part1 = True
  while len(carts) > 1:
      # As problem specifies, need to iterate over carts top-bottom, left-right
      for cart in sorted(carts, key=lambda x: (x.pos.imag, x.pos.real)):
          if cart.active:
              cart.move(grid)
              if [c.pos for c in carts if c.active].count(cart.pos) > 1:
                  if part1:
                      print(f'Part 1: {int(cart.pos.real)},{int(cart.pos.imag)}')
                      part1 = False
                  [c.crash() for c in carts if c.active and c.pos == cart.pos]
      carts = [c for c in carts if c.active]

  print(f'Part 2: {int(carts[0].pos.real)},{int(carts[0].pos.imag)}')

»Day 14: Chocolate Charts«

In the day 14, we are being presented with a list and two pointers. At each step, we extend the list and update the pointers according to the specified rule.

Preprocessing

The problem input is just a single integer.

  n = 293801

Part 1

In the first part, we are asked to keep updating the list until it is reaches the length , then print out the last 10 digits. Although the problem statement itself assumes the list to be actually a string, we shall be using only a list of integers throughout. As Python’s conversions between integers and strings are quite expensive, this speeds up the process substantially.

  a, b, l = 0, 1, [3,7]
  while len(l) < n + 10:
      s = l[a] + l[b]
      l.extend([s] if s < 10 else divmod(s, 10))
      a, b = (a + l[a] + 1)%len(l), (b + l[b] + 1)%len(l)

  print(f'Part 1: {"".join(map(str, l[n:n+10]))}')

Part 2

In the second part, we are asked to keep updating the list until it contains a sublist (continuous) representing the digits of , then print out the index of such a sublist.

  seq = list(map(int, str(n)))
  a, b, l = 0, 1, [3,7]
  while l[-len(seq)-1:-1] != seq and l[-len(seq):] != seq:
      s = l[a] + l[b]
      l.extend([s] if s < 10 else divmod(s, 10))
      a, b = (a + l[a] + 1)%len(l), (b + l[b] + 1)%len(l)

  print(f'Part 2: {next(len(l) - len(seq) - i for i in [0,1] if l[-len(seq)-i:-i] == seq)}')

»Day 15: Beverage Bandits«

In the day 15, we will be simulating a war between Elfs and Goblins. This will be purely an object oriented programming task, where care will be needed to avoid pitfalls in many of the problem statement’s subtleties.

Preprocessing

We construct a class Unit representing the units in the war, equipped with three core methods needed to simulate the war:

  • turn, which takes the whole turn of the unit in the current round. The turn will consist of (possibly) moving and attacking.
  • move, which moves the unit towards the nearest enemy (according to given rules).
  • attack, which attacks the neighbouring enemy unit.

For the sake of compactness, we will (again) use the complex coordinates (as in Day 13). Related to this, a helper function access_grid will come handy. This function, given a complex number and a two dimensional array, returns the entry corresponding to the coordinates represented by the complex number.

Finally, we read the input; a two dimensional grid.

  from itertools import chain
  from copy import deepcopy

  class Unit:
      def __init__(self, *args):
          self.type, self.pos, self.attack_power = args
          self.active = True
          self.hp = 200

      def range(self, grid):
          return [self.pos + d for d in [1j,-1j,1,-1] if access_grid(self.pos + d, grid) == '.']

      def receive_attack(self, power, grid):
          self.hp -= power
          if self.hp <= 0:
              self.active = False
              grid[int(self.pos.imag)][int(self.pos.real)] = '.'

      def move(self, units, grid):
          inrange = set(chain(*[u.range(grid) for u in units if u.active and u.type != self.type]))

          stack, parent = [self.pos], {self.pos: None}
          while stack:
              next_stack = []
              for curr in stack:
                  for ne in [curr+d for d in [1j,-1j,1,-1] if access_grid(curr+d, grid)=='.' and not curr+d in parent]:
                      parent[ne] = curr
                      next_stack.append(ne)
              if any(x in inrange for x in next_stack): # some shortest path encountered
                  towards = sorted([x for x in next_stack if x in inrange], key=lambda x: (x.imag, x.real))[0]
                  while parent[towards] != self.pos:
                      towards = parent[towards]
                  # make the move
                  grid[int(self.pos.imag)][int(self.pos.real)] = '.'
                  self.pos = towards
                  grid[int(towards.imag)][int(towards.real)] = self.type
                  break
              stack = sorted(next_stack, key=lambda x: (x.imag, x.real))

      def attack(self, units, grid):
          inrange = [u for u in units if u.active and u.type != self.type and abs(u.pos - self.pos) == 1]
          if inrange:
              sorted(inrange, key=lambda u: (u.hp, u.pos.imag, u.pos.real))[0].receive_attack(self.attack_power, grid)

      def turn(self, units, grid):
          if self.active:
              if not any(abs(u.pos - self.pos) == 1 and u.active for u in units if u.type != self.type):
                  self.move(units, grid)
              self.attack(units, grid)

  def access_grid(complex_n, grid):
      return grid[int(complex_n.imag)][int(complex_n.real)]

  grid = [list(l.strip()) for l in open('day15.txt').readlines()]

Part 1

In the first part, we are to simulate the war, where each unit, regardless of whether it is Elf or Goblin, has a fighting strength 3. We need to return the “value” of such a war, which is defined as the number of complete rounds multiplied by the sum of the health points of all surviving units.

  def part1(grid):
      units = [Unit(f, x+y*1j, 3) for y, row in enumerate(grid) for x, f in enumerate(row) if f in 'GE']
      for rounds in range(10**9):
          for i, u in enumerate(sorted(units, key=lambda x: (x.pos.imag, x.pos.real))):
              if len(set(u.type for u in units if u.active)) == 1:
                  return rounds * sum(u.hp for u in units if u.active)
              u.turn(units, grid)
  print(f'Part 1: {part1(deepcopy(grid))}')

Part 2

In the second part, we are to find the smallest possible fighting strength for Elves, such that they win the war without any loses. After such a value is found, we need to return the “value” of the corresponding war again. Note that a linear search is necessary here, since the rules of the war are such that “elves with strength win the war without any losses” does not imply “elves with strength win the war without any losses”.

  def part2(grid):
      def simulate(elf_strength, grid):
          units = [Unit(f, x+y*1j, 3 if f=='G' else elf_strength) for y, row in enumerate(grid) for x, f in enumerate(row) if f in 'GE']
          for rounds in range(10**9):
              for i, u in enumerate(sorted(units, key=lambda x: (x.pos.imag, x.pos.real))):
                  if len(set(u.type for u in units if u.active)) == 1:
                      if any(u.type == 'E' and u.active == False for u in units):
                          return -1 # no losses tolerated
                      return rounds * sum(u.hp for u in units if u.active)
                  u.turn(units, grid)
      for elf_strength in range(3, 10**9):
          game_outcome = simulate(elf_strength, deepcopy(grid))
          if game_outcome != -1:
              return game_outcome
  print(f'Part 2: {part2(deepcopy(grid))}')