« Orkut DNS-problem igen | Main | Yes! »

maj 08, 2004

Isomorfa ord (Isomorphic Words)

Mats Andersson ställde häromdagen en kryptografisk gåta Nytt krypto, som helt enkelt frågar vad F O J K Ö N W Å C W N O S Q betyder.

Efter några försök med standardsaker såsom "difford", rot13, rotN etc, funderade jag på om det kanske var ett substitutionschiffer (ersättningschiffer, substitution cipher), dvs där varje bokstav ska bytas ut mot en annan.

Eftersom sådana chiffer inte nödvändigtvis har unika lösningar, skrevs ett litet program för att kontrollera vilka och hur många ord (från en ordlista) som skulle kunna vara tänkbara kandidater.

I det följande kallar jag två ord som kan förvandlas till varandra med sådan substitution för isomorfa ord (av "iso": samma + "morf": form/struktur).

Programmet Isomorphic Words
Programmet som skapades har nu gjorts webbanpassats och finns på Isomorphic Words, där det beskrivs mer hur programmet fungerar, vad som menas med isomorfism etc.

Tillbaka till Mats pyssel
Listan med isomorfa ord till strängen FOJKÖNWÅCWNOSQ blev 984 ord lång (från en ordlista på cirka 117000 svenska ord)! Här är några av dem, kanske inte helt slumpmässigt utvalda:

Programmet visar även en möjlig mappning (av möjligen flera möjliga mappningar) mellan bokstäverna i orden. T.ex. för ordet stjärneskådare kan man göra följande mappning från strängen FOJKÖNWÅCWNOSQ:

Detta innebär att de bokstäver som förekommer exakt en gång i det inknappade ordet, dvs bokstäverna [CÅFKJQSÖ], kan ersättas med vilken bokstavs som helst som förekommer exakt en gång i stjärneskådare, dvs [aäkjntåd]. På samma sätt kan de bokstäver som förekommer två gånger i respektive ord kan bytas ut mot varandra.

Exakt isomorfism
Programmet har även möjlighet att göra en mer strikt kontroll, där inte bara antalet förekomster av respektive bokstäver ska vara samma i de två orden, utan även där bokstävernas positioner är relevanta. T.ex. orden anna, amma och esse är exakt isomorfa eftersom de har exakt samma uppbyggnad/form: Först en bokstav, sedan en annan, därefter samma bokstav som nummer 2 och till sist samma bokstav som började ordet. Ett ord som jojo är isomorft (två förekomster av respektive två bokstäver) men inte exakt isomorft eftersom det inte har den eftersökta strukturen.

För strängen FOJKÖNWÅCWNOSQ hittades ingen exakt isomorfism i den svenska ordlistan; inte heller i den engelska för den delen.

Uppdatering:
Efter att ha kollat i en betydligt större engelsk ordlista som även inkluderar fraser, hittades den exakta isomorfismen parcel of land som vad jag förstår betyder ungefär "jordlott" (som enligt NE i sin tur har "parcell" som synonym). Mappingen är:

Där hittades även en exakt isomorfism på kjellerstrand: nämligen shipping note med mappningen

(Slut på uppdateringen.)

Däremot har ordet Ordet andersson har följande fyra svenska exakta isomorfismer:

Själva mappningen är här något annorlunda jämfört med "vanliga" isomorfa ord, eftersom positionen spelar roll. För ordet undfallen innebär det att bokstäverna "a", "e" och "d" (från andersson) mappas till samma bokstav i undfallen, men "o" ska mappas till "f", "r" till "u", "n" till "i" samt "s" till "n".

Man kan även notera att mats andersson har 806 isomorfa ord, t.ex. visirvärdighet, trosbekännelse samt amfiteatralisk, men inga exakta isomorfa ord.

Här är några exempel på mer strukturerade former. Man kan notera det förenklade sättet att skriva ut strukturen på de eftersökta ordet.

abcdefghijklm, dvs 13-bokstavsord utan upprepning av bokstäverna,. Det finns 42 sådana i ordlistan, t.ex. vänskaplighet, fasmodulering och fetischdyrkan.

abbccdd: irreell
abbcc: reell

Palindrom:
abcba: 12 stycken, t.ex. varav, girig och kajak
abccba: tillit


Se även
Mats tidigare kryptoproblem: Kod.
Mina andra "useless" program.

Programmet är f.ö. skrivet i Python, och innehåller inte ett endaste reguljärt uttryck.

Uppdatering: OK, kryptogåtan är löstes till slut. Det var inte något substitutionschiffer. Se kommentarerna i problemlänken.

Posted by hakank at maj 8, 2004 10:04 FM Posted to Program | Språk