Programming Praxis

I had an email from a reader who found my factoring program on Stack Overflow:

Python 2.7.13 (default, Mar 13 2017, 20:56:15)
[GCC 5.4.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> def isPrime(n, k=5): # miller-rabin
...     from random import randint
...     if n < 2: return False
...     for p in [2,3,5,7,11,13,17,19,23,29]:
...         if n % p == 0: return n == p
...     s, d = 0, n-1
...     while d % 2 == 0:
...         s, d = s+1, d/2
...     for i in range(k):
...         x = pow(randint(2, n-1), d, n)
...         if x == 1 or x == n-1: continue
...         for r in range(1, s):
...             x = (x * x) % n
...             if x == 1: return False
...             if x == n-1: break
...         else: return False
...     return True
...
>>> def factors(n, b2=-1, b1=10000): # 2,3,5-wheel, then rho
...     def gcd(a,b): # euclid's algorithm
...         if b == 0: return a
...         return gcd(b, a%b)
...     def insertSorted(x, xs): # linear search
...         i, ln = 0, len(xs)
...         while i < ln and xs[i] < x: i += 1
...         xs.insert(i,x)
...         return xs
...     if -1 <= n <= 1: return [n]
...     if n < -1: return [-1] + factors(-n)
...     wheel = [1,2,2,4,2,4,2,4,6,2,6]
...     w, f, fs = 0, 2, []
...     while f*f <= n and f < b1:
...         while n % f == 0:
...             fs.append(f)
...             n /= f
...         f, w = f + wheel[w], w+1
...         if w == 11: w = 3
...     if n == 1: return fs
...     h, t, g, c = 1, 1, 1, 1
...     while not isPrime(n):
...         while b2 <> 0 and g == 1:
...             h = (h*h+c)%n # the hare runs
...             h = (h*h+c)%n # twice as fast
...             t = (t*t+c)%n # as the tortoise
...             g = gcd(t-h, n); b2 -= 1
...         if b2 == 0: return fs
...         if isPrime(g):
...             while n % g == 0:
...                 fs = insertSorted(g, fs)
...                 n /= g
...         h, t, g, c = 1, 1, 1, c+1
...     return insertSorted(n, fs)

He complained that the program failed to factor the number 100011322432435545, entering an infinite loop instead of returning a list of factors.

Your task is to figure out what is wrong, and fix it. 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

Today’s exercise comes from one of those online code exercises, via Stack Overflow:

There is a machine that can fix all potholes along a road 3 units in length. A unit of road will be represented by a period in a string. For example, “…” is one section of road 3 units in length. Potholes are marked with an “X” in the road, and also count as 1 unit of length. The task is to take a road of length N and fix all potholes with the fewest possible sections repaired by the machine.

The city where I live needs one of those machines.

Here are some examples:

.X.          1
.X...X       2
XXX.XXXX     3
.X.XX.XX.X   3

Your task is to write a program that takes a string representing a road and returns the smallest number of fixes that will remove all the potholes. 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