How can i implement functional loop statements instead of for loops in this case?

Question

How to check if sum of any two elements in the array exists in the array using functional loop statements(map, forEach, reduce) instead of for loops.

For example an array like this

[1, 2, 9, 4, 3] // would return true as 1 + 2 = 3
[2,7,12,6,8,20]  // true as 2 + 6 = 8 which is enough to make it true
[1, 2, 4, 9] //would return false

I can do this by for loops:

const checkSumExist = arr => {
  for(let i = 0; i < arr.length; i++) {
    for(let j = i + 1; j < arr.length; j++) {
      if(arr.includes(arr[i] + arr[j])) return true;   
    }
  }

  return false; 
}

So is there a solution using functional loop statement instead of nested for loops in this case???

Answer 1

A simplified implementation –

const main = (xs = []) =>
  xs .some ((n, i) =>
    xs .some ((m, j) =>
      i < j && xs .includes (n + m)
    )
  )
  
console.log
  ( main ([ 1, 2, 4, 9, 4, 3 ])   // true
  , main ([ 2, 7, 12, 6, 8, 20 ]) // true
  , main ([ 1, 2, 4, 9 ])         // false
  )

This optimization using Set improves speed to O(1) –

const main = (xs = [], s = new Set (xs)) =>
  xs .some ((n, i) =>
    xs .some ((m, j) =>
      i < j && s .has (n + m)
    )
  )

console.log
  ( main ([ 1, 2, 4, 9, 4, 3 ])   // true
  , main ([ 2, 7, 12, 6, 8, 20 ]) // true
  , main ([ 1, 2, 4, 9 ])         // false
  )

Remember only to optimize where necessary

Answer 2

Edit--I forgot that .some provides the index of each element as the 2nd parameter. This makes it a bit cleaner!

const foo = [1, 2, 9, 4, 3]; // would return true
const bar = [1, 2, 4, 9]; // would return false
const baz = [2,7,12,6,8,20]; // should also be true

const sumOf2Exists = (arr) => {
  // create a hash of the values in arr so we can check the
  // accept condition in O(1) time
  const hash = arr.reduce((acc, n) => {
    acc[n] = true;
    return acc;
  }, {});
  
  // find some n, m where n and m aren't the same entry 
  // and the sum n+m is in arr (using the hash)
  return arr.some((n, i) => arr.some((m, j) => j > i && hash[n + m]));
};

console.log(sumOf2Exists(foo))
console.log(sumOf2Exists(bar))
console.log(sumOf2Exists(baz));

Inspired by comment from tex and using Immutable.js

const { Set, Range } = Immutable

const foo = [1, 2, 9, 4, 3]; // would return true
const bar = [1, 2, 4, 9]; // would return false
const baz = [2, 7, 12, 6, 8, 20]; // should also be true

const sumOf2Exists = (arr) => {
  const hash = Set(arr);
  return arr.some((n, i) => (
    Range(i+1, arr.length).some(j => hash.has(n + arr[j]))
  ));
};

console.log(sumOf2Exists(foo))
console.log(sumOf2Exists(bar))
console.log(sumOf2Exists(baz));

<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.2/immutable.min.js"></script>

Answer 3

The idea in the following solution is to use reduce and map to build all possible combinations of 2 numbers and then use some to test if sum of any combination is in the array.

function sumExists(arr) {
  return arr
    .reduce((acc, curr, i) => acc.concat(arr.slice(i + 1).map(e => [curr, e])), [])
    .some(([a, b]) => arr.includes(a + b));
}

console.log(sumExists([1, 2, 9, 4, 3]));
console.log(sumExists([2, 7, 12, 6, 8, 20]));
console.log(sumExists([1, 2, 4, 9]));

An O(n^2) version would be the following:

