hakank.blogg

« Scale-Free Network Business Development Strategy | Main | Forum för Stephen Wolfram "A New Kind of Science" »

maj 14, 2004

Mats Anderssons två kryptogåtor, lösningar, programkod samt lite kringtänk

För ett tag sedan skrev Mats Andersson två kryptogåtor: Kod samt Nytt krypto. Eftersom han faktiskt inte beskrivit de korrekta lösningarna tänkte jag göra det här, inklusive programkod samt lite tänk bakom lösningarna.

Uppdatering: Lustigt nog publicerade Mats lösningarna på sina gåtor några minuter senare än - och tydligen helt oberoende av - denna anteckning. Läs mer i hans Dekryptering.

Lösningarna koms på ungefär med lika delar tur, intuition och brute force. Samt en viss kännedom om hur Mats Andersson tänker; han är nästan lika fascinerad av heltalssekvenser som jag och har tidigare skrivit andra matte/sekvens-problem som jag löst antingen snabbt eller ... mindre snabbt. Se nedan.

Hans första kryptogåta var vad detta betyder:

21 35 39 57 58 76 91 104 118 145 152 167 181 193 222 241 246 264 268 273 293 313 314


Det var ganska enkelt att lösa eftersom det snabbt observerades att det är en sekvens tal som hela tiden ökar, och där differensen håller sig till tal mellan 0 och 29, dvs antalet svenska bokstäver. Differenssekvensen är:

[14, 4, 18, 1, 18, 15, 13, 14, 27, 7, 15, 14, 12, 29, 19, 5, 18, 4, 5, 20, 20, 1]


Sedan var det enkelt att skriva Python-koden nedan. Huvudprincipen är att göra om bokstäverna till siffror där "A" = 1, "B" = 2, osv och sedan tillbaka på motsvarande sätt, dvs 1="A", 2="B" osv. (I ett tidigare program/problem, PageRank-profetia, använde Mats ASCII-värdet för bokstäverna, men här leder en sådan konvertering till lustiga resultat för "Å", "Ä" och "Ö".)

# skapa differenssekvens
def diff(L):
     return [L[l]-L[l-1] for l in range(1, len(L))]

alfa = "ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ"
# koden
str = "21 35 39 57 58 76 91 104 118 145 152 167 181 193 222 241 246 264 268 273 293 313 314"
# skapa lista av tal
L = [int(l) for l in str.split(" ")]

# skapa differenslista, konvertera tillbaka till bokstäver, lägg till första
# elementet manuellt
print "".join([alfa[i-1] for i in [L[0]] + diff(L)])


Vilket ger som resultat:

UNDRAROMNÅGONLÖSERDETTA


dvs "Undrar om någon löser detta".

Den andra kryptogåtan var något knepigare, dvs vad står här:

F O J K Ö N W Å C W N O S Q


Den - egentligen ogrundade - ingångsintuitionen var att problemet skulle vara en variant av föregående problem, möjligen kombinerat med någon ceasar-kod, dvs rot(N) (se t.ex. Introduction To Codes, Ciphers, & Codebreaking).

Det som ledde mig på avigvägar här var att differensen i sekvensen är negativ. Konvertering från bokstäver till tal är (variabeln s2 i Python-koden nedan) är

[5, 14, 9, 10, 28, 13, 22, 26, 2, 22, 13, 14, 18, 16]

där differensen (variabeln dd) är sålunda

[9, -5, 1, 18, -15, 9, 4, -24, 20, -9, 1, 4, -2]


Detta justerades först med absolutvärdet, men det gav inget intressant resultat. (Här testades f.ö. även med en reverse av strängen. Cf Magnus Bodins rot-13 palindrom som han vänligt nog mailade mig som en gåta att lösa innan han publicerade den på sin sajt).

Varpå substitutionschiffer började dyka upp som en alternativ - med felaktig - lösning, och ledde till skapandet av programmet Isomorphic Words, där egentligen bara "exakta isomorfiska ord" kan vara en lösning på problemet. Se vidare blogganteckningen Isomorfa ord (Isomorphic Words).

När jag några dagar senare tog tag i gåtan igen, insågs med viss plötslighet att modulo-operatorn justerar för negativa tal. Sedan var det bara en fråga om brute force för att testa alla modulo-möjligheter (1..28) där 28 (== -1) är den korrekta.

Här är Python-koden för programmet:

# kodordet
s = "FOJKÖNWÅCWNOSQ"
alfa = "ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ"
alfa_len = len(alfa)

# skapa översättningstabell
alfa_hash = {}
i = 0
for a in alfa:
     alfa_hash[a] = i
     i += 1

# gör om till tal
s2 = [alfa_hash[i] for i in s]

# gör differanssekvens
dd = [s2[l] - s2[l-1] for l in range(1, len(s2))]

# konvertera tillbaka till bokstäver, lägg till första bokstaven ("F") manuellt
x = [s[0]] + [alfa[(i-1) % alfa_len] for i in dd]

# skriv ut
print "".join(x)


Programmet skriver ut svaret

FIXARNIDETTADÅ


dvs "Fixar ni detta då".

Mats har gjort andra skoj matematiska gåtor. Den som var svårast att lösa beskrivs i Mats Anderssons matematiska gåta.

Se även blogganteckningen Rekreationell matematik ocn annat tankegodis där relevant literatur kring heltalssekvenser och annat beskrivs.

Posted by hakank at maj 14, 2004 09:03 EM Posted to Diverse

Comments

Posted by: Daniel Olovsson at maj 14, 2004 10:15 EM