torsdag 19. desember 2013 Julekalender
Åhh, det er spennende nå! Magnar har mistet ledelsen, og Stian er nå utvikleren med flest poeng i årets julekalender.
Luke 17 beskrev en klassisk oppgave som kalles the knapsack problem. Det finnes flere varianter, og dette var en variant hvor man har et begrenset antall av de ulike tingene som skal pakkes.
Det er lett å finne løsninger på nettet om man kjenner til problemet. På rosetta code finner du løsningen implementert i et hav av ulike språk. Likevel var det usedvanlig mange gale svar som ble forsøkt i løpet av dagen.
Raskest ute med riktig svar var Sølve Heggem, som brukte 8 minutter og 27 sekunder. Magnar tok andreplassen, og Stian tredje.
I denne luken presenterte jeg litt kode, om man skulle finne ut hva output ville bli. Jeg hadde også "scrablet" koden med seks søk/erstatt-operasjoner. Dette var et forsøk på å gjøre det vanskeligere å se hvilket språk det var snakk om, og unngå at man bare kunne lime koden inn i en online REPL for å få svaret gratis.
Koden slik den ble presentert var:
def f max x :
query {
for y in [for i in 1 .. max => i * x] do
where (y <: max)
select y
}
[<Abbreviate>]
def main argv :
def f : f 999
( f 4 , f 7 )
||> int.append |> int.sub
|> (fun s => s = (f (4*7) |> int.sub))
|> printfn "%d"
0
Dette er F# i forkledning. Ved å kjøre følgende replace-operasjoner:
s/=/-/g // 3 tilfeller s/:/=/g // 4 tilfeller s/sub/sum/g // 2 tilfeller s/int/Seq/g // 3 tilfeller s/def/let/g // 3 tilfeller s/Abbreviation/EntryPoint/g // 1 tilfelle
får vi denne orginalkoden:
let multiples max x =
query {
for y in [for i in 1 .. max -> i * x] do
where (y <= max)
select y
}
[<EntryPoint>]
let main argv =
let multiples = multiples 999
( multiples 4 , multiples 7 )
||> Seq.append |> Seq.sum
|> (fun s -> s - (multiples (4*7) |> Seq.sum))
|> printfn "%d"
0
For dem som har fulgt med på bloggen min de siste årene så bør de dra kjensel på denne algoritmen. Jeg har nemlig en oppgave jeg sikkert har implementert hundre ganger i diverse artikler (med ulike språk og ulike teknikker): Hvordan finne summen av alle multipler av 3 eller 5 som er mindre enn 1000.
Teknikken her var å se på oppgaven som et sett-problem, noe jeg har blogget om her.
Selv om jeg her brukte multipler av 4 og 7 tenkte jeg at det var mulig å gjenkjenne problemet, og dermed løse oppgaven, selv om man ikke klarte å få F#-koden helt riktig.
Kjersti BB og Stian gjorde meg derimot oppmerksom på at det finnes flere løsninger på oppgaven. sub kunne også byttes ut med enten min eller max og fortsatt gi et korrekt program – men et annet output. Jeg gav derfor manuelt poeng for disse svarene etter når de ble levert inn for alle som ville ha fått mer enn 10 poeng.
Den som var raskest ute med svaret var Stian Veum Møllersen (BEKK Consulting). Jonas Follesø, som blogget om F# her for ett år siden, kom på andre plass, og Stian inntok sammenlagtledelsen med tredjeplass. Magnar "snublet" (hans ord) og klarte ikke å finne løsningen på denne oppgaven.
Det er nå 6 luker igjen å åpne i kalenderen. Vi nærmer oss nå 200+ poeng for første riktige svar, så stillingen i toppen kan raskt endre seg igjen – ingen bør føle seg trygge.
Luke 19 er en litt gøy luke som alle kan løse, og hvor man må bruke litt fantasi. Jeg er spent på å se hvor raskt folk klarer den.
Luke 20 derimot mener jeg er ganske krevende – det blir kanskje den vanskeligste luken av alle – og kan derfor bli helt avgjørende.
Takk til alle som fortsatt henger med og "koser seg" med kalenderen!