Perl Weekly Challenge 141: Like Numbers

Input: $m = 1234, $n = 2
Output: 9

Possible integers created using the digits of 1234 are:
1, 2, 3, 4, 12, 13, 14, 23, 24, 34, 123, 124, 134 and 234.

There are 9 integers divisible by 2 such as:
2, 4, 12, 14, 24, 34, 124, 134 and 234.

Input: $m = 768, $n = 4
Output: 3

Possible integers created using the digits of 768 are:
7, 6, 8, 76, 78 and 68.

There are 3 integers divisible by 4 such as:
8, 76 and 68.

First, some clearification. The description says You are only allowed to use (n-1) digits, but this n has no relation to $n. It seems to mean the number of digits in $m. Confusing if you don't define what n is!

Second, it's unclear what repeating of digits are [sic] not allowed means. If we have $m = 1232 and $n = 2, should we count 22? 2 is repeated, but is it the same digit? What about 12? Count it once, or twice? We take the stance that if digits appear on different places in $m, we consider them as being different. So, we count 22, and we count 12 twice.

Third, what to do with 0s and leading 0s? What if we have $m = 1009, and $n = 3? Some of the substrings of $m are 0, 0, 9, 00, 09,09, and009. We decide to count them all, and hence, would give7` as answer.

In our solutions, n will refer to the first number, and m to the second number, so the other way around as in the challenge description.

We will solve this recursively. We define a subroutine substrings which will count the substrings of the given number matching the specified criteria. It takes the following arguments:

• n: a string. Initially called with the first number of the input.
• m: a number. Initially called with the second number of the input; this number will passed on unmodified to recursive calls.
• prefix: a number. This is a prefix of a constructed number so far. Initially called with -1, which has as meaning "no prefix".
• max: a number. Initially called with the first number of the input; this number will passed on unmodified to recursive calls.

The method works by removing the first character of the first argument (n), and then recursing twice: once with that character added to the prefix, and once not.

Recursion ends if substrings is called with an empty string as first argument. prefix will now be a substring of the input, and we have to decide whether we are going to count it or not:

• If prefix == -1, we reached this by never selecting any character. We do not consider this value, so we return 0.
• If prefix == max, we reached this by selecting all characters. This is not allowed by the challenge specification, so we return 0.
• Otherwise, we check whether m is a proper divisor of prefix (prefix % m == 0), if so, we count prefix and return 1, else, we return 0.

If we are recursing, in the case of selecting the first character of n, we need to calculate the new prefix. First, we set fc to be the value represented by the first character of n (so 0 <= fc <= 9). Then, if prefix == -1, we make the recursive call with prefix = fc, else, we make the recursive call with prefix = 10 * prefix + fc.

Given this, the implementations in the various languages are remarkably similar. We present a small selection.

The substrings function:

sub substrings ($n, $m, $prefix = -1, $max = $n) {
    if (!length $n) {
        return $prefix > -1   &&
               $prefix < $max &&
               $prefix % $m == 0 ? 1 : 0;
    }
    my $fc       = substr ($n, 0, 1);
    my $n_prefix = 10 * ($prefix == -1 ? 0 : $prefix) + $fc;
    substrings (substr ($n, 1), $m, $n_prefix, $max) +
    substrings (substr ($n, 1), $m, $prefix,   $max);
}

Which we call as:

say substrings split while <>;

Find the full program on GitHub.

The substrings function:

public static int substrings (String n, int m, int prefix, int max) {
    if (n . length () == 0) {
        return prefix > -1   &&
               prefix < max  &&
               prefix % m == 0 ? 1 : 0;
    }

    int fc       = Integer . parseInt (n . substring (0, 1));
    int n_prefix = 10 * (prefix == -1 ? 0 : prefix) + fc;
    String tail  = n . substring (1, n. length ());

    return substrings (tail, m, n_prefix, max) +
           substrings (tail, m,   prefix, max);
}

And the main function:

public static void main (String [] args) {
    Scanner scanner = new Scanner (System . in);
    while (scanner . hasNextInt ()) {
        int n = scanner . nextInt ();
        int m = scanner . nextInt ();
        System . out . println (
            substrings (Integer . toString (n), m, -1, n));
    }
}

Find the full program on GitHub.

The substrings function:

substrings <- function (n, m, prefix, max) {
    if (nchar (n) == 0) {
        if (prefix > -1 && prefix < max && prefix %% m == 0) {
            return (1)
        }
        else {
            return (0)
        }
    }

    fc   <- as.numeric (substr (n, 0, 1))
    tail <- substr (n, 2, nchar (n))
    if (prefix < 0) {
        n_prefix <- fc
    } else {
        n_prefix <- 10 * prefix + fc
    }

    return (substrings (tail, m, n_prefix, max) +
            substrings (tail, m,   prefix, max))
}

And the main program:

stdin <- file ('stdin', 'r')
repeat {
    line <- readLines (stdin, n = 1)
    if (length (line) == 0) {
        break
    }
    parts <- strsplit (line, " ")
    list  <- parts [[1]]

    cat (substrings (list [[1]], as.numeric (list [[2]]), -1,
                                 as.numeric (list [[1]])), "\n")
}

Find the full program on GitHub.

The substrings function:

(define (fc n)              (string->number (string-take n 1)))
(define (tail n)                            (string-drop n 1))
(define (n_prefix prefix n) (if (= prefix -1) (fc n) (+ (* prefix 10) (fc n))))

(define (substrings n m prefix max)
    (if (string-null? n)
        (if (and (> prefix -1)
                 (< prefix max)
                 (= (modulo prefix m) 0)) 1 0)
        (+ (substrings (tail n) m (n_prefix prefix n) max)
           (substrings (tail n) m           prefix    max))))

And the main program:

(define (main)
    (define line (read-line))
    (define parts)
    (if (not (eof-object? line))
        (begin
            (set! parts (string-split line #\ ))
            (display (substrings (list-ref parts 0)
                                 (string->number (list-ref parts 1))
                                 -1
                                 (string->number (list-ref parts 0))))
            (newline)
            (main)
        )
    )
)

Find the full program on GitHub.