function sumExists(arr) {
  const sums = new Set(arr);
  return arr
    .reduce((acc, curr, i) => {
      acc.push(...arr.slice(i + 1).map(e => [curr, e]));
      return acc;
    }, [])
    .some(([a, b]) => sums.has(a + b));
}

console.log(sumExists([1, 2, 9, 4, 3]));
console.log(sumExists([2, 7, 12, 6, 8, 20]));
console.log(sumExists([1, 2, 4, 9]));

Answer 4

This is my solution using Rxjs:

import { Observable, from, of, zip, pairs, combineLatest, empty } from 'rxjs';
import { filter, map, takeUntil, takeWhile, single, zipAll, pairwise, combineAll, mergeMap, merge, first, skip, skipWhile, defaultIfEmpty } from 'rxjs/operators';

let test1 = [1, 2, 9, 4, 3]; // would return true as 1 + 2 = 3
let test2 = [2,7,12,6,8,20];  // true as 2 + 6 = 8 which is enough to make it true
let test3 = [1, 2, 4, 9]; //would return false


let observable1 = from(test1);

let skipSameIndex = (arr:number[], anchorIndex:number) => {
    return from(arr).pipe(
        filter((v, i) => {
        // console.log('anchodIndex:', anchorIndex, ', i:', i);
        return anchorIndex !== i;
        })
    )
}

let pairAll = (arr:number[]) => from(arr).pipe(mergeMap( (x, index) => {
    return combineLatest(of(x), skipSameIndex(arr, index))
}));

let isPairExistsInArray = (pair:[number, number], arr: number[]) => {
    let isExists = arr.indexOf(pair[0] + pair[1]) >= 0; 

    // console.log('pair:', pair, ', isExists:', isExists);

    return isExists;
}


let isSumEachElementsExists = (arr:number[]) => pairAll(arr).pipe(    
    map((pair:[number, number]) => isPairExistsInArray(pair, arr)),    
    // first(isExists => isExists)
    filter(x => x),
    defaultIfEmpty(false)
);

// skipSameIndex(test3, 1).subscribe(x => console.log(x));


isSumEachElementsExists(test1).toPromise()
    .then(isExists => console.log('test1 isExists:', isExists))
    .catch(err => console.log('ERROR:', err));


isSumEachElementsExists(test2).toPromise()
    .then(isExists => console.log('test2 isExists:', isExists))
    .catch(err => console.log('ERROR:', err));

isSumEachElementsExists(test3).toPromise()
    .then(isExists => console.log('test3 isExists:', isExists))
    .catch(err => console.log('ERROR:', err));

My conclusion after this is FP is hard and the solution is overly complex compare to iterative programming :). I am open for suggestion or correction if anyone can simplify this.

Answer 5

I am not sure if this is the correct solution because I don't quite understand what you mean by functional loop but check this out, this solution is without any loops.

function check(list, i, j) {
    if(i >= list.length || j >= list.length) return false;
    if(i != j && list.includes(list[i] + list[j])) return true;
    return check(list, i+1, j) || check(list, i, j+1)
}

check([1,2,9,4,3], 0, 0)
true

check([1,2, 4, 9], 0, 0)
false

Answer 6

Maybe this a brute force and over-engineered solution, but I challenged myself to provide a vanilla JS, purely-functional approach to solve the problem.

BTW, there're libraries out there like Sanctuary or Ramda, or many others, which would save the boilerplate part of my answer.

It has just an issue: it checks all summable combinations (possibleSums), but this is a plus, since one can print out all coincidences. Also, there's someSumExists which just checks that possibleSums outputs one or more coincidences.

In the other hand, it has another issue: it relies on the fact that inputs won't contain repeated numbers.

// ::: Combinators :::

// I :: a -> a -> a
const I = x => x

// T :: a -> (a -> a) -> a
const T = x => f => f (x)

// W :: a -> (a -> a -> a) -> a
const W = x => f => f (x) (x)

// ::: Non-generalized, partial Functor, Chain, Applicative Array-specific instances... :::

