Nabladet

Luke 20

Innenfor programmering finnes det mange ulike "sportsgrener". Noen handler om å løse en oppgave på kortest mulig tid, det vil si tiden det tar å skrive et fungerende program. Andre om å løse en oppgave på kortest mulig kjøretid, det vil si tiden programmet bruker på å løse oppgaven. En tredje kategori handler om å løse en oppgave på færrest mulig tegn; kodegolfing. Ordet kommer av at man i golf forsøker å komme seg rundt banen på færrest mulig slag. Dette er en populær gren som til og med har sin egen side på stackexchange. Ofte avhenger lengden på slik kode veldig av språket, og det er til og med laget egne språk som er laget for å være korte for å løse slike problemer. For å unngå for stor variasjon i lengde, kan man gjerne begrense seg til et språk, som i luke 20.

Oppgavebeskrivelse

Skriv ut alle primtallene mellom 0 og 2018 som også resulterer i et annet (ulikt) primtall dersom rekkefølgen på sifrene reverseres. Hvis tallet ikke inneholder sifferet 7 skriv ut "god jul" i stedet.

Python2 er et språk med relativt store likheter til Python3, med få unntak. print er ikke lenger en funksjon, men et nøkkelord, som betyr at man kan skrive print"hello world" uten parenteser. I tillegg ble koden lest og kjørt via en Javascript-interpreter, som la til noen ekstra begrensninger:

• Noen funksjoner, som exec og raw_input ble fjernet, for å hindre at man bare kunne gi løsningen som en innputt.
• Interpreteren led av heltallsoverflyt, slik at 2**16 + 1 == 0. Dette ville ikke skjedd i et vanlig Python2-program.
• Interpreteren manglet også støtte for noe syntaks, som `2` (Python2-syntaks for repr(2), støttes ikke i Python3).

Før vi går igjennom løsningsforslagene, kommer vi til å gå gjennom noen generelle tips for golfing i Python. Viss du fremdeles ikke har prøvd deg på problemet selv, har du nå muligheten før du leser videre på tipsene. Viss du bare er her for løsningsforslagene, kan du bare hoppe over disse.

Pythongolf

Lambdafunksjoner

Anonyme funksjoner er funksjoner uten navn. Vanligvis gir man navn til en funksjon når man definerer den, men man kan lage anonyme funksjoner med lambda-nøkkelordet i Python. Som hovedregel skal man aldri bruke lambdafunksjoner viss funksjonen har et navn, men kan (mis)brukes i golfing til å lage kortere funksjoner. Lambdafunksjoner består kun av én linje og returner resultatet av denne linja. Nedenfor har vi to identiske implementasjoner av samme funksjon, den tar inn et tall og returnerer det dobbelte:

1
2
3

def d(x):return 2*x

d=lambda x:2*x

Siden lambdafunksjoner alltid returner uttrykket, trenger man ikke å skrive return. Da går man fra 19 til 14 tegn.

Short-circuiting og binær assignment

Viss Python kommer over en rekke med or-uttrykk, vil den automatisk kortslutte og returnere det første tilfellet som er Truthy. Det er fordi at viss dette uttrykket er sant, så er det ikke behov å sjekke om det neste uttrykket er sant, fordi vi bare bryr oss om at en av dem er sant. Dette kan brukes til assignment dersom det første uttrykket er usant.

1
2

a = 0 or 1 or 2
print(a) # printer 1

Tilsvarende motsatt med and, dersom Python kommer over et Falsy uttrykk, returnerer den dette og dropper å sjekke resten.

1
2

b = 0 and 1 and 2
print(b) # printer 0

Viss vi bare står mellom to muligheter, kan vi også bruke sannhetsverdien til å velge et element i en liste.

1

c = [a, b][s]

Python tolker True og False som hhv. 1 og 0. Dersom s da er sant, vil vi få c==b, og dersom s er usant får vi c==a .

Multippel sammenligning

I Python kan man sammenligne flere ting samtidig. Mens man i andre språk skal sjekke om et tall t ligger mellom a og b, må man f.eks. i C++ skrive

1

a < t and t < b

mens man i Python bare trenger å skrive

1

a < t < b

Python vil automatisk tolke dette som skrevet i C++-uttrykket.

Tuppel-assignment

Dersom man skal definere flere variabler, skjer dette vanligvis over flere linjer:

1
2
3

a=0
b=1
c=2

