Skip to content

Project Euler Problem 59

December 7, 2011

My Project Euler Problem 59 solution is based on a prompt in the description that the problem should yield to brute force attack. So, I did not bother with NLP stuff and got straight to the business.

textChars represents a set of characters that constitute normal English text. I put all potential passwords into a sequence of sequences of 3 lowercase letters, mapped this sequence into a sequence of indefinite length sequences of repeating password chars, and zipped each with encoded char sequence.

Then I XORed resulting tuples in each sequence from sequence of zips until finding a sequence of XORs containing only members of textChars set. This is a sought phrase, and sum of codes of members yields the answer.

open System
open System.IO

let encoded =
    use suckIn = new StreamReader @"..\..\..\Datafiles\Problem059.data"
    suckIn.ReadLine() |> fun x -> x.Split(',') |> Array.map Int32.Parse |> Array.map char

let textChars = [' '; '.'; ','; ';'; '?'; '!'; '"'; '\''; '('; ')']
                @ ['A'..'Z'] @ ['a'..'z'] @ ['0'..'9'] |> set
let inline isTextChar c = textChars.Contains c

let problem059 () =
    seq { for i in ['a'..'z'] do for j in ['a'..'z'] do  for k in ['a'..'z'] do yield seq [i; j; k] }
    |> Seq.map (fun x -> Seq.collect id (Seq.initInfinite (fun _ -> x)))
    |> Seq.map (Seq.zip encoded)
    |> Seq.map (Seq.map (fun (x,y) -> char ((int x) ^^^ (int y))))
    |> Seq.find (Seq.forall isTextChar) |> Seq.fold (fun s x -> s + (int x)) 0

Interesting that this approach allows not knowing either the password or the original text for providing the answer. Another interesting piece in the code above is using a sequence of finite number of sequences of indefinite length.

Overall, this solution is a “Combinator Heaven” (AFAIK the expression belongs to Jon Harrop), these map of zips and map of maps above are utterly powerful.

Advertisements

From → Project Euler

One Comment
  1. -mk permalink

    Someone jaded like me would argue that “must contain common English words” !== “contains only chars commonly found in English text”.

    An corollary problem then arises: construct the shortest input sequence such that the given algorithm produces incorrect answer.

    I apparently have too much free time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: