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.
Programming Praxis 
one
(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 textHere’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]
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]
I’m mystified.
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]
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)The code formatter didn’t like the “a < b” – not normally a problem.
Sorry about the spam, feel free to delete.