Dette er 11 tegn (man regner med linjeskift). Dette kan skrives på a,b,c=0,1,2 (som for øvrig også er 11 tegn). Men i andre tilfeller kan man skrive a=b=c=0 eller a,b,c="012".

Semikolon

Selv om semikolon er noe man vanligvis finner i andre språk, kan det også bruker i Python, dersom man vil skrive flere ting på samme linje.

1

a=0;b=1;c=2

Man er begrenset til "enkle" uttrykk etter semikolon, så ingen for-løkker eller if-setninger er lov, men det kan spare deg for indentering.

Dropp linjeskift etter kolon

Ikke gjør dette i vanlig kode, men linjeskift etter for-løkke-uttrykk og if-setninger kan ofte droppes.

1

if 1:print(1)

Løsningsforslag til delproblem

Før vi går gjennom sammensatte løsninger, skal vi se på hvordan hver enkelte del kan løses. Det finnes selvsagt andre måter å løse hvert problem på, men dette er et utvalg blant de korteste. Det er heller ikke gitt at den korteste løsningen på hvert delproblem gir den totalt korteste løsningen.

Løsningsforslagene er basert på løsningene som ble gitt, men er blitt ytterligere golfet, for å gi et bedre tall på hvor kort løsningen kunne blitt.

Primtall?

Nedenfor er de flere golfa varianter av primtallstester. Disse er gjerne en del av en funksjon, eller kan brukes direkte. Merk at p%k==0 og p%k<1 er identiske, siden vi opererer med heltall, men sistnevnte er ett tegn kortere. Merk også at viss man skriver return uten noe bak, returneres None, som er Falsy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# 47 tegn
for k in range(2,p):
 if p%k<1:return
 return 1

# 34 tegn: antall faktorer er null
sum(p%k<1for k in range(2,p))==0

# 28 tegn: p modulo alle tall under k gir rest
all(p%k for k in range(2,p))

Reversere en streng

De fleste fant samme løsning på denne:

1
2
3
4
5
6
7
8

# 20 tegn
s=str(p);q=int(s[::-1])

# 19 tegn
q=int(str(p)[::-1])

# 16 tegn
q=int(`p`[::-1])

En ting å merke seg er at man kan skrive `p` istedenfor str(p). Det vil si; `p` er egentlig repr(p) i python2, men til vårt formål gir det samme resultat. Dessverre taklet ikke interpreteren denne syntaksen.

God jul eller 7?

Det var flere varianter her. En ting å merke seg er at mellomrom ofte kan droppes mellom bokstaver og tegn.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# 43 tegn
if "7"in str(p):print"god jul"
else:print p

# 35 tegn
print p if"7"in str(p)else"god jul"

# 33 tegn
print p*("7"in str(p))or"god jul"

# 32 tegn
print("god jul",p)["7"in str(p)]

De to siste får samme lengde i Python3, men i Python2 er ikke print en funksjon, så vi slipper å omslutte uttrykket med parenteser.

Løsningsforslag til problemet

Kanonisk løsning

Dette er den enkleste løsningen vi får ved å kombinere de korteste svarene ovenfor. 239 tegn:

1
2
3
4

is_prime = lambda p: all(p%i for i in range(2,p))
reverse = lambda n: int(str(n)[::-1])
condition = lambda p: is_prime(p) and is_prime(reverse(p)) and q!=reverse(p)
for n in filter(condition, range(2018)):print("god jul",p)["7"in str(p)]

Dette er en kort (men ugolfet) løsning. Vi kan fjerne mellomrom her og der, korte ned variabelnavn og skrive lambdafunksjonen direkte inn i første argumentet til filter. En typisk løsningsstrategi er at viss man gjentar noe, forkorter man det til en funksjon. En annen strategi er å ikke gjenta seg, det vil si at man må prøve å finne en måte å bare bruke reverse én gang.

Enkel golfet løsning

Ved å gjør som vi foreslo overfor, kan vi enkelt korte ned løsningen et part tegn. 174 tegn:

1
2
3

P=lambda p:all(p%i for i in range(2,p))
R=lambda n:int(str(n)[::-1])
for p in filter(lambda p:P(p)*P(R(p))*(p!=R(p)),range(2018)):print("god jul",p)["7"in str(p)]

Merk at vi også brukte * istedenfor and. Det viser seg at det er raskere å bruke en if-setning istedenfor filter. 150 tegn:

1
2
3
4

P=lambda p:all(p%i for i in range(2,p))
R=lambda n:int(str(n)[::-1])
for p in range(2018):
 if P(p)*P(R(p))*(p!=R(p)):print("god jul",p)["7"in str(p)]

