// 1st try
// isUnique함수 문제점

function solution(relation) {
  var answer = 0;
  const totalAttribute = relation[0].length;

  const isUnique = (node) => {
    // @param arr
    const obj = {};

    relation.forEach((row) => {
      const key = node.reduce((acc, each) => acc + row[each], "");
      obj[key] = obj[key] ? obj[key] + 1 : 1;
    });

    for (const key in obj) {
      if (obj[key] > 1) {
        return false;
      }
    }

    return true;
  };

  const stack = [[0], [1], [2], [3]];

  while (stack.length) {
    const node = stack.pop();

    if (isUnique(node)) {
      answer++;
      console.log(node);
    } else {
      const last = node.pop();
      if (last + 1 < totalAttribute) {
        node.push(last);
        node.push(last + 1);
        stack.push(node);
      }
    }
  }

  return answer;
}

// 2nd try
/*
0   1  2  3
01  12 23
012 123  
0123

0                              1          2    3
01         02          03      12   13    23  
012  013   021 022 023         123    
0123

013에 의해 0123이 최소성을 만족하지 않을 수 있음.

*/

function solution(relation) {
  var answer = 0;
  const totalAttribute = relation[0].length;

  const isUnique = (node) => {
    // @param arr
    const obj = {};

    relation.forEach((row) => {
      const key = node.reduce((acc, each) => acc + "," + row[each], "");
      obj[key] = obj[key] ? obj[key] + 1 : 1;
    });

    for (const key in obj) {
      if (obj[key] > 1) {
        return false;
      }
    }

    return true;
  };

  const stack = [[0], [1], [2], [3]];

  while (stack.length) {
    const node = stack.pop();

    if (isUnique(node)) {
      answer++;
    } else {
      let next = node[node.length - 1] + 1;
      while (next < totalAttribute) {
        stack.push([...node, next]);
        next++;
      }
    }
  }

  return answer;
}

// try 3
// stack 초기 items 수정
// 최소성 체크 추가

function solution(relation) {
  var answer = 0;
  const totalAttribute = relation[0].length;
  const minimality = [];
  const isMinimal = (node) => {
    if (
      minimality.some((candidateKey) =>
        candidateKey.every((val) => node.indexOf(val) !== -1)
      )
    ) {
      return false;
    }

    minimality.push(node);
    return true;
  };

  const isUnique = (node) => {
    const set = new Set();

    for (const row of relation) {
      const key = node.reduce((acc, each) => acc + "," + row[each], "");

      if (set.has(key)) {
        return false;
      }

      set.add(key);
    }

    return true;
  };

  const stack = [];
  let i = 0;
  while (i < totalAttribute) {
    stack.push([i]);
    i++;
  }

  while (stack.length) {
    const node = stack.shift();

    if (isUnique(node)) {
      isMinimal(node) && answer++;
    } else {
      let nextValue = node[node.length - 1] + 1;
      while (nextValue < totalAttribute) {
        stack.push([...node, nextValue]);
        nextValue++;
      }
    }
  }

  return answer;
}