torsdag 12. desember 2013 Julekalender Ruby
Luke 11 i utviklernes julekalender 2013 inneholdt litt ruby-kode, navnet til en hemmelig valgt deltager, og et output generert fra dette navnet. Oppgaven var å finne hvilket navn som var brukt, og da har man i grunnen to ulike fremgangsmåter.
Funksjonen i oppgaven går kun én vei; man kan ikke starte med output og få ut hva input var. Derimot kan man forsøke å kalle funksjonen med alle gyldige input – dvs. navnene til alle deltagerne i julekalenderen – og se hvilke navn som gir det riktige output. Dette er en brukbar strategi om man har Ruby installert, og jeg antar det var dette de fleste gjorde.
Men om du ønsker å forstå hva funksjonen gjør så kan du også komme frem til navnet med litt hjernekraft...
def process input
input.
downcase.
split('').
sort.
chunk {|c| c.ord }.
inject('') {|a,x| "#{a}#{x[0]}#{x[1].size}" }
end
Funksjonen process sender input gjennom en pipeline av transformerende funksjonskall. La oss begynne med et tenkt input "Janne", og se hva som skjer i hvert steg.
"Janne".downcase
downcase endrer alle store bokstaver til små bokstaver. Resultatet er "janne".
"janne".split('')
split med en tom streng som argument deler opp strengen bokstav for bokstav. Resultatet er ["j", "a", "n", "n", "e"].
["j", "a", "n", "n", "e"].sort
Her sorterer jeg arrayet, som gir ["a", "e", "j", "n", "n"].
["a", "e", "j", "n", "n"].chunk {|c| c.ord }
chunk brukes til å gruppere elementene i arrayet. Jeg bestemmer at tegnene (c) skal grupperes på integer/ASCII-verdien (c.ord). Resultatet er en enumerasjon som inneholder [[97, ["a"]], [101, ["e"]], [106, ["j"]], [110, ["n", "n"]]].
[[97, ["a"]],
[101, ["e"]],
[106, ["j"]],
[110, ["n", "n"]]].inject('') {|a,x|
"#{a}#{x[0]}#{x[1].size}"
}
inject er Rubys funksjon for å "slå sammen" en enumerasjon til én verdi - det samme som Aggregate i C#, fold i språk som Haskell / ML / F#, reduce i Clojure, Accumulate og Compress andre steder. Jeg har snakket mye om bruk av denne typen funksjoner her på bloggen.
I dette tilfellet bygger jeg opp en streng av ASCII-verdiene konkatenert med antall bokstaver i hver gruppe. Resultatet blir dermed 971101110611102.
Når vi forstår dette kan vi forsøke å bryte opp output fra oppgaven, som var 32297310121031104110611071108111011111114111511161. Vi kan anta at vi holder oss innenfor en range av verdier fra 32 (space) til rundt et par hundre om navnet inkluderer noen sære tegn.
32 2 #=> To space, navnet består av tre deler! 97 3 #=> Tre a 101 2 #=> To e 103 1 #=> En g 104 1 #=> En h 106 1 #=> En j 107 1 #=> En k 108 1 #=> En l 110 1 #=> En n 111 1 #=> En o 114 1 #=> En r 115 1 #=> En s 116 1 #=> En t
Og så gjenstår det å bruke hjernens mønstergjenkjennings-egenskaper til å sette sammen bokstavene til et fornuftig navn. Eller å endelig innse at det er lurere å kjøre funksjonen på alle navnene likevel :P
Hurtigst til å svare riktig på oppgaven i luke 11 var Magnar Sveen, som begynner å få en solid ledelse sammenlagt. Han klarte oppgaven på 5 minutter og 46 sekunder.
Her er en oversikt over poengutviklingen for noen utvalgte spillere:
Og de samme tallene presentert grafisk (klikk for full størrelse):
