Jatketaan Advent of Code 2017:n neljänteen tehtävään, jonka nimi on High-Entropy Passphrases.

Tämä oli minusta oikein mukava ja melko helppo tehtävä. Tykkäsin erityisesti siitä, että a-kohtaan löytyi heti siisti yhden rivin ratkaisu. Kun jokaisen rivin sanat laittaa set-rakenteeseen ja vertaa sen pituutta alkuperäiseen listaan, duplikaatit paljastuvat saman tien. Tällaiset hetket ovat juuri niitä, joissa Pythonin idiomit tuntuvat palkitsevilta.

Moni kirjoittaisi saman ehkä vähän auki pidemmällä silmukalla, mutta minusta pythonic-tyyliä kannattaa käyttää silloin kun se oikeasti tekee ratkaisusta sekä tiiviin että luonnollisen. Kun tällaisiin rakenteisiin tottuu, ne eivät enää tunnu kikkailulta vaan ihan luettavalta perustyyliltä.

Toinen osa nostaa haastetta sen verran, että pelkkä duplikaattien tarkistus ei enää riitä, vaan pitää sulkea pois myös anagrammit. Oma versioni käy läpi saman rivin sanaparit combinations()-funktion avulla ja vertaa sorttaamalla kirjaimet sanoja toisiinsa. En ole lainkaan varma, onko tämä tehokkain tapa ratkaista b-kohta. Todennäköisesti parempikin löytyy. Silti itertools tuntuu tällaisissa pähkinöissä usein hyvältä työkalulta: kirjaston iteraattorit ovat valmiiksi hyvin optimoituja ja koodi pysyy aika kompaktina.

Tällä tavalla ratkaisu vie omalla koneellani noin 2ms, eli hieman enemmän kuin aiemmissa tehtävissä. Uskon kyllä, että tästä voisi ottaa aikaa pois paremmalla lähestymistavalla. Toisaalta jotain työtä b-kohta joka tapauksessa vaatii, koska sanoissa pitää mennä kirjaintasolle asti jollain tavalla.

Ratkaisun lähdekoodi löytyy myös erillisenä tiedostona: d4_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
# Day 4: High-Entropy Passphrases
from itertools import combinations
from time import perf_counter
from u.colors import cyan, purple, red

def d4a():
  # A passphrase is valid for part 1 if every word is unique.
  return sum(1 for row in rows if len(set(row)) == len(row))

def is_anagram(r):
  for w1, w2 in combinations(r, 2):
    if len(w1) == len(w2) and sorted(w1) == sorted(w2):
      return True

def d4b():
  # Part 2 keeps the duplicate-word rule and rejects anagram pairs as well.
  return sum(1 for row in rows if len(set(row)) == len(row) and not is_anagram(row))

t = perf_counter()

# Parse each passphrase once so both parts can reuse the same rows.
rows = [line.split() for line in open('y2017/d4/i.txt').read().splitlines()]

cyan(f'\na) {d4a()}')
purple(f'b) {d4b()}')
red(f'T: {(perf_counter() - t) * 1000} ms\n')

Tykkäsin tässä siitä, että tehtävä pysyi kokonaisuutena aika kompaktina ja helposti hahmotettavana. Jos joskus palaan tähän vielä uudestaan, mietin voiko tämän toteuttaa ilmankin kombinaatioiden generointia.