algorithms

ArrayContainsCommonItem.js

const containsCommonItem = (arr1, arr2) => arr1.some(item => arr2.includes(item))

var foo = [1, 2, 4]
var bar = [4, 4, 5]

console.log(containsCommonItem(foo, bar))

ArrayHasPairWithSum.js

// Naive
function hasPairWithSum(arr, sum){
    var len = arr.length;
    for(var i =0; i<len-1; i++){
       for(var j = i+1;j<len; j++){
          if (arr[i] + arr[j] === sum)
              return true;
       }
    }
  
    return false;
  }
  
  // Better
  function hasPairWithSum2(arr, sum){
    const mySet = new Set();
    const len = arr.length;
    for (let i = 0; i < len; i++){
      if (mySet.has(arr[i])) {
        return true;
      }
      mySet.add(sum - arr[i]);
    }
    return false;
  }
  
  hasPairWithSum2([6,4,3,2,1,7], 9)

ArraySorts.js

const foo = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]
let pequeno = foo.length > 27 ? true : false





// Insertion Sort = Poucos itens ou eu ja acho que ta em ordem
// Vai vendo 1 por 1 e inserindo onde devia estar baseado nos que ja viu

const insertionSort = array => {
    const length = array.length;
    for (let i = 0; i < length; i++) {
        if (array[i] < array[0]) {
            array.unshift(array.splice(i, 1)[0]);
        } else {
            for (let j = 1; j < i; j++) {
                if (array[i] > array[j - 1] && array[i] < array[j]) {
                    array.splice(j, 0, array.splice(i, 1)[0]);
                }
            }
        }
    }
    return array
}

const insertCall = foo => console.log('Insert Sort:', insertionSort(foo))

// QuickSort = muita coisa, sem problema de falta de memória
// Escolhe um pivot e vai jogando pra esquerda e direita dele e ai cada subarray faz a mesma coisa recursivamente
const quickSort = (originalList) => {
    const list = [...originalList]

    if (list.length < 2) {
        return list
    }

    const pivot = list[Math.floor(list.length / 2)]

    const smaller = list.filter((item) => item < pivot)
    const bigger = list.filter((item) => item > pivot)

    return [...quickSort(smaller), pivot, ...quickSort(bigger)]
}
const quickCall = foo => console.log('Quick Sort:', quickSort(foo))


// Mergesort = muita coisa, com problema de falta de memória
// Sai dividindo por 2 até ficar itens individuais, depois vai montando de 2 em 2 
// os blocos ordenando. Meio que vai ordenando aos poucos, entao evita o pior caso em relacao ao quicksort
// mas gasta mais memória
const merge = (left, right) => {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    while (leftIndex < left.length &&
        rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}

const mergeSort = array => {
    if (array.length === 1) {
        return array
    }
    const length = array.length;
    const middle = Math.floor(length / 2);
    const left = array.slice(0, middle);
    const right = array.slice(middle);

    return merge(
        mergeSort(left), mergeSort(right)
    )
}
const mergeCall = foo => console.log('Merge Sort:', mergeSort(foo))




/* CONTROLE DE ESCOLHAS */
// let huge = true
let huge = false

// let PartialSorted = true
let partialSorted = false

let numeric = true
// let numeric = false

const QualUsar = partialSorted || pequeno ? insertCall(foo) : (numeric || huge ? quickCall(foo) : mergeCall(foo))
// console.log(QualUsar)

ArrayToObject.js

// arra1 = ['a', 'b', 'c']
// return = {
// a: true,
// b: true,
// c: true
// }
const ArrayToObjectTrue = (arr1) => {
    let object = {}
    for (let i=0; i< arr1.length; i++) {
        if (!object[arr[i]]) {
            const item = arr[i]
            object[item] = true;
        }
    }
    return object
}


const CheckArrayExistsOnObject = (arr2, ArrayToObjectTrue) => {
    const object = ArrayToObjectTrue

    for (let i=0; i < arr2.length; i++) {
        if (object[arr2[i]]) {
            return true
        }
    }
}

FibonacciMemoizated.js

// fibonacci [0,1,1,2,3,5,8,13,21,34,55,89,144,233...]
const fibonacci = n => {
    if (n < 2) {
        return n
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}


const fibonacciMemoized = (n) => {
    let cache = {};
    return function fibonacci(n) {
        if (n in cache) {
            return cache[n];
        } else {
            if (n < 2) {
                return n;
            } else {
                cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
                return cache[n];
            }
        }
    }()
}

const fibonacciMaster = n => {
    let answer = [0, 1];
    for (let i = 2; i <= n; i++) {
        answer.push(answer[i - 2] + answer[i - 1])
    }
    return answer.pop()
}

console.log(fibonacciMemoized()(32))



const fibonacciMasterGod = n => {
    // let answer = [0, 1];
    if(n===1) {
        return n;
    }
    let first = 1;
    let second = 2;

    for (let i = 3; i <= n; i++) {
        // answer.push(answer[i - 2] + answer[i - 1])
        const third = first+second;
        first = second;
        second=third;
    }
    return second
}

Memoization.js

const memoizationAddTo80 = () => {
    let cache = {}
    return (n) => {
        if (n in cache) {
            return cache[n];
        }
        else [
            cache[n] = n + 80;
            return cache[n];
        ]
    }
}

const memoized = memoizationAddTo80()

StringReverse.js

const ReverseString = str => [...str].reverse().join('')

const foo = "Testando uma String"

console.log(ReverseString(foo))
// gnirtS amu odnatseT