mandag 9. desember 2013 Julekalender
Luke 8 ser ut til å ha vært den vanskeligste luken sålangt i kalenderen. Terje Tjervaag fra Bouvet klarte likevel å løse den 2 minutt og 33 sekunder. Magnar brukte 4 minutter og 39 sekunder, og beholder dermed ledelsen sammenlagt.
Oppgaven gikk ut på å finne den lengste sammenhengende rekken med nukleinsyrer som var felles i to DNA-sekvenser. Det korrekte svaret var TACTTCGATCG. Dette problemet er kjent som Longest Common Substring, og du finner løsninger i mange språk på nettet. Her er en implementasjon i Ruby:
def find_longest_common_substring(s1, s2)
return if (s1 == "" || s2 == "")
m = Array.new(s1.length){ [0] * s2.length }
longest_length, longest_end_pos = 0,0
(0 .. s1.length - 1).each do |x|
(0 .. s2.length - 1).each do |y|
if s1[x] == s2[y]
m[x][y] = 1
if (x > 0 && y > 0)
m[x][y] += m[x-1][y-1]
end
if m[x][y] > longest_length
longest_length = m[x][y]
longest_end_pos = x
end
end
end
end
return s1[longest_end_pos - longest_length + 1 .. longest_end_pos]
end
Nå ser det ut som om de på toppen begynner å få et solid forsprang. Men husk at lukene blir mere og mere verdt for hver dag som går. Dessuten kommer flere av lukene som er igjen til å være krevende, og gjør f.eks. Magnar en feil så er det ikke så veldig vanskelig å ta ham igjen.