ugly.py

# Dynamic programming solution to the ugly numbers problem.
# Author: Jon Brandvein
# See problem at: https://www.codeeval.com/public_sc/42/

from itertools import chain
from functools import lru_cache

uglyprimes = [2, 3, 5, 7]

def ugly(n):
    return any(n % p == 0 for p in uglyprimes)

@lru_cache(None)
def ways(s, d, r=0):
    """Given a digit string s, a dividend d, and optionally a
    remainder r, find the ways that s can be broken up into an
    algebraic expression such that its value is congruent to r,
    mod d. The ways are returned as a set of strings.
    """
    answer = set()
    # Account for taking the digit string as-is with no operators.
    if int(s) % d == r:
        answer.add(s)
    # Choose the position of the first operator, either + or -.
    # Compute the left-most number's remainder. Recursively run
    # ways() on the rest of the digit string such that its
    # remainder combines with the left number's to make r.
    for i in range(1, len(s)):
        left = s[:i]
        right = s[i:]
        leftrem = int(left) % d
        # Try plus and minus operators.
        for neg in [1, -1]:
            goalrem = neg * (r - leftrem) % d
            subways = ways(right, d, goalrem)
            answer.update(left + ('+' if neg == 1 else '-') + w
                          for w in subways)
    return answer

def solution(s):
    return len(set(chain.from_iterable(ways(s, p) for p in uglyprimes)))

from time import clock
t1 = clock()
print('Ways: {}'.format(solution('12345')))
t2 = clock()
print('Time: {:.3f}'.format(t2 - t1))