S\u00e5 ist\u00e4llet f\u00f6r att bara hitta bokst\u00e4verna som f\u00f6rekommer i ordet och sedan testa oss fram, varf\u00f6r klurar vi inte ut alla 2-str\u00e4ngar (2 bokst\u00e4ver l\u00e5nga teckenstr\u00e4ngar) som finns i ordet? Kan vi d\u00e5 f\u00e5 reda p\u00e5 ordet snabbare? Svar: jo.<\/p>\n
Att klura ut alla 2-str\u00e4ngar kr\u00e4ver h\u00f6gst B + bord<\/sub> * (bord<\/sub>-1) \/ 2 <\/strong>eller i v\u00e4rsta fall B\/2 + B2<\/strong><\/sup><\/strong>\/2<\/strong>\u00a0gissningar, d\u00e4r B<\/strong> \u00e4r m\u00e4ngden anv\u00e4ndbara bokst\u00e4ver. Detta tar inte s\u00e5 v\u00e4rst l\u00e4nge, men vad har man f\u00f6r nytta av 2-str\u00e4ngar? Kan man med hj\u00e4lp av dessa bygga snabbt upp 3-str\u00e4ngar?<\/p>\n Genom att visualisera 2-str\u00e4ngar som en graf kan man sk\u00e4ra bort flera on\u00f6diga gissningar. Noderna i grafen \u00e4r alla 2-str\u00e4ngar vi k\u00e4nner till, och kanterna l\u00e4nkar str\u00e4ngarna till varandra s\u00e5 att f\u00f6ljande str\u00e4ng b\u00f6rjar med delstr\u00e4ngen som den f\u00f6rsta slutar med. Notera att m\u00e4ngden olika k-str\u00e4ngar av ordet inte kan vara mer \u00e4n n-k+1<\/strong>\u00a0(eller Bk<\/sup><\/strong>\u00a0f\u00f6r den delen). M\u00e4ngden kanter i grafen kan inte vara mera \u00e4n (n-k+1) * B<\/strong>, eftersom varje nod har h\u00f6gst en kant per bokstav. 3-str\u00e4ngar kan forts\u00e4ttningsvis visualiseras som en graf, vilket till slut leder till en n-str\u00e4ng, vilket m\u00e5ste vara ordet vi s\u00f6ker efter.<\/p>\n Notera att grafen f\u00f6r alla 3-str\u00e4ngar i ”abrakadabra” har blivit en stor \u00f6gla. I detta fall kan man gissa sig fram till l\u00f6sningen genom att v\u00e4lja en nod som startpunkt, och sedan \u00e5ka ett varv runt. I detta fall f\u00e5r man till n\u00e4st gissningarna ”abrakadab”, ”brakadabr” och ”rakadabra”. Dessa skapar en simpel graf p\u00e5 3 noder som sedan leder till ordet vi letade efter, ”abrakadabra”<\/p>\n V\u00e4rsta m\u00f6jliga antalet gissningar f\u00f6r ord blir till sist:<\/p>\n B\/2 + B2<\/sup>\/2 + (n-1) B + (n-2) B + … + 1 B\u00a0= B\/2 + B2<\/sup>\/2 + \u00a0n2<\/sup>B\/2 – nB\/2<\/strong><\/p>\n vilket vi kan avrunda glatt till n2<\/sup>B<\/strong>.\u00a0I verkligheten kr\u00e4vs det mycket mindre arbete, eftersom grafen som bildas snabbt blir en \u00f6gla (”abrakadabra” kr\u00e4vde\u00a045 + B<\/strong> gissningar, och en 137 karakt\u00e4r l\u00e5ng meddelande kr\u00e4vde ~2100 + B<\/strong> gissningar). Att r\u00e4kna ut det praktiska tidskravet av den presenterade algoritmen l\u00e4mnar jag som l\u00e4xa f\u00f6r l\u00e4saren.<\/p>\n PS. Fresh Prince of Bel-Air theme orden (1788 tecken) l\u00f6ses p\u00e5 31446 gissningar.<\/p>\n","protected":false},"excerpt":{"rendered":" Dags f\u00f6r ett litet ordspel! Spelet liknar h\u00e4nggubbe eller h\u00e4ngman, i och med att du skall gissa ett ord som bara jag vet. Du kan gissa bokst\u00e4ver, ord eller delar av ord, exempelvis ”kaff”. Jag m\u00e5ste svara p\u00e5 om din gissning finns i mitt ord. Om det dolda ordet \u00e4r ”abrakadabra” och du gissar p\u00e5 … Forts\u00e4tt l\u00e4sa Extreme h\u00e4nggubbe<\/span> ![\"\"](\"http:\/\/spektrum.fi\/spektraklet\/wp-content\/uploads\/2018\/10\/AB_BR.png\")
<\/a><\/p>\n<\/a><\/p>\n