Selv om vi bruker R-funksjonen to ganger, er de raskere å lagre dette som en variabel. 137 tegn:

1
2
3
4

P=lambda p:all(p%i for i in range(2,p))
for p in range(2018):
 q=int(str(p)[::-1])
 if P(p)*P(q)*(p!=q):print("god jul",p)["7"in str(p)]

Herfra begynner ting å bli virkelig vanskelig. (Selv om løsningen vi nå har på ingen måte er åpenbar.) Vi ser at vi fremdeles har en lambdafunksjon og 3 ting vi må sjekke; at p er primtall, at q er primtall og at p og q er forskjellige.

Overengineering

En måte er å modifisere primtallsfunksjonen litt, slik at den returnerer p dersom p er primtall, og 0 ellers.

1

Q=lambda p:all(p%i for i in range(2,p))*p

Vi trenger da bare å se på forskjellen mellom Q(p) og Q(q), viss denne er 0, er enten verken p eller q primtall, eller så er disse like, så da overser vi dette. Viss forskjellen er et oddetall, så er enten p eller q ikke et primtall, siden alle partall er oddetall (viss vi overser 2). Da er både p og q ulike primtall dersom Q(p)-Q(q) er et partall forskjellig fra null.

Spørsmålet er da hvordan man sjekker om et partall er ulikt 0? Viss vi tar absoluttverdien og trekker fra 1, får vi abs(Q(p)-Q(q))-1, nå ser vi bare etter positive oddetall. Hvordan ser vi etter positive oddetall? Med bit-operatorer så klart! Oddetall ender alltid i 1 i binærtall, så vi trenger den siste biten for å sjekke om et tall er odde. For å sjekke tegn, trenger vi å sjekke det forreste tegnet. Dette er 0 for partall og 1 for oddetall. Dette tilsvarer å ta &-operatoren med et stort negativt tall på formen $-2^{\mathit{k}}-1$. 148 tegn:

1
2
3
4

Q=lambda p:all(p%i for i in range(2,p))*p
for p in range(1,2018,2):
 if abs(Q(p)-Q(int(str(p)[::-1])))-1&-16383>0:
 print("god jul",p)["7"in str(p)]

Denne løsningen fungerer fordi Python bruker two's complement for negative tall. Les mer om dette her.

Det viser seg at viss vi trekker fra 3, omgår vi problemet med 2 som primtall. 143 tegn:

1
2
3
4

Q=lambda p:all(p%i for i in range(2,p))*p
for p in range(2018):
 if abs(Q(p)-Q(int(str(p)[::-1])))-3&-16383>0:
 print("god jul",p)["7"in str(p)]

Denne løsningen bruker bare reverseringen én gang, så vi slipper å lagre denne, men den er lenger, så vi har tatt ett steg frem, men to steg tilbake. Dette er altså et håpløst fårsøk på å overkomplisere noe som har en mye penere løsning:

Multiplikasjon

Vi prøver igjen med Q-funksjonen, denne gang med multiplikasjon. Vi kan utnytte at vi kan koble sammen flere sammenligningoperatorer. 132 tegn:

1
2
3
4

Q=lambda p:all(p%i for i in range(2,p))*p
for p in range(2018):
 if 0<Q(p)!=Q(int(str(p)[::-1]))>0:
 print("god jul",p)["7"in str(p)]

Uttrykket vi har skrevet er ekvivalent med

1

0 < Q(p) and Q(p) != Q(int(str(n)[::-1])) and Q(int(str(n)[::-1])) > 0

Vi nærmer oss grensen for hvor mye vi kan forkorte. Skal vi korte ned mer, må vi finne en måte å bare bruke primtallsfunksjonen én gang, så vi slipper å lagre denne som variabel.

Semiprimtall

Semiprimtall er primtall på formen $n=pq$, der $p$ og $q$ er primtall. Semiprimtall har den egenskapen at de har veldig få faktorer, bare $\{1,p,q,pq\}$. Størrelsen på denne mengden er enten $3$ eller $4$, avhengig av om $p=q$ eller ei; er de like reduseres mengden $\{1,p,p^2\}$. Det vil si at om et tall er et semiprimtall, har det enten $3$ eller $4$ faktorer. Denne implikasjonen går også andre veien:

$n$ er et semiprimtall $\iff$ $n$ har 3 eller 4 (unike) faktorer.

