Här kommer en enkel programmeringsutmaning: skriv i valfritt språk en funktion som beräknar Levenshtein-avståndet mellan två strängar.

Bonusuppgift: funktionen ska dra mindre minne än O(m*n) där m är längden på ena strängen och n längden på den andra. Den ska dessutom vara snabbare och/eller kortare än min (kommentarer räknas givetvis inte.)

Jag använde följande två strängar, kopierade tio gånger vardera, för att testa funktionen:

– Vi ser stora brister i kvaliteten idag. Det skulle krävas runt 5 miljarder kronor för att komma upp i den kvalitet vi hade i mitten av 1990-talet. De rödgröna vill stärka kvaliteten med 400 miljoner per år, men det räcker inte riktigt. Man har också pratat om högre studielån, men utan att komma med några exakta siffror, säger Beatrice Högå. Inte heller den borgerliga alliansen har kommit med några konkreta bud till studenterna. – Folkpartiet och högskoleministern har sagt att satsningar på grundutbildningen är prioriterade, men vi väntar på att se hur satsningen kommer att se ut. Å andra sidan har Anders Borg sagt att man inte ska satsa på högskolan, säger Beatrice Högå.

...och...

Patentansökan beskriver även en teknik som ska göra det möjligt att identifiera en Iphone som blivit modifierad eller hackad, en teknik som populärt kallas jailbreak. Jailbreak gör det bland annat möjligt att köra program som inte är godkända av Apple. Apple har nyligen gått ut och meddelat att användare som utför ett jailbreak på sin Iphone förlorar garantin på telefonen. I Apples patentansökan ska den nya tekniken göra det möjligt att låsa en telefon som utsatts för ett jailbreak. Huruvida Apple kommer att använda tekniken i praktiken är än så länge okänt.

Med den indatan kör funktionen på ~1,25 sekunder på en Core 2 Duo 2,4 GHz, rätt svar är 5030. (Rätt svar om man INTE kopierar texterna 10x är naturligtvis 503.)

Mitt bidrag, i Haskell (om än inte särskilt idiomatisk Haskell, eftersom jag försökt optimera den så mycket som möjligt och skrev den just för att lära mig använda ST-monaden:)

module Levenshtein (distance) where
import Data.Array.ST
import Control.Monad.ST
import Control.Monad
import Data.Bits

-- | Calculate the Levenshtein distance between two lists.
distance :: (Eq a) => [a] -> [a] -> Int
distance [] [] = 0
distance as bs =
runST $ do
let ((as', lenA), (bs', lenB)) =
case (length as, length bs) of
(a, b) | b > a -> ((bs, b+1), (as, a+1))
| otherwise -> ((as, a+1), (bs, b+1))
fill = head as'

arr <- newArray_ ((0, 0), (1, lenB)) :: ST s (STUArray s (Int, Int) Int)
forM_ [0..lenB] $ \j -> writeArray arr (0, j) j

forM_ (zip [1..] $ fill:as') $ \(i, a) -> do
let iidx = i .&. 1
iidxMinusOne = iidx `xor` 1
writeArray arr (iidx, 0) i

forM_ (zip [1..] $ fill:bs') $ \(j, b) -> do
upleft <- readArray arr (iidxMinusOne, j-1)
if a == b
then do
writeArray arr (iidx, j) upleft
else do
left <- readArray arr (iidxMinusOne, j)
up <- readArray arr (iidx, j-1)
writeArray arr (iidx, j) $ (min upleft $ min up left) + 1

readArray arr $ (lenA `mod` 2, lenB)

EDIT: kommentarerna gjorde koden oläsbar, så de fick gå.