Min samkontorboer var så vennlig at han introduserte meg for Code Golf denne uken, akkurat i det jeg hadde bestemt meg for at det var på tide på begynne å skrive på avhandlingen min. Slik har det seg at jeg nå har litt mindre avhandling enn planlagt, men til gjengjeld har jeg en dypere forståelse av obskure triks i Python. Og det er jo alltid kjekt. For eksempel på et jobbintervju ser jeg for meg at det kan være kjekt om man kan svare på en tullete, konstruert programmeringsoppgave med et uleselig program på 30 tegn.

Dagens diskusjon tar utgangspunkt i oppgaven Choose, på codegolf.com, og selv om jeg ikke avslører den beste løsningen (fordi jeg ikke kjenner den) anbefaler jeg at man tar en kikk på oppgaven først, om man er interessert i denslags.

Oppgaven består i å skrive et program som regner ut binomialkoeffisienten av to tall, og som altså skal være kortest mulig. I skrivende stund er den beste løsningen i Python på 39 tegn, og jeg ser for meg at den må involvere noen rimelig skitne triks. Jeg kjenner en som kjenner en som har greid dette, og jeg har spurt om å få se løsningen. Jeg skulle gjerne kommet på den selv, men jeg vet ikke om det er spesielt sannsynlig, og i allefall ikke kompatibelt med å få ferdig doktorgraden på normert tid.

Med utgangspunkt i denne oppgaven kan man diskutere en hel haug med spennende ting, og den første er naturligvis binomialkoeffisienten, også kjent som "utvalg uten tilbakelegging". Hvis du har fire gjenstander, for eksempel fire kuler med forskjellig farge, og du skal velge ut to av dem, vil binomialkoeffisienten av fire og to være det antallet måter du kan gjøre utvalget på, altså seks¹. Dette tallet kan regnes ut på flere måter, som man kan lese mer om på wikipedia, og den første vi skal ta for oss er via fakultet.

Fakultet, som skrives 4! for fakultet av fire, etc., er antall mulige rekkefølger man kan organisere et antall gjenstander i, og regnes ut ved a gange sammen alle tallene fra 1 til det tallet man ønsker å finne fakultet av, så for eksempel 4!=1x2x3x4=24. Dette er en litt kul ting å programmere, fordi den kan brukes til å introdusere rekursive funksjoner, men vi skal begynne med den enkleste måten.

def f(n):
    i = 1
    for x in range(1,n+1):
        i *= x
    return i

Dette er en enkel og grei funksjon i Python som regner ut fakultet av et tall. range(1,n+1) returnerer en liste med alle tallene fra og med 1 til og med n, og *= er en lettvint måte å si et tall skal være lik seg selv ganget med et annet tall.

En annen, og mye frekkere, måte å regne ut faklutet er med en funksjon som kaller seg selv, altså en rekursiv funksjon. Behold:

def f(n):
    if n <= 1:
        return 1
    else:
        return n*f(n-1)

Det krever kanskje litt mer tenking å se hvorfor dette fungerer (i alle fall syntes jeg det, første gang jeg så den), men når man skjønner det er det en veldig elegant liten sak. Det den gjør er rett og slett at hvis n er mindre eller lik 1 returnerer den 1. Hvis ikke returnerer den n ganget med f(n-1), som altså er n ganger (n-1)!, som er det samme som n!. Her er det altså skilpadder hele veien ned. Frekt, eller hur?

Hvis man tar sin golf seriøst er imidlertid begge disse funksjonene for verbøse med minst et par hakk. Her trenger vi sterkere lut. Det er på tide å bryte ut lambda.

lambda er en måte å definere funksjoner i Python som kan være litt vanskelig å få grepet på, så vi begynner med et enkelt eksempel.

f = lambda x: 2*x

Det som skjer her er at vi forteller lambda at vi ønsker å definere en funksjon av x, og at den funksjonen skal returnere 2*x. lambda returnerer så denne funksjonen, slik at vi kan kalle den som f, så for eksempel f(2) vil returnere 4. Det er også mulig å definere mer komplekse funksjoner på denne måten, og gjerne med mer enn et argument, men kravet er at uttrykket (altså det bak kolon) i funksjonsdefinisjonen må bestå av ett uttrykk, som returnerer ett svar.

Ved hjelp av lambda kan vi definere den latterlig frekke funksjonen

f = lambda n: 1 * (n<1 or n*f(n-1))

At denne funker baserer seg på en liten snarvei i implementasjonen av or, og forsåvidt and. Men først, en liten digresjon om boolsk algebra.

I programmering ønsker man ofte å vurdere om noe er sant eller ikke. Det kan være noe enkelt som å vurdere om to tall er like store, men det kan også være mindre intuitive ting som å vurdere om for eksempel 5 eller 'hei' er sant eller usant, eller True eller False som verdiene egentlig heter. I Python, og sikkert i de fleste andre språk, er det slik at 0 er False, og i tillegg er tom liste ([]), tom streng ('') og et par andre litt mer sære ting også False. Alt annet er True.

Det som er trikset med fakultetsfunksjonen over er at det første som skjer er at Python vurderer om det er sant at n er mindre enn 1. or returnerer True hvis minst en av utsagnene er sanne, så hvis n<1 returnerer den True. Videre har det seg slik at 1*True=1, så i såfall returnerer funksjonen 1, som vi forventer hvis vi tar faklutet av 0, som jo er det eneste ikke-negative tallet mindre enn 1.

I motsatt fall, hvis n ikke er mindre enn 1, vil or returnere det som står til høyre uten å faktisk sjekke hva som står der. Logikken er at hvis det som står til venstre er False vil sannhetsverdien av uttrykket som helhet være den samme som sannhetsverdien av det som står til høyre (siden or bare krever at minst ett av utsagnene er sanne). Og siden det tar tid å sjekke ting er det enkleste bare å returnere det som står til høyre².

Det betyr at hvis n ikke er mindre enn 1 returneres n ganget med f(n-1), altså mye det samme som den rekursive funksjonen vi definerte tidligere.

Når vi nå har fått definert en fakultetsfunksjon med akseptabel lengde kan vi begynne å se på den orginale oppgaven, som altså var å ta to tall fra stdin (standard input, som i dette tilfellet vil si at programmet startes, og så venter på input før det gjør noe mer), og regne ut binomialkoeffisienten. Å hente tall fra standard input er en smal sak. I oppgaven er det spesifisert at tallene man skal regne ut blir gikk på formen n,k, som betyr at vi kan skrive

n,k = input()

Da gjenstår det bare å regne ut binomialkoeffisienten ved hjelp av fakultet, som beskrevet for eksempel på wikipedia, og vi ender opp med programmet

n,k=input()
f=lambda n:1*(n<1or n*f(n-1))
print f(n)/f(k)/f(n-k)

som klokker inn på 65 tegn. Jeg har greid litt bedre, med et program på 54 tegn, men den beste løsningen i python er som sagt på latterlige 39 tegn, så jeg har et stykke igjen. Min beste løsning er

f=lambda n,k:k<1or f(n-1,k-1)*n/k
print 1*f(*input())

og jeg overlater det som en øvelse til leseren å skjønne hvordan den funker.

¹Hvis vi ser på bokstavene ABCD er de seks mulige utvalgene av to bokstaver AB, AC, AD, BC, BD, CD.

²Dette høres kanskje sært ut, men det er bare å fyre opp Python og sjekke. 1 or 2 returnerer True, mens 0 or 2 returnerer 2.