# Commits

committed b5d9953

praxis: move greplin-challenge to praxis

# greplin-challenge/challenge.notes

`-Greplin Challenge`
`------------------`
`-`
`-Offered at https://www.greplin.com/jobs, which points to http://challenge.greplin.com/.  Below descriptions taken from that site.`
`-`
`-`
`-So it begins:`
`-  Welcome to the Greplin Programming Challenge.  You should try to complete all three levels in a single sitting.  It should take anywhere from 20 minutes to 2 hours.`
`-`
`-`
`-Level 1: (gettysbury.py)`
`-  Embedded in this block of text is the password for level 2.  The password is the longest substring that is the same in reverse.`
`-`
`-  As an example, if the input was "I like racecars that go fast" the password would be "racecar".`
`-`
`-  [Block of text in my source code.]`
`-`
`-`
`-Level 2: (fib.py)`
`-  Congratulations.  You have reached level 2.`
`-`
`-  To get the password for level 3, write code to find the first prime fibonacci number larger than a given minimum.  For example, the first prime fibonacci number larger than 10 is 13.`
`-`
`-  When you are ready, go here or call this automated number (415) 799-9454.`
`-`
`-  You will receive additional instructions at that time.  For the second portion of this task, note that for the number 12 we consider the sum of the prime divisors to be 2 + 3 = 5.  We do not include 2 twice even though it divides 12 twice.`
`-`
`-`
`-  Additional instructions:`
`-    Step 1. Use your code to compute the smallest prime fibonacci number greater than 227,000.  Call this number X.`
`-`
`-    Step 2. The password for level 3 is the sum of prime divisors of X + 1.`
`-`
`-    Note: If you call the number instead, it will check your answer for step 1.`
`-`
`-`
`-Level 3: (subsets.py)`
`-  Congratulations.  You have reached the final level.`
`-`
`-  For the final task, you must find all subsets of an array where the largest number is the sum of the remaining numbers.  For example, for an input of:`
`-`
`-  (1, 2, 3, 4, 6)`
`-`
`-  the subsets would be`
`-`
`-  1 + 2 = 3`
`-  1 + 3 = 4`
`-  2 + 4 = 6`
`-  1 + 2 + 3 = 6`
`-`
`-  Here is the list of numbers you should run your code on.  The password is the number of subsets.  In the above case the answer would be 4.`
`-`
`-  [Number list included in my source code.]`
`-`
`-`
`-The End:`
`-  Congratulations.  You completed the challenge.  Your completion code is 9401-1-8270-22543.`
`-`
`-  We'd love to talk to you - send your completion code, the code you wrote`
`-  during the challenge, and your resume to`
`-`
`-  jobs+i+solved+the+challenge@greplin.com`
`-`
`-  Even if you're not looking for a job, we'd love to hear what you thought`
`-  about the challenge.`

# greplin-challenge/fib.py

`-#!/usr/bin/env python2.6`
`-`
`-import math`
`-`
`-`
`-def fib():`
`-  a = 1`
`-  b = 1`
`-  yield a`
`-  yield b`
`-  while True:`
`-    c = a + b`
`-    yield c`
`-    a = b`
`-    b = c`
`-`
`-def is_prime(num):`
`-  # naive...`
`-  if num % 2 == 0:`
`-    return False`
`-  last = int(math.sqrt(num)) + 1`
`-  for x in xrange(3, last + 1, 2):`
`-    if num % x == 0:`
`-      return False`
`-  return True`
`-`
`-def primes():`
`-  # naive...`
`-  for x in [2, 3, 5, 7, 11, 13, 17, 19]:`
`-    yield x`
`-  while True:`
`-    x += 2`
`-    if is_prime(x):`
`-      yield x`
`-`
`-def divisors(num):`
`-  print "divisors(%r) % num)"`
`-  for p in primes():`
`-    if p > num: break`
`-    while True:`
`-      d, m = divmod(num, p)`
`-      if m == 0:`
`-        print "divisor", p`
`-        yield p`
`-        num = d`
`-      else:`
`-        break`
`-`
`-`
`-fibs = iter(fib())`
`-for x in fibs:`
`-  if x > 227000:`
`-    break`
`-`
`-while True:`
`-  if is_prime(x):`
`-    print "X =", x`
`-    break`
`-  for x in fibs: break`
`-`
`-D = list(divisors(x + 1))`
`-print D`
`-print "divisors sum =", sum(D)`
`-print "unique divisors sum =", sum(set(D))`

