Jatketaan Advent of Code 2017:n kolmanteen tehtävään, jonka nimi on Spiral Memory.

Tämä oli minusta jo hieman tavallista day 3:a haastavampi. Usein aivan alkupään tehtävät aukeavat vielä aika suoraviivaisesti, mutta tässä piti pysähtyä hetkeksi miettimään mitä ruudukossa oikeastaan tapahtuu. Se on minusta yleensä hyvä merkki: tehtävä ei ole hankala vain työn määrän takia, vaan siksi että se pakottaa hahmottamaan rakennetta.

Ensimmäinen osa kysyy annetun luvun Manhattan-etäisyyttä spiraalin keskelle. Suoraviivainen tapa olisi rakentaa koko ruudukko koordinaatteineen, mutta tähän kohtaan sitä ei oikeastaan tarvita lainkaan. Riittää huomata, että jokaisen kehän kulmiin osuvat parittomien lukujen neliöt. Kun oikea kehä on löydetty, etäisyyden saa laskettua suoraan siitä, kuinka kaukana luku on lähimmästä sivun keskipisteestä. En edes tiedä onko tämä se tavallisin tapa ratkaista a-kohta, mutta minusta ainakin aika siisti shortcut.

Toiseen osaan en sitten keksinyt vastaavaa oikotietä, joten siinä spiraali piti jo käytännössä rakentaa. Kävelen kehää ympäri yksi sivu kerrallaan ja säilytän jokaisen ruudun arvon sanakirjassa koordinaattiparin perusteella. Sanakirja tuntui tässä oikein luontevalta valinnalta: naapurit saa haettua helposti, eikä tarvitse varata etukäteen mitään kiinteää kaksiulotteista taulukkoa.

Ratkaisu pyörii omalla koneellani noin 0,1 ms ajassa, mikä on tällaiseen tehtävään jo oikein hyvä tulos. Toki aina voisi vielä viilata, mutta en tiedä saisinko parempaa aikaa ilman että koodi samalla menisi tarpeettoman erikoiseksi. Varsinkin b-kohdassa sanakirjaratkaisu tuntui hyvinkin oikealta valinnalta.

Ratkaisun lähdekoodi löytyy myös erillisenä tiedostona: d3_2017.py.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# Day 3: Spiral Memory
from time import perf_counter
from u.colors import cyan, purple, red

def d3a(limit, target):
  if target == 1:
    return 0

  for side in range(3, limit + 1, 2):
    if (ring_max := side**2) >= target:
      # Odd squares are the outer corners of each ring.
      # From there the Manhattan distance is just the ring radius plus the
      # shortest walk to one of the side midpoints.
      radius = side // 2
      side_span = side - 1
      offset = (target - (ring_max - radius)) % side_span
      return radius + min(offset, side_span - offset)

def d3b(limit, target):
  grid = {(0, 0): 1}
  neighbors = [
    (1, 0), (1, -1), (0, -1), (-1, -1),
    (-1, 0), (-1, 1), (0, 1), (1, 1),
  ]

  def cnt(x, y):
    # Only already-written cells contribute to the new value.
    c = sum(grid[(x + dx, y + dy)] for dx, dy in neighbors if (x + dx, y + dy) in grid)
    if c > target:
      return c
    grid[(x, y)] = c

  for ring in range(0, limit, 1):
    # Build one outer ring at a time around the origin.
    # Right edge. The first ring starts immediately next to the center.
    if ring == 0:
      for y in range(0, -ring - 2, -1):
        if count := cnt(ring + 1, y):
          return count
    else:
      for y in range(ring, -ring - 2, -1):
        if count := cnt(ring + 1, y):
          return count

    # Bottom edge.
    for x in range(ring + 1, -ring - 2, -1):
      if count := cnt(x, -ring - 1):
        return count

    # Left edge.
    for y in range(-ring - 1, ring + 2, 1):
      if count := cnt(-ring - 1, y):
        return count

    # Top edge.
    for x in range(-ring - 1, ring + 2, 1):
      if count := cnt(x, ring + 1):
        return count

t = perf_counter()
cyan(f'\na) {d3a(1000, 289326)}')
purple(f'b) {d3b(1000, 289326)}')
red(f'\nT: {(perf_counter() - t) * 1000} ms\n')

Tykkäsin tässä erityisesti siitä, että saman tehtävän kaksi osaa menivät lopulta aika eri tavoilla. A-kohdassa pääsi oikaisemaan rakenteen havainnoinnilla, mutta b-kohta palautti nopeasti takaisin koordinaatteihin, naapureihin ja askel askeleelta etenevään rakentamiseen. Ehkä juuri siksi tämä jäi mieleen tavallista parempana day 3:na.