Perl Weekly Challenge 134: Distinct Terms Count

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

      x | 1 2 3
      --+------
      1 | 1 2 3
      2 | 2 4 6
      3 | 3 6 9

Distinct Terms: 1, 2, 3, 4, 6, 9
Count: 6

Input: $m = 3, $n = 5
Output:

      x | 1  2  3  4  5
      --+--------------
      1 | 1  2  3  4  5
      2 | 2  4  6  8 10
      3 | 3  6  9 12 15

Distinct Terms: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15
Count: 11

The challenge description talks about two things: a multiplication table (to be generated), and a count of distinct terms (to be displayed). The examples show three things: a multiplication table, a list of distinct terms, and a count.

Now, the weekly challenge has a long history of examples where it's not clear where the expected output ends, and where the description of why this is the right answer starts.

The only thing of which it's clear which needs to be outputted is the count of distinct terms.

Of the others, the table and list of terms, we assume to be explaination.

If not, then please, please, consider spending a minute more on drafting the challenge, and make it clear what you expect.

We will just generate all the products \(p = i \cdot j, 1 \leq i \leq m, 1 \leq j \leq n\). This is more than we need, as we will be calculating both \(i \cdot j\) and \(j \cdot i\) for all \(1 \leq i < j \leq \text{ min} (m, n)\), but that will be less than twice the optimal number of products.

To keep track of the different products, we will store them in either an array/list/vector, or a hash/map/table/associative array, depending on the language.

To get the count, we either get the number of elements stored, or we keep a running count, incrementing the count each time we get a product we have not seen yet.

Below is a matrix showing which solution we have for which language. The implementations in the languages listed in the column labelled Array use an array as the structure which keeps track of seen products, while the column labelled Hash list implementations in languages using a hash as structure.

The row labelled Size lists implementations in languages where we get the size of the structure to determine the number of distinct products, while the row labelled Count lists implementations in languages where we have a running count.

	Hash	Array
Size	AWK, Bash, Java, Node.js, Perl, Python, Ruby, Tcl	R
Count	Go, Lua, Scheme	bc, C, Pascal

For each of the four techniques, we will show one solution.

All our solutions read pairs of numbers from standard input, one pair per line. For each pair, we print the number of distinct products to standard output.

Our Tcl solution is an example where we're using a hash to keep track of which products we have seen, and where we use the size of the resulting structure to display the count.

In Tcl, arrays are associative arrays (after all, everything is a string in Tcl).

while {[gets stdin line] >= 0} {
    lassign [split $line " "] n m
    array set seen { }
    for {set i 1} {$i <= $n} {incr i} {
        for {set j 1} {$j <= $m} {incr j} {
            set seen([expr $i * $j]) 1
        }
    }
    puts [array size seen]
}

An array is defined using the array set statement. The array is called seen, and we initialize it to an empty list.

The array size statement returns the number of elements in the array.

Find the full program on GitHub.

In Lua, we also use a hash (which Lua calls tables; Lua doesn't have different objects for arrays or hashes). But instead of finding out the size afterwards, for each product generated, we check if it is already in the table. If not, we increment a count.

for line in io . lines () do
    local _, _, m, n = line : find ("([0-9]+)%s+([0-9]+)")
    local seen = {}
    local count = 0
    for i = 1, m do
        for j = 1, n do
            if seen [i * j] == nil then
                seen [i * j] = 1
                count = count + 1
            end
        end
    end
    print (count)
end

Find the full program on GitHub.

bc does not have hashes, just arrays. So, we start off with an array of \(m \cdot n\) elements, all initialized to 0. For each produced product, we set the value on that index to 1. Each time we set a value from 0 to 1, we increment a count.

Now, it sounds expensive to use an array instead of a hash, as there are many numbers between 1 and \(i \cdot j\) which aren't a product. However, for \(m, n < 10000\), about 25% of the numbers between \(1\) and \(10000^2\) can be written as a product of two numbers less than \(10000\). So the waste isn't too bad.

while (1) {
    m = read(); if (m == 0) break
    n = read(); if (n == 0) break
    for (i = 1; i <= m * n; i ++) {
        s[i] = 0
    }
    count = 0
    for (i = 1; i <= n; i ++) {
        for (j = 1; j <= m; j ++) {
            if (s[i * j] == 0) {
                count = count + 1
                s[i * j] = 1
            }
        }
    }
    count
}

Find the full program on GitHub.

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

    m <- as.numeric (parts [[1]] [[1]])
    n <- as.numeric (parts [[1]] [[2]])

    seen <- replicate (m * n, 0)

    for (i in 1 : m) {
        for (j in 1 : n) {
            seen [[i * j]] <- 1
        }
    }

    cat (sum (seen), "\n")
}