# greplin-challenge/gettysburg.py

`-#!/usr/bin/env python2.6`
`-`
`-def is_palindrome(s, start=0, stop=None):`
`-  if stop is None: stop = len(s)`
`-`
`-  # unnecessary optimization to avoid many short-lived strings`
`-  length = stop - start`
`-  return all(s[x + start] == s[stop - (x + 1)] for x in xrange(length / 2))`
`-`
`-assert not is_palindrome("racecars")`
`-assert is_palindrome("racecar")`
`-`
`-def find_palindromes(s):`
`-  for start in xrange(len(s) - 1):`
`-    for stop in xrange(start + 1, len(s) + 1):`
`-      if is_palindrome(s, start, stop):`
`-        yield s[start:stop]`
`-`
`-`
`-gettysburg = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"`
`-`
`-L = [x for x in find_palindromes(gettysburg) if len(x) > 1]`
`-print L`
`-if L:`
`-  print max(L, key=len)`

# greplin-challenge/subsets.py

`-#!/usr/bin/env python2.6`
`-"""Subsets`
`-`
`-This is a naive solution which brute forces all subsets.  I verified it gave the correct results, then didn't think any more of it.`
`-"""`
`-`
`-import sys`
`-import itertools`
`-`
`-`
`-def each_bit(num):`
`-  assert num >= 0`
`-  # second loop is probably unnecessary optimization, could use a single infinite loop here`
`-  while num:`
`-    yield bool(num & 1)`
`-    num >>= 1`
`-  while True:`
`-    yield False`
`-`
`-def subsets(L):`
`-  for bits in xrange(2 ** len(L)):`
`-    yield [x for x, b in zip(L, each_bit(bits)) if b]`
`-`
`-`
`-numbers = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]`
`-#numbers = [1, 2, 3, 4, 6]`
`-`
`-print "numbers = (%d) %r" % (len(numbers), numbers)`
`-count = 0`
`-total = 0`
`-for x in subsets(numbers):`
`-  if not (2 <= len(x) < len(numbers)):`
`-    continue`
`-  total += 1`
`-  if total % 100000 == 0:`
`-    print "examined %d subsets, found %d meeting the criteria" % (total, count)`
`-  mx = max(x)`
`-  if sum(n for n in x if n != mx) == mx:`
`-    print " ", x`
`-    count += 1`
`-`
`-print "examined %d subsets in total" % total`
`-print "count =", count`

# greplin-challenge/subsets2.py

`-#!/usr/bin/env python2.6`
`-"""Subsets`
`-`
`-This is a dynamic solution which runs efficiently.  I did not think of this approach, but implemented it from the description at http://programmingpraxis.com/2010/11/09/subset-sums/.`
`-"""`
`-`
`-def solve(numbers):`
`-  """Solve sum of subsets for numbers.`
`-`
`-  numbers must be positive and in sorted order.`
`-  """`
`-  memo = {}`
`-  def f(stop, target):`
`-    """number of subsets of numbers[:stop] which sum to target"""`
`-    if stop == 0:  # empty set only matches if target is 0`
`-      return target == 0`
`-    if target == 0:  # only empty set matches`
`-      return 1`
`-`
`-    key = (stop, target)`
`-    if key in memo:`
`-      return memo[key]`
`-`
`-    result = f(stop - 1, target)  # without last`
`-    last = numbers[stop - 1]`
`-    if target >= last:`
`-      result += f(stop - 1, target - last)  # with last`
`-`
`-    memo[key] = result`
`-    return result`
`-`
`-  return sum(f(x, numbers[x]) for x in xrange(2, len(numbers)))`
`-`
`-`
`-def show(numbers):`
`-  print numbers`
`-  print "=", solve(numbers)`
`-  print`
`-`
`-show([1, 2, 3, 4, 6])`
`-show([3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99])`
`-`
`-`
`-# primes example from Praxis`
`-`
`-def primes(stop):`
`-  """Return sieve for primes 2..stop."""`
`-  sieve = [True] * stop`
`-  for x in xrange(2, stop):`
`-    if sieve[x]:`
`-      yield x`
`-      for n in xrange(2 * x, stop, x):`
`-        sieve[n] = False`
`-`
`-show(list(primes(2**10)))`

