Jatketaan Advent of Code 2017:n toiseen tehtävään, jonka nimi on Corruption Checksum.

Syötteenä on riveittäin taulukko kokonaislukuja. Ensimmäisessä osassa jokaiselta riviltä haetaan suurimman ja pienimmän luvun erotus, ja nämä erotukset summataan lopuksi yhteen. Toisessa osassa taas etsitään kustakin rivistä ainoa pari, jossa toinen luku jakautuu toisella tasan, ja summataan näiden parien osamäärät.

Oma ratkaisuni on taas tarkoituksella melko tiivis. Käyn jokaisen rivin läpi kerran ja generoin saman rivin luvuista kaikki järjestetyt kahden alkion parit permutations()-funktion avulla. Samassa silmukassa päivitän sekä rivin minimi- ja maksimiarvot että etsin tasan jakautuvan parin. Sillä tavalla molempien osien vastaukset saa rakennettua yhdestä rivikohtaisesta kierroksesta.

Ratkaisu pyörii omalla koneellani noin 0,5 ms luokassa, eli käytännössä heti. Tiedän silti itsekin, ettei tämä ole välttämättä kaikkein optimaalisin tapa: permutaatioita syntyy paljon, ja puhtaampi sisäkkäinen silmukka tai lajitteluun nojaava versio voisi olla sekä selkeämpi että hieman tehokkaampi. Ehkä juuri siinä on tällaisissa pähkinöissä yksi hyvä opetus: vaikka ratkaisu toimii ja on jo nopea, parantamisen varaa löytyy lähes aina.

Ratkaisun lähdekoodi löytyy myös erillisenä tiedostona: d2_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
# Day 2: Corruption Checksum
from itertools import permutations
from time import perf_counter
from u.colors import cyan, purple, red

t, a, b = perf_counter(), 0, 0

for row in open('y2017/d2/i.txt').read().splitlines():
  nums = list(map(int, row.split()))
  max_v = min_v = nums[0]
  row_quotient = None

  for left, right in permutations(nums, 2):
    # Every value appears as the left-side element, so min/max can be tracked
    # for part 1 without a separate pass over the row.
    max_v = max(max_v, left)
    min_v = min(min_v, left)

    # The puzzle guarantees one evenly divisible pair per row.
    # Store it once, but keep the loop running so part 1 still finishes in the
    # same pass.
    if row_quotient is None and left % right == 0:
      row_quotient = left // right

  a += max_v - min_v
  b += row_quotient or 0

cyan(f'\na) {a}')
purple(f'b) {b}')
red(f'{(perf_counter() - t) * 1000} ms\n')

Tykkään tässä erityisesti siitä, että molemmat osat ratkeavat samalla rungolla eikä tarvitse kirjoittaa kahta täysin erillistä ratkaisua. Jos joskus palaan tähän vielä uudestaan, kokeilen todennäköisesti vertailun vuoksi myös versiota, jossa vältetään permutations()-tuottamien parien rakentaminen kokonaan.

Hiffasin tätä kirjoittaessa, että a-kohta saadaan tehokkaammin sorttaamalla nums ja välttämällä sen osalta kokonaan toinen silmukka. Tällöin voidaan lisätä toiseen silmukkaan myös break heti, kun yksikin ehdon täyttävä permutaatio löytyy. Tällä tavalla sain viilattua ajan 0.2 millisekuntiin.

Jätän tarkoituksella hieman heikomman tavan kuitenkin esimerkkiin ylle. Löydätkö sinä myös tuon paremman tavan?