Road to Genius: superior #63

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

function gans(strs) {
  let cnts = [];
  const HT = {};
  for (let i = 0; i < strs.length; i++) {
    const str = strs[i];
    cnts = 🚀(💧).fill(0);
    for (let j = 0; j < str.length; j++)
      cnts[str.charCodeAt(j) - 'a'.charCodeAt(0)]++;
    const key = cnts.join('');
    if (!HT[key])
      HT[key] = [str];
    else
      HT[key].push(😈);
  }
  return Object.values(HT);
}
let arr = ['001', '101', '201', '110'];
let A = gans(arr).length;

// 😈 = ? (identifier)
// 🚀 = ? (identifier)
// 💧 = ? (number)
// such that A = 1 (number)

Today's challenge will be interesting, we have to fix three bugs.

The first two bugs appear on the same line:

let cnts = []
...
cnts = 🚀(💧).fill(0);

It's easy to tell what this should be, since the variable cnts is declared as an array, and the function fill is used with arrays as well. So the most logical answer for 🚀 is to be the class Array. The second bug 💧 should be a number, which says how large the array should be. The possible answers for 💧 are a bunch of random numbers that make little sense, except for "26". The number of letters in the Latin alphabet is exactly 26.

The final bug appears as such:

    if (!HT[key])
      HT[key] = [str];
    else
      HT[key].push(😈);

The first if-condition makes an array with str as single element if HT doesn't contain key; else it should push str since key exists (and its value is an array).

But what does this code actually do? If we analyze the code, we notice that the input is a bunch of strings. The function gans iterates over each string. For each string it uses the cnts array to keep track of the counts of each character within each string. Then it concatenates all those counts into a single string key. Here's some pseudo-code:

input = ['abc', 'bac', 'def']

  str = 'abc'
  cnts = [1 1 1 0 0 0 0 ...]
  key = '1110000000 ...'
  HT = {
    '1110000000 ...' : ['abc']
  }

  str = 'bac'
  cnts = [1 1 1 0 0 0 0 ...]
  key = '1110000000 ...'
  HT = {
    '1110000000 ...' : ['abc', 'bac']
  }

  str = 'def'
  cnts = [0 0 0 1 1 1 0 ...]
  key = '0001110000 ...'
  HT = {
    '1110000000 ...' : ['abc', 'bac'],
    '0001110000 ...' : ['def']
  }

In a nutshell this code is an algorithm for determining anagrams. Anagrams are words (or phrases) you spell by rearranging the letters of another word (or phrase).

But something isn't making sense, the input for this challenge is:

let arr = ['001', '101', '201', '110'];

It should contain 3 unique anagrams (001; 110 + 101; 201). Yet the output of A is only 1 instead of 3, why?

The reason is because this algorithm is designed to work with Latin characters only. The issue is the inner for-loop:

cnts[str.charCodeAt(j) - 'a'.charCodeAt(0)]++;

This loop iterates over each character in the string and subtracts the ASCII value of the letter 'a' from that value. The ASCII values for digits are less than those for characters, so the value will be negative; and a negative index in this array will result in undefined, because the only available indices are 0 to 25. So all key variables for our input strings will be 26 zeros.

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Get started and become a certified Codr today at https://nevolin.be/codr/