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/

Comments

[pentacular]

Do you really think this kind of simple constraint satisfaction puzzle is teaching programming?

It seems kind of unlikely to me. :)

[Ilya Nevolin]

It is not intended as a beginners programming guide. If one wants to learn Python/JavaScript/C++ then they are better off taking some conventional course to learn the basics. Codr teaches problem solving, analysis and debugging skills, in the form of challenges and puzzles.

[pentacular]

Are you sure?

It seems like the problems can be solved by simple substitution and pattern matching with no real understanding of anything that is going on.

I mean, if you look at your thought processes here ...

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.

It's just kind of filling in things that aren't obviously wrong until you get something that works.

[Ilya Nevolin]

Substitution and pattern matching are strategies used in problem solving.

[pentacular]

Very frequently in mindless problem solving. :)

[Ilya Nevolin]

All of our ranked challenges are randomly generated. Some are asking the user to find the answer (some variable value) or fixing several bugs. It is true that some bugs are very trivial to figure out, but sometimes they are not and require an intelligent approach.