Ugly Numbers: A Rags-to-Riches Story

Question

I stumbled upon an unaswered question, which looked like a good fit for a functional programming language.

Here is the problem statement from codeeval:

UGLY NUMBERS

CHALLENGE DESCRIPTION:

Credits: This challenge has appeared in a google competition before.

Once upon a time in a strange situation, people called a number ugly if it was divisible by any of the one-digit primes (2, 3, 5 or 7). Thus, 14 is ugly, but 13 is fine. 39 is ugly, but 121 is not. Note that 0 is ugly. Also note that negative numbers can also be ugly: -14 and -39 are examples of such numbers.

One day on your free time, you are gazing at a string of digits, something like:

123456

You are amused by how many possibilities there are if you are allowed to insert plus or minus signs between the digits. For example you can make:

1 + 234 - 5 + 6 = 236

which is ugly. Or

123 + 4 - 56 = 71

which is not ugly.

It is easy to count the number of different ways you can play with the digits: Between each two adjacent digits you may choose put a plus sign, a minus sign, or nothing. Therefore, if you start with \$D\$ digits there are \$3^{D-1}\$ expressions you can make. Note that it is fine to have leading zeros for a number. If the string is 01023, then 01023, 0+1-02+3 and 01-023 are legal expressions.

Your task is simple: Among the \$3^{D-1}\$ expressions, count how many of them evaluate to an ugly number.

INPUT SAMPLE:

Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Each test case will be a single line containing a non-empty string of decimal digits. The string in each test case will be non-empty and will contain only characters '0' through '9'. Each string is no more than 13 characters long. E.g.

1
9
011
12345

OUTPUT SAMPLE:

Print out the number of expressions that evaluate to an ugly number for each test case, each one on a new line. E.g.

0
1
6
64

And here is my solution (ignoring the part about reading from a file)

type Expression =
    | Plus of Expression * Expression
    | Minus of Expression * Expression
    | Leaf of int64

let rec eval = function
    | Plus (left, right) -> (eval left) + (eval right)
    | Minus (left, right) -> (eval left) - (eval right)
    | Leaf n -> n

let rec expressions (s : string) =
    seq {
        yield Leaf (Int64.Parse(s))
        let n = s.Length
        for i in 1 .. n - 1 do
            let leaf = Leaf (Int64.Parse(s.Substring(0, i)))
            for e in expressions(s.Substring(i, n - i)) do
                yield Plus (leaf, e)
                yield Minus (leaf, e)
    }

let rec isUgly (n : int64) : bool =
    if n < 0L then
        isUgly -n
    else
        n = 0L || n % 2L = 0L || n % 3L = 0L || n % 5L = 0L || n % 7L = 0L

let countUglyNumbers (s : string) =
    expressions s |> Seq.map eval |> Seq.filter isUgly |> Seq.length

for input in ["1"; "9"; "011"; "12345"; "123456"; "1234566543215"] do
    printfn "%d" <| countUglyNumbers input

Answer 1

What is the purpose of the Expression type? Why doesn't expressions just return all the possible results?

This might be useful in other situations (like printing all the possibilities), but I don't see a reason for it here. Basically, it's an unnecessary level of abstraction.

---

if n < 0L then
    isUgly -n
else
    n = 0L || n % 2L = 0L || n % 3L = 0L || n % 5L = 0L || n % 7L = 0L

You don't need the special case for negative numbers, % works for them too.