# praxis/greplin-challenge/challenge.notes

`+Greplin Challenge`
`+-----------------`
`+`
`+Offered at https://www.greplin.com/jobs, which points to http://challenge.greplin.com/.  Below descriptions taken from that site.`
`+`
`+`
`+So it begins:`
`+  Welcome to the Greplin Programming Challenge.  You should try to complete all three levels in a single sitting.  It should take anywhere from 20 minutes to 2 hours.`
`+`
`+`
`+Level 1: (gettysbury.py)`
`+  Embedded in this block of text is the password for level 2.  The password is the longest substring that is the same in reverse.`
`+`
`+  As an example, if the input was "I like racecars that go fast" the password would be "racecar".`
`+`
`+  [Block of text in my source code.]`
`+`
`+`
`+Level 2: (fib.py)`
`+  Congratulations.  You have reached level 2.`
`+`
`+  To get the password for level 3, write code to find the first prime fibonacci number larger than a given minimum.  For example, the first prime fibonacci number larger than 10 is 13.`
`+`
`+  When you are ready, go here or call this automated number (415) 799-9454.`
`+`
`+  You will receive additional instructions at that time.  For the second portion of this task, note that for the number 12 we consider the sum of the prime divisors to be 2 + 3 = 5.  We do not include 2 twice even though it divides 12 twice.`
`+`
`+`
`+  Additional instructions:`
`+    Step 1. Use your code to compute the smallest prime fibonacci number greater than 227,000.  Call this number X.`
`+`
`+    Step 2. The password for level 3 is the sum of prime divisors of X + 1.`
`+`
`+    Note: If you call the number instead, it will check your answer for step 1.`
`+`
`+`
`+Level 3: (subsets.py)`
`+  Congratulations.  You have reached the final level.`
`+`
`+  For the final task, you must find all subsets of an array where the largest number is the sum of the remaining numbers.  For example, for an input of:`
`+`
`+  (1, 2, 3, 4, 6)`
`+`
`+  the subsets would be`
`+`
`+  1 + 2 = 3`
`+  1 + 3 = 4`
`+  2 + 4 = 6`
`+  1 + 2 + 3 = 6`
`+`
`+  Here is the list of numbers you should run your code on.  The password is the number of subsets.  In the above case the answer would be 4.`
`+`
`+  [Number list included in my source code.]`
`+`
`+`
`+The End:`
`+  Congratulations.  You completed the challenge.  Your completion code is 9401-1-8270-22543.`
`+`
`+  We'd love to talk to you - send your completion code, the code you wrote`
`+  during the challenge, and your resume to`
`+`
`+  jobs+i+solved+the+challenge@greplin.com`
`+`
`+  Even if you're not looking for a job, we'd love to hear what you thought`
`+  about the challenge.`

# praxis/greplin-challenge/fib.py

`+#!/usr/bin/env python2.6`
`+`
`+import math`
`+`
`+`
`+def fib():`
`+  a = 1`
`+  b = 1`
`+  yield a`
`+  yield b`
`+  while True:`
`+    c = a + b`
`+    yield c`
`+    a = b`
`+    b = c`
`+`
`+def is_prime(num):`
`+  # naive...`
`+  if num % 2 == 0:`
`+    return False`
`+  last = int(math.sqrt(num)) + 1`
`+  for x in xrange(3, last + 1, 2):`
`+    if num % x == 0:`
`+      return False`
`+  return True`
`+`
`+def primes():`
`+  # naive...`
`+  for x in [2, 3, 5, 7, 11, 13, 17, 19]:`
`+    yield x`
`+  while True:`
`+    x += 2`
`+    if is_prime(x):`
`+      yield x`
`+`
`+def divisors(num):`
`+  print "divisors(%r) % num)"`
`+  for p in primes():`
`+    if p > num: break`
`+    while True:`
`+      d, m = divmod(num, p)`
`+      if m == 0:`
`+        print "divisor", p`
`+        yield p`
`+        num = d`
`+      else:`
`+        break`
`+`
`+`
`+fibs = iter(fib())`
`+for x in fibs:`
`+  if x > 227000:`
`+    break`
`+`
`+while True:`
`+  if is_prime(x):`
`+    print "X =", x`
`+    break`
`+  for x in fibs: break`
`+`
`+D = list(divisors(x + 1))`
`+print D`
`+print "divisors sum =", sum(D)`
`+print "unique divisors sum =", sum(set(D))`