Hvordan hjelper dette oss med oppgaven? Jo, vi ser at viss vi istedenfor å sjekke om p og p reversert er primtall, trenger vi bare å sjekke om p*q er et semiprimtall, det vil si at vi sjekker at p*q har 3 eller 4 faktorer. Vi ser også at viss antall faktorer er 4, vet vi at faktorene er ulike, altså at p!=q. Problemet reduseres altså til å sjekke antall faktorer i p*q. 124 tegn:

1
2
3

for p in range(2018):
 s=str(p);q=int(s[::-1])
 if sum(p*q%i==0 for i in range(1,p*q+1))==4:print("god jul",p)["7"in str(p)]

Ved litt golfing kan vi redusere dette ytterligere. Vi trenger nemlig bare å telle faktorer i $(1\dots pq)$ (dvs. vi kan droppe å sjekke om $1$ og $pq$ er faktorer). 122 tegn:

1
2
3

for p in range(2018):
 s=str(p);q=int(s[::-1])
 if sum(p*q%i<1for i in range(2,p*q))==2<q:print("god jul",p)["7"in str(p)]

Det tok seks dager etter publisering før løsningen over ble funnet. I ettertid virker selvfølgelig løsningen åpenbar, men med såpass stort løsningsrom kan det være vanskelig å vite hvilken retning man skal gå i. Det er heller ikke sagt at overnevnte løsning er perfekt.

Python2

Grunnet feil i interpreteren, støttet denne ikke Python 2s repr-notasjon. Med dette ville vi fått 111 tegn:

1
2
3

for p in range(2018):
 q=int(`p`[::-1])
 if sum(p*q%i<1for i in range(2,p*q))==2<q:print("god jul",p)["7"in`p`]

I python3 har vi ikke denne operatoren, men vi har fordelen at print er en funksjon, slik at vi kan kombinere denne med short-circuiting, og få alt på én linje. 112 tegn:

1

for p in range(2018):s=str(p);q=int(s[::-1]);sum(p*q%i<1for i in range(2,p*q))-2or print(("god jul",p)["7"in s])

Viss antall faktorer er ulik 2, vil utrykket være sant, så Python dropper å evaluere printeleddet.

Bonusspor

Da oppgaven ble lagt ut, ble det sagt at "whitespace" (dvs. mellomrom, tab og linjeskift-tegn) ikke ble regnet med. Dette viste seg å allikevel bli regnet med, men før dette ble oppdatert, ble en løsning som utnyttet dette laget. 71 tegn: (Nabla sin nettside fjerner dessverre mellomrommene som skal være lagret i o-variabelen, dette skal være en streng med mellomrom og tab-mellomrom.)

1
2
3
4
5
6
7
8
9

o = ""
s = i = 0
for c in '                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 ':
    if i%7 == 0:
        o += chr(s)
        s = 0
    s += 2**(i%7)*(c == "    ")
    i += 1
exec o[1:]

Denne har lagret et pythonprogram som whitespace, som den kjører med exec. Ved å konvertere \t til 1 og til 0 får vi en lang bitstreng:

1

1010111111100001000011100100011110001001001011100110110001111001111101100010010100011000100000010011010001111101001100001010000100100111010111011001111101011010010011001111101100010001011011101100010000101000011111001111110101111001000100110110011111011000100111110101111010100001111110111011001111101010110011001000011000010110011111011111001111110110011000000100101100011111011101100111110101101001000100111110110110000111100100010000011000101100111010110110011100101100010001101010110101101011110101111001100000010010110001111101011010011111010110100100010011111011011000011110010001000001100010110011101011011001111100101110010110001011010110100011010111111110111111011111101111110101101001001100111110111110001110101011010001101011111101011110010001001101100111110111110001110101011010010001001101000111010100110001101000101100011101010110100011010100100101010001101000101001010111001010001001101010110101111110101111001000100110110011111010110100100010011010001110101001100011010001011000111010101101000110101001001010100011010001010010101110010100010011010111111010111101010000111111010110100101000110101111111101111110111111011111101111110111111011111101111110101101001001100111110110111010001001101110111111011000100000010011010001111101011010010001001111101001100011010001011000111010101101000110101101000110101111111101111110111111011111101111110111111011111101111110111111011111101111110111111011111000101100001101001000100110100011101011011101000110000001001101100111110110101000101000110010010111010110101101011111111011111101111110111111011111101111110111111011111101010110011001000011000010110010100011010111111110111111011111101111110111111011111101111110111111011111101111110111111011111101111100010110000110100100010011010001110101011010001101011010111