// map :: (a -> a) -> [a] -> [a]
const map = f => xs => xs.map (f)

// chain :: (a -> a) -> [a] -> [a]
const chain = f => xs => xs.reduce((o, x) => [...o, ...f (x)], [])

// ap :: [a -> b] -> [a] -> [b]
const ap = ms => m => chain (x => map (f => f(x)) (ms)) (m)

// lift2 :: [a -> c -> d] -> [a -> b] -> [b -> c] -> [d]
const lift2 = f => xs => ys => ap (map (f) (xs)) (ys)

// join :: [[a]] -> [a]
const join = chain (I)

// ::: Utils :::

// pipe :: [Any -> Any] -> Any -> Any
const pipe = xs => x => xs.reduce ((x, f) => f (x), x)

// any :: (a -> Boolean) -> [a] -> Boolean
const any = f => xs => xs.some (f)

// joinWith :: String -> [Any] -> [String]
const joinWith = sep => xs => xs.join (sep)

// length :: [Any] -> Number
const length = xs => xs.length

// equals :: a -> a -> Boolean
const equals = x => y => x === y

// not :: a -> Boolean
const not = x => x !== true

// possibleSums :: Number -> [[Number, Number, Number]]
const possibleSums = input =>
    pipe ([
       W,
       T (lift2 (x => y => x !== y && input.includes (x + y) ? [[x, y, x + y]] : [])),
       join
    ]) (input)
    
// someSumExists :: [Number] -> Boolean
const someSumExists = pipe ([ 
    possibleSums,
    length,
    equals (0),
    not
])

// printSums :: [[Number, Number, Number]] -> [String]
const printSums = pipe ([
    map (([x, y, r]) => `${x} + ${y} = ${r}`),
    joinWith ('\n')
])

// printPossibleSums :: [[Number, Number, Number]] -> String
const printPossibleSums = pipe ([ possibleSums, printSums ])
      
const input1 = [1, 2, 9, 4, 3] 
const input2 = [2,7,12,6,8,20] 
const input3 = [1, 2, 4, 9]

const output1 = printPossibleSums (input1)
const output1_ = someSumExists (input1)

const output2 = printPossibleSums (input2)
const output2_ = someSumExists (input2)

const output3 = printPossibleSums (input3)
const output3_ = someSumExists (input3)


console.log ('Input 1 has a case:', output1_)
console.log (output1)


console.log ('Input 2 has a case:', output2_)
console.log (output2)


console.log ('Input 3 has a case:', output3_)
console.log (output3)

Less boilerplate: Ramda!

This the same approach using Ramda's functions to save some code lines:

const { map, join, length, equals, not, pipe, lift, unnest } = R
const W = x => f => f (x) (x)
const T = x => f => f (x)

const possibleSums = input =>
    pipe (
       W,
       T (lift ((x, y) => x !== y && input.includes (x + y) ? [[x, y, x + y]] : [])),
       unnest
    ) (input)
    
const someSumExists = pipe ( 
    possibleSums,
    length,
    equals (0),
    not
)

const printSums = pipe (
    map (([x, y, r]) => `${x} + ${y} = ${r}`),
    join ('\n')
)

const printPossibleSums = pipe (possibleSums, printSums)

const input1 = [1, 2, 9, 4, 3] 
const input2 = [2,7,12,6,8,20] 
const input3 = [1, 2, 4, 9]

const output1 = printPossibleSums (input1)
const output1_ = someSumExists (input1)

const output2 = printPossibleSums (input2)
const output2_ = someSumExists (input2)

const output3 = printPossibleSums (input3)
const output3_ = someSumExists (input3)


console.log ('Input 1 has a case:', output1_)
console.log (output1)


console.log ('Input 2 has a case:', output2_)
console.log (output2)


console.log ('Input 3 has a case:', output3_)
console.log (output3)

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.25.0/ramda.min.js"></script>