# praxis/greplin-challenge/gettysburg.py

`+#!/usr/bin/env python2.6`
`+`
`+def is_palindrome(s, start=0, stop=None):`
`+  if stop is None: stop = len(s)`
`+`
`+  # unnecessary optimization to avoid many short-lived strings`
`+  length = stop - start`
`+  return all(s[x + start] == s[stop - (x + 1)] for x in xrange(length / 2))`
`+`
`+assert not is_palindrome("racecars")`
`+assert is_palindrome("racecar")`
`+`
`+def find_palindromes(s):`
`+  for start in xrange(len(s) - 1):`
`+    for stop in xrange(start + 1, len(s) + 1):`
`+      if is_palindrome(s, start, stop):`
`+        yield s[start:stop]`
`+`
`+`
`+gettysburg = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"`
`+`
`+L = [x for x in find_palindromes(gettysburg) if len(x) > 1]`
`+print L`
`+if L:`
`+  print max(L, key=len)`

# praxis/greplin-challenge/subsets.py

`+#!/usr/bin/env python2.6`
`+"""Subsets`
`+`
`+This is a naive solution which brute forces all subsets.  I verified it gave the correct results, then didn't think any more of it.`
`+"""`
`+`
`+import sys`
`+import itertools`
`+`
`+`
`+def each_bit(num):`
`+  assert num >= 0`
`+  # second loop is probably unnecessary optimization, could use a single infinite loop here`
`+  while num:`
`+    yield bool(num & 1)`
`+    num >>= 1`
`+  while True:`
`+    yield False`
`+`
`+def subsets(L):`
`+  for bits in xrange(2 ** len(L)):`
`+    yield [x for x, b in zip(L, each_bit(bits)) if b]`
`+`
`+`
`+numbers = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]`
`+#numbers = [1, 2, 3, 4, 6]`
`+`
`+print "numbers = (%d) %r" % (len(numbers), numbers)`
`+count = 0`
`+total = 0`
`+for x in subsets(numbers):`
`+  if not (2 <= len(x) < len(numbers)):`
`+    continue`
`+  total += 1`
`+  if total % 100000 == 0:`
`+    print "examined %d subsets, found %d meeting the criteria" % (total, count)`
`+  mx = max(x)`
`+  if sum(n for n in x if n != mx) == mx:`
`+    print " ", x`
`+    count += 1`
`+`
`+print "examined %d subsets in total" % total`
`+print "count =", count`

# praxis/greplin-challenge/subsets2.py

`+#!/usr/bin/env python2.6`
`+"""Subsets`
`+`
`+This is a dynamic solution which runs efficiently.  I did not think of this approach, but implemented it from the description at http://programmingpraxis.com/2010/11/09/subset-sums/.`
`+"""`
`+`
`+def solve(numbers):`
`+  """Solve sum of subsets for numbers.`
`+`
`+  numbers must be positive and in sorted order.`
`+  """`
`+  memo = {}`
`+  def f(stop, target):`
`+    """number of subsets of numbers[:stop] which sum to target"""`
`+    if stop == 0:  # empty set only matches if target is 0`
`+      return target == 0`
`+    if target == 0:  # only empty set matches`
`+      return 1`
`+`
`+    key = (stop, target)`
`+    if key in memo:`
`+      return memo[key]`
`+`
`+    result = f(stop - 1, target)  # without last`
`+    last = numbers[stop - 1]`
`+    if target >= last:`
`+      result += f(stop - 1, target - last)  # with last`
`+`
`+    memo[key] = result`
`+    return result`
`+`
`+  return sum(f(x, numbers[x]) for x in xrange(2, len(numbers)))`
`+`
`+`
`+def show(numbers):`
`+  print numbers`
`+  print "=", solve(numbers)`
`+  print`
`+`
`+show([1, 2, 3, 4, 6])`
`+show([3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99])`
`+`
`+`
`+# primes example from Praxis`
`+`
`+def primes(stop):`
`+  """Return sieve for primes 2..stop."""`
`+  sieve = [True] * stop`
`+  for x in xrange(2, stop):`
`+    if sieve[x]:`
`+      yield x`
`+      for n in xrange(2 * x, stop, x):`
`+        sieve[n] = False`
`+`
`+show(list(primes(2**10)))`