Deler vi opp denne strengen i mindre deler, får vi en liste me ascii-verdiene til bokstaver, som blir

1
2
3
4
5
6
7
8

p=lambda n:not sum(d if n%d==0 and n != d else 0 for d in range(2,n))

for i in range(2019):
    if p(i) and p(int(str(i)[::-1])) and int(str(i)[::-1]) != i:
        if "7" not in str(i):
            print("god jul")
        else:
            print(i)

Primtallsmengde

En ting vi kan gjøre er å lage en mengde over primtallene mens vi itererer. Da trenger vi bare å sjekke om q er i primtallsmengden. Enten er q<p, og da trenger vi bare å sjekke q in P, der P er primtallsmengden med primtall opp til p. Dersom q>p, trenger vi bare å itererer fra p til q slik at vi får q<p. 194 tegn:

1
2
3
4
5
6
7
8

P=set();G=set()
for n in range(9999):
 if all(n%p for p in P):
  P.add(i)
  q=int(str(i)[::-1])
  if (q in P)*(p!=q):G.add(n);G.add(q)
for i in sorted(G):
 if i<2018:print("god jul",p)["7"in`p`]

Funksjonell og fungerende

1
2
3
4
5

from itertools import takewhile, count

is_small = lambda x: x < 100
square = lambda x: x**2
small_squared_integers = list(takewhile(is_small, map(square, count(0))))

reduce

Fold (også kalt reduce) er en operator som kombinerer en funksjon med en liste elementer. Dette kan brukes til å lage en verdi som "oppsummerer" lista. F.eks. vanlig summasjon i matematikk er en fold:

er (nesten) det samme som foldl (+) 0 [1..10] i språk som Haskell, reduce(+, 1:10) i Julia eller reduce(add, range(1, 10+1), 0) i Python. Nullen i de to uttrykkene betegner start-leddet, dvs. en tom sum er alltid null. Det er likevel en liten forskjell: dette er egentlig en left fold, altså vi antar venstre-assosiativitet, så vi regner egentlig ut

Men siden addisjon er assosiativ, får vi samme svar. Dette er tanken bak funksjonaliteten til følgende kode

1
2
3
4

from functools import reduce

add = lambda current_sum, next_addend: current_sum + next_addend
number_sum = reduce(add, range(1, 100+1)) #equivalent to sum(range(1, 100+1))

add-funksjonen kan også importeres fra operator-biblioteket som følger med Python. Her kan det være greit å poengtere at dette kan gjøres med vanlige for-løkker:

1
2
3

initial_value = 0
for e in range(1, 10+1):
  initial_value += e

men det ville jo ikke vært like gøy ...

1
2

multiply = lambda current_product, next_factor: current_product*next_factor
number_product = reduce(multiply, range(1, 10+1))

Her kan vi også importere mul fra operator istedenfor å lage denne selv. Python har to andre innebygde funksjoner som er basert på fold-mønsteret. Dette er all og any, som har tilsvarende implementasjon.

1
2

and_ = lambda current_bool, next_bool: current_bool and next_bool
number_all = reduce(and_, range(1, 10+1)) #equivalent to all(range(1, 10+1))

1
2

or_ = lambda current_bool, next_bool: current_bool or next_bool
number_all = reduce(or_, range(1, 10+1)) #equivalent to any(range(1, 10+1))

Med matematisk terminologi har vi en binær funksjon $\mathit{f}(a,b)$ og en (endelig) ordnet liste $\left(x_{\mathit{i}}\right)$ (samt en mulig startverdi $s_0$). En venstrefold blir da

En høyrefold blir tilsvarende

filter

filter er en funksjon som filtrerer ut elementer ut ifra ett sannhets-kriterie. Den tar inn en unær boolsk funksjon og en liste.

1
2
3
4
5

is_odd = lambda x: x%2

for i in filter(is_odd, range(10)):
  print(i, end=' ')
#1 3 5 7 9

Igjen, dette kan også skrives med vanlige for-løkker og if-setninger

1
2
3
4
5
6

is_odd = lambda x: x%2

for i in range(10):
  if is_odd(i):
    print(i, end=' ')
#1 3 5 7 9

Men fordi vi bare bruker oddetall i løkka, kan det være greit å filtrere bort partallene fra lista, istedenfor å sjekke dette i løkka.

Det var alt for denne gang. Nå blir det nok 4 måneder til neste blogginnlegg.