Nabladet
Kodegolfing
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
ograw_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 forrepr(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 |
|
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 |
|
Tilsvarende motsatt med and
, dersom Python kommer over et Falsy uttrykk, returnerer den dette og dropper å sjekke resten.
1 2 |
|
Viss vi bare står mellom to muligheter, kan vi også bruke sannhetsverdien til å velge et element i en liste.
1 |
|
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 |
|
mens man i Python bare trenger å skrive
1 |
|
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 |
|
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 |
|
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 |
|
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.
Reversere en streng
De fleste fant samme løsning på denne:
1 2 3 4 5 6 7 8 |
|
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.
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:
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 |
|
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 |
|
Selv om vi bruker R
-funksjonen to ganger, er de raskere å lagre dette som en variabel. 137 tegn:
1 2 3 4 |
|
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 |
|
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 . 148 tegn:
1 2 3 4 |
|
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 |
|
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 |
|
Uttrykket vi har skrevet er ekvivalent med
1 |
|
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 , der og er primtall. Semiprimtall har den egenskapen at de har veldig få faktorer, bare . Størrelsen på denne mengden er enten eller , avhengig av om eller ei; er de like reduseres mengden . Det vil si at om et tall er et semiprimtall, har det enten eller faktorer. Denne implikasjonen går også andre veien:
er et semiprimtall 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 |
|
Løsningen over har likevel en liten feil, og gir en "false positive". Kan du se hvilket tall? (Trykk for svar)
Problemet ligger i at når vi reverserer 10
så får vi 01
, som Python tolker som 1
. Da er 1*10
et semiprimtall (), selv om 1
ikke er et primtall. Dette slipper vi å tenke på med 100
og 1000
, for verken er semiprimtall. Vi må altså enten starte iterasjonene fra 11
, eller sjekke om 2<q
.
Ved litt golfing kan vi redusere dette ytterligere. Vi trenger nemlig bare å telle faktorer i (dvs. vi kan droppe å sjekke om og er faktorer). 122 tegn:
1 2 3 |
|
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 |
|
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 |
|
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 |
|
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:
Deler vi opp denne strengen i mindre deler, får vi en liste me ascii-verdiene til bokstaver, som blir
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:
Funksjonell og fasjonabel
Funksjonell og fungerende
1 2 3 4 5 |
|
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 |
|
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:
men det ville jo ikke vært like gøy ...
1 2 |
|
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 |
|
1 2 |
|
Med matematisk terminologi har vi en binær funksjon og en (endelig) ordnet liste (samt en mulig startverdi ). 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.
Igjen, dette kan også skrives med vanlige for-løkker og if-setninger
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.