Finding God

February 16, 2016

The first three verses of the Bible are shown below. Pick any word in the first verse, count its letters, and move forward that many words in the text. Then repeat until you reach the third verse. You will always end with God.

1 In the beginning God created the heaven and the earth.

2 And the earth was without form, and void; and darkness was upon the face of the deep. And the Spirit of God moved upon the face of the waters.

3 And God said, Let there be light: and there was light.

For instance, if you start at beginning, count nine letters and move forward to the first the in the second verse. Then count forward three words to without, count forward seven words to upon, then count forward three words to the, count forward three words to another the, count forward three words to God, count forward three words to the, count forward three words to yet another the, and finally count forward three words to God. This trick was discovered by Martin Gardner.

Your task is to write a program that reads a text and checks if the trick works; you might look at the first paragraph of Alice in Wonderland, where starting within the first ten words always leads to sister, or the words of Twinkle, Twinkle Little Star, where starting anywhere within the first two lines always leads to you in the last line. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2 3

10 Responses to “Finding God”

  1. (same before but not linked)

    import Data.Char
    
    -- Convert pure text to word lists removing symbols
    asWords :: [String] -> [[String]]
    asWords = map $ words . map r where r c | isAlpha c = c
                                            | otherwise = ' '
    
    -- Lookup last row indexed word
    jump :: [[String]] -> Int -> Maybe String
    jump []           _ = Nothing
    jump [(x:_)]      0 = Just x
    jump ((x:xs):xss) 0 = jump (xs:xss) (length x)
    jump ([]:xss)     n = jump xss n
    jump ((x:xs):xss) n = jump (xs:xss) (n - 1)
    
    -- With some word check if obey the law
    obey :: String -> [[String]] -> Bool
    obey _ [] = False
    obey w xs@(x:_) = all (Just w ==) $ (jump xs) <$> [1..length x]
    
    
    -- Example
    text =
        "In the beginning God created the heaven and the earth.\n\
        \And the earth was without form, and void; and darkness was upon the face of the deep. And the Spirit of God moved upon the face of the waters.\n\
        \And God said, Let there be light: and there was light"
    
    main = print $ obey "God" $ asWords $ lines text
    
  2. matthew said

    Here’s a simulation: assume words have a uniformly random number of letters from 1 to n. We take two starting points within n words of each other (it doesn’t really matter what the exact distance is, we use -1 and 1 so the average starting value is 0), we then generate two series of random words until the two series coincide (after which they are identical). We can do that by always extending the sequence with the lowest current value. Each time we extend a sequence the probability that we hit the other value is exactly 1/n (since the two sequence values are never more that n away from each other) so the expected number of times we extend a sequence is exactly n, with expected final value n(n+1)/4 and this is the result of the simulation. Of course, real words don’t have such uniformly distributed lengths, but this seems to give a good insight into why the trick (usually) works:

    import random
    trials = 100000; n = 10; total = 0; final = 0
    for i in range(trials):
    count = 0; a = -1; b = 1
    while True:
    assert(abs(a-b) 0)
    count += 1
    if a < b: a += 1 + random.randrange(n)
    else: b += 1 + random.randrange(n)
    if a == b: break
    total += count
    final += a

    print(1.0*total/trials,1.0*final/trials) # eg. (10.01902, 27.55609)
    [/code]

  3. matthew said

    Not sure what happened there. Let’s try again:

    import random
    trials = 100000; n = 10; total = 0; final = 0
    for i in range(trials):
    count = 0; a = -1; b = 1
    while True:
    assert(abs(a-b) 0)
    count += 1
    if a < b: a += 1 + random.randrange(n)
    else: b += 1 + random.randrange(n)
    if a == b: break
    total += count
    final += a

    print(1.0*total/trials,1.0*final/trials)
    [/code]

  4. matthew said

    import random
    trials = 100000; n = 10; total = 0; final = 0
    for i in range(trials):
    count = 0; a = -1; b = 1
    while True:
    assert(abs(a-b) 0)
    count += 1
    if a < b: a += 1 + random.randrange(n)
    else: b += 1 + random.randrange(n)
    if a == b: break
    total += count
    final += a

    print(1.0*total/trials,1.0*final/trials)
    [/code]

  5. matthew said
    import random
    trials = 100000; n = 10; total = 0; final = 0
    for i in range(trials):
        count = 0; a = -1; b = 1
        while True:
            assert(abs(a-b) <= n)
            assert(abs(a-b) > 0)
            count += 1
            if b > a: a += 1 + random.randrange(n)
            else: b += 1 + random.randrange(n)
            if a == b: break
        total += count
        final += a
    
    print(1.0*total/trials,1.0*final/trials)
    
  6. matthew said

    The code formatter didn’t like the “a < b” – not normally a problem.

    Sorry about the spam, feel free to delete.

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: