DEV Community

Daily Challenge #213 - Are they the "same"?

dev.to staff on March 26, 2020

Given two arrays a and b write a function comp(a, b) (compSame(a, b) in Clojure) that checks whether the two arrays have the "same" elements, with ...
Collapse
 
vidit1999 profile image
Vidit Sarkar • Edited

Python solution

from collections import Counter
comp = lambda a, b: a != None and b != None and Counter(map(lambda x: x*x,a))==Counter(b)

print(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 361, 25921, 361, 20736, 361])) # True
print(comp([121, 144, 19, 161, 19, 144, 19, 11], [11*11, 121*121, 144*144, 19*19, 161*161, 19*19, 144*144, 19*19])) # True
print(comp([121, 144, 19, 161, 19, 144, 19, 11], [132, 14641, 20736, 361, 25921, 361, 20736, 361])) # False
print(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 36100, 25921, 361, 20736, 361])) # False
print(comp([], [])) # True
print(comp([1,2,3,4],None)) # False
print(comp(None, None)) # False
Collapse
 
cipharius profile image
Valts Liepiņš • Edited

Solution in Haskell:

import Data.List (sort)

comp :: [Int] -> [Int] -> Bool
comp a b
  | length a == length b = all same $ zip (fmap sq . sort $ a) (sort b)
  | otherwise            = False
  where sq x = x*x
        same x = fst x == snd x

Edit:
I wanted to implement the O(a + b) solution in Haskell as well:

import qualified Data.IntMap.Strict as Map
type Freq = Map.IntMap Int

comp :: [Int] -> [Int] -> Bool
comp as bs
  | length as == length bs = freq (fmap (^2) as) == freq bs
  | otherwise              = False
    where
      freq = foldr inc Map.empty
      inc k = Map.insertWith (+) k 1
Collapse
 
craigmc08 profile image
Craig McIlwrath

Why use all same? Can't you directly test map (^2) (sort a) == sort b?

Collapse
 
cipharius profile image
Valts Liepiņš

Wasn't aware that Haskell's equality operator did deep comparision, but that makes sense. Thanks!

I'd probably rewrite this with the O(a + b) algorithm from the other solution.

Thread Thread
 
craigmc08 profile image
Craig McIlwrath

It's not really deep comparison, it uses the Eq class (==) function. For the primitives, it's by value. For ADTs that derive Eq, it checks equality for all of the values in the ADT, which functions that same as deep comparison.

Collapse
 
dangerontheranger profile image
Kermit Alexander II • Edited

The main point to keep in mind with this one is that all values in b must be accounted for, as we see with the test case with 36100 as a value. Additionally, we can't use a set for this problem since values may show up in either a or b multiple times, so that's out. So instead, we can calculate the frequency of occurrences of values instead, which leads to this O(a + b) solution:

#!/usr/bin/env python3

def calc_frequency(l):
    freqs = {}
    for num in l:
        freqs[num] = freqs.get(num, 0) + 1
    return freqs


def comp(a, b):
    if a is None or b is None:
        # early exit on null arrays
        return False
    b_freqs = calc_frequency(b)
    for num in a:
        square = num ** 2
        if square not in b_freqs:
            # early exit if the square of some value in a simply isn't in b
            return False
        b_freqs[square] -= 1
    for freq in b_freqs.values():
        if freq != 0:
            # could be < 0 if a has more occurrences, or > 0 if b has more occurrences
            return False
    return True


if __name__ == "__main__":
    print(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 361, 25921, 361, 20736, 361]))
    print(comp([121, 144, 19, 161, 19, 144, 19, 11], [11*11, 121*121, 144*144, 19*19, 161*161, 19*19, 144*144, 19*19]))
    print(comp([121, 144, 19, 161, 19, 144, 19, 11], [132, 14641, 20736, 361, 25921, 361, 20736, 361]))
    print(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 36100, 25921, 361, 20736, 361]))
    print(comp([], []))
    print(comp([1, 2, 3], None))
Collapse
 
sabbin profile image
Sabin Pandelovitch • Edited

