1
\$\begingroup\$

Program finds the number of pairs of co-primes in an array using functional concepts in Node.js

const assert = require('assert')

const gcd = (a, b) => (b != 0) ? gcd(b, a % b) : a

const co_prime = (a, b) => gcd(a, b) == 1

const co_prime_pairs = (_list) => {
    co_primes = []
    _list.map(
        (x, i) => _list.slice(i + 1)
                        .filter(y => co_prime(x, y))
                        .forEach(y => co_primes.push([x, y]))
        )
    return co_primes.length
} 

const main = () => {
    assert.equal(co_prime_pairs([1, 2, 3]), 3)
    assert.equal(co_prime_pairs([4, 8, 3, 9]), 4)
}

main()

Is the time complexity similar to that of the simple for-loop implementation?

Is there any scope for improving the time-complexity by using map and filter functions?

How is my choice of variable names?

How is code formatting?

\$\endgroup\$
  • \$\begingroup\$ Random thought: consider prime factoring the list elements, and then using hashes or something so you don't have to loop through each pair. \$\endgroup\$ – Barry Carter Nov 4 '17 at 17:38
1
\$\begingroup\$

How is my choice of variable names?

In general you used snake case for the function names which is more a ruby-style.

Additionally the function co_prime_pairs let me acept that it return pairs of co-primes. However it returns a number of co-pairs inside an array.

The variable co_primes is declared globally.

co_prime_pairs

This function is not a pure function internally because .forEach(y => co_primes.push([x, y])) modifies co_primes.
I rewrite the function and spit the logic into:

  1. build pairs
  2. filter the co primes
  3. return the length

The functions:

const filterCoPrimes = xss =>
    xss.filter(xs => isCoPrime(xs[0], xs[1]))

const buildPair = x => y =>
    [x, y]

const buildPairs = (xs, pairs) =>
    xs.length === 0 || xs.length === 1
        ? pairs
        : buildPairs(
            xs.slice(1), 
            pairs.concat(xs.map(buildPair(xs[0])))
        )

The chain:

const co_prime_pairs = xs =>
    filterCoPrimes(buildPairs(xs, [])).length

If we use pipe as a kind of function composition it can be rewritten to:

const co_prime_pairs = pipe(
    buildPairs([]),
    filterCoPrimes,
    length
)

Full working Example

  • function calls:

const gcd = (a, b) => 
  (b != 0) ? gcd(b, a % b) : a

const isCoPrime = (a, b) => 
  gcd(a, b) === 1

const filterCoPrimes = xss =>
  xss.filter(xs => isCoPrime(xs[0], xs[1]))

const buildPair = x => y =>
  [x, y]

const buildPairs = (xs, pairs) =>
  xs.length === 0 || xs.length === 1
      ? pairs
      : buildPairs(
          xs.slice(1), 
          pairs.concat(xs.map(buildPair(xs[0])))
      )

const co_prime_pairs = xs =>
  filterCoPrimes(buildPairs(xs, [])).length

console.log(co_prime_pairs([4, 8, 3, 9]))

  • with pipe:

const pipe = (...fns) => fns.reduce((f, g) => (...args) => g(f(...args)))

const filter = fn => xs =>
    xs.filter(fn)

const map = fn => xs =>
    xs.map(fn)

const length = xs => 
    xs.length

const gcd = (a, b) => 
    (b != 0) ? gcd(b, a % b) : a

const isCoPrime = (a, b) => 
    gcd(a, b) === 1

const filterCoPrimes = xss =>
    xss.filter(xs => isCoPrime(xs[0], xs[1]))

const buildPair = x => y =>
    [x, y]

const buildPairs = pairs => xs =>
    xs.length === 0 || xs.length === 1
        ? pairs
        : buildPairs
            ( pairs.concat(xs.map(buildPair(xs[0]))) )
            ( xs.slice(1) )

const co_prime_pairs = pipe(
    buildPairs([]),
    filterCoPrimes,
    length
)
    
console.log(co_prime_pairs ([4, 8, 3, 9]))

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.