JS solution

const comp = (a, b) => {
  if (
    a === null ||
    b === null ||
    a.length === 0 ||
    b.length === 0 ||
    a.length !== b.length
  ) {
    return false;
  }

  let status = true;
  let i = 0;
  while (status && i < a.length) {
    status = b.indexOf(Math.pow(a[i],2)) > -1
    i++;
  }

  return status;
};

*fixed

Collapse
 
kesprit profile image
kesprit

My Swift solution :

func comp(a: [Int], b: [Int]) -> Bool {
    guard !a.isEmpty, !b.isEmpty, a.count == b.count else { return false }

    return a.reduce(into: true) {
       $0 = b.contains($1 * $1)
    }
}
Collapse
 
kvharish profile image
K.V.Harish • Edited

My solution in JavaScript

const comp = (arr1, arr2) => {
  if(Array.isArray(arr1) && arr1.length && Array.isArray(arr2) && arr2.length) {
    return arr1.sort((a, b) => a - b).toString() === arr2.sort((a, b) => a - b).map(c => Math.sqrt(c)).toString()
  }
  return false;
};

// Valid arrays
console.log(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 361, 25921, 361, 20736, 361])); // true
console.log(comp([121, 144, 19, 161, 19, 144, 19, 11], [11*11, 121*121, 144*144, 19*19, 161*161, 19*19, 144*144, 19*19])); // true
// Invalid arrays
console.log(comp([121, 144, 19, 161, 19, 144, 19, 11], [132, 14641, 20736, 361, 25921, 361, 20736, 361])); // false
console.log(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 36100, 25921, 361, 20736, 361])); // false
Collapse
 
vidit1999 profile image
Vidit Sarkar • Edited

C++ solution

bool comp(vector<int> a, vector<int> b){
    // if both of them have no element then return true
    if(a.size() == 0 || b.size() == 0)
        return true;

    // if they have different size then return false
    if(a.size() != b.size())
        return false;

    int size = a.size(); // or b.size() as both of them have same size
    unordered_map<int, int> squareCount;

    // squares a number of a, increment squareCount[squareNumber_a] by 1 i.e. squareCount[squareNumber_a]++
    // decrement sqareCount[squareNumber_b] by 1 i.e. squareCount[squareNumber_b]--
    for(int i=0;i<size;i++){
        squareCount[a[i]*a[i]]++;
        squareCount[b[i]]--;
    }

    // if they are "same" then all the values of corresponding
    // keys of sqaureCount will be zero
    // if any one of them is not zero then return false
    for(auto it : squareCount){
        if(it.second != 0)
            return false;
    }
    return true;
}
Collapse
 
nilbert profile image
Nilbert

Ruby

def comp(array1, array2)
  return false if array1.nil?  || array2.nil?
    #method 1 compare dic
    array1.map{|x| x*x}.group_by(&:itself) == array2.group_by(&:itself)
    #method 2 compare sorted array
    array1.sort.map {|x| x*x} == array2.sort
end
Collapse
 
ksyula profile image
Ksenia

Python:

def comp(a: list, b: list) -> bool:
    flag = False
    if a == None or b == None:
        return flag
    elif len(a) == 0 and len(b) == 0:
        return True
    for val_a in a:
        flag = False
        for ind_b, val_b in enumerate(b):
            if val_a*val_a == val_b and flag == False:
                b.pop(ind_b)
                flag = True
    if len(b) == 0:
        return flag
    else:
        return False
Collapse
 
fsarikayaa profile image
Ferhat Sarıkaya • Edited

Php solution

 function comp($a1, $a2)
        {
            if ( is_null($a1) || is_null($a2) )
                return false;

            $t = array_map(function($v) {
                return $v * $v;
            }, $a1);

            sort($a2);
            sort($t);
            return $a2 == $t;
        }
Enter fullscreen mode Exit fullscreen mode
Collapse
 
tufailkaran profile image
Muhammad Tufail

Anyone have PHP Solution???

Collapse
 
darkopecevski profile image
Darko P.